5.6 Proof patterns · Matrix Theory

The chapter described the determinant in four ways: as the only function satisfying three axioms (Definition 5.1.1, Theorem 5.3.4), as the Leibniz sum over permutations (Theorem 5.3.3), as the product of the factors collected while eliminating (Proposition 5.4.21), and as a cofactor expansion (Theorem 5.5.3). Most proofs in the chapter start by choosing one of these descriptions, and the choice decides how long the proof is. This section sorts the chapter’s arguments by the question they answer, compares the descriptions on examples from the chapter, and says when each one is the wrong tool. The exercises at the end practice one move at a time, and the problem set (Problems for Chapter 5) mixes them.

5.6.1Computing a determinant

For a matrix of numbers with no visible structure, use elimination (Algorithm 5.4.22). It takes about $𝑛^{3} / 3$ operations, while the Leibniz formula and a full cofactor expansion take on the order of $𝑛!$ (Remark 5.4.25). Structure changes this, so look for it first. Roughly in order of how quickly they finish:

A known form. Triangular and block-triangular matrices (Proposition 5.3.15, Corollary 5.4.27), permutation and monomial matrices (Theorem 5.2.31, Exercise 5.2.44), Vandermonde matrices (Theorem 5.5.21), and companion matrices (Proposition 5.5.20). Sometimes the form appears only after the rows or columns are reordered, which costs a sign (Exercise 5.3.37).
Few nonzero entries. Ask which permutations avoid every zero (Technique 5.3.12). Often only a few terms survive: one in Example 5.6.2 below, and four of the $24$ in Exercise 5.3.24. A row or column with one or two nonzero entries calls for a cofactor expansion along it (Example 5.5.4), possibly after replacements that create the zeros.
A family. If deleting the last row and column leaves a smaller member of the same family, expand to get a recurrence (Technique 5.5.17), as for tridiagonal and companion matrices (Proposition 5.5.18, Proposition 5.5.20).
Parameters. When the entries are polynomials in some parameters, use replacements that expose a common factor (Technique 5.5.22), as for constant row sums (Example 5.4.24) and powers of a node (Theorem 5.5.21). If the answer should be a product of linear factors, its roots can be found before any computation (Technique 5.5.24).
A product. If every entry is a sum of products, the matrix may factor, and then so does its determinant.

The last item has not been named yet, although several exercises of the chapter rely on it.

Technique 5.6.1 (Factor the matrix). To compute $det 𝑀$ , write $𝑀$ as a product of matrices whose determinants are known, and multiply (Theorem 5.4.10). There are two common sources of factorizations. If every entry is a sum of products, $𝑚_{𝑖 𝑗} =$ $\sum_{𝑘} 𝑥_{𝑖 𝑘} 𝑑_{𝑘} 𝑦_{𝑘 𝑗}$ , then $𝑀 = 𝑋 𝐷 𝑌$ with $𝐷 =$ $diag (𝑑_{1}, \dots, 𝑑_{𝑟})$ , and $𝑋$ and $𝑌$ are often triangular or Vandermonde matrices. If $𝑀$ is a block matrix, block row and column operations (Theorem 2.4.34) multiply it by matrices of determinant $1$ until it is block triangular. When the inner size $𝑟$ is smaller than the size of $𝑀$ , the same factorization shows $det 𝑀 = 0$ instead (Exercise 5.4.38). For instance, the matrix with entries $1 + 𝑥_{𝑖} 𝑦_{𝑗}$ is $𝑋 𝑌$ with rows $(1, 𝑥_{𝑖})$ in $𝑋$ and columns $(1, 𝑦_{𝑗})$ in $𝑌$ . For two rows this gives $(𝑥_{2} - 𝑥_{1}) (𝑦_{2} - 𝑦_{1})$ , and for three or more rows it gives $0$ .

Reach for it when the entries are power sums, binomial expansions, or sums over divisors, or when one block of a block matrix can be cleared. The chapter used it in Exercise 5.4.43, Exercise 5.4.46, and Exercise 5.5.47. The canonical example is the Hankel matrix of power sums, which is $𝑉^{𝖳} 𝑉$ for a Vandermonde matrix $𝑉$ (Problem 5.9).

Used in 7 places

Exercise 5.6.7, Problem 5.9, Problem 5.12, Problem 5.13, Problem 5.19, Problem 5.20, Problem 7.18.

Example 5.6.2 (One determinant, three ways). Let

𝐴 = (\begin{matrix} 0 & 1 & 0 & 0 \\ 2 & 0 & 3 & 0 \\ 0 & 4 & 0 & 5 \\ 0 & 0 & 6 & 0 \end{matrix}) \in ℚ^{4 \times 4} .

Counting the surviving terms. A term $sgn (𝜎) 𝑎_{𝜎 (1) 1} \dots 𝑎_{𝜎 (4) 4}$ is nonzero only if all four entries are. The only nonzero entry of column $1$ is in row $2$ , so $𝜎 (1) = 2$ , and column $4$ forces $𝜎 (4) = 3$ . Then column $2$ , with nonzero entries in rows $1$ and $3$ , must use row $1$ , and column $3$ must use row $4$ . Exactly one permutation survives, $𝜎 = (1 2) (3 4)$ , which is even. So

det 𝐴 = 𝑎_{21} 𝑎_{12} 𝑎_{43} 𝑎_{34} = 2 \cdot 1 \cdot 6 \cdot 5 = 60 .

A recurrence. $𝐴$ is the tridiagonal matrix of Proposition 5.5.18 with every $𝑎_{𝑘} = 0$ , $(𝑏_{1}, 𝑏_{2}, 𝑏_{3}) =$ $(1, 3, 5)$ , and $(𝑐_{1}, 𝑐_{2}, 𝑐_{3}) =$ $(2, 4, 6)$ . The recurrence becomes $𝑑_{𝑚} =$ $- 𝑏_{𝑚 - 1} 𝑐_{𝑚 - 1} 𝑑_{𝑚 - 2}$ , so $𝑑_{1} = 0$ , $𝑑_{2} = - 2$ , $𝑑_{3} = 0$ , and $𝑑_{4} = - 30 \cdot (- 2) = 60$ .

Elimination. Swap rows $1$ and $2$ . Subtracting $4$ times the new row $2$ from row $3$ turns row $3$ into $(0, 0, 0, 5)$ , and swapping rows $3$ and $4$ leaves an upper triangular matrix with diagonal $2, 1, 6, 5$ . There were two swaps, so $det 𝐴 = 60$ .

Elimination always works, but here it spends its steps on swaps and does not explain why the answer is a product of entries. The recurrence treats the whole family at once, and shows for example that $𝑑_{𝑛} = 0$ for every odd $𝑛$ . The count explains why: since the only nonzero entries are next to the diagonal, a surviving $𝜎$ sends every odd index to an even one and every even index to an odd one, and when $𝑛$ is odd there are more odd indices than even ones. On a dense matrix the same count lists all $𝑛!$ permutations, and there it is the wrong tool.

Practice: Exercise 5.6.6 and Exercise 5.6.7.

5.6.2Proving an identity for every matrix

Four arguments recur in the chapter. They differ in what they ask of the identity, and in how they deal with matrices that are not invertible.

Recognize the determinant by its axioms (Technique 5.4.11). If one side, as a function of the columns of a matrix $𝐵$ , is multilinear and alternating, then it is its value at $𝐼_{𝑛}$ times $det 𝐵$ . There are no cases and no formulas. This proved Theorem 5.4.10 (second proof) and Proposition 5.3.17 (first proof). It needs an expression that is visibly linear in each column of something.
Reduce to elementary matrices (Technique 5.4.6). Check the identity on the three types and show that it survives multiplication. It handles transposes, which the axioms do not reach, but it only reaches invertible matrices, and the others need a separate argument (Exercise 5.4.35).
Manipulate the Leibniz formula. Reindex the sum over $𝑆_{𝑛}$ (Proposition 5.2.8), or apply an operation to every term: transposing (second proof of Theorem 5.4.14), conjugating (Exercise 5.3.28), reducing modulo $𝑝$ (Proposition 5.3.20). It works when the identity matches the terms of one sum with the terms of another.
Polynomial identities (Technique 5.5.24). Prove the identity for invertible matrices, replace $𝐴$ by $𝐴 + 𝑡 𝐼_{𝑛}$ , and observe that both sides are polynomial in $𝑡$ and agree for all but finitely many $𝑡$ . This needs more scalars than the degree plus the number of bad values of $𝑡$ , which is automatic only over an infinite field (Exercise 5.6.10).

Example 5.6.3 (Multiplicativity, three ways). The text proved $det (𝐴 𝐵) =$ $det 𝐴 det 𝐵$ twice. The first proof (Technique 5.4.6) factors $𝐵$ into elementary matrices and needs a separate argument when $𝐵$ is not invertible: then $𝐴 𝐵$ is not invertible either, and both sides are $0$ . The second (Technique 5.4.11) notices that $𝐵 \mapsto det (𝐴 𝐵)$ is multilinear and alternating in the columns of $𝐵$ , so it equals $det (𝐴 𝐼_{𝑛}) det 𝐵$ .

A third proof makes the second one explicit. Column $𝑗$ of $𝐴 𝐵$ is $𝐴 𝐛_{𝑗} =$ $\sum_{𝑘} 𝑏_{𝑘 𝑗} 𝐚_{𝑘}$ (Proposition 2.4.8). Expanding every column as in Lemma 5.3.2, but with $𝐚_{𝑘}$ in place of $𝐞_{𝑘}$ ,

det (𝐴 𝐵) = \sum_{𝑓 \in {[𝑛]}^{[𝑛]}} 𝑏_{𝑓 (1) 1} \dots 𝑏_{𝑓 (𝑛) 𝑛} det (𝐚_{𝑓 (1)}, \dots, 𝐚_{𝑓 (𝑛)}) .

The terms with $𝑓$ not injective have a repeated column and vanish. For a permutation $𝜎$ , $det (𝐚_{𝜎 (1)}, \dots, 𝐚_{𝜎 (𝑛)}) =$ $sgn (𝜎) det 𝐴$ by Theorem 5.2.31. So

\begin{aligned} det (𝐴 𝐵) & = det 𝐴 \sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) 𝑏_{𝜎 (1) 1} \dots 𝑏_{𝜎 (𝑛) 𝑛} \\ = det 𝐴 det 𝐵 . \end{aligned}

The same computation, with $𝐞_{𝑘}$ in place of $𝐚_{𝑘}$ , proved Theorem 5.3.3; the second proof quotes its outcome, Theorem 5.3.4, instead of repeating it. Run on a rectangular $𝐴$ and $𝐵$ , the same expansion gives the Cauchy–Binet formula (Exercise 5.5.52), which neither of the first two proofs reaches.

The wrong tool here is the Leibniz formula applied to the entries of $𝐴 𝐵$ : each entry is a sum of $𝑛$ products, each of the $𝑛!$ terms multiplies out into $𝑛^{𝑛}$ products, and the cancellation is invisible. For $det 𝐴^{𝖳} = det 𝐴$ the roles change. There the axioms are the wrong tool, since the multilinearity in rows that Technique 5.4.11 would need is what the theorem is supposed to establish, while elementary matrices and the Leibniz formula both work (Intuition (What the two proofs see)).

