Skip to main content

Section 4.6 A deeper investigation of the properties of determinants

In this section we consider further properties of the determinant. One of the main goals is to have the tools to complete the proof of Theorem 4.3.8.

Up to this point, the examples of the evaluation of the determinant, as in Example 4.3.10, involve the reduction of the evaluation of one matrix of order \(n\) to the evaluation of the \(n\) determinants of matrices of order \(n-1\text{.}\) In this section we will see how, at least in principle, to evaluate the determinant of a large matrix directly.

Subsection 4.6.1 Permutations

The permutations of a set consists of all possible ways of ordering its elements. If, for example, the set is \(\{a,b,c\}\text{,}\) then the possible permutations are

\begin{align*} abc\amp\amp acb\amp\amp bac\amp\amp bca\amp\amp cab\amp\amp cba \text{,} \end{align*}

and so there are six of them.

Now consider the set \(\{a,b,c,d\}\text{.}\) Here is how we can list all the permutations: each permutation that starts with \(a\) can be completed with a permutation of \(\{b,c,d\}\text{,}\) there being six such permutations. Similarly, each permutation starting with \(b\text{,}\) \(c\text{,}\) or \(d\) can be completed using the six permutation of the remaining elements:

\begin{gather*} \text{first element }a\colon \quad abcd\quad abdc\quad acbd\quad acdb\quad adbc\quad adcb \\ \text{first element }b\colon \quad bacd\quad badc\quad bcad\quad bcda\quad bdac\quad bdca \\ \text{first element }c\colon \quad cabd\quad cadb\quad cbad\quad cbda\quad cdab\quad cdba \\ \text{first element }d\colon \quad dabc\quad dacb\quad dbac\quad dbca\quad dcab\quad dcba \text{,} \end{gather*}

and so there are 24 permutations altogether.

How many permutations are there for a set of size 1 and a set of size 2?

Answer

There is one permutation for a set of size 1 and two permutations for a set of size 2.

Definition 4.6.2. \(n\) factorial.

\(n\) factorial, denoted \(n!\text{,}\) is defined by

\begin{equation*} n!=1\cdot2\cdot3\cdot \dots \cdot (n-1)\cdot n\text{.} \end{equation*}

We construct all possible permutations with each one being listed from left to right. We may choose any of the \(n\) elements for the leftmost position. For each of these \(n\) choices, there are \(n-1\) possible choices for the next position to the right make a total of \(n(n-1)\) possibilities for filling out the two leftmost positions. For each of these, there are \(n-2\) remaining elements for the next position to the right, and so there \(n(n-1)(n-2)\) choices for listing the three leftmost positions. Continuing in this manner, the number of ways of filling all \(n\) positions is \(n(n-1)(n-2)\cdots(1)=n!\text{.}\)

For those who know induction.

The statement to prove is

\begin{equation*} P_k\colon \text{The number of permutations of } k \text{ objects is } k!\,. \end{equation*}

Initial step: \(P_1\colon\) The number of permutations of one object is \(1=1!\text{.}\)

Inductive step: Assume \(P_{k-1}\) is true. We want to count the permutations of \(k\) elements. There are \(k\) choices for the first element. For each of these choices, the rest of the permutation is a permutation of the remaining \(k-1\) elements. By \(P_{k-1}\text{,}\) there are \((k-1)!\) of them, and hence the total number of permutations of all \(k\) objects is \(k(k-1)!=k!\,\text{.}\) Hence if \(P_{k-1}\) is valid then \(P_k\) is also valid. This completes the proof by induction.

Subsection 4.6.2 The sign of a permutation

When finding the permutations from a set of size \(n\text{,}\) the particular symbols used for the \(n\) elements are not important: the sets \(\{a,b,c\}\) and \(\{1,2,3\}\) both have six permutations; their properties are not dependent on the names of the individual elements. With this in mind we will now use the first \(n\) positive integers as our set when permuting \(n\) elements.

Each permutation has a sign which is either \(+1\) or \(-1\text{.}\) It is determined using the following algorithm: consider the leftmost entry of the permutation. If is is 1, do nothing. If it is not 1, interchange what is there with 1. In either case, 1 is now in the leftmost position. Now consider the secondmost entry from the left. If it is 2, do nothing; otherwise interchange what is there with 2. Continue interchanging terms in this matter until the permutation is in its natural order, that is, \(123\ldots n\text{.}\) If the number of interchanges required is even, the sign is \(+1\text{.}\) Otherwise the sign is \(-1\text{.}\)

Example 4.6.4. The sign of the permutation 324165.

Here are the steps needed to put the permutation \(324165\) into natural order:

  1. 324165: interchange 3 and 1
  2. 124365: no interchange (2 is in the correct position)
  3. 124365: interchange 4 and 3
  4. 123465: no interchange (4 is in the correct position)
  5. 123465: interchange 6 and 5
  6. 123465: finished

