5.5 Cofactor expansion · Matrix Theory

Expanding the Leibniz formula takes $𝑛!$ products, and elimination computes a determinant in about $𝑛^{3} / 3$ operations (Remark 5.4.25). This section gives a third description of $det$ , which is recursive: a cofactor expansion writes an $𝑛 \times 𝑛$ determinant as a combination of $𝑛$ determinants of size $𝑛 - 1$ , one for each entry of a chosen row or column. For a general matrix this still takes on the order of $𝑛!$ operations. Its strength lies elsewhere. It is quick for matrices with many zeros, and it sets up induction on the size of a matrix, which computes the determinants of whole families of matrices at once: tridiagonal matrices, companion matrices, and the Vandermonde matrices of Section 3.4. It also has a theoretical payoff. The coefficients in the expansions, the cofactors, assemble into a matrix that inverts $𝐵$ up to the scalar factor $det 𝐵$ . This gives explicit formulas for $𝐵^{- 1}$ and for the solution of $𝐵 𝐱 = 𝐲$ (Cramer’s rule).

5.5.1Expansion along a row or a column

We start where Intuition (What the proof did, and where it leads) and Lemma 5.3.2 started, with multilinearity, but this time we expand only one row. Row $𝑖$ of $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ is $\sum_{𝑗} 𝑏_{𝑖 𝑗} 𝐞_{𝑗}^{𝖳}$ , so by linearity of $det$ in row $𝑖$ (Corollary 5.4.15),

det 𝐵 = \sum_{𝑗 = 1}^{𝑛} 𝑏_{𝑖 𝑗} det 𝐵^{(𝑗)},

where $𝐵^{(𝑗)}$ is $𝐵$ with row $𝑖$ replaced by $𝐞_{𝑗}^{𝖳}$ . Each $𝐵^{(𝑗)}$ has a row with a single nonzero entry. The lecture computes the determinant of such a matrix by comparing it with a matrix of size one less. We first name that smaller matrix.

Notation 5.5.1 (Minors). Let

𝑛 \geq 2

𝐵 \in 𝐹^{𝑛 \times 𝑛}

, and

𝑖, 𝑗 \in [𝑛]

. We write

𝐵_{\hat{𝑖 𝑗}} \in

𝐹^{(𝑛 - 1) \times (𝑛 - 1)}

for the matrix obtained from

𝐵

by deleting row

𝑖

and column

𝑗

. Its determinant

det 𝐵_{\hat{𝑖 𝑗}}

is the $(𝑖, 𝑗)$ minor of

𝐵

. The hat marks the row and the column that are left out.

For instance, if $𝐵 = (\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{matrix})$ , then $𝐵_{\hat{23}} = (\begin{matrix} 1 & 2 \\ 7 & 8 \end{matrix})$ , with minor $8 - 14 = - 6$ , and $𝐵_{\hat{11}} = (\begin{matrix} 5 & 6 \\ 8 & 10 \end{matrix})$ , with minor $50 - 48 = 2$ . Two facts are used again and again. First, $𝐵_{\hat{𝑖 𝑗}}$ involves no entry of row $𝑖$ and no entry of column $𝑗$ , so changing $𝐵$ in row $𝑖$ or in column $𝑗$ does not change $𝐵_{\hat{𝑖 𝑗}}$ . Second, deleting row $𝑗$ and column $𝑖$ of $𝐵^{𝖳}$ gives the transpose of $𝐵_{\hat{𝑖 𝑗}}$ , that is, ${(𝐵^{𝖳})}_{\hat{𝑗 𝑖}} =$ ${(𝐵_{\hat{𝑖 𝑗}})}^{𝖳}$ .

Figure 5.5.1. Top: deleting row

2

and column

3

of a

4 \times 4

matrix

𝐵

(the entries in grey) leaves the

3 \times 3

matrix

𝐵_{\hat{23}}

. The remaining rows and columns keep their order. Bottom: the signs

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

that accompany the minors in Theorem 5.5.3 form a checkerboard, with

+

on the diagonal.

Intuition (Moving an entry into the corner). The lecture’s starting point is the case $𝐵 = (\begin{matrix} 1 & 0 \\ 0 & 𝐴 \end{matrix})$ , in block form, where $det 𝐵 = det 𝐴$ . More generally, if the first row of $𝐵$ is $(𝑏_{11}, 0, \dots, 0)$ , then $𝐵$ is block lower triangular with diagonal blocks $(𝑏_{11})$ and $𝐵_{\hat{11}}$ , and Theorem 5.4.26 gives $det 𝐵 =$ $𝑏_{11} det 𝐵_{\hat{11}}$ . The entries below $𝑏_{11}$ play no role.

If the single nonzero entry of row $𝑖$ sits in column $𝑗$ , we move it into the corner. This must be done so that the rest of the matrix becomes exactly $𝐵_{\hat{𝑖 𝑗}}$ . Swapping rows $1$ and $𝑖$ directly does not achieve this: old row $1$ would land in position $𝑖$ , out of order. Instead, move row $𝑖$ up one step at a time, swapping it with the row just above it. After $𝑖 - 1$ swaps it is on top, and the other rows are still in their original order. Do the same with column $𝑗$ . Each swap changes the sign, so the price is ${(- 1)}^{(𝑖 - 1) + (𝑗 - 1)} =$ ${(- 1)}^{𝑖 + 𝑗}$ .

Lemma 5.5.2 (A row or column with one nonzero entry). Let $𝑛 \geq 2$ , $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ , and $𝑖, 𝑗 \in [𝑛]$ . If every entry of row $𝑖$ of $𝐵$ other than $𝑏_{𝑖 𝑗}$ is $0$ , then

det 𝐵 = {(- 1)}^{𝑖 + 𝑗} 𝑏_{𝑖 𝑗} det 𝐵_{\hat{𝑖 𝑗}} .

The same holds if every entry of column $𝑗$ other than $𝑏_{𝑖 𝑗}$ is $0$ .

Proof.standard

Uses. Corollary 5.4.15 (Rows), Proposition 5.1.10 (Alternating implies antisymmetric), Theorem 5.4.26 (Block-triangular matrices), Theorem 5.4.14 (The transpose)

Hint 1. Settle the case

𝑖 = 𝑗 = 1

first. Which block structure does

𝐵

have then?

Hint 2. For general

𝑖

and

𝑗

, move row

𝑖

to the top and column

𝑗

to the front so that the remaining rows and columns stay in their original order. How many swaps does this take?

Hint 3. Use only swaps of adjacent rows (and adjacent columns). For the column statement, transpose.

Sketch. Swap row

𝑖

successively with rows

𝑖 - 1, \dots, 1

, and then column

𝑗

with columns

𝑗 - 1, \dots, 1

. The result