Matrices that are not invertible were handled in three ways. In Theorem 5.4.10, both sides are $0$ on them. In Exercise 5.5.40, a polynomial in $𝑡$ carries the identity from $𝐴 + 𝑡 𝐼_{𝑛}$ to $𝐴$ , provided the field is infinite, and a separate rank argument covers every field. Proofs by the axioms never meet the case at all, which is one reason to prefer them when they apply. Practice: Exercise 5.6.8, Exercise 5.6.9, and Exercise 5.6.11.

5.6.3Showing that a determinant is nonzero

By Theorem 5.4.7, “ $det 𝐴 \neq 0$ ” and “ $𝐴$ is invertible” are the same statement, so either can be proved by proving the other.

A product of nonzero factors. A triangular matrix with nonzero diagonal, a Vandermonde matrix with distinct nodes, or any product of such matrices has nonzero determinant, since a field has no zero divisors (Proposition 1.1.17).
Reduce modulo a prime (Technique 5.3.21). For an integer matrix, one prime $𝑝$ with $det 𝐴 \neq 0$ in $𝔽_{𝑝}$ suffices (Example 5.3.22). The converse inference fails: $det 𝐴 = 0$ says only that $𝑝$ divides $det 𝐴$ .
A polynomial in a parameter (Technique 5.3.18). A polynomial of degree $𝑛$ has at most $𝑛$ roots, so $𝐴 + 𝑡 𝐼_{𝑛}$ is invertible for all but at most $𝑛$ values of $𝑡$ (Proposition 5.3.19). To show that such a polynomial is not the zero polynomial, one nonzero coefficient or one nonzero value is enough.
The kernel instead of the determinant. Show that $𝐴 𝐱 = 𝟎$ forces $𝐱 = 𝟎$ (Corollary 5.4.8). This is often the shortest route, and sometimes the only one available.
A single surviving term. If exactly one permutation avoids the zeros of $𝐴$ , then $det 𝐴$ is $\pm$ a product of nonzero entries (Exercise 5.3.30).

To show $det 𝐴 = 0$ , exhibit a dependence among the rows or columns, possibly after replacements; find a block of zeros that is too large (Exercise 5.3.29); factor $𝐴$ through a smaller size (Exercise 5.4.38); or use a symmetry, such as $det 𝐴 =$ $det 𝐴^{𝖳} =$ $- det 𝐴$ for skew-symmetric $𝐴$ of odd size (Exercise 5.4.33). The symmetry argument divides by $1 + 1$ , and Exercise 5.6.13 replaces it by a pairing that does not.

Example 5.6.4 (One matrix, four certificates). Let $𝑛 \geq 2$ , let $𝐽 \in ℚ^{𝑛 \times 𝑛}$ have every entry equal to $1$ , and let $𝐴 = 𝐽 - 𝐼_{𝑛}$ , with $0$ on the diagonal and $1$ elsewhere.

The determinant. Example 5.4.24 with $𝑥 = 0$ gives $det 𝐴 =$ $(𝑛 - 1) {(- 1)}^{𝑛 - 1} \neq$ $0$ .

The kernel. Suppose $𝐴 𝐱 = 𝟎$ , and let $𝑠 = 𝑥_{1} + \dots + 𝑥_{𝑛}$ . Row $𝑖$ of the system says $𝑠 - 𝑥_{𝑖} = 0$ . So every $𝑥_{𝑖}$ equals $𝑠$ , hence $𝑠 = 𝑛 𝑠$ , that is, $(𝑛 - 1) 𝑠 = 0$ , and $𝑠 = 0$ . So $𝐱 = 𝟎$ .

An inverse. Since $𝐽^{2} = 𝑛 𝐽$ ,

\begin{aligned} (𝐽 - 𝐼_{𝑛}) (𝐽 - (𝑛 - 1) 𝐼_{𝑛}) & = 𝑛 𝐽 - (𝑛 - 1) 𝐽 - 𝐽 + (𝑛 - 1) 𝐼_{𝑛} \\ = (𝑛 - 1) 𝐼_{𝑛}, \end{aligned}

so $𝐴^{- 1} =$ ${(𝑛 - 1)}^{- 1} (𝐽 - (𝑛 - 1) 𝐼_{𝑛})$ (Technique 2.5.16).

Modulo $2$ . For even $𝑛$ , the reduction of $𝐴$ is invertible over $𝔽_{2}$ (Exercise 5.3.40), so $det 𝐴$ is odd. For odd $𝑛$ , every row of $𝐴$ has the even sum $𝑛 - 1$ , so the reduction sends $(1, \dots, 1)$ to $𝟎$ , and this route gives no information.

The determinant contains the most information. The kernel argument is the shortest, needs no formula, and shows exactly where the hypothesis enters: over a field in which $𝑛 - 1 = 0$ , the vector $(1, \dots, 1)$ lies in the kernel. The inverse is the strongest certificate, and finding it used the algebra of $𝐽$ , not determinants. Reducing modulo a prime suits matrices whose pattern is simple modulo that prime, and this one is simple modulo $2$ only for even $𝑛$ .

Practice: Exercise 5.6.12 and Exercise 5.6.13.

5.6.4Signs of permutations

There are three ways to compute $sgn (𝜎)$ : count the factors of any factorization into transpositions, count inversions (Corollary 5.2.24), or read off the lengths of the cycles (Proposition 5.2.26). Cycles are the quickest when $𝜎$ is given in cycle notation, and inversions when it is given by its bottom row. In determinant computations, signs come from reordering rows or columns, and there it usually pays to count adjacent interchanges. That is how the cofactor sign ${(- 1)}^{𝑖 + 𝑗}$ arose (Lemma 5.5.2), and how a cyclic shift of $𝑛$ columns costs ${(- 1)}^{𝑛 - 1}$ (Exercise 5.2.34).

Example 5.6.5 (Moving a block, three ways). Let $𝑛 = 𝑘 + 𝑚$ , and let $𝜋 \in 𝑆_{𝑛}$ have bottom row $𝑚 +$ $1,$ $\dots,$ $𝑚 +$ $𝑘,$ $1,$ $\dots,$ $𝑚$ , the permutation that moves the block $(\begin{matrix} 0 & 𝐴 \\ 𝐵 & 0 \end{matrix})$ into block-diagonal form in Exercise 5.3.37.

Inversions. A pair of positions is out of order exactly when the first lies among the first $𝑘$ positions and the second among the last $𝑚$ , so $inv (𝜋) = 𝑘 𝑚$ and $sgn (𝜋) = {(- 1)}^{𝑘 𝑚}$ .

Adjacent interchanges. Each of the $𝑚$ entries $1, \dots, 𝑚$ moves to the front past each of the $𝑘$ larger entries, one adjacent interchange at a time: $𝑘 𝑚$ interchanges.

Cycles. $𝜋$ adds $𝑚$ modulo $𝑛$ , so its cycles all have length $𝑛 / gcd (𝑛, 𝑚)$ , there are $gcd (𝑛, 𝑚)$ of them, and $sgn (𝜋) =$ ${(- 1)}^{𝑛 - gcd (𝑛, 𝑚)}$ . This is correct, but it depends on number theory, and checking that it agrees with ${(- 1)}^{𝑘 𝑚}$ takes a parity argument about greatest common divisors. Cycle notation is the wrong tool for this permutation.

The definition of $sgn$ through transpositions makes multiplicativity a one-line proof (Proposition 5.2.25), while proving it from inversions takes real work (Exercise 5.2.49). In general, define an invariant through the description in which its main property is easy, and compute it through the description in which it is quick.

Sums over $𝑆_{𝑛}$ with signs are evaluated by pairing terms of opposite sign (Technique 5.3.5). Pairing $𝜎$ with $𝜎 𝜏$ for a fixed transposition $𝜏$ proved that $𝐿$ is alternating (Theorem 5.3.4) and that half of all permutations are even (Proposition 5.2.27). Pairing $𝜎$ with $𝜎^{- 1}$ handles alternating matrices (Exercise 5.6.13). Parity also proves that some configurations cannot be reached (Technique 5.2.19): the $15$ puzzle (Exercise 5.2.47) and the rotation puzzle (Exercise 5.2.48). Practice: Exercise 5.6.14.

5.6.5Reading the chapter’s proofs

Uniqueness first, then existence. The existence proof was found backwards. We assumed that a determinant function exists and asked what it would have to be. Expanding every column (Lemma 5.3.2), letting alternation kill the terms with a repeated column, and sorting the survivors (Theorem 5.2.31) produced Theorem 5.3.3: at most one candidate, given by a formula. Only then did Section 5.3.2 verify that the candidate satisfies the axioms. The $2 \times 2$ case went the same way (Theorem 5.1.13). The derivation also showed what existence requires: sorting the columns must produce a well-defined sign, which is the parity theorem (Remark 5.2.32). This is the “derive the formula” move of Section 1.7.2 on a larger scale. The verification also shows where the difficulty lay. Normalization and multilinearity can be checked one term at a time, but alternation cannot, because equal columns do not force any single term to vanish.

Pairing instead of reindexing. Reindexing the Leibniz sum by $𝜎 \mapsto 𝜎 𝜏$ shows $𝐿 (𝐴) = - 𝐿 (𝐴)$ , which gives $𝐿 (𝐴) = 0$ only after dividing by $1 + 1$ . Pairing each $𝜎$ with $𝜎 𝜏$ writes $𝐿 (𝐴)$ as a sum of pairs that cancel, and never divides (Intuition (Why alternation needs care)). The same distinction separates antisymmetry from alternation (Proposition 5.1.11, Example 5.1.12), and it is the reason the definition asks for alternation. An argument that ends with “ $𝑥 = - 𝑥$ , so $𝑥 = 0$ ” has used $1 + 1 \neq 0$ and should say so.

Tracking which axiom is used. Theorem 5.1.13 kept $𝐷 (𝐼_{2})$ as an unknown and obtained a statement about every multilinear alternating function at no extra cost. The same bookkeeping showed that dependent columns force $𝐷 (𝐴) = 0$ without normalization (Proposition 5.1.17), while the converse fails for $𝐷 = 0$ . So every proof of Theorem 5.4.7 must use normalization somewhere, and the proof in the text uses it through Proposition 5.4.1.

Columns first. The axioms speak about columns, so every statement about rows waited for Theorem 5.4.14 (Corollary 5.4.15, Technique 3.2.27). Statements that mix rows and columns, such as cofactor expansion, were proved for rows and transposed, or proved with whichever kind of operation was convenient.

5.6.6Common errors

Most of these appear in the chapter as find-the-error exercises.