Since there were three interchanges, the sign of the permutation is \(-1\text{.}\)

  1. Show that any permutation of the set \(\{1,\ldots,n\}\) can be put into natural order with at most \(n-1\) interchanges.
  2. Give a permutation of the set \(\{1,\ldots,n\}\) that requires \(n-1\) interchanges to be put into natural order.
Answer
  1. After \(n-1\) interchanges, the elements \(1,2,\ldots,n-1\) are all in their natural position. The only place left for the element \(n\) is in the last position, and so all elements are in their natural position.
  2. Use the permutation \(n123\dots n-1\text{.}\) Each interchange moves \(n\) one position to the right, and so it takes \(n-1\) interchanges to get it in the final position.
Definition 4.6.6.

The sign of a permutation. Suppose a permutation \(\sigma\) can be put into natural order with \(t\) interchanges. Then \(\sgn(\sigma)=(-1)^t\text{,}\) that is,

\begin{equation*} \sgn(\sigma)= \begin{cases} 1 \amp \text{if } t \text{ is even}\\ -1 \amp \text{if } t \text{ is odd} \end{cases}\text{.} \end{equation*}
Table 4.6.7. Signs of permutations \(\sigma\) of \(\{1,2,3,4\}\) with \(t\) interchanges needed to obtain natural order.
\(\sigma\) \(t\) \(\sgn(\sigma)\) \(\) \(\sigma\) \(t\) \(\sgn(\sigma)\) \(\) \(\sigma\) \(t\) \(\sgn(\sigma)\)
1234 0 +1 \(\ \) 1243 1 -1 \(\ \) 1324 1 -1 \(\ \)
1342 2 +1 \(\ \) 1423 2 +1 \(\ \) 1432 1 -1
2134 1 -1 \(\ \) 2143 2 +1 \(\ \) 2314 2 +1
2341 3 -1 \(\ \) 2413 3 -1 \(\ \) 2431 2 +1
3124 2 +1 \(\ \) 3142 3 -1 \(\ \) 3214 1 -1
3241 2 +1 \(\ \) 3412 2 +1 \(\ \) 3421 3 -1
4123 3 -1 \(\ \) 4132 2 +1 \(\ \) 4213 2 +1
4231 1 -1 \(\ \) 4312 3 -1 \(\ \) 4321 2 +1

Subsection 4.6.3 An alternative notation for the permutations of \(\{1,2,\dots,n\}\)

In Example 4.6.4 the properties of the permutation \(324165\) were examined. In our alternative notation we write this permutation as

\begin{equation*} \sigma= \begin{pmatrix} 123456\\324165 \end{pmatrix}\text{.} \end{equation*}

In general, for permutations of \(\{1,2,\dots,n\}\text{,}\) the top row is simply \(12\dots n\) in natural order and the bottom row is the permutation written as the reordered elements. In addition, we let \(\sigma(1)\) denote the number below 1, \(\sigma(2)\) denote the number below 2, etc. At first blush, this just seems like a lot of extra baggage, but, as with all good notation, it eventually allows other interesting properties to emerge.

Example 4.6.8. Permutations of \(\{1,2,3\}\).

The permutations of \(\{1,2,3\}\) in this new notation are

\begin{gather*} \sigma_1=\begin{pmatrix}123\\123\end{pmatrix}\quad \sigma_2=\begin{pmatrix}123\\132\end{pmatrix}\quad \sigma_3=\begin{pmatrix}123\\213\end{pmatrix}\\ \sigma_4=\begin{pmatrix}123\\231\end{pmatrix}\quad \sigma_5=\begin{pmatrix}123\\312\end{pmatrix}\quad \sigma_6=\begin{pmatrix}123\\321\end{pmatrix}\text{.} \end{gather*}

Note that \(\sgn(\sigma_1)=\sgn(\sigma_4)=\sgn(\sigma_5)=1\) while \(\sgn(\sigma_2)=\sgn(\sigma_3)=\sgn(\sigma_6)=-1\text{.}\) In addition, for the permutation \(\sigma_6\text{,}\) we have \(\sigma_6(1)=3\text{,}\) \(\sigma_6(2)=2\) and \(\sigma_6(3)=1\text{,}\) and similarly for the other permutations.

Subsection 4.6.4 Permutations and determinants: the small cases

The evaluation of the determinant of small matrices has been given in Definition 4.1.1. By looking at these examples in more detail, the role of permutations is revealed.

If \(A\) is a square matrix of order 3, the determinant is a sum of six terms:

\begin{align*} \det(A) =\ \amp a_{1,1}a_{2,2}a_{3,3}+a_{1,2}a_{2,3}a_{3,1} +a_{1,3}a_{2,1}a_{3,2} \\ \amp -a_{1,1}a_{2,3}a_{3,2} -a_{1,2}a_{2,1}a_{3,3} -a_{1,3}a_{2,2}a_{3,1}\text{.} \end{align*}

For each term, we construct a permutation \(\sigma\) of \(\{1,2,3\}\) in the following way: if \(a_{ij}\) is one of the factors, the \(j\) is written under \(i\) in the permutation. In other words, \(\sigma(i)=j\text{.}\)

Table 4.6.9. Permutations when \(n=3\)
Term Permutation from term Sign of permutation
\(a_{1,1}a_{2,2}a_{3,3}\) \(\sigma_1=\begin{pmatrix}123\\123\end{pmatrix}\) \(\sgn(\sigma_1)=1\)
\(a_{1,2}a_{2,3}a_{3,1}\) \(\sigma_4=\begin{pmatrix}123\\231\end{pmatrix}\) \(\sgn(\sigma_4)=1\)
\(a_{1,3}a_{2,1}a_{3,2}\) \(\sigma_5=\begin{pmatrix}123\\312\end{pmatrix}\) \(\sgn(\sigma_5)=1\)
\(a_{1,1}a_{2,3}a_{3,2}\) \(\sigma_2=\begin{pmatrix}123\\132\end{pmatrix}\) \(\sgn(\sigma_2)=-1\)
\(a_{1,2}a_{2,1}a_{3,3}\) \(\sigma_3=\begin{pmatrix}123\\213\end{pmatrix}\) \(\sgn(\sigma_3)=-1\)
\(a_{1,3}a_{2,2}a_{3,1}\) \(\sigma_6=\begin{pmatrix}123\\321\end{pmatrix}\) \(\sgn(\sigma_6)=-1\)

Look at Example 4.6.8. We see that something beautiful has happened:

Find an analogous expression \(\det(A)\) when \(A\) is of size 2.

Answer

Let \(\sigma_1=\begin{pmatrix}12\\12\end{pmatrix}\) and \(\sigma_2=\begin{pmatrix}12\\21\end{pmatrix}\text{.}\) Then

\begin{equation*} \det(A)=\sum_{k=1}^2 \sgn(\sigma_k)a_{1,\sigma(1)}a_{2,\sigma(2)} \end{equation*}
Example 4.6.12. A formula for the determinant of a matrix of size \(4\).

Let \(A\) be a matrix of size \(4\text{.}\) We evaluate the determinant using the first row expansion of \(A\) and all of the subsequent minors.