𝐵^{'}

has first row

(𝑏_{𝑖 𝑗}, 0, \dots, 0)

and lower right block

𝐵_{\hat{𝑖 𝑗}}

, because the other rows and columns keep their order. So

𝐵^{'}

is block lower triangular and

det 𝐵^{'} =

𝑏_{𝑖 𝑗} det 𝐵_{\hat{𝑖 𝑗}}

, while

det 𝐵^{'} =

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

. For a column with one nonzero entry, apply the row case to

𝐵^{𝖳}

Suppose first that row $𝑖$ has the given form. Let $𝐵^{″}$ be the matrix obtained from $𝐵$ by swapping row $𝑖$ with row $𝑖 - 1$ , then with row $𝑖 - 2$ , and so on, up to row $1$ . These are $𝑖 - 1$ swaps, and each multiplies the determinant by $- 1$ (Corollary 5.4.15), so $det 𝐵^{″} =$ ${(- 1)}^{𝑖 - 1} det 𝐵$ . The rows of $𝐵^{″}$ are row $𝑖$ of $𝐵$ , followed by rows $1,$ $\dots,$ $𝑖 -$ $1,$ $𝑖 +$ $1,$ $\dots,$ $𝑛$ of $𝐵$ in this order. Next, let $𝐵^{'}$ be obtained from $𝐵^{″}$ by swapping column $𝑗$ with column $𝑗 - 1$ , then with column $𝑗 - 2$ , and so on, up to column $1$ . By Proposition 5.1.10, $det 𝐵^{'} =$ ${(- 1)}^{𝑗 - 1} det 𝐵^{″}$ . The columns of $𝐵^{'}$ are column $𝑗$ of $𝐵^{″}$ , followed by its other columns in their original order.

So the first row of $𝐵^{'}$ is row $𝑖$ of $𝐵$ rearranged, namely $(𝑏_{𝑖 𝑗}, 0, \dots, 0)$ , and deleting the first row and the first column of $𝐵^{'}$ leaves the rows of $𝐵$ other than row $𝑖$ , in their original order, restricted to the columns other than column $𝑗$ , in their original order. That is exactly $𝐵_{\hat{𝑖 𝑗}}$ . Hence, in block form,

𝐵^{'} = (\begin{matrix} 𝑏_{𝑖 𝑗} & 0 \\ 𝐰 & 𝐵_{\hat{𝑖 𝑗}} \end{matrix})

for some $𝐰 \in 𝐹^{𝑛 - 1}$ , which is block lower triangular. By Theorem 5.4.26, $det 𝐵^{'} =$ $𝑏_{𝑖 𝑗} det 𝐵_{\hat{𝑖 𝑗}}$ . Combining,

det 𝐵 = {(- 1)}^{𝑖 - 1} {(- 1)}^{𝑗 - 1} det 𝐵^{'} = {(- 1)}^{𝑖 + 𝑗} 𝑏_{𝑖 𝑗} det 𝐵_{\hat{𝑖 𝑗}},

since ${(- 1)}^{𝑖 + 𝑗 - 2} =$ ${(- 1)}^{𝑖 + 𝑗}$ .

Now suppose instead that every entry of column $𝑗$ other than $𝑏_{𝑖 𝑗}$ is $0$ . Then row $𝑗$ of $𝐵^{𝖳}$ has the single nonzero entry $𝑏_{𝑖 𝑗}$ , in column $𝑖$ . By the case already proved, Theorem 5.4.14, and ${(𝐵^{𝖳})}_{\hat{𝑗 𝑖}} =$ ${(𝐵_{\hat{𝑖 𝑗}})}^{𝖳}$ ,

det 𝐵 = det 𝐵^{𝖳} = {(- 1)}^{𝑗 + 𝑖} 𝑏_{𝑖 𝑗} det {(𝐵_{\hat{𝑖 𝑗}})}^{𝖳} = {(- 1)}^{𝑖 + 𝑗} 𝑏_{𝑖 𝑗} det 𝐵_{\hat{𝑖 𝑗}} .

□

The lecture states the case $𝑖 = 1$ and proves the case $𝑗 = 1$ (with $𝑏_{11} = 1$ ) by observing that Gauss–Jordan elimination on $(\begin{matrix} 1 & 0 \\ 0 & 𝐴 \end{matrix})$ performs the same steps as on $𝐴$ . We had Theorem 5.4.26 available, which already contains that case.

The sign ${(- 1)}^{𝑖 + 𝑗}$ depends only on the position, and it alternates like the colors of a checkerboard (Figure 5.5.1). Now we expand.

Theorem 5.5.3 (Cofactor expansion). Let $𝑛 \geq 2$ and $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ . For every $𝑖 \in [𝑛]$ ,

det 𝐵 = \sum_{𝑗 = 1}^{𝑛} {(- 1)}^{𝑖 + 𝑗} 𝑏_{𝑖 𝑗} det 𝐵_{\hat{𝑖 𝑗}}

(5.5.1)

(expansion along row $𝑖$ ), and for every $𝑗 \in [𝑛]$ ,

det 𝐵 = \sum_{𝑖 = 1}^{𝑛} {(- 1)}^{𝑖 + 𝑗} 𝑏_{𝑖 𝑗} det 𝐵_{\hat{𝑖 𝑗}}

(5.5.2)

(expansion along column $𝑗$ ).

Proof (by linearity in one row).routine

Uses. Corollary 5.4.15 (Rows), Lemma 5.5.2 (A row or column with one nonzero entry), Theorem 5.4.14 (The transpose)

Techniques. Expand by multilinearity (Technique 5.1.7), Transpose to trade rows for columns (Technique 3.2.27)

Hint 1. Write row

𝑖

as a linear combination of

𝐞_{1}^{𝖳}, \dots, 𝐞_{𝑛}^{𝖳}

, and use that

det

is linear in row

𝑖

Hint 2. Each resulting matrix has a row with a single nonzero entry. Apply Lemma 5.5.2, and check that the minor is the same as for

𝐵

Hint 3. For columns, expand

𝐵^{𝖳}

along row

𝑗

Sketch. Row

𝑖

𝐵

\sum_{𝑗} 𝑏_{𝑖 𝑗} 𝐞_{𝑗}^{𝖳}

. By linearity in row

𝑖

det 𝐵 =

\sum_{𝑗} 𝑏_{𝑖 𝑗} det 𝐵^{(𝑗)}

, where

𝐵^{(𝑗)}

𝐵

with row

𝑖

replaced by

𝐞_{𝑗}^{𝖳}

. By Lemma 5.5.2,

det 𝐵^{(𝑗)} =

{(- 1)}^{𝑖 + 𝑗} det 𝐵_{\hat{𝑖 𝑗}}^{(𝑗)}

, and

𝐵_{\hat{𝑖 𝑗}}^{(𝑗)} =

𝐵_{\hat{𝑖 𝑗}}

since the two matrices differ only in row

𝑖

. The expansion of

𝐵

along column

𝑗

is the expansion of

𝐵^{𝖳}

along row

𝑗

Fix $𝑖$ . For $𝑗 \in [𝑛]$ , let $𝐵^{(𝑗)}$ be the matrix obtained from $𝐵$ by replacing row $𝑖$ with $𝐞_{𝑗}^{𝖳}$ . Since row $𝑖$ of $𝐵$ is $\sum_{𝑗} 𝑏_{𝑖 𝑗} 𝐞_{𝑗}^{𝖳}$ and $det$ is linear in row $𝑖$ (Corollary 5.4.15),

det 𝐵 = \sum_{𝑗 = 1}^{𝑛} 𝑏_{𝑖 𝑗} det 𝐵^{(𝑗)} .

The only nonzero entry of row $𝑖$ of $𝐵^{(𝑗)}$ is the $1$ in column $𝑗$ , so $det 𝐵^{(𝑗)} =$ ${(- 1)}^{𝑖 + 𝑗} det 𝐵_{\hat{𝑖 𝑗}}^{(𝑗)}$ by Lemma 5.5.2. The matrices $𝐵^{(𝑗)}$ and $𝐵$ differ only in row $𝑖$ , which is deleted, so $𝐵_{\hat{𝑖 𝑗}}^{(𝑗)} =$ $𝐵_{\hat{𝑖 𝑗}}$ . This proves (5.5.1).

For (5.5.2), fix $𝑗$ . Row $𝑗$ of $𝐵^{𝖳}$ has entries $𝑏_{1 𝑗}, \dots, 𝑏_{𝑛 𝑗}$ , and ${(𝐵^{𝖳})}_{\hat{𝑗 𝑖}} =$ ${(𝐵_{\hat{𝑖 𝑗}})}^{𝖳}$ . By Theorem 5.4.14 and (5.5.1) for $𝐵^{𝖳}$ ,

det 𝐵 = det 𝐵^{𝖳} = \sum_{𝑖 = 1}^{𝑛} {(- 1)}^{𝑗 + 𝑖} 𝑏_{𝑖 𝑗} det {(𝐵_{\hat{𝑖 𝑗}})}^{𝖳} = \sum_{𝑖 = 1}^{𝑛} {(- 1)}^{𝑖 + 𝑗} 𝑏_{𝑖 𝑗} det 𝐵_{\hat{𝑖 𝑗}} .

□

Proof (via the Leibniz formula).hard

Uses. Definition 5.3.6 (Determinant), Proposition 5.2.26 (Sign of a cycle), Proposition 5.2.25 (Multiplicativity of the sign), Theorem 5.2.31 (Alternating functions and permutations), Proposition 5.3.17 (Block-diagonal matrices), Theorem 5.4.14 (The transpose)

Techniques. Read structure off the Leibniz expansion (Technique 5.3.12)

Hint 1. Every term of the Leibniz formula contains exactly one entry of column

𝑗

. Group the terms according to which entry

𝑏_{𝑖 𝑗}

it is, that is, according to

𝑖 = 𝜎 (𝑗)

Hint 2. The terms with

𝜎 (𝑗) = 𝑖

use one entry from each row other than

𝑖

and each column other than

𝑗

, like the terms of

det 𝐵_{\hat{𝑖 𝑗}}

. Match them with the permutations of

[𝑛 - 1]

Hint 3. To compare signs, write

𝜎 = 𝜌_{𝑖} 𝜎^{'} 𝜌_{𝑗}^{- 1}

with

𝜎^{'} (1) = 1

, where

𝜌_{𝑚} (1) = 𝑚

and

𝜌_{𝑚} (𝑝) = 𝑝 - 1

for

2 \leq 𝑝 \leq 𝑚

(and

𝜌_{𝑚}

fixes the rest). This

𝜌_{𝑚}

is an

𝑚

-cycle.

Sketch. Grouping by

𝑖 = 𝜎 (𝑗)

gives

det 𝐵 =

\sum_{𝑖} 𝑏_{𝑖 𝑗} 𝑠_{𝑖}

, where

𝑠_{𝑖}

is the sum of

sgn (𝜎) \prod_{𝑘 \neq 𝑗} 𝑏_{𝜎 (𝑘) 𝑘}

over the

𝜎

with

𝜎 (𝑗) = 𝑖

. The cycle

𝜌_{𝑚}

lists

[𝑛] ∖ {𝑚}

in order on

2, \dots, 𝑛

, so

𝜎 \mapsto 𝜌_{𝑖}^{- 1} 𝜎 𝜌_{𝑗}

is a bijection onto the permutations fixing

1

, which correspond to

𝑆_{𝑛 - 1}

; it multiplies signs by

sgn (𝜌_{𝑖}) sgn (𝜌_{𝑗}) =

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

and turns the product into the Leibniz term of

𝐵_{\hat{𝑖 𝑗}}

. So

𝑠_{𝑖} =

{(- 1)}^{𝑖 + 𝑗} det 𝐵_{\hat{𝑖 𝑗}}

. Rows follow by transposing.

We prove (5.5.2); then (5.5.1) follows by applying it to $𝐵^{𝖳}$ , using Theorem 5.4.14 and ${(𝐵^{𝖳})}_{\hat{𝑗 𝑖}} =$ ${(𝐵_{\hat{𝑖 𝑗}})}^{𝖳}$ .

Fix $𝑗$ . Each term $sgn (𝜎) 𝑏_{𝜎 (1) 1} \dots 𝑏_{𝜎 (𝑛) 𝑛}$ of the Leibniz formula (Definition 5.3.6) contains exactly one factor from column $𝑗$ , namely $𝑏_{𝜎 (𝑗) 𝑗}$ . Grouping the terms by the value $𝑖 = 𝜎 (𝑗)$ ,

det 𝐵 = \sum_{𝑖 = 1}^{𝑛} 𝑏_{𝑖 𝑗} 𝑠_{𝑖}, where 𝑠_{𝑖} = \sum_{𝜎 \in 𝑆_{𝑛}, 𝜎 (𝑗) = 𝑖} sgn (𝜎) \prod_{𝑘 \neq 𝑗} 𝑏_{𝜎 (𝑘) 𝑘} .

We show that $𝑠_{𝑖} =$ ${(- 1)}^{𝑖 + 𝑗} det 𝐵_{\hat{𝑖 𝑗}}$ .

For $𝑚 \in [𝑛]$ , let $𝜌_{𝑚} \in 𝑆_{𝑛}$ be given by $𝜌_{𝑚} (1) = 𝑚$ , $𝜌_{𝑚} (𝑝) = 𝑝 - 1$ for $2 \leq 𝑝 \leq 𝑚$ , and $𝜌_{𝑚} (𝑝) = 𝑝$ for $𝑝 > 𝑚$ . For $𝑚 \geq 2$ this is the $𝑚$ -cycle $(1 𝑚 𝑚 - 1 \dots 2)$ , and $𝜌_{1} = id$ , so $sgn (𝜌_{𝑚}) =$ ${(- 1)}^{𝑚 - 1}$ by Proposition 5.2.26. As $𝑞$ runs through $1, \dots, 𝑛 - 1$ , the values $𝜌_{𝑚} (𝑞 + 1)$ run through $[𝑛] ∖ {𝑚}$ in increasing order. So row $𝑞$ of $𝐵_{\hat{𝑖 𝑗}}$ is row $𝜌_{𝑖} (𝑞 + 1)$ of $𝐵$ , column $𝑞$ of $𝐵_{\hat{𝑖 𝑗}}$ is column $𝜌_{𝑗} (𝑞 + 1)$ of $𝐵$ , and

{(𝐵_{\hat{𝑖 𝑗}})}_{𝑝 𝑞} = 𝑏_{𝜌_{𝑖} (𝑝 + 1), 𝜌_{𝑗} (𝑞 + 1)} .

If $𝜎 (𝑗) = 𝑖$ , then $𝜎^{'} = 𝜌_{𝑖}^{- 1} 𝜎 𝜌_{𝑗}$ satisfies $𝜎^{'} (1) =$ $𝜌_{𝑖}^{- 1} (𝜎 (𝑗)) =$ $1$ . Conversely, if $𝜎^{'} \in 𝑆_{𝑛}$ fixes $1$ , then $𝜎 = 𝜌_{𝑖} 𝜎^{'} 𝜌_{𝑗}^{- 1}$ satisfies $𝜎 (𝑗) =$ $𝜌_{𝑖} (𝜎^{'} (1)) =$ $𝑖$ . So $𝜎 \mapsto 𝜎^{'}$ is a bijection from ${𝜎 | 𝜎 (𝑗) = 𝑖}$ onto the permutations fixing $1$ . These in turn correspond to the $𝜏 \in 𝑆_{𝑛 - 1}$ via $𝜎^{'} (𝑞 + 1) =$ $𝜏 (𝑞) +$ $1$ . By Proposition 5.2.25,

sgn (𝜎) = sgn (𝜌_{𝑖}) sgn (𝜎^{'}) {sgn (𝜌_{𝑗})}^{- 1} = {(- 1)}^{𝑖 + 𝑗} sgn (𝜎^{'}) .

Also $sgn (𝜎^{'}) = sgn (𝜏)$ : if $𝜏 = 𝜏_{1} \dots 𝜏_{𝑟}$ with transpositions $𝜏_{𝑙} = (𝑎_{𝑙} 𝑏_{𝑙})$ of $[𝑛 - 1]$ , then $𝜎^{'}$ is the product of the $𝑟$ transpositions $(𝑎_{𝑙} + 1 𝑏_{𝑙} + 1)$ of $[𝑛]$ , since both sides fix $1$ and send $𝑞 + 1$ to $𝜏 (𝑞) + 1$ .

For the product, the index $𝑘 = 𝜌_{𝑗} (𝑞 + 1)$ runs through $[𝑛] ∖ {𝑗}$ as $𝑞$ runs through $[𝑛 - 1]$ , and $𝜎 (𝜌_{𝑗} (𝑞 + 1)) =$ $𝜌_{𝑖} (𝜎^{'} (𝑞 + 1)) =$ $𝜌_{𝑖} (𝜏 (𝑞) + 1)$ . Hence

\prod_{𝑘 \neq 𝑗} 𝑏_{𝜎 (𝑘) 𝑘} = \prod_{𝑞 = 1}^{𝑛 - 1} 𝑏_{𝜌_{𝑖} (𝜏 (𝑞) + 1), 𝜌_{𝑗} (𝑞 + 1)} = \prod_{𝑞 = 1}^{𝑛 - 1} {(𝐵_{\hat{𝑖 𝑗}})}_{𝜏 (𝑞) 𝑞} .

Summing over $𝜏 \in 𝑆_{𝑛 - 1}$ ,

𝑠_{𝑖} = {(- 1)}^{𝑖 + 𝑗} \sum_{𝜏 \in 𝑆_{𝑛 - 1}} sgn (𝜏) \prod_{𝑞 = 1}^{𝑛 - 1} {(𝐵_{\hat{𝑖 𝑗}})}_{𝜏 (𝑞) 𝑞} = {(- 1)}^{𝑖 + 𝑗} det 𝐵_{\hat{𝑖 𝑗}},

as desired. □

Intuition (Two proofs compared). The first proof is Technique 5.1.7 stopped after one row. Lemma 5.3.2 expanded all $𝑛$ columns at once and needed permutations to sort out the $𝑛^{𝑛}$ terms; expanding a single row produces only $𝑛$ terms, and the lemma about one nonzero entry evaluates each of them. The second proof reads the expansion off the Leibniz formula (Technique 5.3.12): every term uses exactly one entry of column $𝑗$ , and the terms that use $𝑏_{𝑖 𝑗}$ are, up to the sign ${(- 1)}^{𝑖 + 𝑗}$ , the Leibniz terms of $𝐵_{\hat{𝑖 𝑗}}$ . All of the work is in the bookkeeping of signs, which the first proof gets for free from the adjacent swaps.

A third route is Exercise 5.3.39. It takes the expansion along the first column as a definition, by induction on $𝑛$ , and checks the axioms directly.

For $𝑛 = 3$ , expanding along row $1$ gives

det (\begin{matrix} 𝑎 & 𝑏 & 𝑐 \\ 𝑑 & 𝑒 & 𝑓 \\ 𝑔 & ℎ & 𝑘 \end{matrix}) = 𝑎 (𝑒 𝑘 - 𝑓 ℎ) - 𝑏 (𝑑 𝑘 - 𝑓 𝑔) + 𝑐 (𝑑 ℎ - 𝑒 𝑔),

whose six terms are those of the rule of Sarrus (Corollary 5.3.9). Expansion pays off when a row or column has many zeros, since every zero entry removes a minor from the sum.

Example 5.5.4 (A sparse $4 \times 4$ determinant). Let

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

Column $2$ has a single nonzero entry, $𝑎_{32} = 4$ , so expanding along column $2$ (or applying Lemma 5.5.2 directly) gives

det 𝐴 = {(- 1)}^{3 + 2} \cdot 4 det 𝐴_{\hat{32}} = - 4 det (\begin{matrix} 2 & 1 & 3 \\ 1 & 0 & 2 \\ 3 & 1 & 1 \end{matrix}) .

In the $3 \times 3$ minor, row $2$ contains a zero. Expanding along row $2$ ,

det (\begin{matrix} 2 & 1 & 3 \\ 1 & 0 & 2 \\ 3 & 1 & 1 \end{matrix}) = - 1 \cdot det (\begin{matrix} 1 & 3 \\ 1 & 1 \end{matrix}) + 0 - 2 det (\begin{matrix} 2 & 1 \\ 3 & 1 \end{matrix}) = - (- 2) - 2 (- 1) = 4 .

Hence $det 𝐴 = - 16$ .

In practice, expansion is combined with elimination. Row and column replacements do not change the determinant (Corollary 5.4.15, Lemma 5.1.8), so one first creates zeros in some row or column, and then expands along it. This reduces the size by one at the cost of one round of replacements. For a general matrix with no zeros, though, a full cofactor expansion computes $𝑛$ minors of size $𝑛 - 1$ , each of these $𝑛 - 1$ minors of size $𝑛 - 2$ , and so on, about $𝑛!$ products in all; elimination is the better algorithm (Remark 5.4.25).

Exercise 5.5.5.routine Compute the determinant of

𝑀 = (\begin{matrix} 𝑖 & 0 & 2 & 0 \\ 1 & 3 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 2 & 1 & 𝑖 & 1 \end{matrix}) \in ℂ^{4 \times 4}

with two cofactor expansions. Along which rows or columns should you expand?

Solution.

Uses. Theorem 5.5.3 (Cofactor expansion), Lemma 5.5.2 (A row or column with one nonzero entry)

Hint 1. Look for a row or a column with a single nonzero entry.

Hint 2. Row

3

(0, 0, 1, 0)

. After deleting row

3

and column

3

, look at the first row of what is left.

Sketch. Expanding along row

3

leaves

𝑀_{\hat{33}} =

(\begin{matrix} 𝑖 & 0 & 0 \\ 1 & 3 & 1 \\ 2 & 1 & 1 \end{matrix})

with sign

+

. Expanding that along its first row gives

𝑖 (3 - 1) = 2 𝑖

. So

det 𝑀 = 2 𝑖

Row $3$ of $𝑀$ is $(0, 0, 1, 0)$ , so by Lemma 5.5.2,

det 𝑀 = {(- 1)}^{3 + 3} \cdot 1 \cdot det 𝑀_{\hat{33}} = det (\begin{matrix} 𝑖 & 0 & 0 \\ 1 & 3 & 1 \\ 2 & 1 & 1 \end{matrix}) .

The first row of this matrix is $(𝑖, 0, 0)$ , so expanding along it,

det 𝑀 = {(- 1)}^{1 + 1} 𝑖 det (\begin{matrix} 3 & 1 \\ 1 & 1 \end{matrix}) = 𝑖 (3 - 1) = 2 𝑖 .

Rows with a single nonzero entry are the best choice, since each expansion then has a single term.

5.5.2The cofactor matrix and the inverse

The numbers ${(- 1)}^{𝑖 + 𝑗} det 𝐵_{\hat{𝑖 𝑗}}$ appear in both expansions, so we give them a name and arrange them in a matrix.

Definition 5.5.6 (Cofactors, cofactor matrix, adjugate). Let $𝑛 \geq 2$ and $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ . The $(𝑖, 𝑗)$ cofactor of $𝐵$ is

𝑐_{𝑖 𝑗} = {(- 1)}^{𝑖 + 𝑗} det 𝐵_{\hat{𝑖 𝑗}} .

The cofactor matrix of $𝐵$ is $𝐶_{𝐵} =$ $(𝑐_{𝑖 𝑗}) \in$ $𝐹^{𝑛 \times 𝑛}$ , and the adjugate of $𝐵$ is its transpose,

adj 𝐵 = 𝐶_{𝐵}^{𝖳},

whose $(𝑖, 𝑗)$ entry is $𝑐_{𝑗 𝑖}$ . For $𝑛 = 1$ we set $adj (𝑏) = (1)$ .

In this notation, Theorem 5.5.3 says that $det 𝐵 =$ $\sum_{𝑗} 𝑏_{𝑖 𝑗} 𝑐_{𝑖 𝑗}$ for each row $𝑖$ , and $det 𝐵 =$ $\sum_{𝑖} 𝑏_{𝑖 𝑗} 𝑐_{𝑖 𝑗}$ for each column $𝑗$ : multiply each entry of a row or column by its own cofactor and add. The lecture writes the adjugate as $𝐶_{𝐵}^{𝖳}$ , and we use both. The adjugate is sometimes called the classical adjoint, but it is unrelated to the adjoints of Section 6.6, so we avoid that name. (The convention for $𝑛 = 1$ makes the theorems below true for $𝑛 = 1$ as well. It corresponds to declaring the determinant of the empty $0 \times 0$ matrix to be $1$ .)

Example 5.5.7 (The $2 \times 2$ case). Let $𝐵 = (\begin{matrix} 𝑝 & 𝑞 \\ 𝑟 & 𝑠 \end{matrix})$ . Deleting a row and a column leaves a single entry, so

𝑐_{11} = 𝑠, 𝑐_{12} = - 𝑟, 𝑐_{21} = - 𝑞, 𝑐_{22} = 𝑝,

and

𝐶_{𝐵} = (\begin{matrix} 𝑠 & - 𝑟 \\ - 𝑞 & 𝑝 \end{matrix}), adj 𝐵 = (\begin{matrix} 𝑠 & - 𝑞 \\ - 𝑟 & 𝑝 \end{matrix}) .

Then $𝐵 adj 𝐵 =$ $(\begin{matrix} 𝑝 𝑠 - 𝑞 𝑟 & - 𝑝 𝑞 + 𝑞 𝑝 \\ 𝑟 𝑠 - 𝑠 𝑟 & - 𝑟 𝑞 + 𝑠 𝑝 \end{matrix}) =$ $(𝑝 𝑠 - 𝑞 𝑟) 𝐼_{2}$ , and similarly $(adj 𝐵) 𝐵 =$ $(𝑝 𝑠 - 𝑞 𝑟) 𝐼_{2}$ . So when $𝑝 𝑠 - 𝑞 𝑟 \neq 0$ , the inverse of $𝐵$ is ${(𝑝 𝑠 - 𝑞 𝑟)}^{- 1} (\begin{matrix} 𝑠 & - 𝑞 \\ - 𝑟 & 𝑝 \end{matrix})$ : swap the diagonal entries, negate the others, and divide by the determinant. The theorem below says that the same pattern holds for every $𝑛$ .

The product $𝐵 adj 𝐵$ in the example has the determinant on the diagonal, which is expected: its $(𝑖, 𝑖)$ entry is $\sum_{𝑗} 𝑏_{𝑖 𝑗} 𝑐_{𝑖 𝑗}$ , the expansion along row $𝑖$ . Its off-diagonal entries pair row $𝑖$ of $𝐵$ with the cofactors of a different row $𝑘$ . The cofactors of row $𝑘$ do not involve row $𝑘$ at all, so pairing them with a vector $𝐱$ computes the determinant of $𝐵$ with row $𝑘$ replaced by $𝐱^{𝖳}$ . When $𝐱^{𝖳}$ is another row of $𝐵$ , that matrix has two equal rows.

Lemma 5.5.8 (Replacing a row or a column). Let $𝑛 \geq 2$ , let $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ have cofactors $𝑐_{𝑖 𝑗}$ , let $𝑘 \in [𝑛]$ , and let $𝐱 \in 𝐹^{𝑛}$ .

(a)If $𝐵^{'}$ is obtained from $𝐵$ by replacing row $𝑘$ with $𝐱^{𝖳}$ , then $det 𝐵^{'} =$ $\sum_{𝑗 = 1}^{𝑛} 𝑥_{𝑗} 𝑐_{𝑘 𝑗}$ .
(b)If $𝐵_{𝑘} (𝐱)$ is obtained from $𝐵$ by replacing column $𝑘$ with $𝐱$ , then $det 𝐵_{𝑘} (𝐱) =$ $\sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖} 𝑐_{𝑖 𝑘}$ .

In particular, for all $𝑖, 𝑘 \in [𝑛]$ ,

\sum_{𝑗 = 1}^{𝑛} 𝑏_{𝑖 𝑗} 𝑐_{𝑘 𝑗} = 𝛿_{𝑖 𝑘} det 𝐵 and \sum_{𝑗 = 1}^{𝑛} 𝑏_{𝑗 𝑖} 𝑐_{𝑗 𝑘} = 𝛿_{𝑖 𝑘} det 𝐵,

where $𝛿_{𝑖 𝑘}$ is $1$ if $𝑖 = 𝑘$ and $0$ otherwise.

Proof.routine

Uses. Theorem 5.5.3 (Cofactor expansion), Definition 5.5.6 (Cofactors, cofactor matrix, adjugate), Corollary 5.4.15 (Rows), Definition 5.1.1 (Determinant function)

Hint 1. Expand

det 𝐵^{'}

along row

𝑘

. What are the cofactors of row

𝑘

𝐵^{'}

Hint 2.

𝐵^{'}

and

𝐵

differ only in row

𝑘

, which is deleted when forming the minors of row

𝑘

Hint 3. For the last statement, take

𝐱^{𝖳}

to be row

𝑖

𝐵

. If

𝑖 \neq 𝑘

, what does

𝐵^{'}

look like?

Sketch. The minors

𝐵_{\hat{𝑘 𝑗}}^{'}

do not involve row

𝑘

, so they equal

𝐵_{\hat{𝑘 𝑗}}

, and the row

𝑘

cofactors of

𝐵^{'}

are

𝑐_{𝑘 1}, \dots, 𝑐_{𝑘 𝑛}

. Expanding along row

𝑘

gives (a); (b) is the same with columns. With

𝐱^{𝖳}

equal to row

𝑖

𝐵

𝐵^{'} = 𝐵

𝑖 = 𝑘

, and

𝐵^{'}

has two equal rows if

𝑖 \neq 𝑘

. Likewise for columns.

(a) For each $𝑗$ , the matrices $𝐵^{'}$ and $𝐵$ agree outside row $𝑘$ , so $𝐵_{\hat{𝑘 𝑗}}^{'} = 𝐵_{\hat{𝑘 𝑗}}$ , and the $(𝑘, 𝑗)$ cofactor of $𝐵^{'}$ is $𝑐_{𝑘 𝑗}$ . Expanding $det 𝐵^{'}$ along row $𝑘$ (Theorem 5.5.3), whose entries are $𝑥_{1}, \dots, 𝑥_{𝑛}$ , gives $det 𝐵^{'} =$ $\sum_{𝑗} 𝑥_{𝑗} 𝑐_{𝑘 𝑗}$ .

(b) Similarly, $𝐵_{𝑘} (𝐱)$ agrees with $𝐵$ outside column $𝑘$ , so its $(𝑖, 𝑘)$ cofactor is $𝑐_{𝑖 𝑘}$ , and expanding along column $𝑘$ gives $det 𝐵_{𝑘} (𝐱) =$ $\sum_{𝑖} 𝑥_{𝑖} 𝑐_{𝑖 𝑘}$ .

For the last statement, let $𝐱^{𝖳}$ be row $𝑖$ of $𝐵$ , so that $𝑥_{𝑗} = 𝑏_{𝑖 𝑗}$ . If $𝑖 = 𝑘$ , then $𝐵^{'} = 𝐵$ , and (a) gives $\sum_{𝑗} 𝑏_{𝑘 𝑗} 𝑐_{𝑘 𝑗} =$ $det 𝐵$ . If $𝑖 \neq 𝑘$ , then rows $𝑖$ and $𝑘$ of $𝐵^{'}$ are both equal to row $𝑖$ of $𝐵$ , so $det 𝐵^{'} = 0$ (Corollary 5.4.15), and (a) gives $\sum_{𝑗} 𝑏_{𝑖 𝑗} 𝑐_{𝑘 𝑗} = 0$ . For the column version, let $𝐱$ be column $𝑖$ of $𝐵$ , so $𝑥_{𝑗} = 𝑏_{𝑗 𝑖}$ . If $𝑖 = 𝑘$ , then $𝐵_{𝑘} (𝐱) = 𝐵$ ; if $𝑖 \neq 𝑘$ , then $𝐵_{𝑘} (𝐱)$ has equal columns $𝑖$ and $𝑘$ , so its determinant is $0$ (Definition 5.1.1). Now apply (b). □

The sums with $𝑖 \neq 𝑘$ are often called expansions by alien cofactors. Part (b) will give Cramer’s rule, and the last statement gives the main theorem of this subsection.

Theorem 5.5.9 (The adjugate and the inverse). For every $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ ,

𝐵 adj 𝐵 = (adj 𝐵) 𝐵 = (det 𝐵) 𝐼_{𝑛} .

Consequently, if $det 𝐵 \neq 0$ , then $𝐵$ is invertible and

𝐵^{- 1} = \frac{1}{det 𝐵} adj 𝐵 = \frac{1}{det 𝐵} 𝐶_{𝐵}^{𝖳} .

Proof.standard

Uses. Lemma 5.5.8 (Replacing a row or a column), Definition 5.5.6 (Cofactors, cofactor matrix, adjugate), Definition 2.4.1 (Matrix product), Definition 2.5.12 (Invertible)

Techniques. Compute entry by entry (Technique 2.4.15)

Hint 1. Compute the

(𝑖, 𝑘)

entry of

𝐵 adj 𝐵

. The

(𝑗, 𝑘)

entry of

adj 𝐵

𝑐_{𝑘 𝑗}

Hint 2. You get

\sum_{𝑗} 𝑏_{𝑖 𝑗} 𝑐_{𝑘 𝑗}

, which Lemma 5.5.8 evaluates. For

(adj 𝐵) 𝐵

, use the column version.

Sketch. The

(𝑖, 𝑘)

entry of

𝐵 adj 𝐵

\sum_{𝑗} 𝑏_{𝑖 𝑗} 𝑐_{𝑘 𝑗} =

𝛿_{𝑖 𝑘} det 𝐵

, and that of

(adj 𝐵) 𝐵

\sum_{𝑗} 𝑐_{𝑗 𝑖} 𝑏_{𝑗 𝑘} =

𝛿_{𝑖 𝑘} det 𝐵

, both by Lemma 5.5.8. Dividing by

det 𝐵 \neq 0

shows that

{(det 𝐵)}^{- 1} adj 𝐵

is a two-sided inverse.

For $𝑛 = 1$ , $𝐵 = (𝑏)$ and $adj 𝐵 = (1)$ , so both products are $(𝑏) = (det 𝐵) 𝐼_{1}$ . Let $𝑛 \geq 2$ . The $(𝑗, 𝑘)$ entry of $adj 𝐵 = 𝐶_{𝐵}^{𝖳}$ is $𝑐_{𝑘 𝑗}$ . So by Definition 2.4.1 and Lemma 5.5.8, the $(𝑖, 𝑘)$ entry of $𝐵 adj 𝐵$ is

\sum_{𝑗 = 1}^{𝑛} 𝑏_{𝑖 𝑗} 𝑐_{𝑘 𝑗} = 𝛿_{𝑖 𝑘} det 𝐵,

which is the $(𝑖, 𝑘)$ entry of $(det 𝐵) 𝐼_{𝑛}$ . Similarly, the $(𝑖, 𝑘)$ entry of $(adj 𝐵) 𝐵$ is

\sum_{𝑗 = 1}^{𝑛} 𝑐_{𝑗 𝑖} 𝑏_{𝑗 𝑘} = \sum_{𝑗 = 1}^{𝑛} 𝑏_{𝑗 𝑘} 𝑐_{𝑗 𝑖} = 𝛿_{𝑘 𝑖} det 𝐵,

by the column version in Lemma 5.5.8 (with the roles of $𝑖$ and $𝑘$ exchanged). Since $𝛿_{𝑘 𝑖} = 𝛿_{𝑖 𝑘}$ , this is again the $(𝑖, 𝑘)$ entry of $(det 𝐵) 𝐼_{𝑛}$ .

If $det 𝐵 \neq 0$ , multiplying both identities by ${(det 𝐵)}^{- 1}$ gives

𝐵 ({(det 𝐵)}^{- 1} adj 𝐵) = ({(det 𝐵)}^{- 1} adj 𝐵) 𝐵 = 𝐼_{𝑛},

so ${(det 𝐵)}^{- 1} adj 𝐵$ is a two-sided inverse of $𝐵$ (Definition 2.5.12). □

The theorem gives a second proof of (II) $\Rightarrow$ (I) in Theorem 5.4.7 that uses no elimination, and it produces the inverse explicitly. The identity $𝐵 adj 𝐵 =$ $(det 𝐵) 𝐼_{𝑛}$ holds for every $𝐵$ , invertible or not; for instance, if $det 𝐵 = 0$ , it says that every column of $adj 𝐵$ lies in $ker 𝐵$ .

The lecture calls the formula for $𝐵^{- 1}$ more of a curiosity than a useful way to compute inverses. For computing, that is right: it needs $𝑛^{2}$ determinants of size $𝑛 - 1$ , while row reducing $(𝐵 | 𝐼_{𝑛})$ (Algorithm 3.3.24) takes on the order of $𝑛^{3}$ operations, the same order as a single determinant. Its value is that it describes $𝐵^{- 1}$ by a formula. Every entry of $𝐵^{- 1}$ is a polynomial in the entries of $𝐵$ , divided by $det 𝐵$ . Two consequences follow below: integer matrices with determinant $\pm 1$ have integer inverses, and the solution of $𝐵 𝐱 = 𝐲$ is given by Cramer’s rule. The formula also shows how $det 𝐵$ depends on a single entry (Remark 5.5.11), which leads to formulas for derivatives of determinants (Section 5.5.6).

Example 5.5.10 (A $3 \times 3$ inverse). Let $𝐵 =$ $(\begin{matrix} 2 & 1 & 1 \\ 3 & 2 & 1 \\ 2 & 1 & 2 \end{matrix}) \in$ $ℚ^{3 \times 3}$ . The nine cofactors are

\begin{aligned} 𝑐_{11} & = + det (\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}) = 3, & 𝑐_{12} & = - det (\begin{matrix} 3 & 1 \\ 2 & 2 \end{matrix}) = - 4, & 𝑐_{13} & = + det (\begin{matrix} 3 & 2 \\ 2 & 1 \end{matrix}) = - 1, \\ 𝑐_{21} & = - det (\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix}) = - 1, & 𝑐_{22} & = + det (\begin{matrix} 2 & 1 \\ 2 & 2 \end{matrix}) = 2, & 𝑐_{23} & = - det (\begin{matrix} 2 & 1 \\ 2 & 1 \end{matrix}) = 0, \\ 𝑐_{31} & = + det (\begin{matrix} 1 & 1 \\ 2 & 1 \end{matrix}) = - 1, & 𝑐_{32} & = - det (\begin{matrix} 2 & 1 \\ 3 & 1 \end{matrix}) = 1, & 𝑐_{33} & = + det (\begin{matrix} 2 & 1 \\ 3 & 2 \end{matrix}) = 1 . \end{aligned}

Expanding along row $1$ , $det 𝐵 =$ $2 \cdot$ $3 +$ $1 \cdot$ $(- 4) +$ $1 \cdot$ $(- 1) =$ $1$ . Transposing $𝐶_{𝐵}$ ,

𝐵^{- 1} = adj 𝐵 = (\begin{matrix} 3 & - 1 & - 1 \\ - 4 & 2 & 1 \\ - 1 & 0 & 1 \end{matrix}) .

Multiplying out confirms $𝐵 adj 𝐵 = 𝐼_{3}$ . The inverse has integer entries because $det 𝐵 = 1$ .

Remark 5.5.11 (Cofactors measure sensitivity). Let $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ with $𝑛 \geq 2$ , and let $𝑈_{𝑖 𝑗} = 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}$ be the matrix unit (Lemma 2.4.24). Adding $𝑡 𝑈_{𝑖 𝑗}$ to $𝐵$ changes only the entry $𝑏_{𝑖 𝑗}$ , which becomes $𝑏_{𝑖 𝑗} + 𝑡$ . Expanding along row $𝑖$ , whose cofactors do not change,

det (𝐵 + 𝑡 𝑈_{𝑖 𝑗}) = det 𝐵 + 𝑡 𝑐_{𝑖 𝑗} for all 𝑡 \in 𝐹 .

So $det 𝐵$ is an affine function of each single entry, and the cofactor $𝑐_{𝑖 𝑗}$ is its slope. Over $ℝ$ , $𝑐_{𝑖 𝑗} =$ $𝜕 det 𝐵 / 𝜕 𝑏_{𝑖 𝑗}$ . For instance, if $𝑐_{𝑖 𝑗} \neq 0$ , then changing $𝑏_{𝑖 𝑗}$ to $𝑏_{𝑖 𝑗} -$ $det 𝐵 / 𝑐_{𝑖 𝑗}$ makes $𝐵$ singular, while if $𝑐_{𝑖 𝑗} = 0$ , no change of $𝑏_{𝑖 𝑗}$ alone affects $det 𝐵$ .

Corollary 5.5.12 (Integer inverses). Let

𝐴 \in ℚ^{𝑛 \times 𝑛}

have integer entries. Then

adj 𝐴

has integer entries, and so does

(det 𝐴) 𝐴^{- 1}

𝐴

is invertible. In particular,

𝐴

is invertible with

𝐴^{- 1}

having integer entries if and only if

det 𝐴 = \pm 1

Proof.routine

Uses. Theorem 5.5.9 (The adjugate and the inverse), Proposition 5.3.20 (Reduction modulo $𝑝$ ), Exercise 5.4.42, Theorem 5.4.7 (Invertibility and the determinant)

Hint 1. Each cofactor is

\pm

the determinant of a matrix with integer entries.

Hint 2. For the converse direction, take determinants of

𝐴 𝐴^{- 1} = 𝐼_{𝑛}

, as in Exercise 5.4.42.

Sketch. Determinants of integer matrices are integers (Proposition 5.3.20), so all cofactors and hence

adj 𝐴

are integral, and

(det 𝐴) 𝐴^{- 1} = adj 𝐴

. If

det 𝐴 = \pm 1

, then

𝐴^{- 1} = \pm adj 𝐴

is integral. Conversely, if

𝐴^{- 1}

is integral,

det 𝐴 det 𝐴^{- 1} = 1

with both factors integers forces

det 𝐴 = \pm 1

Each cofactor of

𝐴

\pm

the determinant of a matrix with integer entries, hence an integer by Proposition 5.3.20. So

adj 𝐴

has integer entries. If

𝐴

is invertible, then

det 𝐴 \neq 0

(Theorem 5.4.7), and

(det 𝐴) 𝐴^{- 1} = adj 𝐴

by Theorem 5.5.9. If

det 𝐴 = \pm 1

, then

𝐴

is invertible and

𝐴^{- 1} =

{(det 𝐴)}^{- 1} adj 𝐴 =

\pm adj 𝐴

has integer entries. The converse is Exercise 5.4.42. □

So the denominators in $𝐴^{- 1}$ always divide $det 𝐴$ . To manufacture integer matrices with integer inverses, start from an upper triangular matrix with $1$ s on the diagonal and apply row and column replacements with integer multipliers. These keep the entries integral and the determinant equal to $1$ .

Exercise 5.5.13.routine Let

𝐴 =

(\begin{matrix} 1 & 2 & 0 \\ 3 & 1 & 1 \\ 0 & 4 & 3 \end{matrix}) \in

𝔽_{7}^{3 \times 3}

. Compute

det 𝐴

and

adj 𝐴

over

𝔽_{7}

, and use them to find

𝐴^{- 1}

. Check your answer by multiplying.

Solution.

Uses. Definition 5.5.6 (Cofactors, cofactor matrix, adjugate), Theorem 5.5.9 (The adjugate and the inverse), Proposition 5.3.20 (Reduction modulo $𝑝$ )

Hint 1. Compute the cofactors over

ℤ

and reduce modulo

7

at the end. Remember to transpose.

Hint 2.

det 𝐴 = - 19

over

ℤ

, which is

2

𝔽_{7}

, and

2^{- 1} = 4

𝔽_{7}

Sketch. Over

ℤ

adj 𝐴 =

(\begin{matrix} - 1 & - 6 & 2 \\ - 9 & 3 & - 1 \\ 12 & - 4 & - 5 \end{matrix})

and

det 𝐴 = - 19

. In

𝔽_{7}

det 𝐴 = 2

and

adj 𝐴 = (\begin{matrix} 6 & 1 & 2 \\ 5 & 3 & 6 \\ 5 & 3 & 2 \end{matrix})

, so

𝐴^{- 1} =

4 adj 𝐴 =

(\begin{matrix} 3 & 4 & 1 \\ 6 & 5 & 3 \\ 6 & 5 & 1 \end{matrix})

We compute over $ℤ$ and reduce at the end (Proposition 5.3.20). The cofactors are

\begin{aligned} 𝑐_{11} & = 1 \cdot 3 - 1 \cdot 4 = - 1, & 𝑐_{12} & = - (3 \cdot 3 - 1 \cdot 0) = - 9, & 𝑐_{13} & = 3 \cdot 4 - 1 \cdot 0 = 12, \\ 𝑐_{21} & = - (2 \cdot 3 - 0 \cdot 4) = - 6, & 𝑐_{22} & = 1 \cdot 3 - 0 \cdot 0 = 3, & 𝑐_{23} & = - (1 \cdot 4 - 2 \cdot 0) = - 4, \\ 𝑐_{31} & = 2 \cdot 1 - 0 \cdot 1 = 2, & 𝑐_{32} & = - (1 \cdot 1 - 0 \cdot 3) = - 1, & 𝑐_{33} & = 1 \cdot 1 - 2 \cdot 3 = - 5 . \end{aligned}

Expanding along row $1$ , $det 𝐴 =$ $1 \cdot$ $(- 1) +$ $2 \cdot$ $(- 9) +$ $0 \cdot$ $12 =$ $- 19$ , which is $2$ in $𝔽_{7}$ . Transposing $𝐶_{𝐴}$ and reducing modulo $7$ ,

adj 𝐴 = (\begin{matrix} - 1 & - 6 & 2 \\ - 9 & 3 & - 1 \\ 12 & - 4 & - 5 \end{matrix}) = (\begin{matrix} 6 & 1 & 2 \\ 5 & 3 & 6 \\ 5 & 3 & 2 \end{matrix}) in 𝔽_{7}^{3 \times 3} .

Since $2 \cdot 4 = 8 = 1$ in $𝔽_{7}$ , ${(det 𝐴)}^{- 1} = 4$ , and by Theorem 5.5.9

𝐴^{- 1} = 4 adj 𝐴 = (\begin{matrix} 24 & 4 & 8 \\ 20 & 12 & 24 \\ 20 & 12 & 8 \end{matrix}) = (\begin{matrix} 3 & 4 & 1 \\ 6 & 5 & 3 \\ 6 & 5 & 1 \end{matrix}) .

Check: the first row of $𝐴 𝐴^{- 1}$ is $(3 + 12, 4 + 10, 1 + 6) =$ $(15, 14, 7) =$ $(1, 0, 0)$ , the second is $(9 + 6 + 6, 12 + 5 + 5, 3 + 3 + 1) =$ $(21, 22, 7) =$ $(0, 1, 0)$ , and the third is $(24 + 18, 20 + 15, 12 + 3) =$ $(42, 35, 15) =$ $(0, 0, 1)$ , all modulo $7$ .

5.5.3Cramer’s rule

Intuition (Coefficients as ratios of areas). Suppose $𝐚_{1}, 𝐚_{2} \in ℝ^{2}$ are independent and $𝐲 = 𝑥_{1} 𝐚_{1} + 𝑥_{2} 𝐚_{2}$ . Replace $𝐚_{1}$ by $𝐲$ in the parallelogram spanned by $𝐚_{1}$ and $𝐚_{2}$ . The part $𝑥_{2} 𝐚_{2}$ of $𝐲$ is parallel to the other side, and shearing along $𝐚_{2}$ does not change signed area (Lemma 5.1.8). What remains, $𝑥_{1} 𝐚_{1}$ , scales the area by $𝑥_{1}$ . So

det (𝐲, 𝐚_{2}) = det (𝑥_{1} 𝐚_{1} + 𝑥_{2} 𝐚_{2}, 𝐚_{2}) = 𝑥_{1} det (𝐚_{1}, 𝐚_{2}),

and $𝑥_{1}$ is the ratio $det (𝐲, 𝐚_{2}) / det (𝐚_{1}, 𝐚_{2})$ of two signed areas (Figure 5.5.2). The same computation works for every coordinate and in every dimension.

Figure 5.5.2. Here

𝐚_{1} = (2, 0)

𝐚_{2} = (1, 2)

, and

𝐲 =

\frac{3}{2} 𝐚_{1} +

\frac{1}{2} 𝐚_{2} =

(\frac{7}{2}, 1)

. The parallelogram on

𝐚_{1}, 𝐚_{2}

(blue) has signed area

det (𝐚_{1}, 𝐚_{2}) = 4

. The parallelogram on

𝐲, 𝐚_{2}

(green) has the same base

𝐚_{2}

as the parallelogram on

\frac{3}{2} 𝐚_{1}, 𝐚_{2}

(dashed), and its far side lies on the same dotted line, parallel to

𝐚_{2}

. So both have area

6 = \frac{3}{2} \cdot 4

, and

𝑥_{1} =

det (𝐲, 𝐚_{2}) / det (𝐚_{1}, 𝐚_{2}) =

\frac{3}{2}

Theorem 5.5.14 (Cramer’s rule). Let $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ with $det 𝐵 \neq 0$ , and let $𝐲 \in 𝐹^{𝑛}$ . Then the system $𝐵 𝐱 = 𝐲$ has exactly one solution $𝐱 \in 𝐹^{𝑛}$ , and its entries are

𝑥_{𝑖} = \frac{det 𝐵_{𝑖} (𝐲)}{det 𝐵} (𝑖 = 1, \dots, 𝑛),

where $𝐵_{𝑖} (𝐲)$ is the matrix obtained from $𝐵$ by replacing column $𝑖$ with $𝐲$ .

Proof (by multilinearity).routine

Uses. Theorem 5.4.7 (Invertibility and the determinant), Definition 2.3.8 (Matrix–vector product), Definition 5.1.1 (Determinant function)

Techniques. Expand by multilinearity (Technique 5.1.7)

Hint 1. Existence and uniqueness come from invertibility. For the formula, write

𝐲 = 𝐵 𝐱

as a combination of the columns of

𝐵

Hint 2. Substitute

𝐲 = \sum_{𝑘} 𝑥_{𝑘} 𝐛_{𝑘}

into column

𝑖

𝐵_{𝑖} (𝐲)

and expand by linearity in column

𝑖

. Which terms survive?

Sketch.

𝐵

is invertible, so

𝐱 = 𝐵^{- 1} 𝐲

is the only solution. Since

𝐲 = \sum_{𝑘} 𝑥_{𝑘} 𝐛_{𝑘}

, linearity in column

𝑖

gives

det 𝐵_{𝑖} (𝐲) =

\sum_{𝑘} 𝑥_{𝑘} det 𝐵_{𝑖} (𝐛_{𝑘})

. For

𝑘 \neq 𝑖

, the matrix

𝐵_{𝑖} (𝐛_{𝑘})

has

𝐛_{𝑘}

in columns

𝑖

and

𝑘

, so only

𝑘 = 𝑖

survives, and

𝐵_{𝑖} (𝐛_{𝑖}) = 𝐵

. So

det 𝐵_{𝑖} (𝐲) =

𝑥_{𝑖} det 𝐵

By Theorem 5.4.7, $𝐵$ is invertible. If $𝐵 𝐱 = 𝐲$ , then $𝐱 =$ $𝐵^{- 1} 𝐵 𝐱 =$ $𝐵^{- 1} 𝐲$ ; conversely $𝐵 (𝐵^{- 1} 𝐲) = 𝐲$ . So $𝐱 = 𝐵^{- 1} 𝐲$ is the unique solution.

Let $𝐛_{1}, \dots, 𝐛_{𝑛}$ be the columns of $𝐵$ . By Definition 2.3.8, $𝐲 =$ $𝐵 𝐱 =$ $\sum_{𝑘} 𝑥_{𝑘} 𝐛_{𝑘}$ . Fix $𝑖$ . By linearity in column $𝑖$ ,

det 𝐵_{𝑖} (𝐲) = \sum_{𝑘 = 1}^{𝑛} 𝑥_{𝑘} det 𝐵_{𝑖} (𝐛_{𝑘}) .

If $𝑘 \neq 𝑖$ , then $𝐵_{𝑖} (𝐛_{𝑘})$ has $𝐛_{𝑘}$ both in column $𝑖$ and in column $𝑘$ , so its determinant is $0$ since $det$ is alternating. If $𝑘 = 𝑖$ , then $𝐵_{𝑖} (𝐛_{𝑖}) = 𝐵$ . So $det 𝐵_{𝑖} (𝐲) =$ $𝑥_{𝑖} det 𝐵$ , and dividing by $det 𝐵 \neq 0$ gives the formula. □

Proof (via the adjugate).routine

Uses. Theorem 5.5.9 (The adjugate and the inverse), Lemma 5.5.8 (Replacing a row or a column), Definition 5.5.6 (Cofactors, cofactor matrix, adjugate)

Hint 1. Write the solution as

𝐱 = 𝐵^{- 1} 𝐲

and use the formula for

𝐵^{- 1}

Hint 2. The

𝑖

-th entry of

(adj 𝐵) 𝐲

\sum_{𝑗} 𝑐_{𝑗 𝑖} 𝑦_{𝑗}

. Compare with part (b) of Lemma 5.5.8.

Sketch.

𝐱 =

𝐵^{- 1} 𝐲 =

{(det 𝐵)}^{- 1} (adj 𝐵) 𝐲

, and the

𝑖

-th entry of

(adj 𝐵) 𝐲

\sum_{𝑗} 𝑐_{𝑗 𝑖} 𝑦_{𝑗} =

det 𝐵_{𝑖} (𝐲)

, the expansion of

det 𝐵_{𝑖} (𝐲)

along column

𝑖

As in the first proof, the unique solution is

𝐱 = 𝐵^{- 1} 𝐲

, which equals

{(det 𝐵)}^{- 1} (adj 𝐵) 𝐲

by Theorem 5.5.9. For

𝑛 = 1

this reads

𝑥_{1} = 𝑦_{1} / 𝑏_{11}

, which is the claim. For

𝑛 \geq 2

, the

(𝑖, 𝑗)

entry of

adj 𝐵

𝑐_{𝑗 𝑖}

, so the

𝑖

-th entry of

(adj 𝐵) 𝐲

\sum_{𝑗} 𝑦_{𝑗} 𝑐_{𝑗 𝑖}

, which is

det 𝐵_{𝑖} (𝐲)

by part (b) of Lemma 5.5.8. □

The two proofs reverse each other’s logic. The second derives Cramer’s rule from the inverse formula. The first needs nothing but the axioms, and running it backwards gives the inverse formula: column $𝑗$ of $𝐵^{- 1}$ solves $𝐵 𝐱 = 𝐞_{𝑗}$ , so Cramer’s rule computes its entries (Exercise 5.5.16). The first proof also shows more than the theorem states. Its computation never used that $det 𝐵 \neq 0$ : for every $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ and every solution $𝐱$ of $𝐵 𝐱 = 𝐲$ ,

𝑥_{𝑖} det 𝐵 = det 𝐵_{𝑖} (𝐲) (𝑖 = 1, \dots, 𝑛) .

(5.5.3)

So if $det 𝐵 = 0$ but $det 𝐵_{𝑖} (𝐲) \neq 0$ for some $𝑖$ , the system has no solution. The converse fails, as Exercise 5.5.35 shows.

Example 5.5.15 (One unknown at a time). Let $𝐵$ be the matrix of Example 5.5.10, with $det 𝐵 = 1$ , and $𝐲 = (1, 0, 4)$ . To find only $𝑥_{3}$ in the solution of $𝐵 𝐱 = 𝐲$ , we need a single determinant:

𝑥_{3} = det 𝐵_{3} (𝐲) = det (\begin{matrix} 2 & 1 & 1 \\ 3 & 2 & 0 \\ 2 & 1 & 4 \end{matrix}) = 2 (8 - 0) - 1 (12 - 0) + 1 (3 - 4) = 3 .

The full solution, from $𝐱 = (adj 𝐵) 𝐲$ , is $𝐱 = (- 1, 0, 3)$ , and indeed $𝐵 𝐱 =$ $(- 2 + 3, - 3 + 3, - 2 + 6) =$ $(1, 0, 4)$ .

As a method for solving systems, Cramer’s rule needs $𝑛 + 1$ determinants and is far slower than elimination. Its value is theoretical: it expresses each $𝑥_{𝑖}$ as a ratio of two polynomials in the entries of $𝐵$ and $𝐲$ , linear in $𝐲$ , so that, for instance, an integer system with $det 𝐵 = \pm 1$ has an integer solution. It also explains the geometry of Intuition (Coefficients as ratios of areas).

Exercise 5.5.16.routine Let

𝐵 \in 𝐹^{𝑛 \times 𝑛}

with

det 𝐵 \neq 0

and

𝑛 \geq 2

. Use Cramer’s rule, applied to the systems

𝐵 𝐱 = 𝐞_{𝑗}

, to show that the

(𝑖, 𝑗)

entry of

𝐵^{- 1}

𝑐_{𝑗 𝑖} / det 𝐵

. This proves the second half of Theorem 5.5.9 again.

Solution.

Uses. Theorem 5.5.14 (Cramer’s rule), Lemma 5.5.2 (A row or column with one nonzero entry), Definition 5.5.6 (Cofactors, cofactor matrix, adjugate)

Hint 1. Column

𝑗

𝐵^{- 1}

is the solution of

𝐵 𝐱 = 𝐞_{𝑗}

Hint 2. In

𝐵_{𝑖} (𝐞_{𝑗})

, column

𝑖

has a single nonzero entry. Where is it?

Sketch. Column

𝑗

𝐵^{- 1}

𝐵^{- 1} 𝐞_{𝑗}

, the solution of

𝐵 𝐱 = 𝐞_{𝑗}

. Its

𝑖

-th entry is

det 𝐵_{𝑖} (𝐞_{𝑗}) / det 𝐵

. Column

𝑖

𝐵_{𝑖} (𝐞_{𝑗})

has a single

1

in row

𝑗

, and deleting row

𝑗

and column

𝑖

leaves

𝐵_{\hat{𝑗 𝑖}}

. So

det 𝐵_{𝑖} (𝐞_{𝑗}) =

{(- 1)}^{𝑖 + 𝑗} det 𝐵_{\hat{𝑗 𝑖}} =

𝑐_{𝑗 𝑖}

The $(𝑖, 𝑗)$ entry of $𝐵^{- 1}$ is the $𝑖$ -th entry of its $𝑗$ -th column $𝐵^{- 1} 𝐞_{𝑗}$ , which is the solution of $𝐵 𝐱 = 𝐞_{𝑗}$ . By Theorem 5.5.14 it equals $det 𝐵_{𝑖} (𝐞_{𝑗}) / det 𝐵$ . Column $𝑖$ of $𝐵_{𝑖} (𝐞_{𝑗})$ is $𝐞_{𝑗}$ , whose only nonzero entry is the $1$ in row $𝑗$ . Deleting row $𝑗$ and column $𝑖$ from $𝐵_{𝑖} (𝐞_{𝑗})$ removes the replaced column, so it leaves $𝐵_{\hat{𝑗 𝑖}}$ . By Lemma 5.5.2,

det 𝐵_{𝑖} (𝐞_{𝑗}) = {(- 1)}^{𝑗 + 𝑖} det 𝐵_{\hat{𝑗 𝑖}} = 𝑐_{𝑗 𝑖} .

Hence the $(𝑖, 𝑗)$ entry of $𝐵^{- 1}$ is $𝑐_{𝑗 𝑖} / det 𝐵$ , the $(𝑖, 𝑗)$ entry of ${(det 𝐵)}^{- 1} 𝐶_{𝐵}^{𝖳}$ .

5.5.4Determinants of structured matrices

Cofactor expansion reduces the size of a determinant by one. When the smaller determinants have the same shape as the original one, this sets up an induction.

Technique 5.5.17 (Induction on matrix size). Suppose a family of matrices $𝑀_{1}, 𝑀_{2}, 𝑀_{3}, \dots$ , with $𝑀_{𝑛} \in 𝐹^{𝑛 \times 𝑛}$ , has the property that expanding $𝑀_{𝑛}$ along a well-chosen row or column produces minors that are earlier members of the family, or are triangular, or are otherwise known. Then the expansion gives a recurrence for $𝑑_{𝑛} = det 𝑀_{𝑛}$ . Expand along the row or column with the fewest nonzero entries, identify each minor that appears, and write down the recurrence. Then either solve it, or compute $𝑑_{1}, 𝑑_{2}, 𝑑_{3}$ , guess a closed form, and prove it by induction on $𝑛$ .

Reach for it when a matrix has a pattern that repeats along the diagonal, so that deleting the last (or first) row and column gives the same kind of matrix. The canonical example is Proposition 5.5.18. Proposition 5.5.20 and the first proof of Theorem 5.5.21 induct in the same way, and Exercise 5.5.34 reproves Proposition 5.3.15.

Used in 10 places and 2 practice exercises

Proposition 5.5.18, Proposition 5.5.20, Theorem 5.5.21, Exercise 5.5.34, Exercise 5.5.45, Exercise 5.5.53, Exercise 5.6.7, Problem 5.14, Theorem 8.3.23, Lemma 8.4.24; 2 practice exercises.

Proposition 5.5.18 (Tridiagonal determinants). Let $𝑎_{1}, \dots, 𝑎_{𝑛}$ , $𝑏_{1}, \dots, 𝑏_{𝑛 - 1}$ , and $𝑐_{1}, \dots, 𝑐_{𝑛 - 1}$ be elements of $𝐹$ . For $1 \leq 𝑚 \leq 𝑛$ let

𝑇_{𝑚} = (\begin{matrix} 𝑎_{1} & 𝑏_{1} & 0 & \dots & 0 \\ 𝑐_{1} & 𝑎_{2} & 𝑏_{2} & ⋱ & ⋮ \\ 0 & 𝑐_{2} & ⋱ & ⋱ & 0 \\ ⋮ & ⋱ & ⋱ & 𝑎_{𝑚 - 1} & 𝑏_{𝑚 - 1} \\ 0 & \dots & 0 & 𝑐_{𝑚 - 1} & 𝑎_{𝑚} \end{matrix}) \in 𝐹^{𝑚 \times 𝑚},

with $𝑏_{𝑘}$ in position $(𝑘, 𝑘 + 1)$ , $𝑐_{𝑘}$ in position $(𝑘 + 1, 𝑘)$ , and zeros away from the three middle diagonals. Let $𝑑_{𝑚} = det 𝑇_{𝑚}$ , and put $𝑑_{0} = 1$ . Then $𝑑_{1} = 𝑎_{1}$ , and

𝑑_{𝑚} = 𝑎_{𝑚} 𝑑_{𝑚 - 1} - 𝑏_{𝑚 - 1} 𝑐_{𝑚 - 1} 𝑑_{𝑚 - 2} (2 \leq 𝑚 \leq 𝑛) .

Proof.routine

Uses. Theorem 5.5.3 (Cofactor expansion), Lemma 5.5.2 (A row or column with one nonzero entry)

Techniques. Induction on matrix size (Technique 5.5.17)

Hint 1. Expand

det 𝑇_{𝑚}

along its last row. It has at most two nonzero entries.

Hint 2. One minor is

𝑇_{𝑚 - 1}

. In the other, the last column has a single nonzero entry; apply Lemma 5.5.2 once more.

Sketch. The last row of

𝑇_{𝑚}

(0, \dots, 0, 𝑐_{𝑚 - 1}, 𝑎_{𝑚})

. Deleting row

𝑚

and column

𝑚

leaves

𝑇_{𝑚 - 1}

, with sign

+

. Deleting row

𝑚

and column

𝑚 - 1

leaves a matrix whose last column is

(0, \dots, 0, 𝑏_{𝑚 - 1})

, with sign

-

; expanding along that column leaves

𝑇_{𝑚 - 2}

. So

𝑑_{𝑚} =

𝑎_{𝑚} 𝑑_{𝑚 - 1} -

𝑐_{𝑚 - 1} 𝑏_{𝑚 - 1} 𝑑_{𝑚 - 2}

$𝑇_{1} = (𝑎_{1})$ , so $𝑑_{1} = 𝑎_{1}$ . Let $2 \leq 𝑚 \leq 𝑛$ . The last row of $𝑇_{𝑚}$ is $(0, \dots, 0, 𝑐_{𝑚 - 1}, 𝑎_{𝑚})$ , so expanding along it (Theorem 5.5.3),

𝑑_{𝑚} = {(- 1)}^{𝑚 + 𝑚} 𝑎_{𝑚} det {𝑇_{𝑚}}_{\hat{𝑚 𝑚}} + {(- 1)}^{𝑚 + 𝑚 - 1} 𝑐_{𝑚 - 1} det 𝑁 = 𝑎_{𝑚} 𝑑_{𝑚 - 1} - 𝑐_{𝑚 - 1} det 𝑁,

where ${𝑇_{𝑚}}_{\hat{𝑚 𝑚}} = 𝑇_{𝑚 - 1}$ and $𝑁 = {𝑇_{𝑚}}_{\hat{𝑚 𝑚 - 1}}$ . The matrix $𝑁$ consists of rows $1, \dots, 𝑚 - 1$ and columns $1, \dots, 𝑚 - 2, 𝑚$ of $𝑇_{𝑚}$ . Its last column is column $𝑚$ of $𝑇_{𝑚}$ without the last entry, namely $(0, \dots, 0, 𝑏_{𝑚 - 1})$ . If $𝑚 = 2$ , then $𝑁 = (𝑏_{1})$ and $det 𝑁 = 𝑏_{1} = 𝑏_{1} 𝑑_{0}$ . If $𝑚 \geq 3$ , the only nonzero entry of the last column of $𝑁$ is $𝑏_{𝑚 - 1}$ , in position $(𝑚 - 1, 𝑚 - 1)$ , and deleting row $𝑚 - 1$ and column $𝑚 - 1$ of $𝑁$ leaves rows and columns $1, \dots, 𝑚 - 2$ of $𝑇_{𝑚}$ , which form $𝑇_{𝑚 - 2}$ . By Lemma 5.5.2, $det 𝑁 =$ $𝑏_{𝑚 - 1} 𝑑_{𝑚 - 2}$ . In both cases $𝑑_{𝑚} =$ $𝑎_{𝑚} 𝑑_{𝑚 - 1} -$ $𝑏_{𝑚 - 1} 𝑐_{𝑚 - 1} 𝑑_{𝑚 - 2}$ . □

Only the products $𝑏_{𝑘} 𝑐_{𝑘}$ enter, so the entries above and below the diagonal can be traded against each other without changing any $𝑑_{𝑚}$ .

Example 5.5.19 (Two tridiagonal families).

(a)Let $𝑎_{𝑘} = 2$ and $𝑏_{𝑘} = 𝑐_{𝑘} = - 1$ for all $𝑘$ . This is the matrix of second differences, which approximates $- 𝑓^{″}$ when $𝑓$ is sampled at equally spaced points. The recurrence reads $𝑑_{𝑚} =$ $2 𝑑_{𝑚 - 1} -$ $𝑑_{𝑚 - 2}$ with $𝑑_{0} = 1$ and $𝑑_{1} = 2$ , so $𝑑_{2} = 3$ , $𝑑_{3} = 4$ , and by induction $𝑑_{𝑚} = 𝑚 + 1$ : if $𝑑_{𝑚 - 1} = 𝑚$ and $𝑑_{𝑚 - 2} = 𝑚 - 1$ , then $𝑑_{𝑚} =$ $2 𝑚 -$ $(𝑚 - 1) =$ $𝑚 +$ $1$ . So the $𝑛 \times 𝑛$ matrix is invertible over $ℚ$ , and over $𝔽_{𝑝}$ exactly when $𝑝$ does not divide $𝑛 + 1$ (Proposition 5.3.20).
(b)Over $ℂ$ , let $𝑎_{𝑘} = 1$ and $𝑏_{𝑘} = 𝑐_{𝑘} = 𝑖$ . Then $- 𝑏_{𝑘} 𝑐_{𝑘} = - 𝑖^{2} = 1$ , so $𝑑_{𝑚} =$ $𝑑_{𝑚 - 1} +$ $𝑑_{𝑚 - 2}$ with $𝑑_{0} = 𝑑_{1} = 1$ . The determinants are the Fibonacci numbers $1, 1, 2, 3, 5, 8, 13, \dots$ , although every off-diagonal entry is imaginary.

The next family has a single row with more than two nonzero entries. Its determinant is a polynomial chosen in advance.

Proposition 5.5.20 (Companion matrices). Let $𝑛 \geq 1$ , let $𝑎_{0}, \dots, 𝑎_{𝑛 - 1} \in 𝐹$ , let $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑛 - 1} 𝑥^{𝑛 - 1} +$ $𝑥^{𝑛} \in$ $𝐹 [𝑥]$ , and let

𝐶 = (\begin{matrix} 0 & 0 & \dots & 0 & - 𝑎_{0} \\ 1 & 0 & \dots & 0 & - 𝑎_{1} \\ 0 & 1 & \dots & 0 & - 𝑎_{2} \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 0 & 0 & \dots & 1 & - 𝑎_{𝑛 - 1} \end{matrix}) \in 𝐹^{𝑛 \times 𝑛},

whose column $𝑘$ is $𝐞_{𝑘 + 1}$ for $𝑘 < 𝑛$ , and whose last column is $- (𝑎_{0}, \dots, 𝑎_{𝑛 - 1})$ . Then

det (𝑡 𝐼_{𝑛} - 𝐶) = 𝑝 (𝑡) = 𝑡^{𝑛} + 𝑎_{𝑛 - 1} 𝑡^{𝑛 - 1} + \dots + 𝑎_{1} 𝑡 + 𝑎_{0} for every 𝑡 \in 𝐹 .

In particular, $det 𝐶 = {(- 1)}^{𝑛} 𝑎_{0}$ .

Written out,

𝑡 𝐼_{𝑛} - 𝐶 = (\begin{matrix} 𝑡 & 0 & \dots & 0 & 𝑎_{0} \\ - 1 & 𝑡 & \dots & 0 & 𝑎_{1} \\ 0 & - 1 & ⋱ & ⋮ & ⋮ \\ ⋮ & ⋱ & ⋱ & 𝑡 & 𝑎_{𝑛 - 2} \\ 0 & \dots & 0 & - 1 & 𝑡 + 𝑎_{𝑛 - 1} \end{matrix}) .

For $𝑛 = 1$ this is $(𝑡 + 𝑎_{0})$ , and for $𝑛 = 2$ it is $(\begin{matrix} 𝑡 & 𝑎_{0} \\ - 1 & 𝑡 + 𝑎_{1} \end{matrix})$ , with determinant $𝑡^{2} + 𝑎_{1} 𝑡 + 𝑎_{0}$ , as claimed. We give two proofs. The first is an induction in which the polynomial is built up by Horner’s scheme $𝑝 (𝑡) =$ $𝑎_{0} +$ $𝑡 (𝑎_{1} + 𝑡 (𝑎_{2} + \dots))$ ; the second performs the same scheme with row operations.

Proof (by expansion and induction).standard

Uses. Theorem 5.5.3 (Cofactor expansion), Proposition 5.3.15 (Triangular matrices), Definition 1.2.17 (Evaluation), Exercise 5.1.5, induction on $𝑛$

Techniques. Induction on matrix size (Technique 5.5.17)

Hint 1. Expand

det (𝑡 𝐼_{𝑛} - 𝐶)

along the first row, which has at most two nonzero entries.

Hint 2. Deleting row

1

and column

1

gives a matrix of the same kind, for the polynomial

𝑎_{1} +

𝑎_{2} 𝑥 +

\dots +

𝑥^{𝑛 - 1}

. Deleting row

1

and column

𝑛

gives a triangular matrix.

Hint 3. You should find

det (𝑡 𝐼_{𝑛} - 𝐶) =

𝑡 𝑞 (𝑡) +

𝑎_{0}

, where

𝑞 =

𝑎_{1} +

𝑎_{2} 𝑥 +

\dots +

𝑎_{𝑛 - 1} 𝑥^{𝑛 - 2} +

𝑥^{𝑛 - 1}

Sketch. Induct on

𝑛

; for

𝑛 = 1

both sides are

𝑡 + 𝑎_{0}

. Let

𝑀 = 𝑡 𝐼_{𝑛} - 𝐶

. Its first row is

(𝑡, 0, \dots, 0, 𝑎_{0})

. The minor

𝑀_{\hat{11}}

𝑡 𝐼_{𝑛 - 1} - 𝐶^{'}

for the companion matrix

𝐶^{'}

𝑞 =

𝑎_{1} +

𝑎_{2} 𝑥 +

\dots +

𝑥^{𝑛 - 1}

, so its determinant is

𝑞 (𝑡)

. The minor

𝑀_{\hat{1 𝑛}}

is upper triangular with diagonal entries

- 1

, so its determinant is

{(- 1)}^{𝑛 - 1}

. Hence

det 𝑀 =

𝑡 𝑞 (𝑡) +

{(- 1)}^{1 + 𝑛} {(- 1)}^{𝑛 - 1} 𝑎_{0} =

𝑡 𝑞 (𝑡) +

𝑎_{0} =

𝑝 (𝑡)

We induct on $𝑛$ . For $𝑛 = 1$ , $𝐶 = (- 𝑎_{0})$ and $det (𝑡 𝐼_{1} - 𝐶) =$ $𝑡 +$ $𝑎_{0} =$ $𝑝 (𝑡)$ .

Let $𝑛 \geq 2$ , assume the claim for $𝑛 - 1$ , and let $𝑀 = 𝑡 𝐼_{𝑛} - 𝐶$ . Row $𝑘$ of $𝑀$ has $- 1$ in column $𝑘 - 1$ (if $𝑘 \geq 2$ ), $𝑡$ in column $𝑘$ (if $𝑘 < 𝑛$ ), and $𝑎_{𝑘 - 1}$ in column $𝑛$ , plus an extra $𝑡$ in position $(𝑛, 𝑛)$ ; all other entries are $0$ . The first row is $(𝑡, 0, \dots, 0, 𝑎_{0})$ , so expanding along it,

det 𝑀 = 𝑡 det 𝑀_{\hat{11}} + {(- 1)}^{1 + 𝑛} 𝑎_{0} det 𝑀_{\hat{1 𝑛}} .

The matrix $𝑀_{\hat{11}}$ consists of rows and columns $2, \dots, 𝑛$ of $𝑀$ . Renumbering them as $1, \dots, 𝑛 - 1$ , its row $𝑘$ has $- 1$ in column $𝑘 - 1$ (if $𝑘 \geq 2$ ), $𝑡$ in column $𝑘$ (if $𝑘 < 𝑛 - 1$ ), and $𝑎_{𝑘}$ in its last column, plus an extra $𝑡$ in the last position. So $𝑀_{\hat{11}} =$ $𝑡 𝐼_{𝑛 - 1} -$ $𝐶^{'}$ , where $𝐶^{'}$ is the matrix of the proposition for the polynomial $𝑞 =$ $𝑎_{1} +$ $𝑎_{2} 𝑥 +$ $\dots +$ $𝑎_{𝑛 - 1} 𝑥^{𝑛 - 2} +$ $𝑥^{𝑛 - 1}$ . By the induction hypothesis, $det 𝑀_{\hat{11}} = 𝑞 (𝑡)$ .

The matrix $𝑀_{\hat{1 𝑛}}$ consists of rows $2, \dots, 𝑛$ and columns $1, \dots, 𝑛 - 1$ of $𝑀$ . Renumbered, its row $𝑘$ has $- 1$ in column $𝑘$ and $𝑡$ in column $𝑘 + 1$ (if $𝑘 + 1 \leq 𝑛 - 1$ ), and zeros elsewhere. It is upper triangular with every diagonal entry $- 1$ , so $det 𝑀_{\hat{1 𝑛}} =$ ${(- 1)}^{𝑛 - 1}$ by Proposition 5.3.15.

Therefore, by Definition 1.2.17,

\begin{aligned} det 𝑀 & = 𝑡 𝑞 (𝑡) + {(- 1)}^{1 + 𝑛} {(- 1)}^{𝑛 - 1} 𝑎_{0} = 𝑡 (𝑎_{1} + 𝑎_{2} 𝑡 + \dots + 𝑎_{𝑛 - 1} 𝑡^{𝑛 - 2} + 𝑡^{𝑛 - 1}) + 𝑎_{0} \\ = 𝑎_{0} + 𝑎_{1} 𝑡 + \dots + 𝑎_{𝑛 - 1} 𝑡^{𝑛 - 1} + 𝑡^{𝑛} = 𝑝 (𝑡), \end{aligned}

since ${(- 1)}^{1 + 𝑛} {(- 1)}^{𝑛 - 1} =$ ${(- 1)}^{2 𝑛} =$ $1$ . Finally, with $𝑡 = 0$ , $det (- 𝐶) =$ $𝑝 (0) =$ $𝑎_{0}$ , and $det (- 𝐶) =$ ${(- 1)}^{𝑛} det 𝐶$ by Exercise 5.1.5, so $det 𝐶 = {(- 1)}^{𝑛} 𝑎_{0}$ . □

Proof (by row operations).standard

Uses. Corollary 5.4.15 (Rows), Lemma 5.5.2 (A row or column with one nonzero entry), Proposition 5.3.15 (Triangular matrices), Definition 1.2.17 (Evaluation)

Hint 1. Use the

- 1

below each

𝑡

to clear the

𝑡

: add

𝑡

times row

𝑘 + 1

to row

𝑘

. In which order should the rows be processed?

Hint 2. Work from the bottom up. Track the last entry of each row: if

𝑞_{𝑘 + 1}

is the last entry of the new row

𝑘 + 1

, the new last entry of row

𝑘

𝑎_{𝑘 - 1} + 𝑡 𝑞_{𝑘 + 1}

Hint 3. At the end, row

1

(0, \dots, 0, 𝑝 (𝑡))

. Expand along it.

Sketch. For

𝑘 = 𝑛 - 1, 𝑛 - 2, \dots, 1

, add

𝑡

times the current row

𝑘 + 1

to row

𝑘

. This clears the

𝑡

in position

(𝑘, 𝑘)

and makes the last entry of row

𝑘

equal to

𝑞_{𝑘} =

𝑎_{𝑘 - 1} +

𝑡 𝑞_{𝑘 + 1}

, where

𝑞_{𝑛} = 𝑡 + 𝑎_{𝑛 - 1}

; so

𝑞_{1} = 𝑝 (𝑡)

by Horner’s scheme. The determinant is unchanged, row

1

becomes

(0, \dots, 0, 𝑝 (𝑡))

, and the minor of its last entry is

- 𝐼_{𝑛 - 1}

. So

det (𝑡 𝐼_{𝑛} - 𝐶) =

{(- 1)}^{1 + 𝑛} 𝑝 (𝑡) {(- 1)}^{𝑛 - 1} =

𝑝 (𝑡)

For $𝑛 = 1$ both sides are $𝑡 + 𝑎_{0}$ , so let $𝑛 \geq 2$ and $𝑀 = 𝑡 𝐼_{𝑛} - 𝐶$ . Put $𝑞_{𝑛} = 𝑡 + 𝑎_{𝑛 - 1}$ and, for $𝑘 = 𝑛 - 1, \dots, 1$ , $𝑞_{𝑘} =$ $𝑎_{𝑘 - 1} +$ $𝑡 𝑞_{𝑘 + 1}$ . Then

𝑞_{1} = 𝑎_{0} + 𝑡 (𝑎_{1} + 𝑡 (𝑎_{2} + \dots + 𝑡 (𝑎_{𝑛 - 1} + 𝑡))) = 𝑝 (𝑡)

by expanding the nested products (Horner’s scheme).

For $𝑘 = 𝑛 - 1, 𝑛 - 2, \dots, 1$ in this order, add $𝑡$ times the current row $𝑘 + 1$ to row $𝑘$ . We claim that afterwards, for each $𝑘 \geq 2$ , row $𝑘$ has $- 1$ in column $𝑘 - 1$ , $𝑞_{𝑘}$ in column $𝑛$ , and zeros elsewhere, and row $1$ is $(0, \dots, 0, 𝑞_{1})$ . Row $𝑛$ is never changed, and it has $- 1$ in column $𝑛 - 1$ and $𝑞_{𝑛} = 𝑡 + 𝑎_{𝑛 - 1}$ in column $𝑛$ . Suppose row $𝑘 + 1$ already has its final form, with $- 1$ in column $𝑘$ and $𝑞_{𝑘 + 1}$ in column $𝑛$ . Row $𝑘$ of $𝑀$ has $- 1$ in column $𝑘 - 1$ (if $𝑘 \geq 2$ ), $𝑡$ in column $𝑘$ , and $𝑎_{𝑘 - 1}$ in column $𝑛$ . Adding $𝑡$ times row $𝑘 + 1$ changes only columns $𝑘$ and $𝑛$ : the entry in column $𝑘$ becomes $𝑡 + 𝑡 (- 1) = 0$ , and the entry in column $𝑛$ becomes $𝑎_{𝑘 - 1} +$ $𝑡 𝑞_{𝑘 + 1} =$ $𝑞_{𝑘}$ . This proves the claim. Each operation adds a multiple of one row to another, so the determinant is unchanged (Corollary 5.4.15).

In the final matrix, row $1$ has the single nonzero entry $𝑞_{1} = 𝑝 (𝑡)$ , in column $𝑛$ . Deleting row $1$ and column $𝑛$ leaves the matrix whose row $𝑘 - 1$ is $- 𝐞_{𝑘 - 1}^{𝖳}$ for $𝑘 = 2, \dots, 𝑛$ , that is, $- 𝐼_{𝑛 - 1}$ , with determinant ${(- 1)}^{𝑛 - 1}$ (Proposition 5.3.15). By Lemma 5.5.2,

det 𝑀 = {(- 1)}^{1 + 𝑛} 𝑝 (𝑡) {(- 1)}^{𝑛 - 1} = 𝑝 (𝑡),

as desired. The value of $det 𝐶$ follows as in the first proof. □

So every monic polynomial of degree $𝑛$ arises as $𝑡 \mapsto det (𝑡 𝐼_{𝑛} - 𝐶)$ for some $𝐶 \in 𝐹^{𝑛 \times 𝑛}$ . In Section 7.3, $det (𝑡 𝐼_{𝑛} - 𝐴)$ becomes the characteristic polynomial of $𝐴$ , and $𝐶$ (or its transpose, which has the same determinant by Theorem 5.4.14; conventions differ) is called the companion matrix of $𝑝$ . There the identity of the proposition is upgraded to an identity in $𝐹 [𝑥]$ .

5.5.5The Vandermonde determinant

Recall from Definition 3.4.22 that for $𝑐_{0}, \dots, 𝑐_{𝑛} \in 𝐹$ the Vandermonde matrix $𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛}) \in$ $𝐹^{(𝑛 + 1) \times (𝑛 + 1)}$ has row $𝑖 + 1$ equal to $(1, 𝑐_{𝑖}, 𝑐_{𝑖}^{2}, \dots, 𝑐_{𝑖}^{𝑛})$ . In Section 3.4 we showed that it is invertible when the $𝑐_{𝑖}$ are distinct (Theorem 3.4.24), by an argument about roots of polynomials. Now we compute its determinant.

Theorem 5.5.21 (The Vandermonde determinant). Let $𝑛 \geq 0$ and $𝑐_{0}, 𝑐_{1}, \dots, 𝑐_{𝑛} \in 𝐹$ . Then

det 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛}) = det (\begin{matrix} 1 & 𝑐_{0} & 𝑐_{0}^{2} & \dots & 𝑐_{0}^{𝑛} \\ 1 & 𝑐_{1} & 𝑐_{1}^{2} & \dots & 𝑐_{1}^{𝑛} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & 𝑐_{𝑛} & 𝑐_{𝑛}^{2} & \dots & 𝑐_{𝑛}^{𝑛} \end{matrix}) = \prod_{0 \leq 𝑖 < 𝑗 \leq 𝑛} (𝑐_{𝑗} - 𝑐_{𝑖}) .

In particular, $𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛})$ is invertible if and only if $𝑐_{0}, \dots, 𝑐_{𝑛}$ are distinct.

For $𝑛 = 0$ both sides are $1$ (the product is empty). For $𝑛 = 1$ , $det (\begin{matrix} 1 & 𝑐_{0} \\ 1 & 𝑐_{1} \end{matrix}) =$ $𝑐_{1} -$ $𝑐_{0}$ , and for $𝑛 = 2$ the product is $(𝑐_{1} - 𝑐_{0}) (𝑐_{2} - 𝑐_{0}) (𝑐_{2} - 𝑐_{1})$ , which matches the rule of Sarrus after expanding. The last sentence follows from the formula: by Proposition 1.1.17 the product is nonzero exactly when every factor is, and then Theorem 5.4.7 applies.

The first proof creates the factors $𝑐_{𝑗} - 𝑐_{0}$ with column operations. The following technique describes the move.

Technique 5.5.22 (Expose a factor with row and column operations). When the entries of a matrix are polynomial expressions in some parameters and the determinant is expected to have a factor such as $𝑐_{1} - 𝑐_{0}$ , look for replacements that make this factor appear in every entry of one row (or column). Replacements do not change the determinant (Corollary 5.4.15, Lemma 5.1.8), and linearity in that row then pulls the factor out. Choose the replacements so that they also create zeros, so that a cofactor expansion reduces the size at the same step. Repeating this, usually by induction on the size, peels off the factors one at a time.

Reach for it when consecutive columns (or rows) are related by a common multiplier, as the powers $𝑐^{𝑘}$ and $𝑐^{𝑘 + 1}$ are related by $𝑐$ , or when all rows have a common sum. The canonical example is the first proof of Theorem 5.5.21. Example 5.4.24 and Exercise 5.4.44 used the same idea with row sums.

Used in 7 places

Theorem 5.5.21, Exercise 5.5.42, Exercise 5.5.53, Exercise 5.6.6, Exercise 5.6.7, Problem 5.10, Problem 5.19.

Proof (by column operations).standard

Uses. Lemma 5.1.8 (Column replacement), Lemma 5.5.2 (A row or column with one nonzero entry), Corollary 5.4.15 (Rows), induction on $𝑛$

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

Hint 1. Use the first node

𝑐_{0}

: subtract

𝑐_{0}

times each column from the column to its right. In which order must this be done so that each step uses an unchanged column?

Hint 2. Process the columns from right to left. Row

1

becomes

(1, 0, \dots, 0)

, and in every other row

𝑖 + 1

, each entry except the first acquires the factor

𝑐_{𝑖} - 𝑐_{0}

Hint 3. After expanding along row

1

and pulling out the factors, what remains is a smaller Vandermonde matrix.

Sketch. For

𝑚 = 𝑛 + 1, 𝑛, \dots, 2

, subtract

𝑐_{0}

times column

𝑚 - 1

from column

𝑚

. Row

𝑖 + 1

becomes

(1, (𝑐_{𝑖} - 𝑐_{0}), (𝑐_{𝑖} - 𝑐_{0}) 𝑐_{𝑖}, \dots, (𝑐_{𝑖} - 𝑐_{0}) 𝑐_{𝑖}^{𝑛 - 1})

, and row

1

becomes

(1, 0, \dots, 0)

. Expanding along row

1

and pulling

𝑐_{𝑖} - 𝑐_{0}

out of row

𝑖

of the minor gives

det 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛}) =

\prod_{𝑖 = 1}^{𝑛} (𝑐_{𝑖} - 𝑐_{0}) det 𝑉 (𝑐_{1}, \dots, 𝑐_{𝑛})

, and induction finishes.

We induct on $𝑛$ . For $𝑛 = 0$ , both sides equal $1$ . Let $𝑛 \geq 1$ , assume the formula for $𝑛$ nodes, and let $𝑉 = 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛})$ . Number the columns $1, \dots, 𝑛 + 1$ , so that the entry of column $𝑚$ in row $𝑖 + 1$ is $𝑐_{𝑖}^{𝑚 - 1}$ .

For $𝑚 = 𝑛 + 1, 𝑛, \dots, 2$ , in this order, subtract $𝑐_{0}$ times column $𝑚 - 1$ from column $𝑚$ . When column $𝑚$ is changed, column $𝑚 - 1$ has not been changed yet, so the new entry of column $𝑚$ in row $𝑖 + 1$ is

𝑐_{𝑖}^{𝑚 - 1} - 𝑐_{0} 𝑐_{𝑖}^{𝑚 - 2} = (𝑐_{𝑖} - 𝑐_{0}) 𝑐_{𝑖}^{𝑚 - 2} .

Each step adds a multiple of one column to another, so the determinant does not change (Lemma 5.1.8). The new matrix $𝑉^{'}$ has first row $(1, 0, \dots, 0)$ , since $𝑐_{0} - 𝑐_{0} = 0$ , and for $𝑖 = 1, \dots, 𝑛$ its row $𝑖 + 1$ is

(1, (𝑐_{𝑖} - 𝑐_{0}), (𝑐_{𝑖} - 𝑐_{0}) 𝑐_{𝑖}, \dots, (𝑐_{𝑖} - 𝑐_{0}) 𝑐_{𝑖}^{𝑛 - 1}) .

By Lemma 5.5.2 applied to row $1$ , $det 𝑉 = det 𝑉_{\hat{11}}^{'}$ . Row $𝑖$ of $𝑉_{\hat{11}}^{'}$ is $(𝑐_{𝑖} - 𝑐_{0}) (1, 𝑐_{𝑖}, \dots, 𝑐_{𝑖}^{𝑛 - 1})$ , so pulling the factor $𝑐_{𝑖} - 𝑐_{0}$ out of each row (Corollary 5.4.15) gives

det 𝑉 = (𝑐_{1} - 𝑐_{0}) (𝑐_{2} - 𝑐_{0}) \dots (𝑐_{𝑛} - 𝑐_{0}) det 𝑉 (𝑐_{1}, \dots, 𝑐_{𝑛}) .

By the induction hypothesis, $det 𝑉 (𝑐_{1}, \dots, 𝑐_{𝑛}) =$ $\prod_{1 \leq 𝑖 < 𝑗 \leq 𝑛} (𝑐_{𝑗} - 𝑐_{𝑖})$ . The factors $𝑐_{𝑗} - 𝑐_{0}$ are the factors of $\prod_{0 \leq 𝑖 < 𝑗 \leq 𝑛} (𝑐_{𝑗} - 𝑐_{𝑖})$ with $𝑖 = 0$ , so $det 𝑉$ is the full product, as desired. □

Intuition (Where the factors come from). Regard the last node

𝑐_{𝑛}

as a variable

𝑡

, and the other nodes as fixed. Expanding

det 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛 - 1}, 𝑡)

along the last row

(1, 𝑡, 𝑡^{2}, \dots, 𝑡^{𝑛})

shows that it is a polynomial in

𝑡

of degree at most

𝑛

. If

𝑡 = 𝑐_{𝑖}

for some

𝑖 < 𝑛

, then two rows are equal and the determinant is

0

. So when the nodes

𝑐_{0}, \dots, 𝑐_{𝑛 - 1}

are distinct, the polynomial has these

𝑛

roots, and a polynomial of degree at most

𝑛

with

𝑛

prescribed roots is pinned down by one more number, its coefficient of

𝑡^{𝑛}

. That coefficient is the cofactor of the entry

𝑡^{𝑛}

, a smaller Vandermonde determinant. The first proof found the factors by computing; this argument predicts them from the places where the matrix collapses.

To make this precise, we need the fact that a polynomial is determined by its roots and its leading coefficient. Polynomials cannot be multiplied until Section 7.1, so we state it for values.

Lemma 5.5.23 (A polynomial with prescribed roots). Let $𝑛 \geq 0$ , let $𝑃 \in {𝐹 [𝑥]}_{\leq 𝑛}$ , and let $𝑎$ be its coefficient of $𝑥^{𝑛}$ . If $𝑐_{1}, \dots, 𝑐_{𝑛} \in 𝐹$ are distinct and $𝑃 (𝑐_{1}) =$ $\dots =$ $𝑃 (𝑐_{𝑛}) =$ $0$ , then

𝑃 (𝑡) = 𝑎 (𝑡 - 𝑐_{1}) (𝑡 - 𝑐_{2}) \dots (𝑡 - 𝑐_{𝑛}) for every 𝑡 \in 𝐹 .

Proof.standard

Uses. Lemma 3.4.23 (Too many roots), Proposition 1.2.18 (Degree and evaluation versus the operations), Definition 1.2.17 (Evaluation), induction on $𝑛$

Hint 1. First show that

𝑡 \mapsto

𝑎 (𝑡 - 𝑐_{1}) \dots (𝑡 - 𝑐_{𝑛})

is the evaluation of a polynomial

𝑄 \in {𝐹 [𝑥]}_{\leq 𝑛}

whose coefficient of

𝑥^{𝑛}

𝑎

Hint 2. Then

𝑃 - 𝑄

has degree at most

𝑛 - 1

. How many roots does it have?

Sketch. Multiplying out one factor at a time shows

(𝑡 - 𝑐_{1}) \dots (𝑡 - 𝑐_{𝑛}) =

𝑡^{𝑛} +

𝑒_{𝑛 - 1} 𝑡^{𝑛 - 1} +

\dots +

𝑒_{0}

for scalars

𝑒_{𝑘}

that do not depend on

𝑡

. So

𝑎 \prod (𝑡 - 𝑐_{𝑘}) =

𝑄 (𝑡)

for some

𝑄 \in {𝐹 [𝑥]}_{\leq 𝑛}

with coefficient

𝑎

𝑥^{𝑛}

. Then

𝑃 - 𝑄 \in {𝐹 [𝑥]}_{\leq 𝑛 - 1}

vanishes at the

𝑛

distinct points

𝑐_{𝑘}

, so

𝑃 = 𝑄

by Lemma 3.4.23.

For $𝑛 = 0$ , $𝑃$ is the constant $𝑎$ and the product is empty, so there is nothing to prove. Let $𝑛 \geq 1$ .

First, there are $𝑒_{0}, \dots, 𝑒_{𝑛 - 1} \in 𝐹$ , depending only on $𝑐_{1}, \dots, 𝑐_{𝑛}$ , such that

(𝑡 - 𝑐_{1}) \dots (𝑡 - 𝑐_{𝑛}) = 𝑡^{𝑛} + 𝑒_{𝑛 - 1} 𝑡^{𝑛 - 1} + \dots + 𝑒_{1} 𝑡 + 𝑒_{0} for every 𝑡 \in 𝐹 .

We show this by induction on the number $𝑚$ of factors. For $𝑚 = 1$ , take $𝑒_{0} = - 𝑐_{1}$ . If $(𝑡 - 𝑐_{1}) \dots (𝑡 - 𝑐_{𝑚}) =$ $𝑡^{𝑚} +$ $\sum_{𝑘 < 𝑚} 𝑒_{𝑘} 𝑡^{𝑘}$ , then multiplying by $𝑡 - 𝑐_{𝑚 + 1}$ and distributing gives

𝑡^{𝑚 + 1} + \sum_{𝑘 < 𝑚} 𝑒_{𝑘} 𝑡^{𝑘 + 1} - 𝑐_{𝑚 + 1} 𝑡^{𝑚} - \sum_{𝑘 < 𝑚} 𝑐_{𝑚 + 1} 𝑒_{𝑘} 𝑡^{𝑘},

which is $𝑡^{𝑚 + 1}$ plus a combination of $1, 𝑡, \dots, 𝑡^{𝑚}$ with coefficients that do not depend on $𝑡$ .

Let $𝑄 =$ $𝑎 𝑒_{0} +$ $𝑎 𝑒_{1} 𝑥 +$ $\dots +$ $𝑎 𝑒_{𝑛 - 1} 𝑥^{𝑛 - 1} +$ $𝑎 𝑥^{𝑛} \in$ ${𝐹 [𝑥]}_{\leq 𝑛}$ . Then $𝑄 (𝑡) =$ $𝑎 (𝑡 - 𝑐_{1}) \dots (𝑡 - 𝑐_{𝑛})$ for every $𝑡$ . The coefficients of $𝑥^{𝑛}$ in $𝑃$ and $𝑄$ are both $𝑎$ , so $𝑅 = 𝑃 - 𝑄$ lies in ${𝐹 [𝑥]}_{\leq 𝑛 - 1}$ , and for each $𝑘$ , $𝑅 (𝑐_{𝑘}) =$ $𝑃 (𝑐_{𝑘}) -$ $𝑄 (𝑐_{𝑘}) =$ $0 -$ $0 =$ $0$ (Proposition 1.2.18), because the product $𝑄 (𝑐_{𝑘})$ contains the factor $𝑐_{𝑘} - 𝑐_{𝑘} = 0$ . So $𝑅$ has degree at most $𝑛 - 1$ and vanishes at the $𝑛$ distinct points $𝑐_{1}, \dots, 𝑐_{𝑛}$ . By Lemma 3.4.23 (with $𝑛 - 1$ in place of $𝑛$ ), $𝑅 = 𝟎$ . Hence $𝑃 = 𝑄$ , and $𝑃 (𝑡) =$ $𝑄 (𝑡) =$ $𝑎 (𝑡 - 𝑐_{1}) \dots (𝑡 - 𝑐_{𝑛})$ for every $𝑡$ . □

Once polynomials can be multiplied, the lemma says $𝑃 =$ $𝑎 (𝑥 - 𝑐_{1}) \dots (𝑥 - 𝑐_{𝑛})$ in $𝐹 [𝑥]$ ; it is the factor theorem of Section 7.1 (compare Proposition 7.1.22).

Technique 5.5.24 (Polynomial identity arguments). To prove that two quantities depending on a scalar $𝑡$ are equal, show that both are values $𝑃 (𝑡)$ and $𝑄 (𝑡)$ of polynomials $𝑃, 𝑄 \in {𝐹 [𝑥]}_{\leq 𝑛}$ , and then show $𝑃 = 𝑄$ by counting. Two polynomials of degree at most $𝑛$ that agree at $𝑛 + 1$ distinct points are equal, since their difference has $𝑛 + 1$ roots (Lemma 3.4.23). When zeros are easier to find than values, use Lemma 5.5.23 instead: a polynomial of degree at most $𝑛$ with $𝑛$ known distinct roots is determined by its coefficient of $𝑥^{𝑛}$ . Then the proof splits into independent checks: a bound on the degree, the roots, and one coefficient.

Determinants are a rich source of such polynomials. If a parameter $𝑡$ occurs in only one row, the expansion along that row (Theorem 5.5.3) shows that the determinant is a polynomial in $𝑡$ ; if the top power of $𝑡$ occurs in only one entry of that row, as in $(1, 𝑡, \dots, 𝑡^{𝑛})$ , its coefficient is a single cofactor. More generally, see Technique 5.3.18. Roots come from coincidences: a value of $𝑡$ that makes two rows equal, or the rows dependent, is a root.

Reach for it when the expected answer is a product of linear factors, or when an identity is easy to check for many special values of a parameter. Two pitfalls: forgetting the leading coefficient (roots determine a polynomial only up to a scalar factor; see Exercise 5.5.42), and counting roots that are not distinct. Over an infinite field, an identity between polynomials in $𝑡$ that holds for all but finitely many $𝑡$ holds for all $𝑡$ . This extends identities from invertible matrices to all matrices by way of $𝐴 + 𝑡 𝐼_{𝑛}$ (Exercise 5.5.41). The canonical example is the second proof of Theorem 5.5.21. The technique returns in Section 7.3.

Used in 17 places and 3 practice exercises

Theorem 5.5.21, Exercise 5.5.40, Exercise 5.5.41, Exercise 5.5.42, Exercise 5.5.45, Exercise 5.6.9, Exercise 5.6.10, Problem 5.18, Proposition 7.3.11, Proposition 7.3.22, Exercise 7.3.48, Exercise 7.3.49, Theorem 7.5.22, Lemma 7.6.21, Exercise 7.7.14, Proposition B.1.28, Exercise B.1.45; 3 practice exercises.

Proof of Theorem 5.5.21 (by a polynomial identity).standard

Uses. Theorem 5.5.3 (Cofactor expansion), Lemma 5.5.23 (A polynomial with prescribed roots), Corollary 5.4.15 (Rows), induction on $𝑛$

Techniques. Polynomial identity arguments (Technique 5.5.24)

Hint 1. Induct on

𝑛

. Fix

𝑐_{0}, \dots, 𝑐_{𝑛 - 1}

and consider

𝑓 (𝑡) =

det 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛 - 1}, 𝑡)

as a function of

𝑡

Hint 2. Expand along the last row to see that

𝑓

is a polynomial of degree at most

𝑛

. What is its coefficient of

𝑡^{𝑛}

? Where does

𝑓

vanish?

Hint 3. If

𝑐_{0}, \dots, 𝑐_{𝑛 - 1}

are distinct, Lemma 5.5.23 applies. If not, both sides are

0

Sketch. Let

𝑓 (𝑡) =

det 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛 - 1}, 𝑡)

. Expanding along the last row,

𝑓

is a polynomial of degree at most

𝑛

whose coefficient of

𝑡^{𝑛}

is the cofactor of the entry

𝑡^{𝑛}

, namely

𝐷 =

det 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛 - 1})

. It vanishes at

𝑐_{0}, \dots, 𝑐_{𝑛 - 1}

(equal rows). If these are distinct, Lemma 5.5.23 gives

𝑓 (𝑡) =

𝐷 \prod_{𝑖 < 𝑛} (𝑡 - 𝑐_{𝑖})

; put

𝑡 = 𝑐_{𝑛}

and use induction for

𝐷

. If two of them coincide, both sides are

0

We induct on $𝑛$ ; for $𝑛 = 0$ both sides are $1$ . Let $𝑛 \geq 1$ , and assume the formula for $𝑛$ nodes. Fix $𝑐_{0}, \dots, 𝑐_{𝑛 - 1}$ , and for $𝑡 \in 𝐹$ let $𝑓 (𝑡) =$ $det 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛 - 1}, 𝑡)$ .

$𝑓$ is a polynomial. The last row of $𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛 - 1}, 𝑡)$ is $(1, 𝑡, 𝑡^{2}, \dots, 𝑡^{𝑛})$ , with $𝑡^{𝑘}$ in column $𝑘 + 1$ . Expanding along it (Theorem 5.5.3),

𝑓 (𝑡) = \sum_{𝑘 = 0}^{𝑛} {(- 1)}^{(𝑛 + 1) + (𝑘 + 1)} 𝑡^{𝑘} 𝑚_{𝑘},

where $𝑚_{𝑘}$ is the determinant of the matrix obtained by deleting the last row and column $𝑘 + 1$ . These matrices do not involve the last row, so the $𝑚_{𝑘}$ do not depend on $𝑡$ . Hence $𝑓 (𝑡) = 𝑃 (𝑡)$ for the polynomial $𝑃 =$ $\sum_{𝑘 = 0}^{𝑛} {(- 1)}^{𝑛 + 𝑘} 𝑚_{𝑘} 𝑥^{𝑘} \in$ ${𝐹 [𝑥]}_{\leq 𝑛}$ . Its coefficient of $𝑥^{𝑛}$ is $𝑚_{𝑛}$ , and deleting the last row and the last column of $𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛 - 1}, 𝑡)$ leaves $𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛 - 1})$ , so $𝑚_{𝑛} = 𝐷$ , where $𝐷 =$ $det 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛 - 1})$ .

Roots. For $𝑖 < 𝑛$ , the matrix $𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛 - 1}, 𝑐_{𝑖})$ has rows $𝑖 + 1$ and $𝑛 + 1$ equal, so $𝑃 (𝑐_{𝑖}) =$ $𝑓 (𝑐_{𝑖}) =$ $0$ (Corollary 5.4.15).

Conclusion. Suppose first that $𝑐_{0}, \dots, 𝑐_{𝑛 - 1}$ are distinct. By Lemma 5.5.23, $𝑓 (𝑡) =$ $𝐷 (𝑡 - 𝑐_{0}) \dots (𝑡 - 𝑐_{𝑛 - 1})$ for every $𝑡 \in 𝐹$ . Taking $𝑡 = 𝑐_{𝑛}$ and using the induction hypothesis for $𝐷$ ,

det 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛}) = \prod_{0 \leq 𝑖 < 𝑗 \leq 𝑛 - 1} (𝑐_{𝑗} - 𝑐_{𝑖}) \cdot \prod_{𝑖 = 0}^{𝑛 - 1} (𝑐_{𝑛} - 𝑐_{𝑖}) = \prod_{0 \leq 𝑖 < 𝑗 \leq 𝑛} (𝑐_{𝑗} - 𝑐_{𝑖}) .