det is not linear. In general $det (𝐴 + 𝐵) \neq$ $det 𝐴 +$ $det 𝐵$ , and $det (𝑐 𝐴) =$ $𝑐^{𝑛} det 𝐴$ (Exercise 5.1.21, Exercise 5.3.26, Remark 5.1.4). Multilinear means linear in one column at a time. In the same way, a $2 \times 2$ block matrix is not a $2 \times 2$ matrix of numbers (Exercise 5.4.36).
Sarrus for larger matrices. The rule of Sarrus is a coincidence of size $3$ (Remark 5.3.11, Exercise 5.3.25).
The sign of a cofactor. The sign ${(- 1)}^{𝑖 + 𝑗}$ comes from $𝑖 - 1$ and $𝑗 - 1$ adjacent interchanges. Interchanging row $𝑖$ with row $1$ directly puts the old row $1$ out of order, and for $𝑖 \geq 3$ what remains is not the minor $𝐵_{\hat{𝑖 𝑗}}$ (Exercise 5.6.15). Forgetting the checkerboard altogether is the commoner version.
Row operations that scale. Replacing row $𝑖$ by $2$ times row $𝑖$ minus $3$ times row $1$ doubles the determinant (Exercise 5.4.16).
Factoring a singular matrix. Only invertible matrices are products of elementary matrices (Exercise 5.4.35).
A converse for arbitrary $𝐷$ . A multilinear alternating $𝐷$ can vanish on invertible matrices (Exercise 5.1.22).
Circularity. The existence proof in Section 5.3.2 rests on the parity theorem, so quoting Theorem 5.3.4 to prove that theorem is circular (Exercise 5.2.38).
Inversions under a transposition. They change by an odd number, not always by $1$ (Exercise 5.2.35).
Polynomial arguments. Roots determine a polynomial only together with its leading coefficient (Exercise 5.5.42), and agreement at “all but finitely many points” proves nothing over a small finite field (Exercise 5.6.10).
Reducing modulo $𝑝$ in the wrong direction. $det 𝐴 = 0$ in $𝔽_{𝑝}$ does not make $𝐴$ singular over $ℚ$ (Technique 5.3.21, Exercise 5.3.36).
Hidden division by $1 + 1$ . Antisymmetry does not imply alternation over $𝔽_{2}$ (Example 5.1.12), and neither does $det 𝐴 = - det 𝐴$ imply $det 𝐴 = 0$ (Exercise 5.4.33).

Exercises

Exercise 5.6.6.routine For each matrix, choose a method, say why it fits, and compute the determinant.

(a) $𝐴 =$ $(\begin{matrix} 2 & 1 & 0 & 0 & 0 \\ 1 & 2 & 0 & 0 & 0 \\ 7 & 3 & 1 & 2 & 0 \\ - 4 & 5 & 0 & 1 & 3 \\ 9 & 9 & 4 & 0 & 1 \end{matrix}) \in$ $ℚ^{5 \times 5}$ .
(b) $𝐵 (𝑥) =$ $(\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 𝑥 & 1 & 1 \\ 1 & 1 & 𝑥 & 1 \\ 1 & 1 & 1 & 𝑥 \end{matrix})$ , for $𝑥 \in 𝐹$ .
(c) $𝐶 =$ $(\begin{matrix} 0 & 0 & 0 & 3 \\ 0 & 0 & 2 & 0 \\ 0 & 5 & 0 & 0 \\ 1 & 0 & 0 & 7 \end{matrix}) \in$ $ℚ^{4 \times 4}$ .

Solution.

Uses. Theorem 5.4.26 (Block-triangular matrices), Corollary 5.4.15 (Rows), Proposition 5.3.15 (Triangular matrices), Theorem 5.3.3 (The Leibniz formula), Theorem 5.2.31 (Alternating functions and permutations)

Techniques. Read structure off the Leibniz expansion (Technique 5.3.12), Expose a factor with row and column operations (Technique 5.5.22)

Hint 1. In (a), look at the upper right

2 \times 3

corner. In (b), every row differs from row

1

in one entry. In (c), most columns have a single nonzero entry.

Hint 2. (a) is block lower triangular. In (b), subtract row

1

from the other rows. In (c), list the permutations that avoid the zeros, column by column.

Sketch. (a) Block lower triangular with diagonal blocks of determinants

3

and

25

det 𝐴 = 75

. (b) Subtracting row

1

from rows

2

3

4

leaves an upper triangular matrix with diagonal

1, 𝑥 - 1, 𝑥 - 1, 𝑥 - 1

det 𝐵 (𝑥) = {(𝑥 - 1)}^{3}

. (c) Only

𝜎 = (1 4) (2 3)

survives, and it is even:

det 𝐶 = 1 \cdot 5 \cdot 2 \cdot 3 = 30

(a) The entries in rows $1, 2$ and columns $3, 4, 5$ are all $0$ , so $𝐴 = (\begin{matrix} 𝐴_{1} & 0 \\ 𝑋 & 𝐴_{2} \end{matrix})$ is block lower triangular, with

𝐴_{1} = (\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}), 𝐴_{2} = (\begin{matrix} 1 & 2 & 0 \\ 0 & 1 & 3 \\ 4 & 0 & 1 \end{matrix}) .

By Theorem 5.4.26, $det 𝐴 =$ $det 𝐴_{1} det 𝐴_{2}$ . Here $det 𝐴_{1} = 4 - 1 = 3$ , and expanding $𝐴_{2}$ along its first row, $det 𝐴_{2} =$ $1 (1 - 0) -$ $2 (0 - 12) +$ $0 =$ $25$ . So $det 𝐴 = 75$ . The block $𝑋$ never enters; elimination would have computed with it anyway.

(b) Subtract row $1$ from each of rows $2$ , $3$ , $4$ . These replacements do not change the determinant (Corollary 5.4.15), and row $𝑖$ becomes $(𝑥 - 1) 𝐞_{𝑖}^{𝖳}$ . The result is upper triangular with diagonal entries $1, 𝑥 - 1, 𝑥 - 1, 𝑥 - 1$ , so $det 𝐵 (𝑥) = {(𝑥 - 1)}^{3}$ by Proposition 5.3.15. The factor $𝑥 - 1$ was exposed by the replacements before anything was multiplied out.

(c) We find the permutations $𝜎$ with $𝑐_{𝜎 (𝑗) 𝑗} \neq 0$ for every $𝑗$ . Columns $1$ , $2$ , $3$ have their only nonzero entries in rows $4$ , $3$ , $2$ , so $𝜎 (1) = 4$ , $𝜎 (2) = 3$ , $𝜎 (3) = 2$ . Column $4$ has nonzero entries in rows $1$ and $4$ , and row $4$ is taken, so $𝜎 (4) = 1$ . Thus $𝜎 = (1 4) (2 3)$ , a product of two transpositions, which is even (Proposition 5.2.25). By Theorem 5.3.3,

det 𝐶 = 𝑐_{41} 𝑐_{32} 𝑐_{23} 𝑐_{14} = 1 \cdot 5 \cdot 2 \cdot 3 = 30 .

The entry $7$ belongs to no surviving term. Elimination would need swaps, and would carry the $7$ along until it ended up above the diagonal.

Exercise 5.6.7.standard For $𝑛 \geq 1$ , let $𝑃_{𝑛} \in ℚ^{𝑛 \times 𝑛}$ have entries $𝑝_{𝑖 𝑗} =$ $(\binom{𝑖 + 𝑗 - 2}{𝑖 - 1})$ , so that

𝑃_{4} = (\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 \\ 1 & 3 & 6 & 10 \\ 1 & 4 & 10 & 20 \end{matrix}) .

(a)Show that $det 𝑃_{𝑛} = 1$ for every $𝑛$ . You may use Pascal’s rule $(\binom{𝑚}{𝑘}) =$ $(\binom{𝑚 - 1}{𝑘}) +$ $(\binom{𝑚 - 1}{𝑘 - 1})$ for $𝑚, 𝑘 \geq 1$ , and $(\binom{𝑚}{𝑘}) = 0$ for $0 \leq 𝑚 < 𝑘$ .
(b)Deduce that $𝑃_{𝑛}^{- 1}$ has integer entries, and compute $𝑃_{3}^{- 1}$ .

Solution (by row and column operations).

Uses. Corollary 5.4.15 (Rows), Lemma 5.1.8 (Column replacement), Proposition 5.3.17 (Block-diagonal matrices), Corollary 5.5.12 (Integer inverses), Definition 5.5.6 (Cofactors, cofactor matrix, adjugate)

Techniques. Expose a factor with row and column operations (Technique 5.5.22), Induction on matrix size (Technique 5.5.17), Factor the matrix (Technique 5.6.1)

Hint 1. Subtract each row from the row below it, starting from the bottom. What does Pascal’s rule do to the entries?

Hint 2. After the row operations, the first column is

𝐞_{1}

. Now subtract each column from the column to its right, starting from the right, and identify the lower right block.

Sketch. Replacing row

𝑖

by row

𝑖

minus row

𝑖 - 1

(for

𝑖 = 𝑛, \dots, 2

) turns the entries into

(\binom{𝑖 + 𝑗 - 3}{𝑖 - 1})

, so column

1

becomes

𝐞_{1}

. Replacing column

𝑗

by column

𝑗

minus column

𝑗 - 1

(for

𝑗 = 𝑛, \dots, 2

) turns row

1

into

𝐞_{1}^{𝖳}

and the rest into

(\binom{𝑖 + 𝑗 - 4}{𝑖 - 2})

, which is

𝑃_{𝑛 - 1}

. So

det 𝑃_{𝑛} =

det 𝑃_{𝑛 - 1} =

\dots =

1

, and

𝑃_{𝑛}^{- 1} = adj 𝑃_{𝑛}

is integral.

(a) We show $det 𝑃_{𝑛} = det 𝑃_{𝑛 - 1}$ for $𝑛 \geq 2$ ; since $𝑃_{1} = (1)$ , induction on $𝑛$ then gives $det 𝑃_{𝑛} = 1$ .

Rows. For $𝑖 = 𝑛, 𝑛 - 1, \dots, 2$ in turn, subtract row $𝑖 - 1$ from row $𝑖$ . Since we work from the bottom up, row $𝑖 - 1$ is still the original row when it is used. For $𝑖 \geq 2$ , Pascal’s rule with $𝑚 = 𝑖 + 𝑗 - 2 \geq 1$ and $𝑘 = 𝑖 - 1 \geq 1$ gives the new entry

(\binom{𝑖 + 𝑗 - 2}{𝑖 - 1}) - (\binom{𝑖 + 𝑗 - 3}{𝑖 - 2}) = (\binom{𝑖 + 𝑗 - 3}{𝑖 - 1}) .

For $𝑗 = 1$ this is $(\binom{𝑖 - 2}{𝑖 - 1}) = 0$ . So column $1$ is now $𝐞_{1}$ , and row $1$ is still $(1, 1, \dots, 1)$ .

Columns. For $𝑗 = 𝑛, 𝑛 - 1, \dots, 2$ in turn, subtract column $𝑗 - 1$ from column $𝑗$ . In row $1$ the new entries are $1 - 1 = 0$ . In a row $𝑖 \geq 2$ , Pascal’s rule with $𝑚 = 𝑖 + 𝑗 - 3 \geq 1$ and $𝑘 = 𝑖 - 1 \geq 1$ gives

\begin{aligned} (\binom{𝑖 + 𝑗 - 3}{𝑖 - 1}) - (\binom{𝑖 + 𝑗 - 4}{𝑖 - 1}) & = (\binom{𝑖 + 𝑗 - 4}{𝑖 - 2}) \\ = (\binom{(𝑖 - 1) + (𝑗 - 1) - 2}{(𝑖 - 1) - 1}), \end{aligned}

the $(𝑖 - 1, 𝑗 - 1)$ entry of $𝑃_{𝑛 - 1}$ . Column $1$ is unchanged.

The matrix is now $(\begin{matrix} 1 & 0 \\ 0 & 𝑃_{𝑛 - 1} \end{matrix})$ , and all the operations were replacements, which do not change the determinant (Corollary 5.4.15, Lemma 5.1.8). By Proposition 5.3.17, $det 𝑃_{𝑛} = det 𝑃_{𝑛 - 1}$ .