\begin{align*} \det(A) \amp = \det\left( \begin{bmatrix} a_{1,1} \amp a_{1,2} \amp a_{1,3} \amp a_{1,4}\\ a_{2,1} \amp a_{2,2} \amp a_{2,3} \amp a_{2,4}\\ a_{3,1} \amp a_{3,2} \amp a_{3,3} \amp a_{3,4}\\ a_{4,1} \amp a_{4,2} \amp a_{4,3} \amp a_{4,4} \end{bmatrix}\right)\\ \amp = a_{1,1}\det\left(\begin{bmatrix} a_{2,2} \amp a_{2,3} \amp a_{2,4}\\ a_{3,2} \amp a_{3,3} \amp a_{3,4}\\ a_{4,2} \amp a_{4,3} \amp a_{4,4} \end{bmatrix}\right) -a_{1,2}\det\left(\begin{bmatrix} a_{2,1} \amp a_{2,3} \amp a_{2,4}\\ a_{3,1} \amp a_{3,3} \amp a_{3,4}\\ a_{4,1} \amp a_{4,3} \amp a_{4,4} \end{bmatrix}\right)\\ \amp\qquad+a_{1,3}\det\left(\begin{bmatrix} a_{2,1} \amp a_{2,2} \amp a_{2,4}\\ a_{3,1} \amp a_{3,2} \amp a_{3,4}\\ a_{4,1} \amp a_{4,2} \amp a_{4,4} \end{bmatrix}\right) -a_{1,4}\det\left(\begin{bmatrix} a_{2,1} \amp a_{2,2} \amp a_{2,3} \\ a_{3,1} \amp a_{3,2} \amp a_{3,3} \\ a_{4,1} \amp a_{4,2} \amp a_{4,3} \end{bmatrix}\right)\\ \amp= a_{1,1}\left( a_{2,2} \det\left( \begin{bmatrix} a_{3,3}\amp a_{3,4}\\a_{4,3}\amp a_{4,4} \end{bmatrix} \right) -a_{2,3}\det\left( \begin{bmatrix} a_{3,2}\amp a_{3,4}\\a_{4,2}\amp a_{4,4} \end{bmatrix} \right) +a_{2,4}\det\left( \begin{bmatrix} a_{3,2}\amp a_{3,3}\\a_{4,2}\amp a_{4,3} \end{bmatrix} \right) \right)\\ \amp\qquad -a_{1,2}\left( a_{2,1} \det\left( \begin{bmatrix} a_{3,3}\amp a_{3,4}\\a_{4,3}\amp a_{4,4} \end{bmatrix} \right) -a_{2,3}\det\left( \begin{bmatrix} a_{3,1}\amp a_{3,4}\\a_{4,1}\amp a_{4,4} \end{bmatrix} \right) +a_{2,4}\det\left( \begin{bmatrix} a_{3,1}\amp a_{3,3}\\a_{4,1}\amp a_{4,3} \end{bmatrix} \right) \right)\\ \amp\qquad +a_{1,3}\left( a_{2,1} \det\left( \begin{bmatrix} a_{3,2}\amp a_{3,4}\\a_{4,2}\amp a_{4,4} \end{bmatrix} \right) -a_{2,2}\det\left( \begin{bmatrix} a_{3,1}\amp a_{3,4}\\a_{4,1}\amp a_{4,4} \end{bmatrix} \right) +a_{2,4}\det\left( \begin{bmatrix} a_{3,1}\amp a_{3,2}\\a_{4,1}\amp a_{4,2} \end{bmatrix} \right) \right)\\ \amp\qquad -a_{1,4}\left( a_{2,1} \det\left( \begin{bmatrix} a_{3,2}\amp a_{3,3}\\a_{4,2}\amp a_{4,3} \end{bmatrix} \right) -a_{2,2}\det\left( \begin{bmatrix} a_{3,1}\amp a_{3,3}\\a_{4,1}\amp a_{4,3} \end{bmatrix} \right) +a_{2,3}\det\left( \begin{bmatrix} a_{3,1}\amp a_{3,2}\\a_{4,1}\amp a_{4,2} \end{bmatrix} \right) \right)\\ \amp = a_{1,1}a_{2,2}a_{3,3}a_{4,4} - a_{1,1}a_{2,2}a_{3,4}a_{4,3} +a_{1,1}a_{2,3}a_{3,2}a_{4,4} - a_{1,1}a_{2,3}a_{3,4}a_{4,2} +a_{1,1}a_{2,4}a_{3,2}a_{4,3} - a_{1,1}a_{2,4}a_{3,3}a_{4,2}\\ \amp \qquad -a_{1,2}a_{2,1}a_{3,3}a_{4,4} + a_{1,2}a_{2,1}a_{3,4}a_{4,3} -a_{1,2}a_{2,3}a_{3,1}a_{4,4} + a_{1,2}a_{2,3}a_{3,4}a_{4,1} +a_{1,2}a_{2,4}a_{3,1}a_{4,3} + a_{1,2}a_{2,4}a_{3,3}a_{4,1}\\ \amp \qquad a_{1,3}a_{2,1}a_{3,2}a_{4,4} - a_{1,3}a_{2,1}a_{3,4}a_{4,2} +a_{1,3}a_{2,2}a_{3,1}a_{4,4} - a_{1,3}a_{2,2}a_{3,4}a_{4,1} +a_{1,3}a_{2,4}a_{3,1}a_{4,2} - a_{1,3}a_{2,4}a_{3,2}a_{4,1}\\ \amp \qquad -a_{1,4}a_{2,1}a_{3,2}a_{4,3} + a_{1,4}a_{2,1}a_{3,3}a_{4,2} -a_{1,4}a_{2,2}a_{3,1}a_{4,3} + a_{1,4}a_{2,2}a_{3,3}a_{4,1} -a_{1,4}a_{2,3}a_{3,1}a_{4,2} + a_{1,4}a_{2,3}a_{3,2}a_{4,1} \end{align*}

The final line reveals a pattern: it is a sum of \(24=4!\) terms, each of which is of the form \(\pm a_{1,i}a_{2,j}a_{3,k}a_{4,\ell}\) where \(\begin{pmatrix} 1234\\ijk\ell \end{pmatrix} \) is a permutation. Each of the \(4!\) possible permutations appears exactly once. In addition, the sign in front of the term is equal to the sign of the associated permutation.

Subsection 4.6.5 Permutations and determinants

The pattern exhibited in Proposition 4.6.10 and in Example 4.6.12 cries for generalization. Our goal is to do so with the proof of the following important theorem:

The determinant of a matrix \(A\text{,}\) as given in Definition 4.3.9, is simply the first row expansion of \(A\text{.}\) The proof of Theorem 4.6.13 may be completed by showing that

\begin{equation} \sum_\sigma \sgn(\sigma)a_{1,\sigma(1)}a_{2,\sigma(2)}\cdots a_{n,\sigma(n)}\label{PermutationDeterminantExpression}\tag{4.6.1} \end{equation}