If instead $𝑐_{𝑖} = 𝑐_{𝑘}$ for some $𝑖 < 𝑘 < 𝑛$ , then $𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛})$ has two equal rows, so its determinant is $0$ , and the product is $0$ as well, since it contains the factor $𝑐_{𝑘} - 𝑐_{𝑖} = 0$ . □

Intuition (Two proofs compared). The first proof is a computation organized by induction: column operations expose all factors that involve

𝑐_{0}

at once, and what is left is a smaller Vandermonde matrix. It is the proof to imitate for determinants with a similar pattern of powers. The second proof hardly computes. It identifies the determinant as a polynomial in one node, locates its roots by asking when the matrix collapses, and pins down the one remaining constant with a cofactor. It explains why the answer is a product of differences: the factor

𝑐_{𝑗} - 𝑐_{𝑖}

is there because the matrix becomes singular when

𝑐_{𝑗} = 𝑐_{𝑖}

. The second proof needs the nodes

𝑐_{0}, \dots, 𝑐_{𝑛 - 1}

to be distinct and treats the degenerate case separately, while the first does not split into cases at all.

Remark 5.5.25 (Back to permutations and interpolation). The polynomial $Δ (𝐱) =$ $\prod_{1 \leq 𝑖 < 𝑗 \leq 𝑛} (𝑥_{𝑗} - 𝑥_{𝑖})$ of Approach 1: a product of differences is $det 𝑉 (𝑥_{1}, \dots, 𝑥_{𝑛})$ . Rearranging the entries of $𝐱$ by $𝜎$ rearranges the rows of $𝑉$ : row $𝑘$ of $𝑉 (𝑥_{𝜎 (1)}, \dots, 𝑥_{𝜎 (𝑛)})$ is row $𝜎 (𝑘)$ of $𝑉 (𝑥_{1}, \dots, 𝑥_{𝑛})$ , so $𝑉 (𝐱^{𝜎}) =$ $𝐸_{𝜎}^{𝖳} 𝑉 (𝐱)$ , and $Δ (𝐱^{𝜎}) =$ $sgn (𝜎) Δ (𝐱)$ . For a transposition this is Lemma 5.2.20. This is not a new proof of Theorem 5.2.18, since the existence of $det$ relied on it, but it explains why $Δ$ was the right invariant.

The theorem also completes the second proof of invertibility promised in Section 3.4. For distinct nodes, $det 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛}) \neq$ $0$ , so $𝑉$ is invertible and the interpolation problem has exactly one solution.

Exercise 5.5.26.routine

(a)Show that $det 𝑉 (1, 2, \dots, 𝑛) =$ $1! \cdot 2! \dots (𝑛 - 1)!$ , and evaluate it for $𝑛 = 4$ .
(b)Compute $det 𝑉 (0, 1, 2, 3, 4)$ in $𝔽_{5}$ . Deduce that every function $𝑔 : 𝔽_{5} \to 𝔽_{5}$ is of the form $𝑡 \mapsto 𝑃 (𝑡)$ for exactly one $𝑃 \in 𝔽_{5} {[𝑥]}_{\leq 4}$ .

Solution.

Uses. Theorem 5.5.21 (The Vandermonde determinant), Theorem 5.4.7 (Invertibility and the determinant), Theorem 3.4.24 (Polynomial interpolation)

Hint 1. Group the factors

𝑗 - 𝑖

of the product by their larger index

𝑗

Hint 2. For (b), the nodes

0, 1, 2, 3, 4

are all the elements of

𝔽_{5}

. Reduce the integer from (a) modulo

5

, or compute directly. Then think of

𝑔

as a list of

5

values.

Sketch. (a) For fixed

𝑗

, the factors

𝑗 - 𝑖

with

1 \leq 𝑖 < 𝑗

are

𝑗 - 1, 𝑗 - 2, \dots, 1

, with product

(𝑗 - 1)!

. So the determinant is

\prod_{𝑗 = 2}^{𝑛} (𝑗 - 1)! =

1! \dots (𝑛 - 1)!

, which is

12

for

𝑛 = 4

. (b) The same grouping gives

1! 2! 3! 4! = 288 = 3

𝔽_{5}

, which is nonzero. So

𝑉

is invertible, and for any values

𝑔 (0), \dots, 𝑔 (4)

there is exactly one

𝑃

of degree at most

4

taking them.

(a) With $𝑐_{𝑘} = 𝑘 + 1$ , Theorem 5.5.21 gives $det 𝑉 (1, \dots, 𝑛) =$ $\prod_{1 \leq 𝑖 < 𝑗 \leq 𝑛} (𝑗 - 𝑖)$ . For a fixed $𝑗$ , the factors with $𝑖 = 1, \dots, 𝑗 - 1$ are $𝑗 - 1, 𝑗 - 2, \dots, 1$ , whose product is $(𝑗 - 1)!$ . So

det 𝑉 (1, \dots, 𝑛) = \prod_{𝑗 = 2}^{𝑛} (𝑗 - 1)! = 1! \cdot 2! \dots (𝑛 - 1)! .

For $𝑛 = 4$ this is $1 \cdot 2 \cdot 6 = 12$ .

(b) By Theorem 5.5.21, $det 𝑉 (0, 1, 2, 3, 4) =$ $\prod_{0 \leq 𝑖 < 𝑗 \leq 4} (𝑗 - 𝑖)$ , computed in $𝔽_{5}$ . Grouping by $𝑗$ as in (a), this is $1! \cdot 2! \cdot 3! \cdot 4! =$ $1 \cdot$ $2 \cdot$ $6 \cdot$ $24 =$ $288$ , and $288 = 57 \cdot 5 + 3$ , so the determinant is $3 \neq 0$ in $𝔽_{5}$ . (Each factor $𝑗 - 𝑖$ lies in ${1, 2, 3, 4}$ , so the product is nonzero by Proposition 1.1.17, without computing it.) So $𝑉 = 𝑉 (0, 1, 2, 3, 4)$ is invertible by Theorem 5.4.7.

Given $𝑔 : 𝔽_{5} \to 𝔽_{5}$ , a polynomial $𝑃 = \sum_{𝑘 = 0}^{4} 𝑎_{𝑘} 𝑥^{𝑘}$ satisfies $𝑃 (𝑡) = 𝑔 (𝑡)$ for all $𝑡 \in 𝔽_{5}$ if and only if $𝑉 𝐚 =$ $(𝑔 (0), 𝑔 (1), 𝑔 (2), 𝑔 (3), 𝑔 (4))$ , where $𝐚 = (𝑎_{0}, \dots, 𝑎_{4})$ . Since $𝑉$ is invertible, this system has exactly one solution. (This is Theorem 3.4.24 with all five elements of $𝔽_{5}$ as nodes.)

5.5.6Rank-one updates Beyond 21-242

Not covered in lecture. The matrix determinant lemma is a standard application of the adjugate in statistics and numerical linear algebra.

Remark 5.5.11 computed $det (𝐵 + 𝑡 𝑈_{𝑖 𝑗})$ , where $𝑈_{𝑖 𝑗} = 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}$ has rank one. The same computation works for every matrix of rank one, that is, for every $𝐮 𝐯^{𝖳}$ with $𝐮, 𝐯 \in 𝐹^{𝑛}$ .

Theorem 5.5.27 (Matrix determinant lemma). Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ and $𝐮, 𝐯 \in 𝐹^{𝑛}$ . Then

det (𝐴 + 𝐮 𝐯^{𝖳}) = det 𝐴 + 𝐯^{𝖳} (adj 𝐴) 𝐮 .

In particular, if $𝐴$ is invertible, then $det (𝐴 + 𝐮 𝐯^{𝖳}) =$ $det 𝐴 (1 + 𝐯^{𝖳} 𝐴^{- 1} 𝐮)$ .

Proof (by multilinearity).standard

Uses. Definition 2.4.1 (Matrix product), Definition 5.1.1 (Determinant function), Lemma 5.5.8 (Replacing a row or a column), Definition 5.5.6 (Cofactors, cofactor matrix, adjugate), Theorem 5.5.9 (The adjugate and the inverse)

Techniques. Expand by multilinearity (Technique 5.1.7)

Hint 1. Column

𝑗

𝐮 𝐯^{𝖳}

𝑣_{𝑗} 𝐮

. Expand

det (𝐚_{1} + 𝑣_{1} 𝐮, \dots, 𝐚_{𝑛} + 𝑣_{𝑛} 𝐮)

by multilinearity. Which terms vanish?

Hint 2. Every term that uses

𝐮

in two columns vanishes. The terms that use

𝐮

in exactly one column

𝑗

are

𝑣_{𝑗} det 𝐴_{𝑗} (𝐮)

; evaluate them with Lemma 5.5.8.

Sketch. Expanding every column

𝐚_{𝑗} + 𝑣_{𝑗} 𝐮

gives a sum over the sets

𝑆

of columns in which

𝐮

is chosen. Sets with two or more elements give a matrix with two columns equal to

𝐮

. So

det (𝐴 + 𝐮 𝐯^{𝖳}) =

det 𝐴 +

\sum_{𝑗} 𝑣_{𝑗} det 𝐴_{𝑗} (𝐮)

, and

det 𝐴_{𝑗} (𝐮) =

\sum_{𝑖} 𝑢_{𝑖} 𝑐_{𝑖 𝑗}

. The double sum

\sum_{𝑖, 𝑗} 𝑣_{𝑗} 𝑐_{𝑖 𝑗} 𝑢_{𝑖}

𝐯^{𝖳} 𝐶_{𝐴}^{𝖳} 𝐮

For $𝑛 = 1$ both sides are $𝑎 + 𝑣 𝑢$ , since $adj (𝑎) = (1)$ . Let $𝑛 \geq 2$ . Column $𝑗$ of $𝐮 𝐯^{𝖳}$ is $𝑣_{𝑗} 𝐮$ (Definition 2.4.1), so column $𝑗$ of $𝐴 + 𝐮 𝐯^{𝖳}$ is $𝐚_{𝑗} + 𝑣_{𝑗} 𝐮$ . Expanding by linearity in each column, $det (𝐴 + 𝐮 𝐯^{𝖳})$ is the sum, over all subsets $𝑆 \subseteq [𝑛]$ , of $(\prod_{𝑗 \in 𝑆} 𝑣_{𝑗}) det 𝐴_{𝑆}$ , where $𝐴_{𝑆}$ has column $𝐮$ in the positions $𝑗 \in 𝑆$ and column $𝐚_{𝑗}$ in the other positions. If $𝑆$ has two or more elements, then $𝐴_{𝑆}$ has two equal columns and $det 𝐴_{𝑆} = 0$ . The set $𝑆 = \emptyset$ contributes $det 𝐴$ , and $𝑆 = {𝑗}$ contributes $𝑣_{𝑗} det 𝐴_{𝑗} (𝐮)$ , where $𝐴_{𝑗} (𝐮)$ is $𝐴$ with column $𝑗$ replaced by $𝐮$ . By part (b) of Lemma 5.5.8, $det 𝐴_{𝑗} (𝐮) =$ $\sum_{𝑖} 𝑢_{𝑖} 𝑐_{𝑖 𝑗}$ , where the $𝑐_{𝑖 𝑗}$ are the cofactors of $𝐴$ . Hence

det (𝐴 + 𝐮 𝐯^{𝖳}) = det 𝐴 + \sum_{𝑗 = 1}^{𝑛} \sum_{𝑖 = 1}^{𝑛} 𝑣_{𝑗} 𝑐_{𝑖 𝑗} 𝑢_{𝑖} = det 𝐴 + 𝐯^{𝖳} 𝐶_{𝐴}^{𝖳} 𝐮,

since the $(𝑗, 𝑖)$ entry of $𝐶_{𝐴}^{𝖳} = adj 𝐴$ is $𝑐_{𝑖 𝑗}$ . If $𝐴$ is invertible, then $adj 𝐴 = (det 𝐴) 𝐴^{- 1}$ by Theorem 5.5.9, and the right side is $det 𝐴 +$ $det 𝐴 \cdot$ $𝐯^{𝖳} 𝐴^{- 1} 𝐮$ . □

Proof (by block matrices, for invertible $𝐴$ ).standard

Uses. Theorem 2.4.34 (Block multiplication), Theorem 5.4.26 (Block-triangular matrices), Theorem 5.4.10 (Multiplicativity)