(b) Since $det 𝑃_{𝑛} = 1$ and $𝑃_{𝑛}$ has integer entries, $𝑃_{𝑛}^{- 1} = adj 𝑃_{𝑛}$ has integer entries (Corollary 5.5.12). For $𝑃_{3} = (\begin{matrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 3 & 6 \end{matrix})$ the cofactors are

\begin{aligned} 𝑐_{11} & = 3, & 𝑐_{12} & = - 3, & 𝑐_{13} & = 1, \\ 𝑐_{21} & = - 3, & 𝑐_{22} & = 5, & 𝑐_{23} & = - 2, \\ 𝑐_{31} & = 1, & 𝑐_{32} & = - 2, & 𝑐_{33} & = 1, \end{aligned}

𝑃_{3}^{- 1} = (\begin{matrix} 3 & - 3 & 1 \\ - 3 & 5 & - 2 \\ 1 & - 2 & 1 \end{matrix}) .

Multiplying out confirms $𝑃_{3} 𝑃_{3}^{- 1} = 𝐼_{3}$ .

Solution (by factoring).

Uses. Theorem 5.4.10 (Multiplicativity), Theorem 5.4.14 (The transpose), Proposition 5.3.15 (Triangular matrices)

Techniques. Expose a factor with row and column operations (Technique 5.5.22), Induction on matrix size (Technique 5.5.17), Factor the matrix (Technique 5.6.1)

Hint 1. Look for a lower triangular

𝐿

with

𝑃_{𝑛} = 𝐿 𝐿^{𝖳}

. Try

𝐿

with entries

(\binom{𝑖 - 1}{𝑘 - 1})

, the rows of Pascal’s triangle.

Hint 2. The

(𝑖, 𝑗)

entry of

𝐿 𝐿^{𝖳}

\sum_{𝑘} (\binom{𝑖 - 1}{𝑘 - 1}) (\binom{𝑗 - 1}{𝑘 - 1})

. Count the ways to choose

𝑗 - 1

objects from

𝑖 - 1

red and

𝑗 - 1

blue ones.

Sketch. With

𝑙_{𝑖 𝑘} = (\binom{𝑖 - 1}{𝑘 - 1})

𝐿

is lower triangular with

1

s on the diagonal, and Vandermonde’s identity gives

{(𝐿 𝐿^{𝖳})}_{𝑖 𝑗} =

\sum_{𝑘} (\binom{𝑖 - 1}{𝑘 - 1}) (\binom{𝑗 - 1}{𝑗 - 𝑘}) =

(\binom{𝑖 + 𝑗 - 2}{𝑗 - 1}) =

𝑝_{𝑖 𝑗}

. So

det 𝑃_{𝑛} =

{(det 𝐿)}^{2} =

1

Let $𝐿 \in ℚ^{𝑛 \times 𝑛}$ have entries $𝑙_{𝑖 𝑘} = (\binom{𝑖 - 1}{𝑘 - 1})$ . Then $𝑙_{𝑖 𝑘} = 0$ for $𝑘 > 𝑖$ and $𝑙_{𝑖 𝑖} = 1$ , so $𝐿$ is lower triangular with $1$ s on the diagonal, and $det 𝐿 = 1$ by Proposition 5.3.15. The terms with $𝑘 > min (𝑖, 𝑗)$ vanish, and for $𝑘 \leq 𝑗$ we have $(\binom{𝑗 - 1}{𝑘 - 1}) =$ $(\binom{𝑗 - 1}{𝑗 - 𝑘})$ , so

{(𝐿 𝐿^{𝖳})}_{𝑖 𝑗} = \sum_{𝑘 = 1}^{min (𝑖, 𝑗)} (\binom{𝑖 - 1}{𝑘 - 1}) (\binom{𝑗 - 1}{𝑗 - 𝑘}) .

The $𝑘$ -th term counts the ways to choose $𝑗 - 1$ objects from a set of $𝑖 - 1$ red and $𝑗 - 1$ blue objects using exactly $𝑘 - 1$ red and $𝑗 - 𝑘$ blue ones. Every choice has between $0$ and $min (𝑖, 𝑗) - 1$ red objects, so the sum is $(\binom{𝑖 + 𝑗 - 2}{𝑗 - 1}) =$ $(\binom{𝑖 + 𝑗 - 2}{𝑖 - 1}) =$ $𝑝_{𝑖 𝑗}$ . Hence $𝑃_{𝑛} = 𝐿 𝐿^{𝖳}$ , and $det 𝑃_{𝑛} =$ $det 𝐿 det 𝐿^{𝖳} =$ $1$ by Theorem 5.4.10 and Theorem 5.4.14.

The row operations of the first approach compute this factorization step by step. The second approach finds it at once, but only after guessing $𝐿$ .

Exercise 5.6.8.standard Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . For $𝑋 \in 𝐹^{𝑛 \times 𝑛}$ with columns $𝐱_{1}, \dots, 𝐱_{𝑛}$ , let

𝐷 (𝑋) = \sum_{𝑗 = 1}^{𝑛} det (𝐱_{1}, \dots, 𝐱_{𝑗 - 1}, 𝐴 𝐱_{𝑗}, 𝐱_{𝑗 + 1}, \dots, 𝐱_{𝑛}),

the sum of the determinants obtained by applying $𝐴$ to one column at a time.

(a)Show that $𝐷 (𝑋) =$ $(tr 𝐴) det 𝑋$ for every $𝑋 \in 𝐹^{𝑛 \times 𝑛}$ .
(b)Deduce that for every multilinear alternating $𝐸 : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ ,
$\sum_{𝑗 = 1}^{𝑛} 𝐸 (𝐱_{1}, \dots, 𝐴 𝐱_{𝑗}, \dots, 𝐱_{𝑛}) = (tr 𝐴) 𝐸 (𝐱_{1}, \dots, 𝐱_{𝑛}) .$

Solution.

Uses. Theorem 5.3.4 (Existence and uniqueness of the determinant), Proposition 5.1.10 (Alternating implies antisymmetric), Definition 5.1.1 (Determinant function), Definition 2.4.26 (Trace)

Techniques. Recognize the determinant by its axioms (Technique 5.4.11), Expand by multilinearity (Technique 5.1.7)

Hint 1. Do not compute. Show that

𝐷

is multilinear and alternating, and evaluate it at

𝐼_{𝑛}

Hint 2. For alternation, suppose columns

𝑘

and

𝑙

𝑋

are equal. Only the summands

𝑗 = 𝑘

and

𝑗 = 𝑙

survive. How are their matrices related?

Hint 3.

𝐷 (𝐼_{𝑛}) =

\sum_{𝑗} det (𝐞_{1}, \dots, 𝐴 𝐞_{𝑗}, \dots, 𝐞_{𝑛})

. Expand

𝐴 𝐞_{𝑗} =

\sum_{𝑖} 𝑎_{𝑖 𝑗} 𝐞_{𝑖}

in column

𝑗

Sketch. Each summand is multilinear (in column

𝑗

it is

det

composed with

𝐱 \mapsto 𝐴 𝐱

), so

𝐷

is. If

𝐱_{𝑘} = 𝐱_{𝑙}

with

𝑘 \neq 𝑙

, the summands with

𝑗 \notin {𝑘, 𝑙}

have two equal columns, and the summands

𝑗 = 𝑘

and

𝑗 = 𝑙

differ by interchanging columns

𝑘

and

𝑙

, so they cancel. Hence

𝐷 = 𝐷 (𝐼_{𝑛}) det

, and

𝐷 (𝐼_{𝑛}) =

\sum_{𝑗} 𝑎_{𝑗 𝑗} =

tr 𝐴

(a) Write $𝐷 = 𝐷_{1} + \dots + 𝐷_{𝑛}$ , where $𝐷_{𝑗} (𝑋)$ is the $𝑗$ -th summand. We check the hypotheses of Theorem 5.3.4.

Multilinear. In column $𝑗$ , $𝐷_{𝑗}$ is the composite of the linear map $𝐱 \mapsto 𝐴 𝐱$ with $det$ as a function of column $𝑗$ , so it is linear in column $𝑗$ . In every other column $𝐷_{𝑗}$ is linear because $det$ is. So each $𝐷_{𝑗}$ is multilinear, and so is their sum, since a sum of functions that are linear in a column is linear in that column.

Alternating. Suppose $𝐱_{𝑘} = 𝐱_{𝑙} = 𝐱$ for some $𝑘 < 𝑙$ . If $𝑗 \notin {𝑘, 𝑙}$ , the matrix in $𝐷_{𝑗} (𝑋)$ still has $𝐱$ in columns $𝑘$ and $𝑙$ , so $𝐷_{𝑗} (𝑋) = 0$ . The matrix in $𝐷_{𝑘} (𝑋)$ has $𝐴 𝐱$ in column $𝑘$ and $𝐱$ in column $𝑙$ ; the matrix in $𝐷_{𝑙} (𝑋)$ has $𝐱$ in column $𝑘$ and $𝐴 𝐱$ in column $𝑙$ , and agrees with the first elsewhere. So it is the first matrix with columns $𝑘$ and $𝑙$ interchanged, and $𝐷_{𝑙} (𝑋) =$ $- 𝐷_{𝑘} (𝑋)$ by Proposition 5.1.10. Hence $𝐷 (𝑋) = 0$ .

By Theorem 5.3.4, $𝐷 (𝑋) =$ $𝐷 (𝐼_{𝑛}) det 𝑋$ . To find $𝐷 (𝐼_{𝑛})$ , note that $𝐴 𝐞_{𝑗} =$ $\sum_{𝑖} 𝑎_{𝑖 𝑗} 𝐞_{𝑖}$ and expand $𝐷_{𝑗} (𝐼_{𝑛})$ in column $𝑗$ :

𝐷_{𝑗} (𝐼_{𝑛}) = \sum_{𝑖 = 1}^{𝑛} 𝑎_{𝑖 𝑗} det (𝐞_{1}, \dots, 𝐞_{𝑗 - 1}, 𝐞_{𝑖}, 𝐞_{𝑗 + 1}, \dots, 𝐞_{𝑛}) .

For $𝑖 \neq 𝑗$ the vector $𝐞_{𝑖}$ appears twice, so only $𝑖 = 𝑗$ survives, with value $𝑎_{𝑗 𝑗} det 𝐼_{𝑛} =$ $𝑎_{𝑗 𝑗}$ . So $𝐷 (𝐼_{𝑛}) =$ $\sum_{𝑗} 𝑎_{𝑗 𝑗} =$ $tr 𝐴$ , as desired.

(b) By Theorem 5.3.4, $𝐸 = 𝐸 (𝐼_{𝑛}) det$ . Applying this to each summand and using (a),

\begin{aligned} \sum_{𝑗} 𝐸 (𝐱_{1}, \dots, 𝐴 𝐱_{𝑗}, \dots, 𝐱_{𝑛}) & = 𝐸 (𝐼_{𝑛}) 𝐷 (𝑋) \\ = 𝐸 (𝐼_{𝑛}) (tr 𝐴) det 𝑋 = (tr 𝐴) 𝐸 (𝑋) . \end{aligned}

The left side of (b) makes sense for any alternating form on a vector space, without a basis, so it can serve as a definition of the trace of an operator; compare Section 13.4. Over $ℝ$ , $𝐷 (𝑋)$ is the coefficient of $𝑡$ in $det (𝑋 + 𝑡 𝐴 𝑋) =$ $det (𝐼_{𝑛} + 𝑡 𝐴) det 𝑋$ , so (a) says that the trace is the rate at which $det (𝐼_{𝑛} + 𝑡 𝐴)$ changes at $𝑡 = 0$ (Remark 5.5.28).

Exercise 5.6.9.hard Let $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ and $𝑡 \in 𝐹$ . We show that

det (𝑡 𝐼_{𝑛} - 𝐴 𝐵) = det (𝑡 𝐼_{𝑛} - 𝐵 𝐴) .

(a)Prove this when $𝐴$ is invertible.
(b)Let $𝐹$ be infinite. Fix $𝑡$ , and show that $𝑔 (𝑠) =$ $det (𝑡 𝐼_{𝑛} - (𝐴 + 𝑠 𝐼_{𝑛}) 𝐵) -$ $det (𝑡 𝐼_{𝑛} - 𝐵 (𝐴 + 𝑠 𝐼_{𝑛}))$ satisfies $𝑔 (𝑠) =$ $𝑒_{0} +$ $𝑒_{1} 𝑠 +$ $\dots +$ $𝑒_{𝑛} 𝑠^{𝑛}$ for some $𝑒_{0}, \dots, 𝑒_{𝑛} \in 𝐹$ and all $𝑠 \in 𝐹$ , and that $𝑔 (𝑠) = 0$ for all but at most $𝑛$ values of $𝑠$ . Conclude that the identity holds for every $𝐴$ .
(c)Prove the identity over every field, using Exercise 5.5.47 when $𝑡 \neq 0$ .

Solution.

Uses. Proposition 5.4.17 (Similar matrices have equal determinants), Theorem 5.4.10 (Multiplicativity), Proposition 5.3.19 ( $det (𝐴 + 𝑡 𝐼_{𝑛})$ as a function of $𝑡$ ), Lemma 3.4.23 (Too many roots), Exercise 5.5.47, Exercise 5.1.5

Techniques. Polynomial identity arguments (Technique 5.5.24), $det$ is a polynomial in the entries (Technique 5.3.18)

Hint 1. For (a),

𝐵 𝐴 = 𝐴^{- 1} (𝐴 𝐵) 𝐴

Hint 2. For (b), the entries of

𝑡 𝐼_{𝑛} -

(𝐴 + 𝑠 𝐼_{𝑛}) 𝐵

have the form

𝛼 + 𝛽 𝑠

. What does the Leibniz formula then say about its determinant? For which

𝑠

does (a) apply to

𝐴 + 𝑠 𝐼_{𝑛}

Hint 3. For (c), write

𝑡 𝐼_{𝑛} -

𝐴 𝐵 =

𝑡 (𝐼_{𝑛} - 𝑡^{- 1} 𝐴 𝐵)

and pull out

𝑡^{𝑛}

. The case

𝑡 = 0

is multiplicativity.

Sketch. (a)

𝑡 𝐼_{𝑛} -

𝐵 𝐴 =

𝐴^{- 1} (𝑡 𝐼_{𝑛} - 𝐴 𝐵) 𝐴

is similar to

𝑡 𝐼_{𝑛} - 𝐴 𝐵

. (b) Both determinants are sums of products of

𝑛

affine functions of

𝑠

, hence polynomial of degree at most

𝑛

𝑠

. By (a),

𝑔 (𝑠) = 0

whenever

𝐴 + 𝑠 𝐼_{𝑛}

is invertible, which fails for at most

𝑛

values of

𝑠

. An infinite field supplies

𝑛 + 1

other values, so all

𝑒_{𝑘} = 0

and

𝑔 (0) = 0

. (c) For

𝑡 \neq 0

det (𝑡 𝐼_{𝑛} - 𝐴 𝐵) =

𝑡^{𝑛} det (𝐼_{𝑛} + (- 𝑡^{- 1} 𝐴) 𝐵) =

𝑡^{𝑛} det (𝐼_{𝑛} + 𝐵 (- 𝑡^{- 1} 𝐴)) =

det (𝑡 𝐼_{𝑛} - 𝐵 𝐴)

. For

𝑡 = 0

det (- 𝐴 𝐵) =

{(- 1)}^{𝑛} det 𝐴 det 𝐵 =

det (- 𝐵 𝐴)

(a) Since $𝐴$ is invertible, $𝐵 𝐴 = 𝐴^{- 1} (𝐴 𝐵) 𝐴$ , so

\begin{aligned} 𝑡 𝐼_{𝑛} - 𝐵 𝐴 & = 𝐴^{- 1} (𝑡 𝐼_{𝑛}) 𝐴 - 𝐴^{- 1} (𝐴 𝐵) 𝐴 \\ = 𝐴^{- 1} (𝑡 𝐼_{𝑛} - 𝐴 𝐵) 𝐴 . \end{aligned}

Similar matrices have equal determinants (Proposition 5.4.17), so $det (𝑡 𝐼_{𝑛} - 𝐵 𝐴) =$ $det (𝑡 𝐼_{𝑛} - 𝐴 𝐵)$ .

(b) Every entry of $𝑡 𝐼_{𝑛} -$ $(𝐴 + 𝑠 𝐼_{𝑛}) 𝐵 =$ $(𝑡 𝐼_{𝑛} - 𝐴 𝐵) -$ $𝑠 𝐵$ has the form $𝛼 + 𝛽 𝑠$ with $𝛼, 𝛽 \in 𝐹$ independent of $𝑠$ . Each term of the Leibniz formula is $\pm$ a product of $𝑛$ such entries, and multiplying out a product of $𝑛$ affine functions of $𝑠$ gives $𝑐_{0} +$ $𝑐_{1} 𝑠 +$ $\dots +$ $𝑐_{𝑛} 𝑠^{𝑛}$ for scalars $𝑐_{𝑘}$ independent of $𝑠$ (as in the proof of Proposition 5.3.19). Summing over $𝑆_{𝑛}$ , the first determinant has this form, and likewise the second, whose matrix $(𝑡 𝐼_{𝑛} - 𝐵 𝐴) -$ $𝑠 𝐵$ also has affine entries. Their difference $𝑔$ is therefore $𝑒_{0} +$ $𝑒_{1} 𝑠 +$ $\dots +$ $𝑒_{𝑛} 𝑠^{𝑛}$ for some $𝑒_{𝑘} \in 𝐹$ .

By Proposition 5.3.19, $det (𝐴 + 𝑠 𝐼_{𝑛})$ is the value at $𝑠$ of a polynomial of degree $𝑛$ with leading coefficient $1$ . That polynomial is not zero, so by Lemma 3.4.23 it has at most $𝑛$ roots, and $𝐴 + 𝑠 𝐼_{𝑛}$ is invertible for all but at most $𝑛$ values of $𝑠$ . For each such $𝑠$ , (a) applied to $𝐴 + 𝑠 𝐼_{𝑛}$ gives $𝑔 (𝑠) = 0$ .

Since $𝐹$ is infinite, there are $𝑛 + 1$ distinct values of $𝑠$ at which $𝐴 + 𝑠 𝐼_{𝑛}$ is invertible. The polynomial $𝑒_{0} +$ $𝑒_{1} 𝑥 +$ $\dots +$ $𝑒_{𝑛} 𝑥^{𝑛} \in$ ${𝐹 [𝑥]}_{\leq 𝑛}$ vanishes at all of them, so it is zero by Lemma 3.4.23, and $𝑔 (𝑠) = 0$ for every $𝑠$ . At $𝑠 = 0$ this is the identity for $𝐴$ .

(c) If $𝑡 \neq 0$ , then $𝑡 𝐼_{𝑛} -$ $𝐴 𝐵 =$ $𝑡 (𝐼_{𝑛} + (- 𝑡^{- 1} 𝐴) 𝐵)$ , so by Exercise 5.1.5 and Exercise 5.5.47 (with $𝑚 = 𝑛$ , and $- 𝑡^{- 1} 𝐴$ in place of $𝐴$ ),

\begin{aligned} det (𝑡 𝐼_{𝑛} - 𝐴 𝐵) & = 𝑡^{𝑛} det (𝐼_{𝑛} + (- 𝑡^{- 1} 𝐴) 𝐵) \\ = 𝑡^{𝑛} det (𝐼_{𝑛} + 𝐵 (- 𝑡^{- 1} 𝐴)) = det (𝑡 𝐼_{𝑛} - 𝐵 𝐴) . \end{aligned}

If $𝑡 = 0$ , then by Exercise 5.1.5 and Theorem 5.4.10, $det (- 𝐴 𝐵) =$ ${(- 1)}^{𝑛} det 𝐴 det 𝐵 =$ ${(- 1)}^{𝑛} det 𝐵 det 𝐴 =$ $det (- 𝐵 𝐴)$ .

The two proofs pay in different ways. The polynomial argument has to avoid the at most $𝑛$ values where $𝐴 + 𝑠 𝐼_{𝑛}$ is singular and still find $𝑛 + 1$ others, so it needs more than $2 𝑛$ scalars, which an infinite field guarantees. Sylvester’s identity holds over every field, but the reduction to it divides by $𝑡$ , so $𝑡 = 0$ is a separate case. In Section 7.3 the identity says that $𝐴 𝐵$ and $𝐵 𝐴$ have the same characteristic polynomial.

Exercise 5.6.10.standard Find the error in the following argument, and give a matrix $𝐴 \in 𝔽_{2}^{2 \times 2}$ for which its key step fails. (The claim itself is true over every field; see the second approach to Exercise 5.5.40.)

Claim. For every field $𝐹$ , every $𝑛 \geq 2$ , and every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , $adj (adj 𝐴) =$ ${(det 𝐴)}^{𝑛 - 2} 𝐴$ , with the convention $0^{0} = 1$ when $𝑛 = 2$ .

Proof. For invertible $𝐴$ this is a short computation (Exercise 5.5.40). For general $𝐴$ , the entries of $adj (adj (𝐴 + 𝑡 𝐼_{𝑛}))$ and of ${det (𝐴 + 𝑡 𝐼_{𝑛})}^{𝑛 - 2} (𝐴 + 𝑡 𝐼_{𝑛})$ are polynomial functions of $𝑡$ . They agree whenever $𝐴 + 𝑡 𝐼_{𝑛}$ is invertible, that is, for all but at most $𝑛$ values of $𝑡$ . Polynomial functions that agree at all but finitely many points are equal, so they also agree at $𝑡 = 0$ .

Solution.

Uses. Lemma 3.4.23 (Too many roots), Proposition 5.3.19 ( $det (𝐴 + 𝑡 𝐼_{𝑛})$ as a function of $𝑡$ ), Definition 5.5.6 (Cofactors, cofactor matrix, adjugate)

Techniques. Polynomial identity arguments (Technique 5.5.24), Try small cases and small fields (Technique 1.2.38)

Hint 1. Over a finite field, how many values of

𝑡

can be left after excluding up to

𝑛

of them?

Hint 2. Polynomials of degree at most

𝑑

that agree at

𝑑 + 1

distinct points are equal. What are the degrees here? For the example, try a diagonal matrix with diagonal entries

0

and

1

Sketch. The last step needs more agreement points than the degree of the polynomials, which is up to

{(𝑛 - 1)}^{2}

. Over a finite field, “all but at most

𝑛

values” can be very few values, or none: for

𝐴 =

diag (0, 1) \in

𝔽_{2}^{2 \times 2}

, both

𝐴

and

𝐴 + 𝐼_{2} = diag (1, 0)

are singular. The argument is valid once

| 𝐹 | \geq 𝑛^{2} - 𝑛 + 2

, in particular over every infinite field.

The error is the last step. Two polynomial functions of degree at most $𝑑$ are equal if they agree at $𝑑 + 1$ distinct points (Lemma 3.4.23), and “all but finitely many points” supplies that many points only if the field has enough elements. Over a finite field it can supply none.

The example. Let $𝐴 = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) \in 𝔽_{2}^{2 \times 2}$ . Then $𝐴 + 0 \cdot 𝐼_{2} = 𝐴$ and $𝐴 + 1 \cdot 𝐼_{2} = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ are both singular, so there is no $𝑡 \in 𝔽_{2}$ at which the two sides are known to agree, and the argument proves nothing about $𝐴$ .