and the first row expansion of \(A\) are identical.

So here is the plan: we examine first row expansion of \(A\) carefully and compare it to the expression (4.6.1) in two steps:

  1. Show that every permutation \(\sigma\) from (4.6.1) shows up exactly once as a summand in the first row expansion.
  2. Show that \(\sgn(\sigma)\) is correct for every permutation \(\sigma\) in expression (4.6.1).

Examining the case for a matrix \(A\) of size \(n=4\) will clarify the ideas necessary for the general proof.

Example 4.6.14. Proof for \(n=4\).

Let \(A\) be a matrix of size \(4\text{,}\) and consider the permutation

\begin{equation*} \sigma=\begin{pmatrix}1234\\3142\end{pmatrix}\text{.} \end{equation*}

Then \(\sigma(1)=3\text{,}\) \(\sigma(2)=1\text{,}\) \(\sigma(3)=4\text{,}\) and \(\sigma(4)=2\text{,}\) and we are searching for a term within the expansion of \(\det(A)\) containing \(a_{1,3} a_{2,1} a_{3,4} a_{4,2}\text{.}\) The first row expansion of \(A\) is

\begin{equation*} \det(A)= a_{1,1}M_{1,1} -a_{1,2}M_{1,2} +a_{1,3}M_{1,3} -a_{1,4}M_{1,4} \text{,} \end{equation*}

and so the only hope of finding \(a_{1,3} a_{2,1} a_{3,4} a_{4,2}\) is by examining the only term that includes \(a_{1,3}\text{,}\) namely, \(a_{1,3}M_{1,3}\text{.}\) Now

\begin{align*} a_{1,3}M_{1,3} \amp = a_{1,3}\det \begin{bmatrix} a_{2,1}\amp a_{2,2} \amp a_{2,4}\\ a_{3,1}\amp a_{3,2} \amp a_{3,4}\\ a_{4,1}\amp a_{4,2} \amp a_{4,4} \end{bmatrix}\\ \amp = a_{1,3} \left( a_{2,1}\det\begin{bmatrix} a_{3,2}\amp a_{3,4}\\a_{4,2}\amp a_{4,4}\end{bmatrix} -a_{2,2}\det\begin{bmatrix} a_{3,1}\amp a_{3,4}\\a_{4,1}\amp a_{4,4}\end{bmatrix} +a_{2,4}\det\begin{bmatrix} a_{3,1}\amp a_{3,2}\\a_{4,1}\amp a_{4,2}\end{bmatrix} \right)\text{.} \end{align*}

Since we are searching for a term that contains \(a_{2,1}\text{,}\) we must focus our attention on the first summand since it is the only one that includes it. Expanding on the first row:

\begin{equation*} a_{1,3}a_{2,1}\det \begin{bmatrix} a_{3,2}\amp a_{3,4}\\a_{4,2}\amp a_{4,4} \end{bmatrix} = a_{1,3}a_{2,1}(a_{3,2}\det[a_{4,4}] -a_{3,4}\det[a_{4,2}])\text{.} \end{equation*}

Since we are searching for a term that contains \(a_{3,4}\text{,}\) we must take the second summand, which leaves us with

\begin{equation*} -a_{1,3} a_{2,1} a_{3,4} \det[a_{4,2}] = -a_{1,3} a_{2,1} a_{3,4} a_{4,2}\text{,} \end{equation*}

exactly what we were looking for. Note also the \(\sgn(\sigma)=-1\text{.}\)

There was nothing special about our choice of permutation \(\sigma\text{.}\) For any choice of permutation the same thing happens: the permutation forces a single choice of summand within each of the successive first-row expansions.

Notice also that the process we have described is an algorithm that determines the exact position of \(a_{1,3} a_{2,1} a_{3,4} a_{4,2}\) after the full expansion of the determinant. This implies that for every permutation \(\sigma\text{,}\) the term \(a_{1,\sigma(1)} a_{2,\sigma(2)} a_{3,\sigma(3)} a_{4,\sigma(4)}\) appears exactly once.

Now we consider Item 1 more generally.

The proof follows the pattern of Example 4.6.14.

Consider the first row expansion of \(A\text{:}\)

\begin{equation*} a_{1,1}M_{1,1}-a_{1,2}M_{1,2}+a_{1,3}M_{1,3}- \cdots + (-1)^{1+n}a_{1,n}M_{1,n}\text{.} \end{equation*}