Techniques. Block elimination (Technique 5.4.28)

Hint 1. Consider the

(𝑛 + 1) \times (𝑛 + 1)

matrix

𝑀 = (\begin{matrix} 𝐴 & - 𝐮 \\ 𝐯^{𝖳} & 1 \end{matrix})

, and compute

det 𝑀

in two ways.

Hint 2. Clear

𝐯^{𝖳}

using the entry

1

, or clear it using

𝐴

. Each is a multiplication by a block triangular matrix with determinant

1

Sketch. With

𝑀 = (\begin{matrix} 𝐴 & - 𝐮 \\ 𝐯^{𝖳} & 1 \end{matrix})

, block multiplication gives

(\begin{matrix} 𝐼_{𝑛} & 𝐮 \\ 0 & 1 \end{matrix}) 𝑀 =

(\begin{matrix} 𝐴 + 𝐮 𝐯^{𝖳} & 0 \\ 𝐯^{𝖳} & 1 \end{matrix})

and

(\begin{matrix} 𝐼_{𝑛} & 0 \\ - 𝐯^{𝖳} 𝐴^{- 1} & 1 \end{matrix}) 𝑀 =

(\begin{matrix} 𝐴 & - 𝐮 \\ 0 & 1 + 𝐯^{𝖳} 𝐴^{- 1} 𝐮 \end{matrix})

. Both multipliers have determinant

1

, so

det (𝐴 + 𝐮 𝐯^{𝖳}) =

det 𝑀 =

det 𝐴 (1 + 𝐯^{𝖳} 𝐴^{- 1} 𝐮)

Let $𝑀 =$ $(\begin{matrix} 𝐴 & - 𝐮 \\ 𝐯^{𝖳} & 1 \end{matrix}) \in$ $𝐹^{(𝑛 + 1) \times (𝑛 + 1)}$ . By Theorem 2.4.34,

(\begin{matrix} 𝐼_{𝑛} & 𝐮 \\ 0 & 1 \end{matrix}) 𝑀 = (\begin{matrix} 𝐴 + 𝐮 𝐯^{𝖳} & - 𝐮 + 𝐮 \\ 𝐯^{𝖳} & 1 \end{matrix}) = (\begin{matrix} 𝐴 + 𝐮 𝐯^{𝖳} & 0 \\ 𝐯^{𝖳} & 1 \end{matrix})

and

(\begin{matrix} 𝐼_{𝑛} & 0 \\ - 𝐯^{𝖳} 𝐴^{- 1} & 1 \end{matrix}) 𝑀 = (\begin{matrix} 𝐴 & - 𝐮 \\ - 𝐯^{𝖳} + 𝐯^{𝖳} & 𝐯^{𝖳} 𝐴^{- 1} 𝐮 + 1 \end{matrix}) = (\begin{matrix} 𝐴 & - 𝐮 \\ 0 & 1 + 𝐯^{𝖳} 𝐴^{- 1} 𝐮 \end{matrix}) .

The two multipliers are block triangular with diagonal blocks $𝐼_{𝑛}$ and $(1)$ , so they have determinant $1$ by Theorem 5.4.26. The right sides are block triangular as well. Taking determinants with Theorem 5.4.10 and Theorem 5.4.26,

det (𝐴 + 𝐮 𝐯^{𝖳}) = det 𝑀 = det 𝐴 (1 + 𝐯^{𝖳} 𝐴^{- 1} 𝐮),

as desired. □

The first proof is shorter, works for every $𝐴$ , and shows that $det (𝐴 + 𝑡 𝐮 𝐯^{𝖳}) =$ $det 𝐴 +$ $𝑡 𝐯^{𝖳} (adj 𝐴) 𝐮$ is affine in $𝑡$ . The second is an instance of Technique 5.4.28 and needs $𝐴^{- 1}$ . For example, let $𝐽 \in 𝐹^{𝑛 \times 𝑛}$ be the matrix of all $1$ s, so $𝐽 = 𝟏 𝟏^{𝖳}$ with $𝟏 = (1, \dots, 1)$ . For $𝑎, 𝑏 \in 𝐹$ , since $adj (𝑎 𝐼_{𝑛}) =$ $𝑎^{𝑛 - 1} 𝐼_{𝑛}$ ,

det (𝑎 𝐼_{𝑛} + 𝑏 𝐽) = 𝑎^{𝑛} + 𝑏 𝟏^{𝖳} 𝑎^{𝑛 - 1} 𝐼_{𝑛} 𝟏 = 𝑎^{𝑛 - 1} (𝑎 + 𝑛 𝑏) .

With $𝑎 = 𝑥 - 1$ and $𝑏 = 1$ this is Example 5.4.24 again.

Remark 5.5.28 (Derivatives of determinants). Let $𝐴 (𝑠)$ be an $𝑛 \times 𝑛$ matrix whose entries are differentiable functions of $𝑠 \in ℝ$ . Applying Remark 5.5.11 entry by entry with the chain rule (or Exercise 5.5.48) gives Jacobi’s formula

\frac{𝑑}{𝑑 𝑠} det 𝐴 (𝑠) = \sum_{𝑖, 𝑗} 𝑐_{𝑖 𝑗} (𝑠) 𝑎_{𝑖 𝑗}^{'} (𝑠) = tr (adj (𝐴 (𝑠)) 𝐴^{'} (𝑠)),