When the argument works. The entries of $𝐴 + 𝑡 𝐼_{𝑛}$ have degree at most $1$ in $𝑡$ , so the cofactors of $𝐴 + 𝑡 𝐼_{𝑛}$ , which are determinants of size $𝑛 - 1$ , have degree at most $𝑛 - 1$ , and the entries of $adj (adj (𝐴 + 𝑡 𝐼_{𝑛}))$ have degree at most ${(𝑛 - 1)}^{2}$ . On the other side, ${det (𝐴 + 𝑡 𝐼_{𝑛})}^{𝑛 - 2}$ has degree at most $𝑛 (𝑛 - 2)$ , so the entries of ${det (𝐴 + 𝑡 𝐼_{𝑛})}^{𝑛 - 2} (𝐴 + 𝑡 𝐼_{𝑛})$ have degree at most $𝑛 (𝑛 - 2) +$ $1 =$ ${(𝑛 - 1)}^{2}$ . The difference has degree at most ${(𝑛 - 1)}^{2}$ , and it vanishes at every $𝑡$ for which $𝐴 + 𝑡 𝐼_{𝑛}$ is invertible, of which there are at least $| 𝐹 | - 𝑛$ (Proposition 5.3.19). So the argument is correct when $| 𝐹 | - 𝑛 \geq {(𝑛 - 1)}^{2} + 1$ , that is, $| 𝐹 | \geq 𝑛^{2} - 𝑛 + 2$ , and in particular over every infinite field.