The given permutation \(\sigma\) has \(\sigma(1)=i_1\text{,}\) and so the only hope of finding the permutation \(\sigma\) in the final expansion is to look for it in the only term where \(a_{1,i_1}\) appears: \(a_{1,i_1}M_{1,i_1}\text{.}\) The first row of \(M_{1,i_1}\) consists of \(a_{2,j}\text{,}\) with \(j\in\{1,2,\ldots,n\}\text{,}\) \(j\not=i_1\text{.}\) Since \(\sigma(2)=i_2\text{,}\) we must continue the expansion using the term of the form \(a_{2,\sigma(i_2)}M\text{.}\) This algorithm may proceed until \(a_{1,\sigma(1)}a_{2,\sigma(2)}\cdots a_{n,\sigma(n)}\) is found. Note that the entries of \(\{i_1,\ldots,i_n\}\) must be different to complete the argument.

Since first-row expansions are used, the order of deletion of rows from \(A\) is clearly \(1,2,\ldots,n\text{,}\) which is just the first row in the notation for \(\sigma\text{.}\) The first column deleted must be the \(i_1\) column, since that is the only way \(a_{1,i_1}\) can appear in the expansion. More generally, the only way for \(a_{j,i_j}\) to appear is if the \(i_j\) column of \(A\) is deleted when the \(j\)-th row of \(A\) is deleted. This means that the order of deletion of columns of \(A\) must be \(i_1,i_2,\ldots,i_n\text{.}\)

Suppose we define the determinant of a matrix \(A\) as the value of the second row expansion. Modify Algorithm 4.6.15 to show that it is still true that \(a_{1,\sigma(1)}a_{2,\sigma(2)}a_{3,\sigma(3)} \cdots a_{n,\sigma(n)}\) appears exactly once in the full expansion.

Answer

The order of deletion of rows is \(2,3,\ldots,n,1\text{,}\) and so the order of deletion of columns must be \(i_2,i_3,\ldots,i_n,i_1\text{.}\)

Suppose we define the determinant of a matrix \(A\) as the value of the first column expansion. Modify Algorithm 4.6.15 to show that it is still true that \(a_{1,\sigma(1)}a_{2,\sigma(2)}a_{3,\sigma(3)} \cdots a_{n,\sigma(n)}\) appears exactly once in the full expansion.

Answer

This takes a little trick. Start with the permutation

\begin{equation*} \sigma= \begin{pmatrix} 1\amp 2\amp 3\amp \cdots\amp n\\ i_1\amp i_2\amp i_3\amp \cdots\amp i_n \end{pmatrix} \end{equation*}

and rearrange the columns so that the bottom row is \(123\cdots n\text{.}\) For example, if \(\sigma= \begin{pmatrix} 123456\\324165\end{pmatrix}\text{,}\) rearranging the columns gives the permutation \(\begin{pmatrix} 421365\\123456\end{pmatrix}\text{.}\)

Since we are using a first-column expansion, the order of deletion of columns from \(A\) is \(1,2,\ldots,n\text{,}\) which is exactly the second row in our new notation. The first row of our new notation then gives the order of deletion of rows from \(A\text{.}\) Note that \(a_{1,\sigma(1)}a_{2,\sigma(2)}\cdots a_{n,\sigma(n)}\) is the resulting expression, but the order of the terms has been changed so that the second subscripts are in natural order.

Next, we consider Item 2. We need an additional property of permutations. We use Example 4.6.4 for in initial illustration:

\begin{equation*} \sigma= \begin{pmatrix} 123456\\324165 \end{pmatrix}\text{.} \end{equation*}

Consider the \(15\) possible ordered pairs of entries taken from the second row. They are

\begin{equation*} \begin{array}{ccccc} \color{red}{32}\amp 34 \amp \color{red}{31}\amp 36 \amp 35 \\ \amp 24 \amp \color{red}{21}\amp 26 \amp 25 \\ \amp \amp \color{red}{41}\amp 46 \amp 45 \\ \amp \amp \amp 16 \amp 15 \\ \amp \amp \amp \amp \color{red}{65} \end{array}\text{.} \end{equation*}

Each pair either appears in its natural order, or not. A pair not in natural order is called an inversion. The inversions are shown in red. In this case, the number of interchanges needed to put \(\sigma\) into its natural order is 3 and the number of inversions is 5, both of which are odd numbers. Our next result shows that this is true for any permutation: the sign of a permutation is determined by the parity 1  of the number of inversions.

The parity of a number is even if it is divisible by 2 and odd otherwise.

Let

\begin{equation*} \sigma= \begin{pmatrix} 1\amp 2\amp 3\amp \cdots\amp n\\ i_1\amp i_2\amp i_3\amp \cdots\amp i_n \end{pmatrix} \end{equation*}

By Definition 4.6.6 we need to keep track of the number of interchanges needed to put \(\sigma\) into natural order. If \(i_1=1\text{,}\) the first position is in natural order we are finished with the that position. Nothing has changed, including the number of inversions. Otherwise, we need to interchange whatever is in the first position with \(1\text{,}\) and we need to know the effect of that interchange on the parity of the number of inversions. Here is the situation before interchanging \(1\) and \(k\text{.}\)