where $𝑐_{𝑖 𝑗} (𝑠)$ are the cofactors of $𝐴 (𝑠)$ and $𝐴^{'} (𝑠)$ is the entrywise derivative. At an invertible $𝐴 (𝑠)$ this reads ${(det 𝐴)}^{'} =$ $det 𝐴 \cdot$ $tr (𝐴^{- 1} 𝐴^{'})$ . For $𝐴 (𝑠) = 𝐼_{𝑛} + 𝑠 𝐻$ at $𝑠 = 0$ it gives $tr 𝐻$ , the coefficient of $𝑠$ in $det (𝐼_{𝑛} + 𝑠 𝐻)$ found in Exercise 5.5.48 (with $𝐴 = 𝐼_{𝑛}$ and $𝐵 = 𝐻$ ).

5.5.7Minors and rank Beyond 21-242

Minors of arbitrary order appear in LADW 3.6 and in Cauchy–Binet, but not in the course.

The minors $det 𝐵_{\hat{𝑖 𝑗}}$ come from square submatrices one size smaller than $𝐵$ . Submatrices of every size describe the rank.

Definition 5.5.29 (Minors of order

𝑘

). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

and

1 \leq 𝑘 \leq min (𝑚, 𝑛)

. For sets

𝐼 \subseteq [𝑚]

and

𝐽 \subseteq [𝑛]

with

𝑘

elements each, the submatrix

𝐴_{𝐼 𝐽} \in 𝐹^{𝑘 \times 𝑘}

consists of the entries

𝑎_{𝑖 𝑗}

with

𝑖 \in 𝐼

and

𝑗 \in 𝐽

, with rows and columns in increasing order. Its determinant

det 𝐴_{𝐼 𝐽}

is a minor of order $𝑘$ of

𝐴

So $𝐵_{\hat{𝑖 𝑗}} = 𝐵_{𝐼 𝐽}$ with $𝐼 = [𝑛] ∖ {𝑖}$ and $𝐽 = [𝑛] ∖ {𝑗}$ , and the $1 \times 1$ minors are the entries.

Theorem 5.5.30 (Rank via minors). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

be nonzero. Then

rank 𝐴

is the largest

𝑘

such that

𝐴

has a nonzero minor of order

𝑘

. In particular, every minor of order greater than

rank 𝐴

0

Proof.hard

Uses. Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ), Theorem 4.1.10 (Independent lists are short), Theorem 1.6.10 (Every spanning list contains a basis), Theorem 4.3.8 (Row rank equals column rank), Corollary 5.4.8 (Vanishing determinants), Corollary 5.4.15 (Rows)

Hint 1. If

𝐴_{𝐼 𝐽}

has nonzero determinant, its columns are independent. What does that say about the columns

𝑗 \in 𝐽

𝐴

Hint 2. Conversely, with

𝑟 = rank 𝐴

, choose

𝑟

independent columns of

𝐴

. The

𝑚 \times 𝑟

matrix they form has rank

𝑟

, so its transpose does too. Choose

𝑟

independent rows of it.

Sketch. If

det 𝐴_{𝐼 𝐽} \neq 0

, the columns of

𝐴_{𝐼 𝐽}

are independent, so the columns of

𝐴

indexed by

𝐽

are independent (a relation among them restricts to the rows in

𝐼

). They lie in the column space, of dimension

rank 𝐴

, so

𝑘 \leq rank 𝐴

. Conversely,

𝑟 = rank 𝐴

columns of

𝐴

form a basis of its column space; the

𝑚 \times 𝑟

matrix

𝐴^{'}

they form has rank

𝑟

, so by Theorem 4.3.8 some

𝑟

rows of

𝐴^{'}

are independent, and the

𝑟 \times 𝑟

submatrix they form has nonzero determinant.

The columns of $𝐴$ span $im 𝑇_{𝐴}$ , which has dimension $rank 𝐴$ by Theorem 4.2.7.

Suppose $det 𝐴_{𝐼 𝐽} \neq 0$ for some $𝐼, 𝐽$ with $𝑘$ elements. By Corollary 5.4.8, the columns of $𝐴_{𝐼 𝐽}$ are linearly independent. For $𝑗 \in 𝐽$ , the column of $𝐴_{𝐼 𝐽}$ that comes from column $𝑗$ of $𝐴$ is $𝐚_{𝑗}^{'} \in 𝐹^{𝑘}$ , the vector of entries $𝑎_{𝑖 𝑗}$ with $𝑖 \in 𝐼$ . We claim that the columns $𝐚_{𝑗}$ , $𝑗 \in 𝐽$ , of $𝐴$ are linearly independent. If $\sum_{𝑗 \in 𝐽} 𝑥_{𝑗} 𝐚_{𝑗} = 𝟎$ , then in particular the entries in the rows $𝑖 \in 𝐼$ vanish, that is, $\sum_{𝑗 \in 𝐽} 𝑥_{𝑗} 𝐚_{𝑗}^{'} =$ $𝟎$ ; so all $𝑥_{𝑗} = 0$ . Hence $im 𝑇_{𝐴}$ contains $𝑘$ independent vectors, and $𝑘 \leq rank 𝐴$ by Theorem 4.1.10. This proves the last sentence of the theorem.

Now let $𝑟 = rank 𝐴 \geq 1$ . By Theorem 1.6.10, the list of columns of $𝐴$ , which spans $im 𝑇_{𝐴}$ , contains a basis of $im 𝑇_{𝐴}$ ; it has $𝑟$ elements, say the columns indexed by $𝐽$ . Let $𝐴^{'} \in 𝐹^{𝑚 \times 𝑟}$ be the matrix with these columns. Its columns are independent, so $rank 𝐴^{'} = 𝑟$ (Theorem 4.2.7), and $rank 𝐴^{' 𝖳} = 𝑟$ by Theorem 4.3.8. Applying the same argument to $𝐴^{' 𝖳}$ , some $𝑟$ columns of $𝐴^{' 𝖳}$ are independent, that is, some $𝑟$ rows of $𝐴^{'}$ , indexed by a set $𝐼$ , are independent. These rows form the $𝑟 \times 𝑟$ matrix $𝐴_{𝐼 𝐽}$ , which therefore has independent rows, so $det 𝐴_{𝐼 𝐽} \neq 0$ by Corollary 5.4.15. So $𝐴$ has a nonzero minor of order $𝑟$ , and none of larger order. □

The theorem is not a practical way to find the rank, since row reduction is much faster than evaluating minors. Its value is that minors are polynomials in the entries, so statements about rank become statements about polynomials.

Corollary 5.5.31 (Rank does not depend on the field). Let

𝐾

be a subfield of

𝐹

(Definition 1.1.32), and let

𝐴 \in 𝐾^{𝑚 \times 𝑛}

. Then the rank of

𝐴

is the same whether

𝐴

is regarded as a matrix over

𝐾

or over

𝐹

Proof.routine

Uses. Theorem 5.5.30 (Rank via minors), Definition 5.3.6 (Determinant), Definition 1.1.32 (Subfield)

Hint 1. Is a minor of

𝐴

computed over

𝐾

the same element as the minor computed over

𝐹

Hint 2. The Leibniz formula uses only sums and products, and

𝐾

inherits these from

𝐹

Sketch. Each minor is given by the Leibniz formula, which uses only the operations of

𝐾

, and these agree with those of

𝐹

. So

𝐴

has the same minors over

𝐾

and over

𝐹

, and by Theorem 5.5.30 the same rank.

𝐴 = 0

, its rank is

0

over both fields. Otherwise, each minor

det 𝐴_{𝐼 𝐽}

is the sum in the Leibniz formula (Definition 5.3.6), a combination of sums, negatives, and products of entries of

𝐴

. These operations in

𝐾

are the restrictions of those in

𝐹

(Definition 1.1.32), so the minor is the same element whether computed in

𝐾

or in

𝐹

. In particular, the minors that are nonzero are the same, and Theorem 5.5.30 gives the same rank. □

For example, a matrix with rational entries has the same rank over $ℚ$ , $ℝ$ , and $ℂ$ . (Exercise 3.3.54 proves this with Gauss–Jordan elimination instead: the reduced row echelon form computed in $𝐾$ is also the one over $𝐹$ .) By contrast, reducing an integer matrix modulo a prime can lower its rank, because nonzero integer minors can become $0$ in $𝔽_{𝑝}$ .

Remark 5.5.32 (The Cauchy–Binet formula). For $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ , the determinant of the $𝑚 \times 𝑚$ matrix $𝐴 𝐵$ is a sum of products of minors of order $𝑚$ :

det (𝐴 𝐵) = \sum_{𝑆 \subseteq [𝑛], | 𝑆 | = 𝑚} det 𝐴_{[𝑚] 𝑆} det 𝐵_{𝑆 [𝑚]} .

If $𝑚 > 𝑛$ , the sum is empty and $det (𝐴 𝐵) = 0$ , in line with $rank (𝐴 𝐵) \leq$ $𝑛 <$ $𝑚$ . If $𝑚 = 𝑛$ , there is one term, $det 𝐴 det 𝐵$ . For $𝐴 = 𝐵^{𝖳}$ over $ℝ$ , it gives $det (𝐵^{𝖳} 𝐵) =$ $\sum_{𝑆} {(det 𝐵_{𝑆 [𝑚]})}^{2} \geq$ $0$ . Exercise 5.5.52 proves the formula.

Exercises

Exercise 5.5.33.routine Let

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

(a)Compute $det 𝐴$ with cofactor expansions, choosing each row or column to keep the work small.
(b)For which primes $𝑝$ is the reduction of $𝐴$ modulo $𝑝$ invertible over $𝔽_{𝑝}$ ?

Solution.

Uses. Lemma 5.5.2 (A row or column with one nonzero entry), Theorem 5.5.3 (Cofactor expansion), Proposition 5.3.20 (Reduction modulo $𝑝$ ), Theorem 5.4.7 (Invertibility and the determinant)

Hint 1. Row

2

has a single nonzero entry. After deleting its row and column, look for another row or column with a single nonzero entry.

Hint 2. For (b), reduce the answer to (a) modulo

𝑝

Sketch. Row

2

gives

det 𝐴 =

2 det (\begin{matrix} 3 & 0 & 2 \\ 1 & 5 & 1 \\ 2 & 0 & 1 \end{matrix})

, and column

2

of that minor gives

5 det (\begin{matrix} 3 & 2 \\ 2 & 1 \end{matrix}) = - 5

. So

det 𝐴 = - 10

, and the reduction is invertible exactly for

𝑝 \notin {2, 5}

(a) Row $2$ is $(0, 2, 0, 0)$ , so by Lemma 5.5.2,

det 𝐴 = {(- 1)}^{2 + 2} \cdot 2 det 𝐴_{\hat{22}} = 2 det (\begin{matrix} 3 & 0 & 2 \\ 1 & 5 & 1 \\ 2 & 0 & 1 \end{matrix}) .

Column $2$ of this minor is $(0, 5, 0)$ , so, again by Lemma 5.5.2,

det (\begin{matrix} 3 & 0 & 2 \\ 1 & 5 & 1 \\ 2 & 0 & 1 \end{matrix}) = {(- 1)}^{2 + 2} \cdot 5 det (\begin{matrix} 3 & 2 \\ 2 & 1 \end{matrix}) = 5 (3 - 4) = - 5 .

Hence $det 𝐴 = - 10$ .

(b) By Proposition 5.3.20, the determinant of the reduction is $- 10 mod 𝑝$ , which is $0$ exactly when $𝑝$ divides $10$ . By Theorem 5.4.7 over $𝔽_{𝑝}$ , the reduction is invertible exactly when $𝑝 \neq 2$ and $𝑝 \neq 5$ .

Exercise 5.5.34.routine Use cofactor expansion and induction on

𝑛

to give another proof of Proposition 5.3.15: the determinant of an upper or lower triangular matrix is the product of its diagonal entries.

Solution.

Uses. Lemma 5.5.2 (A row or column with one nonzero entry), Definition 3.3.31 (Triangular matrices), Theorem 5.4.14 (The transpose), induction on $𝑛$

Techniques. Induction on matrix size (Technique 5.5.17)

Hint 1. For an upper triangular matrix, look at the first column.

Hint 2. Deleting row

1

and column

1

of an upper triangular matrix leaves an upper triangular matrix. Which diagonal entries does it have?

Sketch. If

𝐴

is upper triangular, its first column is

(𝑎_{11}, 0, \dots, 0)

, so

det 𝐴 =

𝑎_{11} det 𝐴_{\hat{11}}

, and

𝐴_{\hat{11}}

is upper triangular with diagonal

𝑎_{22}, \dots, 𝑎_{𝑛 𝑛}

. Induction finishes. A lower triangular matrix is the transpose of an upper triangular one.

We induct on $𝑛$ ; for $𝑛 = 1$ there is nothing to prove. Let $𝑛 \geq 2$ and let $𝐴$ be upper triangular, so $𝑎_{𝑖 𝑗} = 0$ whenever $𝑖 > 𝑗$ . The first column of $𝐴$ is $(𝑎_{11}, 0, \dots, 0)$ , so by Lemma 5.5.2,

det 𝐴 = {(- 1)}^{1 + 1} 𝑎_{11} det 𝐴_{\hat{11}} .

The $(𝑝, 𝑞)$ entry of $𝐴_{\hat{11}}$ is $𝑎_{𝑝 + 1, 𝑞 + 1}$ , which is $0$ when $𝑝 > 𝑞$ . So $𝐴_{\hat{11}}$ is upper triangular with diagonal entries $𝑎_{22}, \dots, 𝑎_{𝑛 𝑛}$ , and by the induction hypothesis $det 𝐴_{\hat{11}} =$ $𝑎_{22} \dots 𝑎_{𝑛 𝑛}$ . Hence $det 𝐴 =$ $𝑎_{11} 𝑎_{22} \dots 𝑎_{𝑛 𝑛}$ .

If $𝐴$ is lower triangular, then $𝐴^{𝖳}$ is upper triangular with the same diagonal, and $det 𝐴 = det 𝐴^{𝖳}$ by Theorem 5.4.14. (Alternatively, expand along the first row.)

Exercise 5.5.35.standard For $𝑡 \in ℚ$ , consider the system $𝐵 (𝑡) 𝐱 = 𝐲$ with

𝐵 (𝑡) = (\begin{matrix} 1 & 1 & 𝑡 \\ 1 & 𝑡 & 1 \\ 𝑡 & 1 & 1 \end{matrix}), 𝐲 = (1, 2, 3) .

(a)Show that $det 𝐵 (𝑡) =$ $- {(𝑡 - 1)}^{2} (𝑡 + 2)$ . For which $𝑡$ does the system have exactly one solution?
(b)For those $𝑡$ , find $𝑥_{2}$ with Cramer’s rule.
(c)Show that for $𝑡 = 1$ , every determinant $det 𝐵_{𝑖} (𝐲)$ is $0$ , but the system has no solution. What happens for $𝑡 = - 2$ ?

Solution.

Uses. Theorem 5.5.3 (Cofactor expansion), Theorem 5.5.14 (Cramer’s rule), Theorem 5.4.7 (Invertibility and the determinant), (5.5.3)

Hint 1. Expand

det 𝐵 (𝑡)

along the first row and factor. Check your factorization at

𝑡 = 1

Hint 2. For (b),

det 𝐵_{2} (𝐲) =

det (\begin{matrix} 1 & 1 & 𝑡 \\ 1 & 2 & 1 \\ 𝑡 & 3 & 1 \end{matrix})

; it factors as

- 2 {(𝑡 - 1)}^{2}

Hint 3. For

𝑡 = 1

, every column of

𝐵 (1)

(1, 1, 1)

. For

𝑡 = - 2

, add the three equations.

Sketch. (a) Expanding along row

1

det 𝐵 (𝑡) =

(𝑡 - 1) -

(1 - 𝑡) +

𝑡 (1 - 𝑡^{2}) =

- 𝑡^{3} +

3 𝑡 -

2 =

- {(𝑡 - 1)}^{2} (𝑡 + 2)

, so the solution is unique exactly for

𝑡 \notin {1, - 2}

. (b)

det 𝐵_{2} (𝐲) =

- 2 {(𝑡 - 1)}^{2}

, so

𝑥_{2} = 2 / (𝑡 + 2)

. (c) At

𝑡 = 1

, each

𝐵_{𝑖} (𝐲)

keeps two columns

(1, 1, 1)

, so all three determinants vanish, but the equations say

𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 1, 2, 3

at once. At

𝑡 = - 2

det 𝐵_{2} (𝐲) = - 18 \neq 0

, so there is no solution by (5.5.3).

(a) Expanding along the first row,

\begin{aligned} det 𝐵 (𝑡) & = 1 \cdot (𝑡 - 1) - 1 \cdot (1 - 𝑡) + 𝑡 (1 - 𝑡^{2}) \\ = - 𝑡^{3} + 3 𝑡 - 2 = - {(𝑡 - 1)}^{2} (𝑡 + 2), \end{aligned}

since ${(𝑡 - 1)}^{2} (𝑡 + 2) =$ $(𝑡^{2} - 2 𝑡 + 1) (𝑡 + 2) =$ $𝑡^{3} -$ $3 𝑡 +$ $2$ . By Theorem 5.4.7 and Theorem 5.5.14, the system has exactly one solution when $det 𝐵 (𝑡) \neq 0$ , that is, when $𝑡 \neq 1$ and $𝑡 \neq - 2$ . (If $det 𝐵 (𝑡) = 0$ , then $𝐵 (𝑡)$ is not invertible, so the system has either no solution or more than one.)

(b) Replacing column $2$ by $𝐲$ and expanding along the first row,

\begin{aligned} det 𝐵_{2} (𝐲) & = det (\begin{matrix} 1 & 1 & 𝑡 \\ 1 & 2 & 1 \\ 𝑡 & 3 & 1 \end{matrix}) = (2 - 3) - (1 - 𝑡) + 𝑡 (3 - 2 𝑡) \\ = - 2 𝑡^{2} + 4 𝑡 - 2 = - 2 {(𝑡 - 1)}^{2} . \end{aligned}

By Theorem 5.5.14, for $𝑡 \notin {1, - 2}$ ,

𝑥_{2} = \frac{- 2 {(𝑡 - 1)}^{2}}{- {(𝑡 - 1)}^{2} (𝑡 + 2)} = \frac{2}{𝑡 + 2} .

(c) For $𝑡 = 1$ , every column of $𝐵 (1)$ is $(1, 1, 1)$ . Replacing one column by $𝐲$ leaves two columns equal to $(1, 1, 1)$ , so $det 𝐵_{𝑖} (𝐲) = 0$ for $𝑖 = 1, 2, 3$ . But the three equations read $𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 1$ , $𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 2$ , and $𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 3$ , which contradict each other. So the vanishing of all the determinants in (5.5.3) does not imply that a solution exists.

For $𝑡 = - 2$ , part (b) gives $det 𝐵_{2} (𝐲) =$ $- 2 \cdot$ $9 =$ $- 18 \neq$ $0$ , while $det 𝐵 (- 2) = 0$ . By (5.5.3), a solution would satisfy $𝑥_{2} \cdot 0 = - 18$ , so there is none. Directly: the rows of $𝐵 (- 2)$ add up to $𝟎^{𝖳}$ , so adding the three equations gives $0 = 1 + 2 + 3$ .

Exercise 5.5.36.routine Construct a matrix

𝐴 \in ℚ^{3 \times 3}

with integer entries, none of them

0

, such that

𝐴^{- 1}

also has integer entries. Compute

𝐴^{- 1}

with the adjugate.

Solution.

Uses. Corollary 5.5.12 (Integer inverses), Theorem 5.5.9 (The adjugate and the inverse), Corollary 5.4.15 (Rows), Proposition 5.3.15 (Triangular matrices)

Hint 1. By Corollary 5.5.12 it is enough to have

det 𝐴 = \pm 1

Hint 2. Start from an upper triangular matrix with

1

s on the diagonal, and add rows to other rows until no entry is

0

Sketch. From

(\begin{matrix} 1 & 2 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix})

, add row

1

to row

2

and then the new row

2

to row

3

𝐴 = (\begin{matrix} 1 & 2 & 1 \\ 1 & 3 & 2 \\ 1 & 3 & 3 \end{matrix})

, with

det 𝐴 = 1

. Its adjugate is

(\begin{matrix} 3 & - 3 & 1 \\ - 1 & 2 & - 1 \\ 0 & - 1 & 1 \end{matrix})

, which is

𝐴^{- 1}

Start with $𝑈 = (\begin{matrix} 1 & 2 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix})$ , which has $det 𝑈 = 1$ by Proposition 5.3.15. Adding row $1$ to row $2$ , and then the new row $2$ to row $3$ , gives

𝐴 = (\begin{matrix} 1 & 2 & 1 \\ 1 & 3 & 2 \\ 1 & 3 & 3 \end{matrix}),

and these replacements do not change the determinant (Corollary 5.4.15), so $det 𝐴 = 1$ . No entry of $𝐴$ is $0$ . The cofactors are

\begin{aligned} 𝑐_{11} & = 9 - 6 = 3, & 𝑐_{12} & = - (3 - 2) = - 1, & 𝑐_{13} & = 3 - 3 = 0, \\ 𝑐_{21} & = - (6 - 3) = - 3, & 𝑐_{22} & = 3 - 1 = 2, & 𝑐_{23} & = - (3 - 2) = - 1, \\ 𝑐_{31} & = 4 - 3 = 1, & 𝑐_{32} & = - (2 - 1) = - 1, & 𝑐_{33} & = 3 - 2 = 1 . \end{aligned}

(As a check, $1 \cdot$ $3 +$ $2 \cdot$ $(- 1) +$ $1 \cdot$ $0 =$ $1 =$ $det 𝐴$ .) By Theorem 5.5.9,

𝐴^{- 1} = adj 𝐴 = 𝐶_{𝐴}^{𝖳} = (\begin{matrix} 3 & - 3 & 1 \\ - 1 & 2 & - 1 \\ 0 & - 1 & 1 \end{matrix}) .

Indeed, the first row of $𝐴 𝐴^{- 1}$ is $(3 - 2 + 0, - 3 + 4 - 1, 1 - 2 + 1) =$ $(1, 0, 0)$ , and the other rows check the same way.

Exercise 5.5.37.standard Let $𝑛 \geq 2$ and let $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ be upper triangular.

(a)Show that $adj 𝐵$ is upper triangular, with diagonal entries $\prod_{𝑘 \neq 𝑖} 𝑏_{𝑘 𝑘}$ for $𝑖 = 1, \dots, 𝑛$ .
(b)Deduce that if $𝐵$ is invertible, then $𝐵^{- 1}$ is upper triangular with diagonal entries $𝑏_{11}^{- 1}, \dots, 𝑏_{𝑛 𝑛}^{- 1}$ .

Solution.

Uses. Definition 5.5.6 (Cofactors, cofactor matrix, adjugate), Proposition 5.3.15 (Triangular matrices), Theorem 5.5.9 (The adjugate and the inverse), Definition 3.3.31 (Triangular matrices)

Hint 1. The

(𝑖, 𝑗)

entry of

adj 𝐵

𝑐_{𝑗 𝑖} =

{(- 1)}^{𝑖 + 𝑗} det 𝐵_{\hat{𝑗 𝑖}}

. For

𝑖 > 𝑗

, show that

𝐵_{\hat{𝑗 𝑖}}

is upper triangular with a zero on its diagonal.

Hint 2. Row

𝑝

𝐵_{\hat{𝑗 𝑖}}

is row

𝑝

𝑝 + 1

𝐵

, and column

𝑞

is column

𝑞

𝑞 + 1

. Look at the diagonal position

𝑝 = 𝑗

Sketch. For

𝑗 < 𝑖

, row

𝑝

𝐵_{\hat{𝑗 𝑖}}

is row

𝑟_{𝑝}

𝐵

and column

𝑞

is column

𝑠_{𝑞}

, with

𝑟_{𝑝} = 𝑝

for

𝑝 < 𝑗

𝑟_{𝑝} = 𝑝 + 1

otherwise,

𝑠_{𝑞} = 𝑞

for

𝑞 < 𝑖

𝑠_{𝑞} = 𝑞 + 1

otherwise. For

𝑝 > 𝑞

one checks

𝑟_{𝑝} > 𝑠_{𝑞}

, so the minor matrix is upper triangular, and its

(𝑗, 𝑗)

entry is

𝑏_{𝑗 + 1, 𝑗} = 0

. So

𝑐_{𝑗 𝑖} = 0

. The diagonal entry

𝑐_{𝑖 𝑖} = det 𝐵_{\hat{𝑖 𝑖}}

is the product of the other diagonal entries. Then

𝐵^{- 1} =

{(det 𝐵)}^{- 1} adj 𝐵

(a) The $(𝑖, 𝑗)$ entry of $adj 𝐵$ is $𝑐_{𝑗 𝑖} =$ ${(- 1)}^{𝑖 + 𝑗} det 𝐵_{\hat{𝑗 𝑖}}$ . Let $𝑖 > 𝑗$ , and let $𝑁 = 𝐵_{\hat{𝑗 𝑖}}$ . For $𝑝, 𝑞 \in [𝑛 - 1]$ , the $(𝑝, 𝑞)$ entry of $𝑁$ is $𝑏_{𝑟_{𝑝} 𝑠_{𝑞}}$ , where

𝑟_{𝑝} = {\begin{cases} 𝑝 & if 𝑝 < 𝑗 \\ 𝑝 + 1 & if 𝑝 \geq 𝑗 \end{cases}, 𝑠_{𝑞} = {\begin{cases} 𝑞 & if 𝑞 < 𝑖 \\ 𝑞 + 1 & if 𝑞 \geq 𝑖 \end{cases} .

Let $𝑝 > 𝑞$ . Then $𝑟_{𝑝} \geq 𝑝 \geq 𝑞 + 1 \geq 𝑠_{𝑞}$ . If $𝑟_{𝑝} = 𝑠_{𝑞}$ , all these are equalities, so $𝑟_{𝑝} = 𝑝$ and $𝑠_{𝑞} = 𝑞 + 1$ , which means $𝑝 < 𝑗$ and $𝑞 \geq 𝑖$ ; but then $𝑝 = 𝑞 + 1 > 𝑖 > 𝑗 > 𝑝$ , which is impossible. So $𝑟_{𝑝} > 𝑠_{𝑞}$ and $𝑏_{𝑟_{𝑝} 𝑠_{𝑞}} = 0$ , since $𝐵$ is upper triangular. Hence $𝑁$ is upper triangular. Its diagonal entry in position $(𝑗, 𝑗)$ , which exists since $𝑗 < 𝑖 \leq 𝑛$ , is $𝑏_{𝑟_{𝑗} 𝑠_{𝑗}} =$ $𝑏_{𝑗 + 1, 𝑗} =$ $0$ (as $𝑗 \geq 𝑗$ and $𝑗 < 𝑖$ ). By Proposition 5.3.15, $det 𝑁 = 0$ , so the $(𝑖, 𝑗)$ entry of $adj 𝐵$ is $0$ . Thus $adj 𝐵$ is upper triangular.

The $(𝑖, 𝑖)$ entry of $adj 𝐵$ is $𝑐_{𝑖 𝑖} = det 𝐵_{\hat{𝑖 𝑖}}$ . Deleting row $𝑖$ and column $𝑖$ of an upper triangular matrix leaves an upper triangular matrix whose diagonal entries are the $𝑏_{𝑘 𝑘}$ with $𝑘 \neq 𝑖$ (the same index computation with $𝑖 = 𝑗$ gives $𝑟_{𝑝} = 𝑠_{𝑝}$ ). So $𝑐_{𝑖 𝑖} =$ $\prod_{𝑘 \neq 𝑖} 𝑏_{𝑘 𝑘}$ by Proposition 5.3.15.

(b) If $𝐵$ is invertible, then $det 𝐵 =$ $𝑏_{11} \dots 𝑏_{𝑛 𝑛} \neq$ $0$ , and $𝐵^{- 1} =$ ${(det 𝐵)}^{- 1} adj 𝐵$ by Theorem 5.5.9. This is upper triangular by (a), and its $(𝑖, 𝑖)$ entry is $\prod_{𝑘 \neq 𝑖} 𝑏_{𝑘 𝑘} / \prod_{𝑘} 𝑏_{𝑘 𝑘} =$ $𝑏_{𝑖 𝑖}^{- 1}$ .

Exercise 5.5.38.standard Let $𝑛 \geq 2$ , $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ , and $𝑐 \in 𝐹$ . Prove or disprove each statement. Where the answer depends on $𝑛$ , say how.

(a) $adj (𝐴^{𝖳}) =$ ${(adj 𝐴)}^{𝖳}$ .
(b) $adj (𝑐 𝐴) =$ $𝑐^{𝑛 - 1} adj 𝐴$ .
(c) $adj (𝐴 + 𝐵) =$ $adj 𝐴 +$ $adj 𝐵$ .
(d)The map $adj : 𝐹^{𝑛 \times 𝑛} \to$ $𝐹^{𝑛 \times 𝑛}$ is injective.

Solution.

Uses. Definition 5.5.6 (Cofactors, cofactor matrix, adjugate), Theorem 5.4.14 (The transpose), Exercise 5.1.5, Example 5.5.7 (The $2 \times 2$ case)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. For (a) and (b), compare the minors of

𝐴^{𝖳}

and of

𝑐 𝐴

with those of

𝐴

Hint 2. For

𝑛 = 2

, Example 5.5.7 gives

adj

explicitly; is it linear? For

𝑛 \geq 3

, compare

adj (𝐼_{𝑛} + 𝑈_{11})

with

adj 𝐼_{𝑛} + adj 𝑈_{11}

in (c), where

𝑈_{11}

has a single entry

1

, and use

𝑈_{11}

again in (d).

Sketch. (a) True:

{(𝐴^{𝖳})}_{\hat{𝑖 𝑗}} =

{(𝐴_{\hat{𝑗 𝑖}})}^{𝖳}

, so the cofactor matrix of

𝐴^{𝖳}

𝐶_{𝐴}^{𝖳}

. (b) True:

{(𝑐 𝐴)}_{\hat{𝑖 𝑗}} =

𝑐 𝐴_{\hat{𝑖 𝑗}}

has determinant

𝑐^{𝑛 - 1} det 𝐴_{\hat{𝑖 𝑗}}

. (c) True for

𝑛 = 2

, where

adj (\begin{matrix} 𝑝 & 𝑞 \\ 𝑟 & 𝑠 \end{matrix}) =

(\begin{matrix} 𝑠 & - 𝑞 \\ - 𝑟 & 𝑝 \end{matrix})

is linear; false for

𝑛 \geq 3

: the

(2, 2)

entry of

adj (𝐼_{𝑛} + 𝑈_{11})

2

, but that of

adj 𝐼_{𝑛} +

adj 𝑈_{11} =

𝐼_{𝑛} +

0

1

. (d) True for

𝑛 = 2

(applying

adj

twice gives the identity); false for

𝑛 \geq 3

, since

adj 𝑈_{11} = 0 = adj 0

(a) True. Deleting row $𝑖$ and column $𝑗$ of $𝐴^{𝖳}$ gives ${(𝐴_{\hat{𝑗 𝑖}})}^{𝖳}$ , so by Theorem 5.4.14 the $(𝑖, 𝑗)$ cofactor of $𝐴^{𝖳}$ is ${(- 1)}^{𝑖 + 𝑗} det 𝐴_{\hat{𝑗 𝑖}} =$ $𝑐_{𝑗 𝑖}$ , where $𝑐_{𝑗 𝑖}$ is a cofactor of $𝐴$ . So $𝐶_{𝐴^{𝖳}} = 𝐶_{𝐴}^{𝖳}$ , and $adj (𝐴^{𝖳}) =$ $𝐶_{𝐴^{𝖳}}^{𝖳} =$ $𝐶_{𝐴} =$ ${(adj 𝐴)}^{𝖳}$ .

(b) True. Deleting a row and a column of $𝑐 𝐴$ gives $𝑐 𝐴_{\hat{𝑖 𝑗}}$ , an $(𝑛 - 1) \times (𝑛 - 1)$ matrix, so its determinant is $𝑐^{𝑛 - 1} det 𝐴_{\hat{𝑖 𝑗}}$ (Exercise 5.1.5). So every cofactor, and hence $adj$ , is multiplied by $𝑐^{𝑛 - 1}$ .

(c) True for $𝑛 = 2$ and false for $𝑛 \geq 3$ . For $𝑛 = 2$ , Example 5.5.7 shows $adj (\begin{matrix} 𝑝 & 𝑞 \\ 𝑟 & 𝑠 \end{matrix}) =$ $(\begin{matrix} 𝑠 & - 𝑞 \\ - 𝑟 & 𝑝 \end{matrix})$ , whose entries are linear in $𝑝, 𝑞, 𝑟, 𝑠$ , so $adj (𝐴 + 𝐵) =$ $adj 𝐴 +$ $adj 𝐵$ . For $𝑛 \geq 3$ , first note that for a diagonal matrix $𝐷$ with diagonal entries $𝑑_{1}, \dots, 𝑑_{𝑛}$ and $𝑖 \neq 𝑗$ , the matrix $𝐷_{\hat{𝑖 𝑗}}$ has a zero row, namely what is left of row $𝑗$ of $𝐷$ after its only nonzero entry, in column $𝑗$ , is deleted. So $adj 𝐷$ is diagonal, with $(𝑖, 𝑖)$ entry $det 𝐷_{\hat{𝑖 𝑖}} =$ $\prod_{𝑘 \neq 𝑖} 𝑑_{𝑘}$ . Now take $𝐴 = 𝐼_{𝑛}$ and $𝐵 = 𝑈_{11}$ , the matrix with a single entry $1$ in position $(1, 1)$ . Then $𝐴 + 𝐵$ is diagonal with entries $2, 1, \dots, 1$ , so the $(2, 2)$ entry of $adj (𝐴 + 𝐵)$ is $2 \cdot 1 \dots 1 = 2$ . On the other hand, $adj 𝐼_{𝑛} = 𝐼_{𝑛}$ and $adj 𝑈_{11} = 0$ (see (d)), so the $(2, 2)$ entry of $adj 𝐴 + adj 𝐵$ is $1$ . Since $2 \neq 1$ in every field, $adj (𝐴 + 𝐵) \neq$ $adj 𝐴 +$ $adj 𝐵$ .

(d) True for $𝑛 = 2$ and false for $𝑛 \geq 3$ . For $𝑛 = 2$ , applying the formula of Example 5.5.7 twice returns $(\begin{matrix} 𝑝 & 𝑞 \\ 𝑟 & 𝑠 \end{matrix})$ , so $adj$ has a left inverse (itself) and is injective. For $𝑛 \geq 3$ , let $𝑈_{11}$ have a single entry $1$ in position $(1, 1)$ . Every $(𝑛 - 1) \times (𝑛 - 1)$ submatrix ${𝑈_{11}}_{\hat{𝑖 𝑗}}$ has at most one nonzero entry, so it has a zero row (as $𝑛 - 1 \geq 2$ ) and determinant $0$ . So $adj 𝑈_{11} = 0 = adj 0$ , with $𝑈_{11} \neq 0$ .

Exercise 5.5.39.standard Let

𝑛 \geq 2

and

𝐴 \in 𝐹^{𝑛 \times 𝑛}

. Show that

det (adj 𝐴) =

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

, including when

𝐴

is not invertible.

Solution.

Uses. Theorem 5.5.9 (The adjugate and the inverse), Theorem 5.4.10 (Multiplicativity), Exercise 5.1.5, Theorem 5.4.7 (Invertibility and the determinant)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Take determinants of

𝐴 adj 𝐴 =

(det 𝐴) 𝐼_{𝑛}

. This settles the invertible case.

Hint 2. If

det 𝐴 = 0

, suppose

adj 𝐴

were invertible and multiply

𝐴 adj 𝐴 = 0

on the right by

{(adj 𝐴)}^{- 1}

. What is the adjugate of the zero matrix?

Sketch. From

𝐴 adj 𝐴 =

(det 𝐴) 𝐼_{𝑛}

det 𝐴 det (adj 𝐴) =

{(det 𝐴)}^{𝑛}

, so we can divide when

det 𝐴 \neq 0

. If

det 𝐴 = 0

and

adj 𝐴

were invertible, then

𝐴 =

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

0

, so

adj 𝐴 = adj 0 = 0

(as

𝑛 \geq 2

), which is not invertible. So

det (adj 𝐴) =

0 =

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

By Theorem 5.5.9, Theorem 5.4.10, and Exercise 5.1.5,

det 𝐴 det (adj 𝐴) = det (𝐴 adj 𝐴) = det ((det 𝐴) 𝐼_{𝑛}) = {(det 𝐴)}^{𝑛} .

If $det 𝐴 \neq 0$ , dividing by $det 𝐴$ gives $det (adj 𝐴) =$ ${(det 𝐴)}^{𝑛 - 1}$ .

Suppose $det 𝐴 = 0$ ; we show $det (adj 𝐴) = 0$ , which equals ${(det 𝐴)}^{𝑛 - 1}$ since $𝑛 - 1 \geq 1$ . Suppose instead that $adj 𝐴$ is invertible (Theorem 5.4.7). Since $𝐴 adj 𝐴 = 0 \cdot 𝐼_{𝑛} = 0$ ,

𝐴 = 𝐴 (adj 𝐴) {(adj 𝐴)}^{- 1} = 0 {(adj 𝐴)}^{- 1} = 0 .

But every minor of the zero matrix is the determinant of a zero matrix of size $𝑛 - 1 \geq 1$ , hence $0$ , so $adj 𝐴 = adj 0 = 0$ , which is not invertible. This contradiction shows $det (adj 𝐴) = 0$ .

Exercise 5.5.40.hard Let $𝑛 \geq 2$ and $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . Show that

adj (adj 𝐴) = {(det 𝐴)}^{𝑛 - 2} 𝐴,

with the convention $0^{0} = 1$ when $𝑛 = 2$ . Prove it first for invertible $𝐴$ , and then for all $𝐴$ when $𝐹$ is infinite.

Solution (invertible case and a polynomial identity).

Uses. Theorem 5.5.9 (The adjugate and the inverse), Exercise 5.5.39, Proposition 5.3.19 ( $det (𝐴 + 𝑡 𝐼_{𝑛})$ as a function of $𝑡$ ), Lemma 3.4.23 (Too many roots), Technique 5.3.18 ( $det$ is a polynomial in the entries)

Techniques. Polynomial identity arguments (Technique 5.5.24)

Hint 1. For invertible

𝐴

adj 𝐴 = (det 𝐴) 𝐴^{- 1}

, and

adj 𝐴

is invertible too. Apply the same formula to

adj 𝐴

, using Exercise 5.5.39.

Hint 2. For general

𝐴

, replace

𝐴

𝐴 + 𝑡 𝐼_{𝑛}

. Each entry of both sides is a polynomial in

𝑡

, and the two sides agree whenever

det (𝐴 + 𝑡 𝐼_{𝑛}) \neq 0

Hint 3. How many

𝑡

can make

det (𝐴 + 𝑡 𝐼_{𝑛}) = 0

? If two polynomials of degree at most

𝑑

agree at more than

𝑑

points, they are equal. Then put

𝑡 = 0

Sketch. If

𝐴

is invertible,

adj 𝐴 = (det 𝐴) 𝐴^{- 1}

is invertible with determinant

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

, so

adj (adj 𝐴) =

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

{(det 𝐴)}^{𝑛 - 2} 𝐴

. In general, every entry of

adj (adj (𝐴 + 𝑡 𝐼_{𝑛}))

and of

{det (𝐴 + 𝑡 𝐼_{𝑛})}^{𝑛 - 2} (𝐴 + 𝑡 𝐼_{𝑛})

is a polynomial in

𝑡

of bounded degree, and they agree for all

𝑡

outside the at most

𝑛

roots of

det (𝐴 + 𝑡 𝐼_{𝑛})

. Over an infinite field that is more points than the degree, so they agree as polynomials, in particular at

𝑡 = 0

Invertible $𝐴$ . By Theorem 5.5.9, $adj 𝐴 = (det 𝐴) 𝐴^{- 1}$ , which is invertible, and $det (adj 𝐴) =$ ${(det 𝐴)}^{𝑛 - 1}$ by Exercise 5.5.39. Applying Theorem 5.5.9 to $adj 𝐴$ ,

\begin{aligned} adj (adj 𝐴) & = det (adj 𝐴) {(adj 𝐴)}^{- 1} = {(det 𝐴)}^{𝑛 - 1} {((det 𝐴) 𝐴^{- 1})}^{- 1} \\ = {(det 𝐴)}^{𝑛 - 1} {(det 𝐴)}^{- 1} 𝐴 = {(det 𝐴)}^{𝑛 - 2} 𝐴 . \end{aligned}

All $𝐴$ , $𝐹$ infinite. For $𝑡 \in 𝐹$ , let $𝐴_{𝑡} = 𝐴 + 𝑡 𝐼_{𝑛}$ . Every entry of $𝐴_{𝑡}$ is a polynomial in $𝑡$ of degree at most $1$ . A determinant of size $𝑚$ whose entries are polynomials in $𝑡$ of degree at most $𝑑$ is a polynomial in $𝑡$ of degree at most $𝑚 𝑑$ , by the Leibniz formula (Technique 5.3.18). So each entry of $adj 𝐴_{𝑡}$ is a polynomial in $𝑡$ of degree at most $𝑛 - 1$ , and each entry of $adj (adj 𝐴_{𝑡})$ is one of degree at most ${(𝑛 - 1)}^{2}$ . Also $det 𝐴_{𝑡}$ is a polynomial of degree at most $𝑛$ , and a product of polynomials in $𝑡$ of degrees at most $𝑑_{1}$ and $𝑑_{2}$ is a polynomial of degree at most $𝑑_{1} + 𝑑_{2}$ (expand by distributivity, as in the proof of Lemma 5.5.23). So each entry of ${det (𝐴_{𝑡})}^{𝑛 - 2} 𝐴_{𝑡}$ is a polynomial of degree at most $𝑛 (𝑛 - 2) +$ $1 =$ ${(𝑛 - 1)}^{2}$ . Let $𝑑 = {(𝑛 - 1)}^{2}$ , which bounds both degrees.

Fix a position $(𝑖, 𝑗)$ , and let $𝑃$ and $𝑄$ be the polynomials of degree at most $𝑑$ that give the $(𝑖, 𝑗)$ entries of the two sides. By Proposition 5.3.19, $det 𝐴_{𝑡}$ is the value at $𝑡$ of a polynomial of degree $𝑛$ with leading coefficient $1$ , which is nonzero, so it has at most $𝑛$ roots (Lemma 3.4.23). For every other $𝑡$ , $𝐴_{𝑡}$ is invertible, and the first part gives $𝑃 (𝑡) = 𝑄 (𝑡)$ . Since $𝐹$ is infinite, there are more than $𝑑 + 1$ such $𝑡$ , so $𝑃 - 𝑄$ is a polynomial of degree at most $𝑑$ with more than $𝑑 + 1$ roots, and $𝑃 = 𝑄$ by Lemma 3.4.23. In particular $𝑃 (0) = 𝑄 (0)$ . As this holds for every $(𝑖, 𝑗)$ , $adj (adj 𝐴) =$ ${(det 𝐴)}^{𝑛 - 2} 𝐴$ .

Solution (via the rank of the adjugate, over every field).Beyond 21-242

Uses. Exercise 5.5.51, Theorem 5.5.30 (Rank via minors), Example 5.5.7 (The $2 \times 2$ case)

Techniques. Polynomial identity arguments (Technique 5.5.24)

Hint 1. For

𝑛 = 2

, compute

adj (adj 𝐴)

from Example 5.5.7.

Hint 2. For

𝑛 \geq 3

and

det 𝐴 = 0

, the right side is

0

. What is the rank of

adj 𝐴

(Exercise 5.5.51), and what does that say about its minors of order

𝑛 - 1

Sketch. For

𝑛 = 2

adj

swaps the diagonal entries and negates the others, so applying it twice gives

𝐴 = {(det 𝐴)}^{0} 𝐴

. For

𝑛 \geq 3

and

𝐴

not invertible,

rank (adj 𝐴) \leq

1 \leq

𝑛 -

2

, so all minors of order

𝑛 - 1

adj 𝐴

vanish (Theorem 5.5.30), and

adj (adj 𝐴) =

0 =

{(det 𝐴)}^{𝑛 - 2} 𝐴

. Invertible

𝐴

was handled in the first approach.

For

𝑛 = 2

, Example 5.5.7 gives

adj (\begin{matrix} 𝑝 & 𝑞 \\ 𝑟 & 𝑠 \end{matrix}) =

(\begin{matrix} 𝑠 & - 𝑞 \\ - 𝑟 & 𝑝 \end{matrix})

, and applying it again gives

(\begin{matrix} 𝑝 & 𝑞 \\ 𝑟 & 𝑠 \end{matrix})

. So

adj (adj 𝐴) =

𝐴 =

{(det 𝐴)}^{0} 𝐴

. Let

𝑛 \geq 3

. Invertible

𝐴

was handled in the first approach. If

𝐴

is not invertible, then

{(det 𝐴)}^{𝑛 - 2} 𝐴 = 0

, and by Exercise 5.5.51,

rank (adj 𝐴) \leq

1 \leq

𝑛 -

2

. By Theorem 5.5.30, every minor of order

𝑛 - 1

adj 𝐴

0

(and if

adj 𝐴 = 0

, trivially so). These minors are, up to sign, the entries of

adj (adj 𝐴)

, so

adj (adj 𝐴) = 0

Exercise 5.5.41.hard Let

𝐹

be an infinite field and

𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}

. Show that

adj (𝐴 𝐵) =

(adj 𝐵) (adj 𝐴)

. (The identity holds over every field, but the proof suggested here needs infinitely many scalars.)

Solution.

Uses. Theorem 5.5.9 (The adjugate and the inverse), Theorem 5.4.10 (Multiplicativity), Proposition 5.3.19 ( $det (𝐴 + 𝑡 𝐼_{𝑛})$ as a function of $𝑡$ ), Lemma 3.4.23 (Too many roots), Technique 5.3.18 ( $det$ is a polynomial in the entries)

Techniques. Polynomial identity arguments (Technique 5.5.24)

Hint 1. Prove it first for invertible

𝐴

and

𝐵

, using

adj 𝑋 = (det 𝑋) 𝑋^{- 1}

Hint 2. Then replace

𝐴

and

𝐵

𝐴 + 𝑡 𝐼_{𝑛}

and

𝐵 + 𝑡 𝐼_{𝑛}

. For how many

𝑡

can either fail to be invertible? Compare the entries of both sides as polynomials in

𝑡

Sketch. For invertible

𝐴, 𝐵

adj (𝐴 𝐵) =

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

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

(adj 𝐵) (adj 𝐴)

. In general, the entries of

adj ((𝐴 + 𝑡 𝐼) (𝐵 + 𝑡 𝐼))

and of

adj (𝐵 + 𝑡 𝐼) adj (𝐴 + 𝑡 𝐼)

are polynomials in

𝑡

of degree at most

2 (𝑛 - 1)

, and they agree except at the at most

2 𝑛

values of

𝑡

where

𝐴 + 𝑡 𝐼

𝐵 + 𝑡 𝐼

is singular. An infinite field has more points than that, so the polynomials are equal; set

𝑡 = 0

For $𝑛 = 1$ both sides are $(1)$ , so let $𝑛 \geq 2$ .

Invertible $𝐴$ and $𝐵$ . By Theorem 5.5.9 and Theorem 5.4.10, $𝐴 𝐵$ is invertible and

adj (𝐴 𝐵) = det (𝐴 𝐵) {(𝐴 𝐵)}^{- 1} = det 𝐴 det 𝐵 𝐵^{- 1} 𝐴^{- 1} = (det 𝐵 𝐵^{- 1}) (det 𝐴 𝐴^{- 1}) = (adj 𝐵) (adj 𝐴) .

General $𝐴$ and $𝐵$ . For $𝑡 \in 𝐹$ , let $𝐴_{𝑡} = 𝐴 + 𝑡 𝐼_{𝑛}$ and $𝐵_{𝑡} = 𝐵 + 𝑡 𝐼_{𝑛}$ . The entries of $𝐴_{𝑡} 𝐵_{𝑡} =$ $𝐴 𝐵 +$ $𝑡 (𝐴 + 𝐵) +$ $𝑡^{2} 𝐼_{𝑛}$ are polynomials in $𝑡$ of degree at most $2$ , so by the Leibniz formula (Technique 5.3.18) the entries of $adj (𝐴_{𝑡} 𝐵_{𝑡})$ , which are $\pm$ determinants of size $𝑛 - 1$ , are polynomials in $𝑡$ of degree at most $2 (𝑛 - 1)$ . The entries of $adj 𝐴_{𝑡}$ and $adj 𝐵_{𝑡}$ have degree at most $𝑛 - 1$ , so the entries of $(adj 𝐵_{𝑡}) (adj 𝐴_{𝑡})$ , which are sums of products of two such, have degree at most $2 (𝑛 - 1)$ (a product of polynomials in $𝑡$ of degrees at most $𝑑_{1}$ and $𝑑_{2}$ is one of degree at most $𝑑_{1} + 𝑑_{2}$ , by distributivity).

Fix a position, and let $𝑃,$ $𝑄 \in$ ${𝐹 [𝑥]}_{\leq 2 (𝑛 - 1)}$ give the corresponding entries of the two sides. By Proposition 5.3.19, $det 𝐴_{𝑡}$ and $det 𝐵_{𝑡}$ are values of polynomials of degree $𝑛$ with leading coefficient $1$ , so each vanishes for at most $𝑛$ values of $𝑡$ (Lemma 3.4.23). For all other $𝑡$ , $𝐴_{𝑡}$ and $𝐵_{𝑡}$ are invertible, and $𝑃 (𝑡) = 𝑄 (𝑡)$ by the first part. Since $𝐹$ is infinite, this happens for more than $2 (𝑛 - 1) + 1$ values of $𝑡$ , so $𝑃 = 𝑄$ by Lemma 3.4.23. Setting $𝑡 = 0$ at every position gives $adj (𝐴 𝐵) =$ $(adj 𝐵) (adj 𝐴)$ .

Exercise 5.5.42.standard Here is a “proof” that for all $𝑎, 𝑏, 𝑐 \in 𝐹$ ,

𝐷 (𝑎, 𝑏, 𝑐) = det (\begin{matrix} 1 & 𝑎 & 𝑎^{3} \\ 1 & 𝑏 & 𝑏^{3} \\ 1 & 𝑐 & 𝑐^{3} \end{matrix}) = (𝑏 - 𝑎) (𝑐 - 𝑎) (𝑐 - 𝑏) .

Fix distinct $𝑎$ and $𝑏$ . Expanding along the last row, $𝐷 (𝑎, 𝑏, 𝑐)$ is a polynomial in $𝑐$ of degree at most $3$ . It vanishes at $𝑐 = 𝑎$ and at $𝑐 = 𝑏$ , since the matrix then has two equal rows. The right side also vanishes exactly at $𝑐 = 𝑎$ and $𝑐 = 𝑏$ . Two polynomials with the same roots are equal, so $𝐷 (𝑎, 𝑏, 𝑐) =$ $(𝑏 - 𝑎) (𝑐 - 𝑎) (𝑐 - 𝑏)$ . If $𝑎 = 𝑏$ , both sides are $0$ .

(a)Find the errors, and show that the claimed formula is false for $𝐹 = ℚ$ .
(b)Find and prove the correct formula.

Solution.

Uses. Lemma 5.5.23 (A polynomial with prescribed roots), Theorem 5.5.3 (Cofactor expansion), Corollary 5.4.15 (Rows), Lemma 5.5.2 (A row or column with one nonzero entry)

Techniques. Expose a factor with row and column operations (Technique 5.5.22), Polynomial identity arguments (Technique 5.5.24)

Hint 1. What is the coefficient of

𝑐^{3}

𝐷 (𝑎, 𝑏, 𝑐)

? Compare with the right side. Then test

𝑎 = 0

𝑏 = 1

𝑐 = 2

Hint 2. For (b), subtract row

1

from rows

2

and

3

, and use

𝑏^{3} -

𝑎^{3} =

(𝑏 - 𝑎) (𝑏^{2} + 𝑎 𝑏 + 𝑎^{2})

Sketch. (a) Two polynomials with the same roots need not be equal:

𝐷

has degree

3

𝑐

with leading coefficient

𝑏 - 𝑎

, two known roots do not determine it, and the right side has degree

2

. At

(0, 1, 2)

𝐷 = 6

but the right side is

2

. (b) Row operations give

𝐷 =

(𝑏 - 𝑎) (𝑐 - 𝑎) det (\begin{matrix} 1 & 𝑏^{2} + 𝑎 𝑏 + 𝑎^{2} \\ 1 & 𝑐^{2} + 𝑐 𝑎 + 𝑎^{2} \end{matrix}) =

(𝑏 - 𝑎) (𝑐 - 𝑎) (𝑐 - 𝑏) (𝑎 + 𝑏 + 𝑐)

(a) The step “two polynomials with the same roots are equal” is false: $𝑥$ and $2 𝑥$ have the same roots. Lemma 5.5.23 says that a polynomial of degree at most $𝑛$ is determined by $𝑛$ distinct roots together with its coefficient of $𝑥^{𝑛}$ . Here $𝑛 = 3$ , but only two roots are known, and the coefficients are not compared. In fact, expanding along the last row, the coefficient of $𝑐^{3}$ in $𝐷 (𝑎, 𝑏, 𝑐)$ is the cofactor ${(- 1)}^{3 + 3} det (\begin{matrix} 1 & 𝑎 \\ 1 & 𝑏 \end{matrix}) =$ $𝑏 -$ $𝑎$ , which is nonzero, while the right side has degree $2$ in $𝑐$ . (The claim “the right side vanishes exactly at $𝑐 = 𝑎$ and $𝑐 = 𝑏$ ” does not repair this, since $𝐷$ may have a third root.) Concretely, for $𝑎 = 0$ , $𝑏 = 1$ , $𝑐 = 2$ ,

𝐷 (0, 1, 2) = det (\begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 2 & 8 \end{matrix}) = 8 - 2 = 6,

while $(1 - 0) (2 - 0) (2 - 1) = 2$ , in $ℚ$ . (Over some fields the claim happens to hold, for instance over $𝔽_{2}$ , where three distinct elements do not exist; by (b), it fails exactly when there are distinct $𝑎, 𝑏, 𝑐$ with $𝑎 + 𝑏 + 𝑐 \neq 1$ .)

(b) We show $𝐷 (𝑎, 𝑏, 𝑐) =$ $(𝑎 + 𝑏 + 𝑐) (𝑏 - 𝑎) (𝑐 - 𝑎) (𝑐 - 𝑏)$ for all $𝑎, 𝑏, 𝑐 \in 𝐹$ . Subtract row $1$ from rows $2$ and $3$ ; this does not change the determinant (Corollary 5.4.15). Since $𝑏^{3} -$ $𝑎^{3} =$ $(𝑏 - 𝑎) (𝑏^{2} + 𝑎 𝑏 + 𝑎^{2})$ , the new rows $2$ and $3$ are

(𝑏 - 𝑎) (0, 1, 𝑏^{2} + 𝑎 𝑏 + 𝑎^{2}) and (𝑐 - 𝑎) (0, 1, 𝑐^{2} + 𝑐 𝑎 + 𝑎^{2}) .

Pulling out the factors $𝑏 - 𝑎$ and $𝑐 - 𝑎$ (Corollary 5.4.15) and expanding along the first column, whose only nonzero entry is the $1$ in row $1$ (Lemma 5.5.2),

\begin{aligned} 𝐷 (𝑎, 𝑏, 𝑐) & = (𝑏 - 𝑎) (𝑐 - 𝑎) det (\begin{matrix} 1 & 𝑏^{2} + 𝑎 𝑏 + 𝑎^{2} \\ 1 & 𝑐^{2} + 𝑐 𝑎 + 𝑎^{2} \end{matrix}) \\ = (𝑏 - 𝑎) (𝑐 - 𝑎) (𝑐^{2} - 𝑏^{2} + 𝑎 (𝑐 - 𝑏)) = (𝑏 - 𝑎) (𝑐 - 𝑎) (𝑐 - 𝑏) (𝑎 + 𝑏 + 𝑐) . \end{aligned}

No division was used, so this holds in every field, including when $𝑎, 𝑏, 𝑐$ are not distinct. At $(0, 1, 2)$ it gives $3 \cdot 2 = 6$ , as computed in (a).

Exercise 5.5.43.routine Use Theorem 5.5.21 to give short proofs of the following, which Section 1.5 proved without determinants.

(a)If $𝜆_{1}, \dots, 𝜆_{𝑘} \in 𝐹$ are distinct, then the sequences $𝐬_{𝜆_{𝑖}} =$ $(1, 𝜆_{𝑖}, 𝜆_{𝑖}^{2}, \dots)$ are linearly independent (Exercise 1.5.44).
(b)If $𝜆_{1}, \dots, 𝜆_{𝑘} \in ℝ$ are distinct, then the functions $𝑡 \mapsto 𝑒^{𝜆_{𝑖} 𝑡}$ are linearly independent in $ℝ^{ℝ}$ (Exercise 1.5.45).

Solution.

Uses. Theorem 5.5.21 (The Vandermonde determinant), Theorem 5.4.14 (The transpose), Corollary 5.4.8 (Vanishing determinants), Theorem 1.5.5 (Independence is decided at zero)

Hint 1. A linear relation among infinite sequences gives in particular a relation among their first

𝑘

entries. Which matrix has columns

(1, 𝜆_{𝑖}, \dots, 𝜆_{𝑖}^{𝑘 - 1})

Hint 2. For (b), differentiate a relation

\sum_{𝑖} 𝑎_{𝑖} 𝑒^{𝜆_{𝑖} 𝑡} = 0

repeatedly and set

𝑡 = 0

Sketch. (a) If

\sum_{𝑖} 𝑎_{𝑖} 𝐬_{𝜆_{𝑖}} = 𝟎

, the entries in positions

0, \dots, 𝑘 - 1

give

𝑉^{𝖳} 𝐚 = 𝟎

with

𝑉 = 𝑉 (𝜆_{1}, \dots, 𝜆_{𝑘})

. Since

det 𝑉^{𝖳} =

det 𝑉 =

\prod_{𝑖 < 𝑗} (𝜆_{𝑗} - 𝜆_{𝑖}) \neq

0

𝐚 = 𝟎

. (b) Differentiating

𝑚

times and setting

𝑡 = 0

gives

\sum_{𝑖} 𝑎_{𝑖} 𝜆_{𝑖}^{𝑚} = 0

for

𝑚 = 0, \dots, 𝑘 - 1

, the same system.

Let $𝑉 =$ $𝑉 (𝜆_{1}, \dots, 𝜆_{𝑘}) \in$ $𝐹^{𝑘 \times 𝑘}$ , whose row $𝑖$ is $(1, 𝜆_{𝑖}, \dots, 𝜆_{𝑖}^{𝑘 - 1})$ . The $(𝑚 + 1)$ -th row of $𝑉^{𝖳}$ is $(𝜆_{1}^{𝑚}, \dots, 𝜆_{𝑘}^{𝑚})$ , so for $𝐚 = (𝑎_{1}, \dots, 𝑎_{𝑘})$ , the system $𝑉^{𝖳} 𝐚 = 𝟎$ says that $\sum_{𝑖} 𝑎_{𝑖} 𝜆_{𝑖}^{𝑚} = 0$ for $𝑚 = 0, \dots, 𝑘 - 1$ . By Theorem 5.5.21 and Theorem 5.4.14, $det 𝑉^{𝖳} =$ $\prod_{𝑖 < 𝑗} (𝜆_{𝑗} - 𝜆_{𝑖}) \neq$ $0$ , so $𝑉^{𝖳}$ is invertible and the only solution is $𝐚 = 𝟎$ (Corollary 5.4.8).

(a) If $\sum_{𝑖} 𝑎_{𝑖} 𝐬_{𝜆_{𝑖}} = 𝟎$ , then the entries in positions $𝑚 = 0, \dots, 𝑘 - 1$ give $\sum_{𝑖} 𝑎_{𝑖} 𝜆_{𝑖}^{𝑚} = 0$ . So $𝐚 = 𝟎$ , and the sequences are independent by Theorem 1.5.5.

(b) If $\sum_{𝑖} 𝑎_{𝑖} 𝑒^{𝜆_{𝑖} 𝑡} = 0$ for all $𝑡 \in ℝ$ , then differentiating $𝑚$ times gives $\sum_{𝑖} 𝑎_{𝑖} 𝜆_{𝑖}^{𝑚} 𝑒^{𝜆_{𝑖} 𝑡} =$ $0$ for all $𝑡$ , and setting $𝑡 = 0$ gives $\sum_{𝑖} 𝑎_{𝑖} 𝜆_{𝑖}^{𝑚} = 0$ , for $𝑚 = 0, \dots, 𝑘 - 1$ . So $𝐚 = 𝟎$ .

Exercise 5.5.44.hard Let $𝑐_{0}, \dots, 𝑐_{𝑛} \in 𝐹$ be distinct and $𝑑_{0}, \dots, 𝑑_{𝑛} \in 𝐹$ , and let $𝑝 \in {𝐹 [𝑥]}_{\leq 𝑛}$ be the polynomial with $𝑝 (𝑐_{𝑖}) = 𝑑_{𝑖}$ for all $𝑖$ (Theorem 3.4.24).

(a)Use Cramer’s rule to show that the coefficient of $𝑥^{𝑛}$ in $𝑝$ is
$\sum_{𝑖 = 0}^{𝑛} \frac{𝑑_{𝑖}}{\prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗})} .$
(b)Deduce that $\sum_{𝑖 = 0}^{𝑛} 𝑐_{𝑖}^{𝑚} / \prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗})$ is $0$ for $0 \leq 𝑚 < 𝑛$ and $1$ for $𝑚 = 𝑛$ .