Exercise 5.6.11.standard

(a)Let $𝐴 \in ℝ^{𝑛 \times 𝑛}$ be invertible. Show that $det 𝐴 > 0$ if and only if $𝐴$ is a product of replacement matrices $𝐸_{𝑖 𝑐 𝑗}$ and scaling matrices $𝐸_{𝑖 𝑐}$ with $𝑐 > 0$ .
(b)Write the swap $𝐸_{12} \in ℝ^{2 \times 2}$ as a product of three replacements and one scaling, and explain why some factor must be a scaling by a negative number.

Solution.

Uses. Proposition 5.4.1 (Determinants of elementary matrices), Corollary 5.4.4 (Products of elementary matrices), Exercise 5.4.48, Proposition 5.1.10 (Alternating implies antisymmetric)

Techniques. Reduce to elementary matrices (Technique 5.4.6)

Hint 1. One direction is multiplicativity. For the other, Exercise 5.4.48 writes every invertible matrix as replacements times one scaling.

Hint 2. For (b), the second proof of Proposition 5.1.10 performs a swap with three column replacements and one sign change.

Sketch. (a) Replacements have determinant

1

and

𝐸_{𝑖 𝑐}

has determinant

𝑐 > 0

, so such a product has positive determinant. Conversely,

𝐴 =

𝐸_{1} \dots 𝐸_{𝑡} 𝐸_{𝑛, det 𝐴}

with replacements

𝐸_{𝑘}

, and

𝐸_{𝑛, det 𝐴}

is a positive scaling when

det 𝐴 > 0

. (b)

𝐸_{12} =

𝐸_{1, 1, 2} 𝐸_{2, - 1, 1} 𝐸_{1, 1, 2} 𝐸_{2, - 1}

; a product of replacements and positive scalings has positive determinant, while

det 𝐸_{12} = - 1

(a) ( $\Leftarrow$ ) By Proposition 5.4.1, a replacement has determinant $1$ and $𝐸_{𝑖 𝑐}$ has determinant $𝑐$ . So by Corollary 5.4.4, a product of replacements and scalings $𝐸_{𝑖 𝑐}$ with $𝑐 > 0$ has determinant equal to the product of the scaling factors, which is positive.

( $\Rightarrow$ ) By Exercise 5.4.48 (b), $𝐴 =$ $𝐸_{1} \dots 𝐸_{𝑡} 𝐸_{𝑛, det 𝐴}$ , where $𝐸_{1}, \dots, 𝐸_{𝑡}$ are replacements. If $det 𝐴 > 0$ , the last factor is a scaling by a positive number. (If $𝑛 = 1$ , then $𝐴 =$ $(det 𝐴) =$ $𝐸_{1, det 𝐴}$ directly.)

(b) In the second proof of Proposition 5.1.10, the columns $(𝐱, 𝐲)$ become $(𝐱 + 𝐲, 𝐲)$ , then $(𝐱 + 𝐲, - 𝐱)$ , then $(𝐲, - 𝐱)$ , and finally $(𝐲, 𝐱)$ after scaling the second column by $- 1$ . Starting from $𝐼_{2}$ and recording each column operation as a multiplication on the right (Proposition 3.2.28), this reads

\begin{aligned} 𝐸_{12} & = 𝐸_{1, 1, 2} 𝐸_{2, - 1, 1} 𝐸_{1, 1, 2} 𝐸_{2, - 1} \\ = (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}) (\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix}) (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}) (\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix}), \end{aligned}