\begin{equation*} \sigma= \begin{pmatrix} 1\amp \amp \cdots\amp \amp j\amp \amp\cdots\amp \amp n\\ k\amp \cdots\amp t \amp \cdots \amp1 \amp\cdots\amp u \amp\cdots\amp i_n \end{pmatrix}\text{.} \end{equation*}

If \(u\) is an entry to the right of \(1\text{,}\) then the interchange of \(1\) and \(k\) causes the pairs \(ku\) and \(1u\) to be replaced by \(1u\) and \(ku\) respectively, and so the number of inversions is unchanged as far as \(u\) is concerned.

If \(t\) is to the left of \(1\text{,}\) then \(kt\) is replaced by \(1t\) and \(t1\) is replace by \(tk\text{.}\) Clearly \(t1\) is an inversion and \(1t\) is not, and so there is a net loss of one inversion. Also \(tk\) is an inversion if and only if \(kt\) is not, and so the number of inversions involving \(t\) either stays the same or is decreased by \(2\text{.}\) Finally the interchange itself of \(k1\) to \(1k\) reduces the number of inversions by one, so the total number of inversions is reduced by one or three. In either case, the parity of the number of inversions changes as the interchange moves the permutation one step closer to being in natural order.

Each step (interchange) that moves the permutation closer to natural order changes the parity of both the number of inversions and the number of steps needed for completion, so the parities of the two numbers start the same and remain the same, or they start opposite and remain opposite. When the permutation is finally in natural order, the number of steps necessary to put it into natural order is zero, as is the number of inversions, so the parities are the same and hence must have been identical to start with. This in turn implies the desired conclusion of the theorem.

To complete the verification of Item 2, we follow Algorithm 4.6.15 keeping track of the signs of the terms that arise. As in that algorithm, we start with

\begin{equation*} \sigma= \begin{pmatrix} 1\amp 2\amp 3\amp \cdots\amp n\\ i_1\amp i_2\amp i_3\amp \cdots\amp i_n \end{pmatrix} \end{equation*}

and keep track of the number of times a \(+1\) or \(-1\) appears as we construct \(a_{1,i_1}a_{2,i_2}a_{3,i_3} \cdots a_{n,i_n} =a_{1,\sigma(1)}a_{2,\sigma(2)}a_{3,\sigma(3)} \cdots a_{n,\sigma(n)}\text{.}\)

Expanding on the first row of \(A\) gives us

\begin{equation*} \det(A)=a_{1,1}M_{1,1}-a_{1,2}M_{1,2}+a_{1,3}M_{1,3}- \cdots + (-1)^{1+n}a_{1,n}M_{1,n}\text{.} \end{equation*}

Since \(\sigma(1)=i_1\text{,}\) we must select the summand \((-1)^{1+i_1}a_{1,i_1}M_{1,i_1}\) expand it further. The first row expansion of \(M_{1,i_1}\) is

\begin{equation*} a_{2,1} - a_{2,2} + a_{2,3} + \cdots + \color{red}{(-1)^{i_1}a_{2,i_{1}-1}} +\color{red}{(-1)^{i_1+1} a_{2,i_1+1}} + \cdots +(-1)^{n-1} a_{2,n-1}\text{.} \end{equation*}

The crux of the argument is shown by the two terms in red. Since the \(i_1\)-column has been deleted, as we pass from the first to the second, the second subscript goes up by two but the exponent of \(-1\) increases by only one. This implies that the exponent of \(-1\) in the coefficient of \(a_{2,k}\) and \(k\) have the opposite parity if \(k \lt i_1\) and the same parity if \(k \gt i_1\text{.}\) In other words, we have \(i=2\) and

\begin{equation*} \text{The coefficient of } a_{i,j}= \begin{cases} (-1)^{i+j+1}\amp \text{if } j \lt i_1\\ (-1)^{i+j}\amp \text{if } i_1 \lt j. \end{cases} \end{equation*}

Note that \(i_2 \lt i_1\) is the exact condition for \(i_1 i_2\) to be an inversion, and so \(i_2 \lt i_1\) being an inversion adds one extra \(-1\) to our count.

We carry out the algorithm for one more step to see the emerging pattern. We have now deleted row one, row two, column \(i_1\) and column \(i_2\) from \(A\text{.}\) We call this matrix \(N\) for simplicity. The first row of \(N\) consists of \(\{a_{3,1} \cdots a_{3,n}\}\) with \(a_{3,i_0}\) and \(a_{3,i_1}\) deleted. We now have \(i=3\) and