Solution.

Uses. Theorem 5.5.14 (Cramer’s rule), Theorem 5.5.21 (The Vandermonde determinant), Theorem 5.5.3 (Cofactor expansion), Definition 3.4.22 (Vandermonde matrix), Theorem 3.4.24 (Polynomial interpolation)

Hint 1. The coefficient vector

𝐚

𝑝

solves

𝑉 𝐚 = 𝐝

, and the coefficient of

𝑥^{𝑛}

is its last entry. Replace the last column of

𝑉

𝐝

and expand along that column.

Hint 2. Deleting row

𝑖 + 1

and the last column of

𝑉

leaves

𝑉 (𝑐_{0}, \dots, 𝑐_{𝑖 - 1}, 𝑐_{𝑖 + 1}, \dots, 𝑐_{𝑛})

. Divide its Vandermonde product into that of

𝑉

: which factors are left over?

Hint 3. For (b), which polynomial of degree at most

𝑛

takes the values

𝑐_{𝑖}^{𝑚}

Sketch. By Cramer,

𝑎_{𝑛} =

det 𝑉_{𝑛 + 1} (𝐝) / det 𝑉

. Expanding along the last column,

det 𝑉_{𝑛 + 1} (𝐝) =

\sum_{𝑖} {(- 1)}^{𝑖 + 𝑛} 𝑑_{𝑖} det 𝑉_{𝑖}

, where

𝑉_{𝑖}

omits

𝑐_{𝑖}

. The quotient

det 𝑉 / det 𝑉_{𝑖}

is the product of the factors of

det 𝑉

involving

𝑐_{𝑖}

, namely

\prod_{𝑗 < 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗}) \prod_{𝑘 > 𝑖} (𝑐_{𝑘} - 𝑐_{𝑖}) =

{(- 1)}^{𝑛 - 𝑖} \prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗})

. The signs cancel. For (b), the interpolating polynomial of the values

𝑐_{𝑖}^{𝑚}

𝑥^{𝑚}

(a) Write $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑛} 𝑥^{𝑛}$ . As in Section 3.4, $𝐚 = (𝑎_{0}, \dots, 𝑎_{𝑛})$ solves $𝑉 𝐚 = 𝐝$ , where $𝑉 = 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛})$ and $𝐝 = (𝑑_{0}, \dots, 𝑑_{𝑛})$ , and $det 𝑉 \neq 0$ by Theorem 5.5.21. The coefficient $𝑎_{𝑛}$ is the entry of $𝐚$ in position $𝑛 + 1$ , so by Theorem 5.5.14, $𝑎_{𝑛} =$ $det 𝑉_{𝑛 + 1} (𝐝) / det 𝑉$ , where $𝑉_{𝑛 + 1} (𝐝)$ is $𝑉$ with its last column replaced by $𝐝$ .

Expanding along the last column, whose entry in row $𝑖 + 1$ is $𝑑_{𝑖}$ ,

det 𝑉_{𝑛 + 1} (𝐝) = \sum_{𝑖 = 0}^{𝑛} {(- 1)}^{(𝑖 + 1) + (𝑛 + 1)} 𝑑_{𝑖} det 𝑊_{𝑖},

where $𝑊_{𝑖}$ is $𝑉$ with row $𝑖 + 1$ and the last column deleted. Its rows are $(1, 𝑐_{𝑘}, \dots, 𝑐_{𝑘}^{𝑛 - 1})$ for $𝑘 \neq 𝑖$ , so $𝑊_{𝑖} =$ $𝑉 (𝑐_{0}, \dots, 𝑐_{𝑖 - 1}, 𝑐_{𝑖 + 1}, \dots, 𝑐_{𝑛})$ , and by Theorem 5.5.21 $det 𝑊_{𝑖}$ is the product of $𝑐_{𝑙} - 𝑐_{𝑘}$ over all $𝑘 < 𝑙$ with $𝑘, 𝑙 \neq 𝑖$ . The product for $det 𝑉$ has, in addition, exactly the factors that involve $𝑖$ :

det 𝑉 = det 𝑊_{𝑖} \cdot \prod_{𝑗 < 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗}) \cdot \prod_{𝑘 > 𝑖} (𝑐_{𝑘} - 𝑐_{𝑖}) = {(- 1)}^{𝑛 - 𝑖} det 𝑊_{𝑖} \prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗}),

since there are $𝑛 - 𝑖$ indices $𝑘 > 𝑖$ , and $𝑐_{𝑘} -$ $𝑐_{𝑖} =$ $- (𝑐_{𝑖} - 𝑐_{𝑘})$ . Hence

𝑎_{𝑛} = \sum_{𝑖 = 0}^{𝑛} {(- 1)}^{𝑖 + 𝑛} 𝑑_{𝑖} \frac{det 𝑊_{𝑖}}{det 𝑉} = \sum_{𝑖 = 0}^{𝑛} {(- 1)}^{𝑖 + 𝑛} {(- 1)}^{𝑛 - 𝑖} \frac{𝑑_{𝑖}}{\prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗})} = \sum_{𝑖 = 0}^{𝑛} \frac{𝑑_{𝑖}}{\prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗})},

since ${(- 1)}^{𝑖 + 𝑛} {(- 1)}^{𝑛 - 𝑖} =$ ${(- 1)}^{2 𝑛} =$ $1$ .

(b) Let $0 \leq 𝑚 \leq 𝑛$ and $𝑑_{𝑖} = 𝑐_{𝑖}^{𝑚}$ . The polynomial $𝑥^{𝑚}$ has degree at most $𝑛$ and takes the values $𝑐_{𝑖}^{𝑚}$ at the nodes, so by the uniqueness in Theorem 3.4.24 it is $𝑝$ . Its coefficient of $𝑥^{𝑛}$ is $0$ if $𝑚 < 𝑛$ and $1$ if $𝑚 = 𝑛$ , and by (a) this coefficient is $\sum_{𝑖} 𝑐_{𝑖}^{𝑚} / \prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗})$ .

Exercise 5.5.45.hard For $𝑥 \in ℝ$ and $𝑛 \geq 1$ , let $𝑀_{𝑛} (𝑥) \in ℝ^{𝑛 \times 𝑛}$ be tridiagonal with every diagonal entry equal to $𝑥$ and every entry directly above or below the diagonal equal to $1$ . Let $𝑑_{𝑛} (𝑥) =$ $det 𝑀_{𝑛} (𝑥)$ and $𝑑_{0} (𝑥) = 1$ .

(a)Show that $𝑑_{𝑛} (𝑥) =$ $𝑥 𝑑_{𝑛 - 1} (𝑥) -$ $𝑑_{𝑛 - 2} (𝑥)$ for $𝑛 \geq 2$ , and that $𝑑_{𝑛} (𝑥) = 𝑃_{𝑛} (𝑥)$ for a polynomial $𝑃_{𝑛} \in {ℝ [𝑥]}_{\leq 𝑛}$ with coefficient $1$ of $𝑥^{𝑛}$ .
(b)Show that if $𝑥 = 2 cos 𝜃$ with $0 < 𝜃 < 𝜋$ , then $𝑑_{𝑛} (𝑥) =$ $sin ((𝑛 + 1) 𝜃) / sin 𝜃$ .
(c)Deduce that $𝑀_{𝑛} (𝑥)$ is singular exactly for the $𝑛$ values $𝑥 =$ $2 cos (𝑘 𝜋 / (𝑛 + 1))$ , $𝑘 = 1, \dots, 𝑛$ , and that $𝑑_{𝑛} (𝑥) =$ $\prod_{𝑘 = 1}^{𝑛} (𝑥 - 2 cos (𝑘 𝜋 / (𝑛 + 1)))$ for every $𝑥 \in ℝ$ .

Solution.

Uses. Proposition 5.5.18 (Tridiagonal determinants), Lemma 5.5.23 (A polynomial with prescribed roots), Theorem 5.4.7 (Invertibility and the determinant), $sin (𝑎 + 𝑏) +$ $sin (𝑎 - 𝑏) =$ $2 sin 𝑎 cos 𝑏$

Techniques. Induction on matrix size (Technique 5.5.17), Polynomial identity arguments (Technique 5.5.24)

Hint 1. (a) is Proposition 5.5.18 with

𝑎_{𝑘} = 𝑥

and

𝑏_{𝑘} 𝑐_{𝑘} = 1

. For the polynomial, induct with the recurrence.

Hint 2. (b) Induct on

𝑛

. The identity

sin ((𝑛 + 2) 𝜃) +

sin (𝑛 𝜃) =

2 sin ((𝑛 + 1) 𝜃) cos 𝜃

is the recurrence in disguise.

Hint 3. (c) The numbers

2 cos (𝑘 𝜋 / (𝑛 + 1))

𝑘 = 1, \dots, 𝑛

, are distinct roots of

𝑃_{𝑛}

. How many roots can a polynomial of degree

𝑛

with leading coefficient

1

have, given Lemma 5.5.23?

Sketch. (a) By Proposition 5.5.18,

𝑑_{𝑛} =

𝑥 𝑑_{𝑛 - 1} -

𝑑_{𝑛 - 2}

, and by induction

𝑃_{𝑛} =

𝑥 𝑃_{𝑛 - 1} -

𝑃_{𝑛 - 2}

has degree

𝑛

and leading coefficient

1

. (b)

𝑑_{0} = 1

and

𝑑_{1} =

2 cos 𝜃 =

sin 2 𝜃 / sin 𝜃

; the sine identity turns the recurrence into the claim for

𝑛 + 1

. (c)

sin ((𝑛 + 1) 𝜃) = 0

for

𝜃 = 𝑘 𝜋 / (𝑛 + 1)

, giving

𝑛

distinct roots

2 cos (𝑘 𝜋 / (𝑛 + 1))

(- 2, 2)

. By Lemma 5.5.23,

𝑃_{𝑛} (𝑥) =

\prod_{𝑘} (𝑥 - 2 cos (𝑘 𝜋 / (𝑛 + 1)))

for all

𝑥

, which vanishes only at these points.

(a) By Proposition 5.5.18 with $𝑎_{𝑘} = 𝑥$ and $𝑏_{𝑘} = 𝑐_{𝑘} = 1$ , $𝑑_{𝑛} (𝑥) =$ $𝑥 𝑑_{𝑛 - 1} (𝑥) -$ $𝑑_{𝑛 - 2} (𝑥)$ for $𝑛 \geq 2$ , with $𝑑_{0} (𝑥) = 1$ and $𝑑_{1} (𝑥) = 𝑥$ . Define $𝑃_{0} = 1$ , $𝑃_{1} = 𝑥$ , and $𝑃_{𝑛} =$ $𝑥 𝑃_{𝑛 - 1} -$ $𝑃_{𝑛 - 2}$ , where multiplying by $𝑥$ shifts the coefficients up by one place. By induction, $𝑃_{𝑛} \in {ℝ [𝑥]}_{\leq 𝑛}$ has coefficient $1$ of $𝑥^{𝑛}$ (it comes from $𝑥 𝑃_{𝑛 - 1}$ alone, as $𝑃_{𝑛 - 2}$ has degree at most $𝑛 - 2$ ), and $𝑃_{𝑛} (𝑥) = 𝑑_{𝑛} (𝑥)$ for every $𝑥$ , since both sides satisfy the same recurrence with the same initial values.

(b) Let $𝑥 = 2 cos 𝜃$ with $0 < 𝜃 < 𝜋$ , so $sin 𝜃 \neq 0$ , and let $𝑒_{𝑛} =$ $sin ((𝑛 + 1) 𝜃) / sin 𝜃$ . Then $𝑒_{0} = 1 = 𝑑_{0}$ and $𝑒_{1} =$ $sin 2 𝜃 / sin 𝜃 =$ $2 cos 𝜃 =$ $𝑑_{1}$ . With $𝑎 = (𝑛 + 1) 𝜃$ and $𝑏 = 𝜃$ , the identity $sin (𝑎 + 𝑏) +$ $sin (𝑎 - 𝑏) =$ $2 sin 𝑎 cos 𝑏$ gives

𝑒_{𝑛 + 1} + 𝑒_{𝑛 - 1} = 2 cos 𝜃 𝑒_{𝑛} = 𝑥 𝑒_{𝑛},

so $(𝑒_{𝑛})$ satisfies the same recurrence as $(𝑑_{𝑛} (𝑥))$ . By induction, $𝑑_{𝑛} (𝑥) = 𝑒_{𝑛}$ for all $𝑛$ .

(c) For $𝑘 = 1, \dots, 𝑛$ , let $𝜃_{𝑘} =$ $𝑘 𝜋 / (𝑛 + 1) \in$ $(0, 𝜋)$ and $𝑥_{𝑘} = 2 cos 𝜃_{𝑘}$ . Since $cos$ is strictly decreasing on $(0, 𝜋)$ , the $𝑥_{𝑘}$ are distinct. By (b), $𝑑_{𝑛} (𝑥_{𝑘}) =$ $sin (𝑘 𝜋) / sin 𝜃_{𝑘} =$ $0$ . So $𝑃_{𝑛}$ is a polynomial of degree at most $𝑛$ with coefficient $1$ of $𝑥^{𝑛}$ and the $𝑛$ distinct roots $𝑥_{1}, \dots, 𝑥_{𝑛}$ , and Lemma 5.5.23 gives

𝑑_{𝑛} (𝑥) = 𝑃_{𝑛} (𝑥) = (𝑥 - 𝑥_{1}) (𝑥 - 𝑥_{2}) \dots (𝑥 - 𝑥_{𝑛}) for every 𝑥 \in ℝ .

A product of real numbers is $0$ only if a factor is, so $𝑑_{𝑛} (𝑥) = 0$ exactly when $𝑥$ is one of the $𝑥_{𝑘}$ , and by Theorem 5.4.7 these are exactly the $𝑥$ for which $𝑀_{𝑛} (𝑥)$ is singular.

Exercise 5.5.46.routine Find a matrix

𝐴 \in 𝔽_{3}^{4 \times 4}

such that

det (𝑡 𝐼_{4} - 𝐴) =

𝑡^{4} +

𝑡 +

2

for every

𝑡 \in 𝔽_{3}

. Then show that

𝑡 𝐼_{4} - 𝐴

is invertible for every

𝑡 \in 𝔽_{3}

Solution.

Uses. Proposition 5.5.20 (Companion matrices), Theorem 5.4.7 (Invertibility and the determinant)

Hint 1. Use Proposition 5.5.20 with

𝑎_{0} = 2

𝑎_{1} = 1

𝑎_{2} = 𝑎_{3} = 0

, and reduce

- 𝑎_{𝑘}

modulo

3

Hint 2. Evaluate

𝑡^{4} + 𝑡 + 2

𝑡 = 0, 1, 2

Sketch. The matrix

𝐴

of Proposition 5.5.20 has last column

- (2, 1, 0, 0) =

(1, 2, 0, 0)

𝔽_{3}

and

1

s just below the diagonal. The values

𝑝 (0) = 2

𝑝 (1) = 1

𝑝 (2) = 2

are nonzero.

Let $𝑝 =$ $2 +$ $𝑥 +$ $𝑥^{4} \in$ $𝔽_{3} [𝑥]$ , so $𝑎_{0} = 2$ , $𝑎_{1} = 1$ , $𝑎_{2} = 𝑎_{3} = 0$ . In $𝔽_{3}$ , $- 2 = 1$ and $- 1 = 2$ , so the matrix of Proposition 5.5.20 is

𝐴 = (\begin{matrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix}),

and $det (𝑡 𝐼_{4} - 𝐴) =$ $𝑝 (𝑡)$ for every $𝑡 \in 𝔽_{3}$ . Now $𝑝 (0) = 2$ , $𝑝 (1) = 1 + 1 + 2 = 4 = 1$ , and $𝑝 (2) = 16 + 2 + 2 = 20 = 2$ in $𝔽_{3}$ . None of these is $0$ , so $𝑡 𝐼_{4} - 𝐴$ is invertible for every $𝑡 \in 𝔽_{3}$ by Theorem 5.4.7. (In Section 7.2 this says that $𝐴$ has no eigenvalue in $𝔽_{3}$ .)

Exercise 5.5.47.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ .

(a)Show that $det (𝐼_{𝑚} + 𝐴 𝐵) =$ $det (𝐼_{𝑛} + 𝐵 𝐴)$ (Sylvester’s determinant identity). Hint: compute the determinant of $𝑀 =$ $(\begin{matrix} 𝐼_{𝑚} & - 𝐴 \\ 𝐵 & 𝐼_{𝑛} \end{matrix})$ in two ways.
(b)Deduce that $det (𝐼_{𝑛} + 𝐮 𝐯^{𝖳}) =$ $1 +$ $𝐯^{𝖳} 𝐮$ for $𝐮, 𝐯 \in 𝐹^{𝑛}$ , and compute $det (𝐼_{𝑛} + 𝐽)$ , where every entry of $𝐽$ is $1$ .

Solution.

Uses. Theorem 2.4.34 (Block multiplication), Theorem 5.4.26 (Block-triangular matrices), Theorem 5.4.10 (Multiplicativity)

Techniques. Block decomposition (Technique 2.4.35)

Hint 1. Multiply

𝑀

on the left by

(\begin{matrix} 𝐼_{𝑚} & 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix})

, and on the right by the same matrix.

Hint 2. For (b), apply (a) to

𝐮 \in 𝐹^{𝑛 \times 1}

and

𝐯^{𝖳} \in 𝐹^{1 \times 𝑛}

, so that one of the two products is

1 \times 1

Sketch. With

𝑃 = (\begin{matrix} 𝐼_{𝑚} & 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix})

, block multiplication gives

𝑃 𝑀 =

(\begin{matrix} 𝐼_{𝑚} + 𝐴 𝐵 & 0 \\ 𝐵 & 𝐼_{𝑛} \end{matrix})

and

𝑀 𝑃 =

(\begin{matrix} 𝐼_{𝑚} & 0 \\ 𝐵 & 𝐼_{𝑛} + 𝐵 𝐴 \end{matrix})

. Since

det 𝑃 = 1

, both

det (𝐼_{𝑚} + 𝐴 𝐵)

and

det (𝐼_{𝑛} + 𝐵 𝐴)

equal

det 𝑀

. For (b),

𝐮 𝐯^{𝖳}

𝑛 \times 𝑛

and

𝐯^{𝖳} 𝐮

1 \times 1

; with

𝐮 = 𝐯 = (1, \dots, 1)

det (𝐼_{𝑛} + 𝐽) = 1 + 𝑛

(a) Let $𝑃 = (\begin{matrix} 𝐼_{𝑚} & 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix})$ . By Theorem 2.4.34,

𝑃 𝑀 = (\begin{matrix} 𝐼_{𝑚} + 𝐴 𝐵 & - 𝐴 + 𝐴 \\ 𝐵 & 𝐼_{𝑛} \end{matrix}) = (\begin{matrix} 𝐼_{𝑚} + 𝐴 𝐵 & 0 \\ 𝐵 & 𝐼_{𝑛} \end{matrix}), 𝑀 𝑃 = (\begin{matrix} 𝐼_{𝑚} & 𝐴 - 𝐴 \\ 𝐵 & 𝐵 𝐴 + 𝐼_{𝑛} \end{matrix}) = (\begin{matrix} 𝐼_{𝑚} & 0 \\ 𝐵 & 𝐼_{𝑛} + 𝐵 𝐴 \end{matrix}) .

By Theorem 5.4.26, $det 𝑃 =$ $det 𝐼_{𝑚} det 𝐼_{𝑛} =$ $1$ , $det (𝑃 𝑀) =$ $det (𝐼_{𝑚} + 𝐴 𝐵)$ , and $det (𝑀 𝑃) =$ $det (𝐼_{𝑛} + 𝐵 𝐴)$ . By Theorem 5.4.10, both equal $det 𝑃 det 𝑀 = det 𝑀$ .

(b) Apply (a) with $𝐴 = 𝐮 \in 𝐹^{𝑛 \times 1}$ and $𝐵 = 𝐯^{𝖳} \in 𝐹^{1 \times 𝑛}$ , so that $𝐴 𝐵 =$ $𝐮 𝐯^{𝖳} \in$ $𝐹^{𝑛 \times 𝑛}$ and $𝐵 𝐴 = 𝐯^{𝖳} 𝐮 \in 𝐹^{1 \times 1}$ :

det (𝐼_{𝑛} + 𝐮 𝐯^{𝖳}) = det (1 + 𝐯^{𝖳} 𝐮) = 1 + 𝐯^{𝖳} 𝐮 .

With $𝐮 = 𝐯 = (1, \dots, 1)$ , we have $𝐮 𝐯^{𝖳} = 𝐽$ and $𝐯^{𝖳} 𝐮 = 𝑛$ , so $det (𝐼_{𝑛} + 𝐽) = 1 + 𝑛$ .

Exercise 5.5.48.hard Let $𝑛 \geq 2$ and $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ .

(a)Show that there are scalars $𝑒_{0}, \dots, 𝑒_{𝑛} \in 𝐹$ , depending only on $𝐴$ and $𝐵$ , such that $det (𝐴 + 𝑡 𝐵) =$ $𝑒_{0} +$ $𝑒_{1} 𝑡 +$ $\dots +$ $𝑒_{𝑛} 𝑡^{𝑛}$ for every $𝑡 \in 𝐹$ , with $𝑒_{0} = det 𝐴$ , $𝑒_{𝑛} = det 𝐵$ , and
$𝑒_{1} = tr (adj (𝐴) 𝐵) .$
(b)Deduce that the coefficient of $𝑡$ in $det (𝐴 + 𝑡 𝐼_{𝑛})$ (in the sense of Proposition 5.3.19) is $\sum_{𝑖 = 1}^{𝑛} det 𝐴_{\hat{𝑖 𝑖}}$ , the sum of the minors along the diagonal.

Solution.

Uses. Definition 5.1.1 (Determinant function), Lemma 5.5.8 (Replacing a row or a column), Definition 5.5.6 (Cofactors, cofactor matrix, adjugate), Definition 2.4.26 (Trace), Definition 2.4.1 (Matrix product), Definition 5.3.6 (Determinant), Proposition 5.3.19 ( $det (𝐴 + 𝑡 𝐼_{𝑛})$ as a function of $𝑡$ )

Techniques. Expand by multilinearity (Technique 5.1.7)

Hint 1. Column

𝑗

𝐴 + 𝑡 𝐵

𝐚_{𝑗} + 𝑡 𝐛_{𝑗}

. Expand by multilinearity in every column, and group the terms by the number of columns in which

𝑡 𝐛_{𝑗}

was chosen.

Hint 2. The terms with exactly one such column

𝑗

are

𝑡 det 𝐴_{𝑗} (𝐛_{𝑗})

. Evaluate

det 𝐴_{𝑗} (𝐛_{𝑗})

with Lemma 5.5.8 and compare with the diagonal entries of

adj (𝐴) 𝐵

Sketch. Expanding,

det (𝐴 + 𝑡 𝐵) =

\sum_{𝑆 \subseteq [𝑛]} 𝑡^{| 𝑆 |} det 𝐴_{𝑆}

, where

𝐴_{𝑆}

takes

𝐛_{𝑗}

in the columns

𝑗 \in 𝑆

and

𝐚_{𝑗}

elsewhere. So

𝑒_{𝑘} =

\sum_{| 𝑆 | = 𝑘} det 𝐴_{𝑆}

, with

𝑒_{0} = det 𝐴

and

𝑒_{𝑛} = det 𝐵

. For

| 𝑆 | = 1

det 𝐴_{𝑗} (𝐛_{𝑗}) =

\sum_{𝑖} 𝑏_{𝑖 𝑗} 𝑐_{𝑖 𝑗}

, which is the

(𝑗, 𝑗)

entry of

adj (𝐴) 𝐵

. For (b), take

𝐵 = 𝐼_{𝑛}

tr (adj 𝐴) =

\sum_{𝑖} 𝑐_{𝑖 𝑖}

. Expanding each

det 𝐴_{𝑆}

by the Leibniz formula shows that these

𝑒_{𝑘}

are the coefficients of Proposition 5.3.19.

(a) Column $𝑗$ of $𝐴 + 𝑡 𝐵$ is $𝐚_{𝑗} + 𝑡 𝐛_{𝑗}$ . For $𝑆 \subseteq [𝑛]$ , let $𝐴_{𝑆}$ be the matrix whose column $𝑗$ is $𝐛_{𝑗}$ if $𝑗 \in 𝑆$ and $𝐚_{𝑗}$ if $𝑗 \notin 𝑆$ . Expanding by linearity in each column, one column at a time,

det (𝐴 + 𝑡 𝐵) = \sum_{𝑆 \subseteq [𝑛]} 𝑡^{| 𝑆 |} det 𝐴_{𝑆} .

Grouping by $𝑘 = | 𝑆 |$ gives the claim with $𝑒_{𝑘} =$ $\sum_{| 𝑆 | = 𝑘} det 𝐴_{𝑆}$ , which does not depend on $𝑡$ . In particular $𝑒_{0} = det 𝐴_{\emptyset} = det 𝐴$ and $𝑒_{𝑛} =$ $det 𝐴_{[𝑛]} =$ $det 𝐵$ . The sets with one element give

𝑒_{1} = \sum_{𝑗 = 1}^{𝑛} det 𝐴_{𝑗} (𝐛_{𝑗}) = \sum_{𝑗 = 1}^{𝑛} \sum_{𝑖 = 1}^{𝑛} 𝑏_{𝑖 𝑗} 𝑐_{𝑖 𝑗}