and multiplying out gives $(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ . A negative scaling is unavoidable: by (a), a product of replacements and positive scalings has positive determinant, while $det 𝐸_{12} = - 1$ . Over $ℝ$ , the sign of the determinant splits the invertible matrices into two classes, and the factors allowed in (a) never leave the class with positive determinant; Section 8.4 returns to this for rotations and reflections.

Exercise 5.6.12.standard Prove each statement, choosing a suitable certificate of invertibility.

(a)The matrix $𝐴 \in ℚ^{4 \times 4}$ with entries $𝑎_{𝑖 𝑗} = 𝑖^{𝑗}$ is invertible.
(b)For $𝑥 \in ℝ$ , let $𝑀 (𝑥) =$ $(\begin{matrix} 𝑥 & 1 & 0 \\ 1 & 𝑥 & 1 \\ 0 & 1 & 𝑥 + 1 \end{matrix})$ . Then $𝑀 (𝑥)$ is invertible for every integer $𝑥$ , but not for every real $𝑥$ .
(c)For every $𝐴 \in ℝ^{𝑚 \times 𝑛}$ , the matrix $𝐼_{𝑛} + 𝐴^{𝖳} 𝐴$ is invertible. (For $𝐯 \in ℝ^{𝑛}$ , $𝐯^{𝖳} 𝐯 =$ $𝑣_{1}^{2} +$ $\dots +$ $𝑣_{𝑛}^{2}$ .)
(d)For every $𝐴 \in ℚ^{𝑛 \times 𝑛}$ , the matrix $𝐴 + 𝑡 𝐼_{𝑛}$ is invertible for some integer $𝑡$ with $0 \leq 𝑡 \leq 𝑛$ .

Solution.

Uses. Theorem 5.5.21 (The Vandermonde determinant), Exercise 5.5.26, Corollary 5.4.15 (Rows), Theorem 5.4.7 (Invertibility and the determinant), Corollary 5.4.8 (Vanishing determinants), Proposition 2.4.23 (Transpose of a product), Proposition 5.3.19 ( $det (𝐴 + 𝑡 𝐼_{𝑛})$ as a function of $𝑡$ ), Lemma 3.4.23 (Too many roots)

Techniques. Reduce modulo $𝑝$ (Technique 5.3.21), $det$ is a polynomial in the entries (Technique 5.3.18)

Hint 1. (a) Factor

𝑖

out of row

𝑖

. (b) Compute

det 𝑀 (𝑥)

as a polynomial in

𝑥

and look at its parity. (c) Do not compute a determinant: look at the kernel. (d) How many roots can

det (𝐴 + 𝑡 𝐼_{𝑛})

have?

Hint 2. (b) The polynomial is

𝑥^{3} + 𝑥^{2} - 2 𝑥 - 1

, and

𝑥^{3} + 𝑥^{2} = 𝑥^{2} (𝑥 + 1)

is even for integers. For real

𝑥

, compare the values at

1

and

2

. (c) If

(𝐼_{𝑛} + 𝐴^{𝖳} 𝐴) 𝐯 =

𝟎

, multiply on the left by

𝐯^{𝖳}

Sketch. (a) Row

𝑖

𝑖 (1, 𝑖, 𝑖^{2}, 𝑖^{3})

, so

det 𝐴 =

4! det 𝑉 (1, 2, 3, 4) =

24 \cdot

12 =

288

. (b)

det 𝑀 (𝑥) =

𝑥^{3} +

𝑥^{2} -

2 𝑥 -

1

is odd at every integer, but changes sign between

1

and

2

. (c)

𝐯^{𝖳} (𝐼_{𝑛} + 𝐴^{𝖳} 𝐴) 𝐯 =

𝐯^{𝖳} 𝐯 +

{(𝐴 𝐯)}^{𝖳} (𝐴 𝐯)

is a sum of squares, zero only for

𝐯 = 𝟎

. (d)

det (𝐴 + 𝑡 𝐼_{𝑛})

is a nonzero polynomial of degree

𝑛

, so it cannot vanish at all of

0, 1, \dots, 𝑛

(a) Row $𝑖$ of $𝐴$ is $(𝑖, 𝑖^{2}, 𝑖^{3}, 𝑖^{4}) =$ $𝑖 (1, 𝑖, 𝑖^{2}, 𝑖^{3})$ , which is $𝑖$ times row $𝑖$ of the Vandermonde matrix $𝑉 (1, 2, 3, 4)$ . Pulling the factor $𝑖$ out of each row (Corollary 5.4.15) and using Exercise 5.5.26 (a),

\begin{aligned} det 𝐴 & = 1 \cdot 2 \cdot 3 \cdot 4 \cdot det 𝑉 (1, 2, 3, 4) \\ = 24 \cdot (1! \cdot 2! \cdot 3!) = 288 \neq 0 . \end{aligned}

So $𝐴$ is invertible by Theorem 5.4.7. Recognizing the form made the computation unnecessary; even $det 𝑉 \neq 0$ follows at once from Theorem 5.5.21, since the nodes are distinct.

(b) Expanding along the first row,

\begin{aligned} det 𝑀 (𝑥) & = 𝑥 (𝑥 (𝑥 + 1) - 1) - 1 \cdot ((𝑥 + 1) - 0) \\ = 𝑥^{3} + 𝑥^{2} - 2 𝑥 - 1 . \end{aligned}

If $𝑥$ is an integer, $𝑥^{3} + 𝑥^{2} = 𝑥^{2} (𝑥 + 1)$ is a product with an even factor, and $2 𝑥$ is even, so $det 𝑀 (𝑥)$ is odd, in particular nonzero, and $𝑀 (𝑥)$ is invertible. (This is Technique 5.3.21 applied to a family: modulo $2$ the determinant is $1$ for every integer $𝑥$ .) On the other hand $det 𝑀 (1) =$ $- 1 <$ $0 <$ $7 =$ $det 𝑀 (2)$ , and a polynomial function is continuous, so by the intermediate value theorem $det 𝑀 (𝑥_{0}) = 0$ for some real $𝑥_{0} \in (1, 2)$ , and $𝑀 (𝑥_{0})$ is not invertible.

(c) Let $𝐶 = 𝐼_{𝑛} + 𝐴^{𝖳} 𝐴$ , and suppose $𝐶 𝐯 = 𝟎$ . By Proposition 2.4.23, $𝐯^{𝖳} 𝐴^{𝖳} 𝐴 𝐯 =$ ${(𝐴 𝐯)}^{𝖳} (𝐴 𝐯)$ , so

\begin{aligned} 0 = 𝐯^{𝖳} 𝐶 𝐯 & = 𝐯^{𝖳} 𝐯 + {(𝐴 𝐯)}^{𝖳} (𝐴 𝐯) \\ = \sum_{𝑖 = 1}^{𝑛} 𝑣_{𝑖}^{2} + \sum_{𝑘 = 1}^{𝑚} {(𝐴 𝐯)}_{𝑘}^{2} . \end{aligned}

A sum of squares of real numbers is $0$ only if every term is $0$ , so $𝐯 = 𝟎$ . By Corollary 5.4.8, $𝐶$ is invertible. A determinant would be hopeless here: $det 𝐶$ is a polynomial of degree up to $2 𝑛$ in the entries of $𝐴$ , with no evident sign.

(d) By Proposition 5.3.19, $det (𝐴 + 𝑡 𝐼_{𝑛}) =$ $𝑝 (𝑡)$ for the polynomial $𝑝 =$ $𝑥^{𝑛} +$ $𝑐_{𝑛 - 1} 𝑥^{𝑛 - 1} +$ $\dots +$ $𝑐_{0} \in$ $ℚ [𝑥]$ . Since its coefficient of $𝑥^{𝑛}$ is $1$ , $𝑝$ is not zero, so by Lemma 3.4.23 it does not vanish at all $𝑛 + 1$ points $0, 1, \dots, 𝑛$ . For a point $𝑡$ where it does not vanish, $𝐴 + 𝑡 𝐼_{𝑛}$ is invertible by Theorem 5.4.7.

Exercise 5.6.13.hard Call $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ alternating if $𝑎_{𝑖 𝑖} = 0$ and $𝑎_{𝑗 𝑖} = - 𝑎_{𝑖 𝑗}$ for all $𝑖, 𝑗$ . (When $1 + 1 \neq 0$ this means skew-symmetric; over $𝔽_{2}$ it means symmetric with zero diagonal.) Let $𝑛$ be odd and $𝐴$ alternating, and write $𝑡_{𝜎} (𝐴) =$ $sgn (𝜎) 𝑎_{𝜎 (1) 1} \dots 𝑎_{𝜎 (𝑛) 𝑛}$ for the terms of the Leibniz formula.

(a)Show that $𝑡_{𝜎^{- 1}} (𝐴) =$ $- 𝑡_{𝜎} (𝐴)$ for every $𝜎 \in 𝑆_{𝑛}$ .
(b)Show that if $𝜎^{2} = id$ , then $𝜎$ has a fixed point, and $𝑡_{𝜎} (𝐴) = 0$ .
(c)Deduce that $det 𝐴 = 0$ , over every field.
(d)Exercise 5.4.33 proved (c) when $1 + 1 \neq 0$ by showing $det 𝐴 = - det 𝐴$ . Explain why that argument fails over $𝔽_{2}$ , why this one does not, and where the hypothesis $𝑎_{𝑖 𝑖} = 0$ is used.

Solution.

Uses. Theorem 5.3.3 (The Leibniz formula), Proposition 5.2.25 (Multiplicativity of the sign), Proposition 5.2.16 (Cycle decomposition), Proposition 5.2.8 (Reindexing sums over $𝑆_{𝑛}$ )

Techniques. Cancel terms in pairs (Technique 5.3.5), Read structure off the Leibniz expansion (Technique 5.3.12)

Hint 1. In

𝑡_{𝜎^{- 1}} (𝐴)

, reindex the product by

𝑗 = 𝜎 (𝑖)

, and then use

𝑎_{𝑖 𝜎 (𝑖)} =

- 𝑎_{𝜎 (𝑖) 𝑖}

Hint 2. If

𝜎^{2} = id

, every orbit of

𝜎

has one or two elements. Since

𝑛

is odd, they cannot all have two.

Hint 3. Pair

𝜎

with

𝜎^{- 1}

. The permutations equal to their own inverse are left over, and (b) disposes of them.

Sketch. (a)

\prod_{𝑗} 𝑎_{𝜎^{- 1} (𝑗) 𝑗} =

\prod_{𝑖} 𝑎_{𝑖 𝜎 (𝑖)} =

{(- 1)}^{𝑛} \prod_{𝑖} 𝑎_{𝜎 (𝑖) 𝑖}

and

sgn (𝜎^{- 1}) = sgn (𝜎)

. (b) Orbits of an involution have size

1

2

and partition a set of odd size, so some

𝑗

is fixed, and

𝑎_{𝑗 𝑗} = 0

is a factor. (c)

𝜎 \mapsto 𝜎^{- 1}

is an involution of

𝑆_{𝑛}

whose fixed points are the

𝜎

with

𝜎^{2} = id

; pairs cancel by (a), and fixed points contribute

0

by (b). (d)

det 𝐴 = - det 𝐴

only gives

(1 + 1) det 𝐴 = 0

; pairing never divides.

(a) By definition, $𝑡_{𝜎^{- 1}} (𝐴) =$ $sgn (𝜎^{- 1}) \prod_{𝑗 = 1}^{𝑛} 𝑎_{𝜎^{- 1} (𝑗) 𝑗}$ . As $𝑖$ runs over $[𝑛]$ , so does $𝑗 = 𝜎 (𝑖)$ , so the product can be indexed by $𝑖$ instead:

\begin{aligned} \prod_{𝑗 = 1}^{𝑛} 𝑎_{𝜎^{- 1} (𝑗) 𝑗} & = \prod_{𝑖 = 1}^{𝑛} 𝑎_{𝑖 𝜎 (𝑖)} \\ = \prod_{𝑖 = 1}^{𝑛} (- 𝑎_{𝜎 (𝑖) 𝑖}) = {(- 1)}^{𝑛} \prod_{𝑖 = 1}^{𝑛} 𝑎_{𝜎 (𝑖) 𝑖} . \end{aligned}

Since $sgn (𝜎^{- 1}) = sgn (𝜎)$ (Proposition 5.2.25) and $𝑛$ is odd, $𝑡_{𝜎^{- 1}} (𝐴) =$ $- 𝑡_{𝜎} (𝐴)$ .

(b) Suppose $𝜎^{2} = id$ , and let $𝑖 \in [𝑛]$ . The least $𝑘 \geq 1$ with $𝜎^{𝑘} (𝑖) = 𝑖$ is $1$ or $2$ , so by Proposition 5.2.16 the orbit of $𝑖$ has one or two elements, and the orbits partition $[𝑛]$ . If every orbit had two elements, $𝑛$ would be even. So some orbit is ${𝑗}$ , that is, $𝜎 (𝑗) = 𝑗$ , and $𝑡_{𝜎} (𝐴)$ contains the factor $𝑎_{𝜎 (𝑗) 𝑗} =$ $𝑎_{𝑗 𝑗} =$ $0$ .

(c) The map $𝜑 (𝜎) = 𝜎^{- 1}$ is a bijection of $𝑆_{𝑛}$ with $𝜑 (𝜑 (𝜎)) = 𝜎$ , and its fixed points are the $𝜎$ with $𝜎 = 𝜎^{- 1}$ , that is, $𝜎^{2} = id$ . Let $𝑄$ be the set of fixed points, and let $𝑃$ contain exactly one element of each pair ${𝜎, 𝜎^{- 1}}$ with $𝜎 \neq 𝜎^{- 1}$ . Every permutation lies in exactly one of $𝑄$ , $𝑃$ , and $𝜑 (𝑃)$ , so by Theorem 5.3.3, (a), and (b),

\begin{aligned} det 𝐴 & = \sum_{𝜎 \in 𝑃} (𝑡_{𝜎} (𝐴) + 𝑡_{𝜎^{- 1}} (𝐴)) + \sum_{𝜎 \in 𝑄} 𝑡_{𝜎} (𝐴) \\ = 0 + 0 = 0 . \end{aligned}

This is Technique 5.3.5 in its version with fixed points.

(d) The earlier argument shows $det 𝐴 =$ $det 𝐴^{𝖳} =$ $det (- 𝐴) =$ ${(- 1)}^{𝑛} det 𝐴 =$ $- det 𝐴$ , that is, $(1 + 1) det 𝐴 = 0$ , and concludes by dividing by $1 + 1$ . Over $𝔽_{2}$ this equation reads $0 = 0$ . The pairing argument never divides: over $𝔽_{2}$ , (a) says that $𝑡_{𝜎^{- 1}} (𝐴) =$ $𝑡_{𝜎} (𝐴)$ , and the two terms of each pair cancel because $𝑥 + 𝑥 = 0$ there. The hypothesis $𝑎_{𝑖 𝑖} = 0$ enters only in (b). When $1 + 1 \neq 0$ it follows from $𝑎_{𝑖 𝑖} = - 𝑎_{𝑖 𝑖}$ , but over $𝔽_{2}$ it is a genuine assumption: $𝐼_{3}$ satisfies $𝑎_{𝑗 𝑖} = - 𝑎_{𝑖 𝑗}$ over $𝔽_{2}$ and has determinant $1$ (Exercise 5.4.33 (c)).

Exercise 5.6.14.standard Let $𝑛 \geq 1$ , and let $𝜋 \in 𝑆_{2 𝑛}$ have $𝜋 (2 𝑖 - 1) = 𝑖$ and $𝜋 (2 𝑖) = 𝑛 + 𝑖$ for $𝑖 = 1, \dots, 𝑛$ . Its bottom row is $1,$ $𝑛 +$ $1,$ $2,$ $𝑛 +$ $2,$ $\dots,$ $𝑛,$ $2 𝑛$ , so the columns of $𝑀 𝐸_{𝜋}$ interleave the first $𝑛$ columns of $𝑀$ with the last $𝑛$ (Proposition 5.2.30).

(a)Show that $inv (𝜋) =$ $𝑛 (𝑛 - 1) / 2$ .
(b)Write $𝜋$ in cycle notation for $𝑛 = 3$ and $𝑛 = 4$ , and check (a) against Proposition 5.2.26.
(c)Let $𝐴,$ $𝐵,$ $𝐶,$ $𝐷 \in$ $𝐹^{𝑛 \times 𝑛}$ be diagonal, with diagonal entries $𝑎_{𝑖}$ , $𝑏_{𝑖}$ , $𝑐_{𝑖}$ , $𝑑_{𝑖}$ . Show that
$det (\begin{matrix} 𝐴 & 𝐵 \\ 𝐶 & 𝐷 \end{matrix}) = \prod_{𝑖 = 1}^{𝑛} (𝑎_{𝑖} 𝑑_{𝑖} - 𝑏_{𝑖} 𝑐_{𝑖}) .$
Does the sign of $𝜋$ enter?

Solution.

Uses. Definition 5.2.21 (Inversion), Corollary 5.2.24 (Formulas for the sign), Proposition 5.2.26 (Sign of a cycle), Proposition 5.2.30 (Algebra of permutation matrices), Exercise 5.2.36, Corollary 5.4.27 (Several diagonal blocks), Theorem 5.4.10 (Multiplicativity), Theorem 5.4.14 (The transpose), Theorem 5.2.31 (Alternating functions and permutations)

Techniques. Block decomposition (Technique 2.4.35)

Hint 1. Sort the pairs of positions

𝑝 < 𝑞

by the parities of

𝑝

and

𝑞

. Only one kind of pair can be inverted.

Hint 2. For (c), rearrange the rows and the columns of

𝑀

𝜋

: consider

𝐸_{𝜋}^{𝖳} 𝑀 𝐸_{𝜋}

, whose

(𝑝, 𝑞)

entry is

𝑚_{𝜋 (𝑝) 𝜋 (𝑞)}

Sketch. (a) The odd positions carry

1, \dots, 𝑛

in order and the even positions

𝑛 + 1, \dots, 2 𝑛

in order. A pair (position

2 𝑖

, position

2 𝑗 - 1

) with

𝑗 > 𝑖

is inverted, since

𝑛 + 𝑖 > 𝑗

, and no other pair is; there are

\sum_{𝑖} (𝑛 - 𝑖) =

𝑛 (𝑛 - 1) / 2

of them. (b)

𝑛 = 3

(2 4 5 3)

, sign

- 1

;

𝑛 = 4

(2 5 3) (4 6 7)

, sign

1

. (c)

𝐸_{𝜋}^{𝖳} 𝑀 𝐸_{𝜋}

is block diagonal with blocks

(\begin{matrix} 𝑎_{𝑖} & 𝑏_{𝑖} \\ 𝑐_{𝑖} & 𝑑_{𝑖} \end{matrix})

, and

det (𝐸_{𝜋}^{𝖳} 𝑀 𝐸_{𝜋}) =

{sgn (𝜋)}^{2} det 𝑀 =

det 𝑀

(a) The entry in position $2 𝑖 - 1$ is $𝑖$ , and the entry in position $2 𝑖$ is $𝑛 + 𝑖$ . Consider positions $𝑝 < 𝑞$ . If both are odd, or both even, their entries are in increasing order. If $𝑝 = 2 𝑖 - 1$ and $𝑞 = 2 𝑗$ , then $𝑖 \leq 𝑗 < 𝑛 + 𝑗$ , so the pair is in order. If $𝑝 = 2 𝑖$ and $𝑞 = 2 𝑗 - 1$ , then $𝑞 > 𝑝$ means $𝑗 > 𝑖$ , and the entries satisfy $𝑛 + 𝑖 > 𝑛 \geq 𝑗$ , so the pair is an inversion. For fixed $𝑖$ there are $𝑛 - 𝑖$ such $𝑗$ , so

inv (𝜋) = \sum_{𝑖 = 1}^{𝑛} (𝑛 - 𝑖) = 𝑛 \frac{𝑛 - 1}{2},

and $sgn (𝜋) =$ ${(- 1)}^{𝑛 (𝑛 - 1) / 2}$ by Corollary 5.2.24.

(b) For $𝑛 = 3$ the bottom row is $1, 4, 2, 5, 3, 6$ . Following $2 \mapsto 4 \mapsto 5 \mapsto 3 \mapsto 2$ , and noting that $1$ and $6$ are fixed, $𝜋 = (2 4 5 3)$ , a $4$ -cycle, with sign $- 1 = {(- 1)}^{3}$ . For $𝑛 = 4$ the bottom row is $1, 5, 2, 6, 3, 7, 4, 8$ , so $𝜋 = (2 5 3) (4 6 7)$ , with sign $1 = {(- 1)}^{6}$ . Both agree with (a) by Proposition 5.2.26. The cycle type changes irregularly with $𝑛$ , while the inversion count has a closed form, so inversions are the right tool for this permutation.

(c) Let $𝑀 = (\begin{matrix} 𝐴 & 𝐵 \\ 𝐶 & 𝐷 \end{matrix})$ and $𝑁 = 𝐸_{𝜋}^{𝖳} 𝑀 𝐸_{𝜋}$ . By Proposition 5.2.30 (a), column $𝑞$ of $𝑀 𝐸_{𝜋}$ is column $𝜋 (𝑞)$ of $𝑀$ . By Proposition 5.2.30 (c), $𝐸_{𝜋}^{𝖳} = 𝐸_{𝜋^{- 1}}$ , and by Exercise 5.2.36 (a), row $𝑝$ of $𝐸_{𝜋^{- 1}} 𝑋$ is row $𝜋 (𝑝)$ of $𝑋$ . So $𝑛_{𝑝 𝑞} =$ $𝑚_{𝜋 (𝑝) 𝜋 (𝑞)}$ .

For $𝑝, 𝑞 \in {2 𝑖 - 1, 2 𝑖}$ the indices $𝜋 (𝑝), 𝜋 (𝑞)$ lie in ${𝑖, 𝑛 + 𝑖}$ , and these four entries of $𝑁$ form the block $(\begin{matrix} 𝑚_{𝑖 𝑖} & 𝑚_{𝑖, 𝑛 + 𝑖} \\ 𝑚_{𝑛 + 𝑖, 𝑖} & 𝑚_{𝑛 + 𝑖, 𝑛 + 𝑖} \end{matrix}) =$ $(\begin{matrix} 𝑎_{𝑖} & 𝑏_{𝑖} \\ 𝑐_{𝑖} & 𝑑_{𝑖} \end{matrix})$ . If instead $𝑝 \in {2 𝑖 - 1, 2 𝑖}$ and $𝑞 \in {2 𝑗 - 1, 2 𝑗}$ with $𝑖 \neq 𝑗$ , then $𝑚_{𝜋 (𝑝) 𝜋 (𝑞)}$ is an off-diagonal entry of one of the diagonal matrices $𝐴, 𝐵, 𝐶, 𝐷$ , so it is $0$ . Hence $𝑁$ is block diagonal with the $2 \times 2$ blocks $(\begin{matrix} 𝑎_{𝑖} & 𝑏_{𝑖} \\ 𝑐_{𝑖} & 𝑑_{𝑖} \end{matrix})$ , and by Corollary 5.4.27,

det 𝑁 = \prod_{𝑖 = 1}^{𝑛} (𝑎_{𝑖} 𝑑_{𝑖} - 𝑏_{𝑖} 𝑐_{𝑖}) .

Finally, $det 𝑁 =$ $det 𝐸_{𝜋}^{𝖳} det 𝑀 det 𝐸_{𝜋} =$ ${sgn (𝜋)}^{2} det 𝑀 =$ $det 𝑀$ by Theorem 5.4.10, Theorem 5.4.14, and Theorem 5.2.31. So the sign does not enter: rearranging the rows and the columns in the same way costs ${sgn (𝜋)}^{2} = 1$ . Only rearranging the columns alone, as in $det (𝑀 𝐸_{𝜋}) =$ $sgn (𝜋) det 𝑀$ , costs a sign.

Exercise 5.6.15.routine Find the error in the following argument, and show that its conclusion fails for

𝐵 = (\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}), 𝑖 = 3, 𝑗 = 1 .