\begin{equation*} \text{The coefficient of } a_{i,j}= \begin{cases} (-1)^{i+j+2}\amp \text{if } j \text{ is less than } i_1 \text{ and } i_2\\ (-1)^{i+j+1}\amp \text{if } j \text{ is between } i_1 \text{ and } i_2\\ (-1)^{i+j}\amp \text{if } j \text{ is greater than } i_1 \text{ and } i_2. \end{cases} \end{equation*}

Notice that after setting \(j=i_3\text{,}\) this is the same as

\begin{equation*} \text{The coefficient of } a_{i,j}= \begin{cases} (-1)^{i+j+2}\amp \text{if } i_1 i_3 \text{ and } i_2 i_3 \text{ are both inversions}\\ (-1)^{i+j+1}\amp \text{if one of } i_1 i_3 \text{ and } i_2 i_3 \text{ is an inversion}\\ (-1)^{i+j}\amp\text{if neither of } i_1 i_3 \text{ nor } i_2 i_3 \text{ is an inversion}. \end{cases} \end{equation*}

Algorithm 4.6.15 proceeds step by step: at each step the matrix under consideration has its top row and one column deleted. At step \(k\) we have a matrix \(N\) derived from \(A\) by deleting the first \(k-1\) row and columns \(\{i_1,i_2,\ldots,i_{k-1}\}\text{,}\) and so the remaining entries in the first row of \(N\) are \(\{a_{k,1},\ldots,a_{k,n}\} \setminus \{a_{k,i_1},\ldots,a_{k,i_{k-1}}\} \text{.}\) This can be visualized in the following figure:

Figure 4.6.20.

\(B_1,\ldots,B_k\) are the blocks of remaining columns between the deleted ones. The column corresponding to \(i_k\) is in one of these blocks. The particular one will determine the sign that is used in the first row expansion of \(N\text{.}\)

As a starting point, suppose that \(B_1\) is nonempty. That means that the upper left entry is \(a_{k,1}\text{,}\) and it has a sign of \(+1\) in the first row expansion, and so as we expand along the columns in \(B_1\text{:}\)

\begin{equation*} \text{For columns } j \text{ in } B_1 \text{, the coefficient of } a_{k,j}= \begin{cases} (-1)^{k+j} \amp \text{if } k \text{ is odd}\\ (-1)^{k+j-1}\amp \text{if } k \text{ is even.} \end{cases} \end{equation*}

As we move from columns in \(B_1\) to those in \(B_2\text{,}\) an extra \(-1\) is added to the coefficient, that is:

\begin{equation*} \text{For columns } j \text{ in } B_2 \text{, the coefficient of } a_{k,j}= \begin{cases} (-1)^{k+j-1} \amp \text{if } k \text{ is odd}\\ (-1)^{k+j}\amp \text{if } k \text{ is even.} \end{cases} \end{equation*}

When we get to \(B_k\text{,}\) something beautiful happens: the result for the even case and the odd case is the same.

\begin{equation*} \text{For columns } j \text{ in } B_k \text{, the coefficient of } a_{k,j}= (-1)^{k+j}\text{.} \end{equation*}

A couple of observations when \(j\) corresponds to a column in \(B_k\text{:}\)

  • The coefficient of \(a_{k,j}\) is the same as it would be if we were taking the \(k\)-th row expansion of \(A\text{.}\)
  • During this step of the algorithm, the first row and the \(j=i_k\) column will be deleted. If that column is in \(B_k\text{,}\) then the pairs \(i_1i_k\text{,}\) \(i_2i_k,\dots, i_{k-1}i_k\) are all in their natural order, that is, there are no inversions.

Now suppose that \(j\) corresponds to a column in \(B_{k-1}\text{.}\) Moving from \(B_k\) to \(B_{k-1}\) passes over a deleted column. Let \(i_t\) correspond to that deleted column. The deleted column causes the coefficient of \(a_{k,j}\) change sign, that is, the coefficient is \((-1)^{i+j+1}\text{.}\) In addition, the pair \(i_t i_k\) is now an inversion. A useful pattern now emerges: as we move one block to the left, the exponent of the coefficient \((-1)\) increases by one, and passing over the deleted column changes one pair from natural order to an inversion. Thus for any block, the number of extra factors of \((-1)\) is equal to the number of inversions among the pairs \(i_1i_k, i_2,i_k,\ldots,i_{k-1}i_k\text{.}\)

Now consider what happens as Algorithm 4.6.15 proceeds step by step. For any two \(i_r\) and \(i_s\text{,}\) say with \(r\lt s\text{,}\) the expansion on row \(s\) will add an extra factor of \((-1)\) if and only if the pair \(i_r i_s\) is an inversion. Thus as the algorithm runs, every possible inversion shows up exactly once and contributes one factor of \((-1)\text{.}\) The validity of Item 2 then follows from Theorem 4.6.19. This completes the proof of Theorem 4.6.13.