by part (b) of Lemma 5.5.8, where $𝑐_{𝑖 𝑗}$ are the cofactors of $𝐴$ . The $(𝑗, 𝑗)$ entry of $adj (𝐴) 𝐵$ is $\sum_{𝑖} {(adj 𝐴)}_{𝑗 𝑖} 𝑏_{𝑖 𝑗} =$ $\sum_{𝑖} 𝑐_{𝑖 𝑗} 𝑏_{𝑖 𝑗}$ , so $𝑒_{1} =$ $\sum_{𝑗} {(adj (𝐴) 𝐵)}_{𝑗 𝑗} =$ $tr (adj (𝐴) 𝐵)$ .

(b) With $𝐵 = 𝐼_{𝑛}$ , $𝑒_{1} =$ $tr (adj 𝐴) =$ $\sum_{𝑖} 𝑐_{𝑖 𝑖} =$ $\sum_{𝑖} det 𝐴_{\hat{𝑖 𝑖}}$ . It remains to see that these $𝑒_{𝑘}$ are the coefficients $𝑐_{𝑘}$ built in the proof of Proposition 5.3.19. (Comparing values of $𝑡 \mapsto det (𝐴 + 𝑡 𝐼_{𝑛})$ is not enough, since over a small field a function does not determine its coefficients.) Now $𝐴_{𝑆}$ has column $𝐞_{𝑗}$ for $𝑗 \in 𝑆$ , so in the Leibniz formula for $det 𝐴_{𝑆}$ the term of $𝜎$ vanishes unless $𝜎 (𝑗) = 𝑗$ for all $𝑗 \in 𝑆$ , that is, unless $𝑆 \subseteq Fix (𝜎)$ ; in that case it is $sgn (𝜎) \prod_{𝑗 \notin 𝑆} 𝑎_{𝜎 (𝑗) 𝑗}$ . Writing $𝑆^{'} = Fix (𝜎) ∖ 𝑆$ ,

\prod_{𝑗 \notin 𝑆} 𝑎_{𝜎 (𝑗) 𝑗} = \prod_{𝑗 \notin Fix (𝜎)} 𝑎_{𝜎 (𝑗) 𝑗} \prod_{𝑗 \in 𝑆^{'}} 𝑎_{𝑗 𝑗} .

Summing over the $𝑆$ with $| 𝑆 | = 𝑘$ , that is, over the $𝑆^{'} \subseteq Fix (𝜎)$ with $| 𝑆^{'} | =$ $| Fix (𝜎) | -$ $𝑘$ , gives exactly the coefficient $𝑒_{𝜎, 𝑘}$ of that proof, and summing over $𝜎$ gives $𝑒_{𝑘} = 𝑐_{𝑘}$ . (For $𝑛 = 2$ , $det 𝐴_{\hat{11}} +$ $det 𝐴_{\hat{22}} =$ $𝑎_{22} +$ $𝑎_{11} =$ $tr 𝐴$ , in agreement with the coefficient of $𝑡^{𝑛 - 1}$ found there.)

Exercise 5.5.49.standard Let $𝑛 \geq 2$ , $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ , and $𝐲 \in 𝐹^{𝑛}$ . Prove or disprove:

(a)If $det 𝐵 = 0$ and $det 𝐵_{𝑖} (𝐲) \neq 0$ for some $𝑖$ , then $𝐵 𝐱 = 𝐲$ has no solution.
(b)If $det 𝐵 = 0$ and $det 𝐵_{𝑖} (𝐲) = 0$ for every $𝑖$ , then $𝐵 𝐱 = 𝐲$ has a solution.
(c)If $𝐹 = ℚ$ , $𝐵$ and $𝐲$ have integer entries, and $det 𝐵 \neq 0$ , then the solution of $𝐵 𝐱 = 𝐲$ has integer entries.
(d)If $det 𝐵 \neq 0$ and $det 𝐵_{𝑖} (𝐲) = 0$ for every $𝑖$ , then $𝐲 = 𝟎$ .

Solution.

Uses. (5.5.3), Theorem 5.5.14 (Cramer’s rule), Corollary 5.5.12 (Integer inverses)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Recall (5.5.3): every solution satisfies

𝑥_{𝑖} det 𝐵 =

det 𝐵_{𝑖} (𝐲)

, whether or not

𝐵

is invertible.

Hint 2. For (b), try a matrix all of whose columns are equal. For (c), try

𝑛 = 2

and

𝐵 = 2 𝐼_{2}

Sketch. (a) True, by (5.5.3). (b) False:

𝐵 = 𝐽

(all entries

1

) with

𝑛 = 3

and

𝐲 = 𝐞_{1}

; each

𝐵_{𝑖} (𝐲)

has two equal columns, but the equations contradict each other. (c) False:

2 𝐼_{2} 𝐱 = 𝐞_{1}

gives

𝑥_{1} = 1 / 2

. (d) True: Cramer gives

𝐱 = 𝟎

, so

𝐲 = 𝐵 𝟎 = 𝟎

(a) True. If $𝐱$ were a solution, then by (5.5.3), $det 𝐵_{𝑖} (𝐲) =$ $𝑥_{𝑖} det 𝐵 =$ $0$ , a contradiction.

(b) False. Let $𝑛 = 3$ , let $𝐵 = 𝐽$ be the matrix with all entries $1$ , and let $𝐲 = 𝐞_{1}$ . Replacing one column of $𝐽$ by $𝐞_{1}$ leaves two columns equal to $(1, 1, 1)$ , so $det 𝐵_{𝑖} (𝐲) = 0$ for every $𝑖$ , and $det 𝐽 = 0$ . But the equations $𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 1$ and $𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 0$ (rows $1$ and $2$ ) contradict each other, so there is no solution. (Exercise 5.5.35 gives another example.) For general $𝑛 \geq 2$ , the same $𝐽$ and $𝐲 = 𝐞_{1}$ work when $𝑛 \geq 3$ ; for $𝑛 = 2$ , take $𝐵 = 0$ and $𝐲 = 𝐞_{1}$ .

(c) False. With $𝐵 = 2 𝐼_{2}$ and $𝐲 = 𝐞_{1}$ , the solution is $𝐱 = (1 / 2, 0)$ . Integrality does hold when $det 𝐵 = \pm 1$ , by Corollary 5.5.12.

(d) True. By Theorem 5.5.14, the unique solution has $𝑥_{𝑖} =$ $det 𝐵_{𝑖} (𝐲) / det 𝐵 =$ $0$ for every $𝑖$ , so $𝐱 = 𝟎$ and $𝐲 = 𝐵 𝟎 = 𝟎$ .

Exercise 5.5.50.standard

(a)Compute $det 𝑉 (1, 𝑖, - 1, - 𝑖)$ over $ℂ$ with Theorem 5.5.21.
(b)Let $𝑉 =$ $𝑉 (1, 𝑖, - 1, - 𝑖)$ and $𝜔 = 𝑖$ , so $𝑉$ has $(𝑗 + 1, 𝑘 + 1)$ entry $𝜔^{𝑗 𝑘}$ for $0 \leq 𝑗, 𝑘 \leq 3$ . Show that $𝑉^{2} = 4 𝑃$ for a permutation matrix $𝑃$ with $det 𝑃 = - 1$ , and use this to check (a) up to sign.
(c)In $𝔽_{5}$ , the element $2$ satisfies $2^{4} = 1$ , and its powers are $1, 2, 4, 3$ . Compute $det 𝑉 (1, 2, 4, 3)$ in $𝔽_{5}$ .

Solution.

Uses. Theorem 5.5.21 (The Vandermonde determinant), Theorem 5.4.10 (Multiplicativity), Exercise 5.1.5, Theorem 5.2.31 (Alternating functions and permutations), Definition 5.2.29 (Permutation matrix)

Hint 1. (a) List the six factors

𝑐_{𝑗} - 𝑐_{𝑖}

for

𝑖 < 𝑗

with

𝑐_{0} = 1

𝑐_{1} = 𝑖

𝑐_{2} = - 1

𝑐_{3} = - 𝑖

, and multiply them in pairs.

Hint 2. (b) The

(𝑗 + 1, 𝑙 + 1)

entry of

𝑉^{2}

\sum_{𝑘 = 0}^{3} 𝜔^{𝑘 (𝑗 + 𝑙)}

. When is

𝜔^{𝑗 + 𝑙} = 1

? If

𝑧^{4} = 1

and

𝑧 \neq 1

, then

1 + 𝑧 + 𝑧^{2} + 𝑧^{3} = 0

Sketch. (a) The factors are

𝑖 - 1

- 2

- 𝑖 - 1

- 1 - 𝑖

- 2 𝑖

1 - 𝑖

, with product

- 16 𝑖

. (b)

{(𝑉^{2})}_{𝑗 + 1, 𝑙 + 1} =

\sum_{𝑘} 𝜔^{𝑘 (𝑗 + 𝑙)}

4

when

𝑗 + 𝑙 \equiv 0 mod 4

and

0

otherwise, so

𝑉^{2} = 4 𝑃

with

𝑃

the matrix of

𝑗 \mapsto - 𝑗 mod 4

, a single transposition

(2 4)

on the indices;

{det (𝑉)}^{2} =

4^{4} (- 1) =

- 256 =

{(- 16 𝑖)}^{2}

. (c)

(2 - 1) (4 - 1) (3 - 1) (4 - 2) (3 - 2) (3 - 4) =

- 12 =

3

(a) With $𝑐_{0} = 1$ , $𝑐_{1} = 𝑖$ , $𝑐_{2} = - 1$ , $𝑐_{3} = - 𝑖$ , Theorem 5.5.21 gives the product of

𝑐_{1} - 𝑐_{0} = 𝑖 - 1, 𝑐_{2} - 𝑐_{0} = - 2, 𝑐_{3} - 𝑐_{0} = - 1 - 𝑖, 𝑐_{2} - 𝑐_{1} = - 1 - 𝑖, 𝑐_{3} - 𝑐_{1} = - 2 𝑖, 𝑐_{3} - 𝑐_{2} = 1 - 𝑖 .

Now $(𝑖 - 1) (1 - 𝑖) =$ $- {(1 - 𝑖)}^{2} =$ $- (- 2 𝑖) =$ $2 𝑖$ and ${(- 1 - 𝑖)}^{2} =$ ${(1 + 𝑖)}^{2} =$ $2 𝑖$ , so the product is

2 𝑖 \cdot 2 𝑖 \cdot (- 2) \cdot (- 2 𝑖) = (- 4) (4 𝑖) = - 16 𝑖 .

(b) The $(𝑗 + 1, 𝑙 + 1)$ entry of $𝑉^{2}$ is $\sum_{𝑘 = 0}^{3} 𝜔^{𝑗 𝑘} 𝜔^{𝑘 𝑙} =$ $\sum_{𝑘 = 0}^{3} 𝑧^{𝑘}$ with $𝑧 = 𝜔^{𝑗 + 𝑙}$ . If $𝑗 + 𝑙$ is divisible by $4$ , then $𝑧 = 1$ and the sum is $4$ . Otherwise $𝑧 \neq 1$ and $𝑧^{4} = {(𝜔^{4})}^{𝑗 + 𝑙} = 1$ , so $(𝑧 - 1) (1 + 𝑧 + 𝑧^{2} + 𝑧^{3}) =$ $𝑧^{4} -$ $1 =$ $0$ gives $1 + 𝑧 + 𝑧^{2} + 𝑧^{3} = 0$ . So $𝑉^{2} = 4 𝑃$ , where $𝑃$ has a $1$ in position $(𝑗 + 1, 𝑙 + 1)$ exactly when $𝑙 \equiv - 𝑗 mod 4$ . This is the permutation matrix $𝐸_{𝜋}$ of the permutation $𝜋$ of ${1, 2, 3, 4}$ that fixes $1$ and $3$ and swaps $2$ and $4$ (the indices $𝑗 + 1$ for $𝑗 = 1, 3$ ), so $det 𝑃 = sgn (𝜋) = - 1$ (Theorem 5.2.31). By Theorem 5.4.10 and Exercise 5.1.5,

{(det 𝑉)}^{2} = det (𝑉^{2}) = 4^{4} det 𝑃 = - 256 .

Indeed ${(- 16 𝑖)}^{2} =$ $256 𝑖^{2} =$ $- 256$ . This determines $det 𝑉$ up to sign, as $\pm 16 𝑖$ .

(c) With $𝑐_{0}, \dots, 𝑐_{3} = 1, 2, 4, 3$ , the factors are $2 - 1 = 1$ , $4 - 1 = 3$ , $3 - 1 = 2$ , $4 - 2 = 2$ , $3 - 2 = 1$ , and $3 - 4 = - 1$ . Their product is $1 \cdot$ $3 \cdot$ $2 \cdot$ $2 \cdot$ $1 \cdot$ $(- 1) =$ $- 12 =$ $3$ in $𝔽_{5}$ . (The argument of (b) works verbatim in $𝔽_{5}$ with $𝜔 = 2$ and gives ${(det 𝑉)}^{2} =$ $4^{4} \cdot$ $(- 1) =$ $- 256 =$ $4$ , and indeed $3^{2} = 9 = 4$ .)

Exercise 5.5.51.hardBeyond 21-242 Let $𝑛 \geq 2$ and $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . Show that

rank (adj 𝐴) = {\begin{cases} 𝑛 & if rank 𝐴 = 𝑛 \\ 1 & if rank 𝐴 = 𝑛 - 1 \\ 0 & if rank 𝐴 \leq 𝑛 - 2 . \end{cases}

Solution.

Uses. Theorem 5.5.9 (The adjugate and the inverse), Theorem 5.5.30 (Rank via minors), Theorem 4.2.11 (Rank–nullity), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ), Proposition 4.1.21 (Dimensions of subspaces)

Hint 1. The entries of

adj 𝐴

are, up to sign, the minors of order

𝑛 - 1

. Use Theorem 5.5.30 for the last two cases.

Hint 2. If

rank 𝐴 = 𝑛 - 1

, then

𝐴 adj 𝐴 = 0

. Where do the columns of

adj 𝐴

lie, and what is the dimension of that subspace?

Sketch. If

rank 𝐴 = 𝑛

adj 𝐴 = (det 𝐴) 𝐴^{- 1}

is invertible. If

rank 𝐴 \leq 𝑛 - 2

, all minors of order

𝑛 - 1

vanish (Theorem 5.5.30), so

adj 𝐴 = 0

. If

rank 𝐴 = 𝑛 - 1

, then

det 𝐴 = 0

, so

𝐴 adj 𝐴 = 0

and

im 𝑇_{adj 𝐴} \subseteq ker 𝑇_{𝐴}

, which has dimension

1

by rank–nullity; and some minor of order

𝑛 - 1

is nonzero, so

adj 𝐴 \neq 0

If $rank 𝐴 = 𝑛$ , then $𝐴$ is invertible and $adj 𝐴 = (det 𝐴) 𝐴^{- 1}$ is invertible (Theorem 5.5.9), so $rank (adj 𝐴) = 𝑛$ .

The entries of $adj 𝐴$ are $\pm det 𝐴_{\hat{𝑖 𝑗}}$ , the minors of order $𝑛 - 1$ of $𝐴$ . If $rank 𝐴 \leq 𝑛 - 2$ , these all vanish by Theorem 5.5.30 (if $𝐴 = 0$ , trivially), so $adj 𝐴 = 0$ and $rank (adj 𝐴) = 0$ .

Let $rank 𝐴 = 𝑛 - 1$ . Then $𝐴$ is not invertible, so $det 𝐴 = 0$ and $𝐴 adj 𝐴 = 0$ by Theorem 5.5.9. So for every $𝐱$ , $𝐴 (adj 𝐴) 𝐱 = 𝟎$ , that is, $im 𝑇_{adj 𝐴} \subseteq ker 𝑇_{𝐴}$ . By rank–nullity (Theorem 4.2.11), $dim ker 𝑇_{𝐴} =$ $𝑛 -$ $(𝑛 - 1) =$ $1$ , so $rank (adj 𝐴) =$ $dim im 𝑇_{adj 𝐴} \leq$ $1$ (Theorem 4.2.7, Proposition 4.1.21). On the other hand, by Theorem 5.5.30, $𝐴$ has a nonzero minor of order $𝑛 - 1$ , so $adj 𝐴 \neq 0$ and $rank (adj 𝐴) \geq 1$ . Hence $rank (adj 𝐴) = 1$ .

Exercise 5.5.52.hardBeyond 21-242 Prove the Cauchy–Binet formula of Remark 5.5.32: for $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ ,

det (𝐴 𝐵) = \sum_{𝑆 \subseteq [𝑛], | 𝑆 | = 𝑚} det 𝐴_{[𝑚] 𝑆} det 𝐵_{𝑆 [𝑚]} .

Solution.

Uses. Definition 2.4.1 (Matrix product), Definition 5.1.1 (Determinant function), Theorem 5.2.31 (Alternating functions and permutations), Definition 5.3.6 (Determinant), Definition 5.5.29 (Minors of order $𝑘$ )

Techniques. Expand by multilinearity (Technique 5.1.7)

Hint 1. Column

𝑗

𝐴 𝐵

\sum_{𝑘} 𝑏_{𝑘 𝑗} 𝐚_{𝑘}

, where

𝐚_{1}, \dots, 𝐚_{𝑛} \in 𝐹^{𝑚}

are the columns of

𝐴

. Expand

det (𝐴 𝐵)

by multilinearity in all

𝑚

columns, as in Lemma 5.3.2.

Hint 2. The terms are indexed by functions

𝑓 : [𝑚] \to [𝑛]

. Which vanish? An injective

𝑓

is determined by its image

𝑆

and a permutation

𝜎 \in 𝑆_{𝑚}

Hint 3. For fixed

𝑆 =

{𝑠_{1} < \dots < 𝑠_{𝑚}}

, collect the terms with image

𝑆

and recognize the Leibniz formula for

𝐵_{𝑆 [𝑚]}

Sketch. Expanding,

det (𝐴 𝐵) =

\sum_{𝑓} (\prod_{𝑗} 𝑏_{𝑓 (𝑗) 𝑗}) det (𝐚_{𝑓 (1)}, \dots, 𝐚_{𝑓 (𝑚)})

over all

𝑓 : [𝑚] \to [𝑛]

. Non-injective

𝑓

repeat a column. An injective

𝑓

with image

𝑆 =

{𝑠_{1} < \dots < 𝑠_{𝑚}}

𝑓 (𝑗) = 𝑠_{𝜎 (𝑗)}

for a unique

𝜎 \in 𝑆_{𝑚}

, and

det (𝐚_{𝑠_{𝜎 (1)}}, \dots) =

sgn (𝜎) det 𝐴_{[𝑚] 𝑆}

. Summing over

𝜎

gives

det 𝐴_{[𝑚] 𝑆} \sum_{𝜎} sgn (𝜎) \prod_{𝑗} 𝑏_{𝑠_{𝜎 (𝑗)} 𝑗} =

det 𝐴_{[𝑚] 𝑆} det 𝐵_{𝑆 [𝑚]}

Let $𝐚_{1}, \dots, 𝐚_{𝑛} \in 𝐹^{𝑚}$ be the columns of $𝐴$ . By Definition 2.4.1, column $𝑗$ of $𝐴 𝐵$ is $𝐴 𝐛_{𝑗} =$ $\sum_{𝑘 = 1}^{𝑛} 𝑏_{𝑘 𝑗} 𝐚_{𝑘}$ . Expanding $det (𝐴 𝐵)$ by linearity in each of its $𝑚$ columns (exactly as in the proof of Lemma 5.3.2, with $𝐚_{𝑘}$ in place of $𝐞_{𝑘}$ ),

det (𝐴 𝐵) = \sum_{𝑓 : [𝑚] \to [𝑛]} (\prod_{𝑗 = 1}^{𝑚} 𝑏_{𝑓 (𝑗) 𝑗}) det (𝐚_{𝑓 (1)}, \dots, 𝐚_{𝑓 (𝑚)}),

the sum running over all functions $𝑓 : [𝑚] \to [𝑛]$ . If $𝑓$ is not injective, the matrix $(𝐚_{𝑓 (1)}, \dots, 𝐚_{𝑓 (𝑚)})$ has two equal columns, so its determinant is $0$ .

An injective $𝑓$ has an image $𝑆 = 𝑓 ([𝑚])$ with $𝑚$ elements; write $𝑆 =$ ${𝑠_{1} < 𝑠_{2} < \dots < 𝑠_{𝑚}}$ . Then there is exactly one $𝜎 \in 𝑆_{𝑚}$ with $𝑓 (𝑗) = 𝑠_{𝜎 (𝑗)}$ for all $𝑗$ , and conversely every pair $(𝑆, 𝜎)$ gives an injective $𝑓$ in this way. The matrix with columns $𝐚_{𝑠_{1}}, \dots, 𝐚_{𝑠_{𝑚}}$ is $𝐴_{[𝑚] 𝑆}$ (Definition 5.5.29), so by Theorem 5.2.31,

det (𝐚_{𝑠_{𝜎 (1)}}, \dots, 𝐚_{𝑠_{𝜎 (𝑚)}}) = sgn (𝜎) det 𝐴_{[𝑚] 𝑆} .

Hence

det (𝐴 𝐵) = \sum_{| 𝑆 | = 𝑚} det 𝐴_{[𝑚] 𝑆} \sum_{𝜎 \in 𝑆_{𝑚}} sgn (𝜎) \prod_{𝑗 = 1}^{𝑚} 𝑏_{𝑠_{𝜎 (𝑗)} 𝑗} .

The $(𝑝, 𝑗)$ entry of $𝐵_{𝑆 [𝑚]}$ is $𝑏_{𝑠_{𝑝} 𝑗}$ , so the inner sum is the Leibniz formula (Definition 5.3.6) for $det 𝐵_{𝑆 [𝑚]}$ . This proves the formula. If $𝑚 > 𝑛$ , there are no injective $𝑓$ and no sets $𝑆$ , and both sides are $0$ .

Exercise 5.5.53.challenge Let $𝑥_{1},$ $\dots,$ $𝑥_{𝑛},$ $𝑦_{1},$ $\dots,$ $𝑦_{𝑛} \in$ $𝐹$ with $𝑥_{𝑖} + 𝑦_{𝑗} \neq 0$ for all $𝑖, 𝑗$ , and let $𝐶_{𝑛} \in 𝐹^{𝑛 \times 𝑛}$ have entries $1 / (𝑥_{𝑖} + 𝑦_{𝑗})$ .

(a)Show that
$det 𝐶_{𝑛} = \frac{\prod_{1 \leq 𝑖 < 𝑗 \leq 𝑛} (𝑥_{𝑗} - 𝑥_{𝑖}) (𝑦_{𝑗} - 𝑦_{𝑖})}{\prod_{𝑖, 𝑗 = 1}^{𝑛} (𝑥_{𝑖} + 𝑦_{𝑗})} .$
(b)Deduce that the Hilbert matrix $𝐻_{𝑛} \in ℚ^{𝑛 \times 𝑛}$ , with entries $1 / (𝑖 + 𝑗 - 1)$ , is invertible, and compute $det 𝐻_{3}$ .

Solution.

Uses. Corollary 5.4.15 (Rows), Lemma 5.1.8 (Column replacement), Theorem 5.4.26 (Block-triangular matrices), Theorem 5.4.7 (Invertibility and the determinant), induction on $𝑛$

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

Hint 1. Subtract the last row from each other row. The difference

1 / (𝑥_{𝑖} + 𝑦_{𝑗}) -

1 / (𝑥_{𝑛} + 𝑦_{𝑗})

has numerator

𝑥_{𝑛} - 𝑥_{𝑖}

, which does not depend on

𝑗

Hint 2. Pull

𝑥_{𝑛} - 𝑥_{𝑖}

out of row

𝑖

and

1 / (𝑥_{𝑛} + 𝑦_{𝑗})

out of column

𝑗

; the last row becomes all

1

s. Then subtract the last column from the others and do the same with the

𝑦

’s.

Hint 3. After both rounds, the matrix is block triangular with

𝐶_{𝑛 - 1}

in the corner and

1

in position

(𝑛, 𝑛)

Sketch. Subtracting row

𝑛

from row

𝑖 < 𝑛

gives entries

(𝑥_{𝑛} - 𝑥_{𝑖}) / ((𝑥_{𝑖} + 𝑦_{𝑗}) (𝑥_{𝑛} + 𝑦_{𝑗}))

. Pulling out

𝑥_{𝑛} - 𝑥_{𝑖}

from rows

𝑖 < 𝑛

and

1 / (𝑥_{𝑛} + 𝑦_{𝑗})

from every column makes row

𝑛

all

1

s and leaves

1 / (𝑥_{𝑖} + 𝑦_{𝑗})

elsewhere. Subtracting column

𝑛

from columns

𝑗 < 𝑛

and pulling out

𝑦_{𝑛} - 𝑦_{𝑗}

and

1 / (𝑥_{𝑖} + 𝑦_{𝑛})

leaves

(\begin{matrix} 𝐶_{𝑛 - 1} & 𝟏 \\ 0 & 1 \end{matrix})

. So

det 𝐶_{𝑛}

det 𝐶_{𝑛 - 1}

times the factors involving index

𝑛

, and induction finishes. For

𝐻_{𝑛}

, take

𝑥_{𝑖} = 𝑖

𝑦_{𝑗} = 𝑗 - 1

;

det 𝐻_{3} = 1 / 2160

(a) We induct on $𝑛$ . For $𝑛 = 1$ , both sides are $1 / (𝑥_{1} + 𝑦_{1})$ . Let $𝑛 \geq 2$ .

Rows. For each $𝑖 < 𝑛$ , subtract row $𝑛$ from row $𝑖$ ; the determinant does not change (Corollary 5.4.15). The new $(𝑖, 𝑗)$ entry, for $𝑖 < 𝑛$ , is

\frac{1}{𝑥_{𝑖} + 𝑦_{𝑗}} - \frac{1}{𝑥_{𝑛} + 𝑦_{𝑗}} = \frac{𝑥_{𝑛} - 𝑥_{𝑖}}{(𝑥_{𝑖} + 𝑦_{𝑗}) (𝑥_{𝑛} + 𝑦_{𝑗})} .

Pull the factor $𝑥_{𝑛} - 𝑥_{𝑖}$ out of row $𝑖$ , for each $𝑖 < 𝑛$ , and then the factor $1 / (𝑥_{𝑛} + 𝑦_{𝑗})$ out of column $𝑗$ , for each $𝑗$ (Corollary 5.4.15 and linearity in columns). The result is the matrix $𝐶^{'}$ with entries $1 / (𝑥_{𝑖} + 𝑦_{𝑗})$ for $𝑖 < 𝑛$ and with last row $(1, \dots, 1)$ , and

det 𝐶_{𝑛} = \frac{\prod_{𝑖 < 𝑛} (𝑥_{𝑛} - 𝑥_{𝑖})}{\prod_{𝑗 = 1}^{𝑛} (𝑥_{𝑛} + 𝑦_{𝑗})} det 𝐶^{'} .

Columns. For each $𝑗 < 𝑛$ , subtract column $𝑛$ from column $𝑗$ of $𝐶^{'}$ (Lemma 5.1.8). The last row becomes $(0, \dots, 0, 1)$ , and for $𝑖 < 𝑛$ the new $(𝑖, 𝑗)$ entry is

\frac{1}{𝑥_{𝑖} + 𝑦_{𝑗}} - \frac{1}{𝑥_{𝑖} + 𝑦_{𝑛}} = \frac{𝑦_{𝑛} - 𝑦_{𝑗}}{(𝑥_{𝑖} + 𝑦_{𝑗}) (𝑥_{𝑖} + 𝑦_{𝑛})} .

Pull $𝑦_{𝑛} - 𝑦_{𝑗}$ out of column $𝑗$ , for each $𝑗 < 𝑛$ , and $1 / (𝑥_{𝑖} + 𝑦_{𝑛})$ out of row $𝑖$ , for each $𝑖 < 𝑛$ . Row $𝑖 < 𝑛$ becomes $(1 / (𝑥_{𝑖} + 𝑦_{1}), \dots, 1 / (𝑥_{𝑖} + 𝑦_{𝑛 - 1}), 1)$ , since its last entry $1 / (𝑥_{𝑖} + 𝑦_{𝑛})$ is divided by $1 / (𝑥_{𝑖} + 𝑦_{𝑛})$ , and the last row stays $(0, \dots, 0, 1)$ . So the result is $(\begin{matrix} 𝐶_{𝑛 - 1} & 𝟏 \\ 0 & 1 \end{matrix})$ , where $𝐶_{𝑛 - 1}$ is built from $𝑥_{1}, \dots, 𝑥_{𝑛 - 1}$ and $𝑦_{1}, \dots, 𝑦_{𝑛 - 1}$ , and its determinant is $det 𝐶_{𝑛 - 1}$ by Theorem 5.4.26. Altogether

det 𝐶_{𝑛} = \frac{\prod_{𝑖 < 𝑛} (𝑥_{𝑛} - 𝑥_{𝑖}) \prod_{𝑗 < 𝑛} (𝑦_{𝑛} - 𝑦_{𝑗})}{\prod_{𝑗 = 1}^{𝑛} (𝑥_{𝑛} + 𝑦_{𝑗}) \prod_{𝑖 < 𝑛} (𝑥_{𝑖} + 𝑦_{𝑛})} det 𝐶_{𝑛 - 1} .

The new numerator factors are those of the claimed numerator with larger index $𝑛$ , and the new denominator factors are the $𝑥_{𝑖} + 𝑦_{𝑗}$ with $𝑖 = 𝑛$ or $𝑗 = 𝑛$ . So the induction hypothesis for $𝐶_{𝑛 - 1}$ gives the formula.

(b) With $𝑥_{𝑖} = 𝑖$ and $𝑦_{𝑗} = 𝑗 - 1$ , we have $𝑥_{𝑖} +$ $𝑦_{𝑗} =$ $𝑖 +$ $𝑗 -$ $1 \geq$ $1$ , so $𝐶_{𝑛} = 𝐻_{𝑛}$ . The $𝑥_{𝑖}$ are distinct and the $𝑦_{𝑗}$ are distinct, so every factor in the numerator of (a) is nonzero, and $det 𝐻_{𝑛} \neq 0$ ; $𝐻_{𝑛}$ is invertible by Theorem 5.4.7. For $𝑛 = 3$ , the numerator is ${((2 - 1) (3 - 1) (3 - 2))}^{2} =$ $4$ , and the denominator is the product of $𝑖 + 𝑗 - 1$ over $𝑖, 𝑗 \in {1, 2, 3}$ :

(1 \cdot 2 \cdot 3) (2 \cdot 3 \cdot 4) (3 \cdot 4 \cdot 5) = 6 \cdot 24 \cdot 60 = 8640 .

So $det 𝐻_{3} =$ $4 / 8640 =$ $1 / 2160$ .

More practice

The practice bank has 21 exercises on this section’s topics.