Claim. Let $𝑛 \geq 2$ and $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ . If every entry of row $𝑖$ of $𝐵$ other than $𝑏_{𝑖 𝑗}$ is $0$ , then $det 𝐵 =$ $𝜀 𝑏_{𝑖 𝑗} det 𝐵_{\hat{𝑖 𝑗}}$ , where $𝜀 = - 1$ if exactly one of $𝑖$ and $𝑗$ equals $1$ , and $𝜀 = 1$ otherwise.

Proof. Interchange rows $1$ and $𝑖$ (if $𝑖 \neq 1$ ), and then columns $1$ and $𝑗$ (if $𝑗 \neq 1$ ). Each interchange negates the determinant. The resulting matrix has $𝑏_{𝑖 𝑗}$ in position $(1, 1)$ and zeros in the rest of row $1$ , so it is block lower triangular, and by Theorem 5.4.26 its determinant is $𝑏_{𝑖 𝑗}$ times the determinant of its lower right block, which is $𝐵_{\hat{𝑖 𝑗}}$ .

Solution.

Uses. Lemma 5.5.2 (A row or column with one nonzero entry), Theorem 5.2.31 (Alternating functions and permutations), Theorem 5.4.26 (Block-triangular matrices)

Techniques. Try small cases and small fields (Technique 1.2.38)

Hint 1. Carry out the interchange of rows

1

and

3

for the given

𝐵

, and compare the lower right

2 \times 2

block with

𝐵_{\hat{31}}

Hint 2. After interchanging rows

1

and

𝑖

, in which position is the old row

1

? Deleting row

𝑖

from

𝐵

keeps the other rows in their original order.

Sketch. The lower right block is not

𝐵_{\hat{𝑖 𝑗}}

: after interchanging rows

1

and

𝑖

, the old row

1

sits in position

𝑖

, behind rows

2, \dots, 𝑖 - 1

. For the given

𝐵

, the claim predicts

det 𝐵 =

- 1 \cdot

det 𝐼_{2} =

- 1

, but

𝐵

is the permutation matrix of the

3

-cycle

(1 3 2)

, so

det 𝐵 = 1

, as

{(- 1)}^{3 + 1}

predicts. Moving row

𝑖

to the top by

𝑖 - 1

adjacent interchanges keeps the other rows in order and gives the correct sign

{(- 1)}^{𝑖 + 𝑗}

The error. The last step identifies the lower right block with $𝐵_{\hat{𝑖 𝑗}}$ . Interchanging rows $1$ and $𝑖$ moves the old row $1$ into position $𝑖$ , so after the first row is removed, the remaining rows appear in the order $2,$ $3,$ $\dots,$ $𝑖 -$ $1,$ $1,$ $𝑖 +$ $1,$ $\dots,$ $𝑛$ . The minor $𝐵_{\hat{𝑖 𝑗}}$ has them in the order $1,$ $2,$ $\dots,$ $𝑖 -$ $1,$ $𝑖 +$ $1,$ $\dots,$ $𝑛$ . The two agree only when $𝑖 \leq 2$ , and the same problem occurs with the columns when $𝑗 \geq 3$ .

The counterexample. For the given $𝐵$ , row $3$ is $(1, 0, 0)$ , so $𝑏_{31} = 1$ is the only nonzero entry, and $𝐵_{\hat{31}}$ , obtained by deleting row $3$ and column $1$ , is $𝐼_{2}$ . The claim, with $𝜀 = - 1$ , predicts $det 𝐵 = - 1$ . But the columns of $𝐵$ are $𝐞_{3}, 𝐞_{1}, 𝐞_{2}$ , so $𝐵 = 𝐸_{𝜎}$ for the $3$ -cycle $𝜎 = (1 3 2)$ , which is even, and $det 𝐵 = 1$ (Theorem 5.2.31). In the argument, interchanging rows $1$ and $3$ gives $(\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix})$ , whose lower right block $(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ is $𝐵_{\hat{31}}$ with its rows interchanged.

The repair. Move row $𝑖$ to the top by $𝑖 - 1$ interchanges of adjacent rows, which keeps the other rows in order, and likewise for column $𝑗$ . This gives the sign ${(- 1)}^{(𝑖 - 1) + (𝑗 - 1)} =$ ${(- 1)}^{𝑖 + 𝑗}$ of Lemma 5.5.2, which for this $𝐵$ is ${(- 1)}^{4} = 1$ .