5.4 Determinants and invertibility

Corollary 5.1.18 says that a matrix that is not invertible has determinant $0$ . This section proves the converse, so that $det 𝐴 \neq 0$ exactly when $𝐴$ is invertible. The converse cannot follow from multilinearity and alternation alone, since the zero function has both properties, so the proof has to use normalization. Normalization only tells us that $det 𝐼_{𝑛} = 1$ , and we get from $𝐼_{𝑛}$ to an arbitrary invertible matrix by multiplying by elementary matrices (Theorem 3.5.19). So we first work out what one elementary matrix does to the determinant, and then build up. The same analysis proves $det (𝐴 𝐵) =$ $det 𝐴 det 𝐵$ and $det 𝐴^{𝖳} = det 𝐴$ . From these we get the row versions of all the column properties, a fast way to compute determinants by row reduction, the determinant of a linear operator, and the determinants of block-triangular matrices.

5.4.1Elementary matrices

Recall the elementary $𝑛 \times 𝑛$ matrices (Definition 3.2.2). For $𝑖 \neq 𝑗$ , $𝐸_{𝑖 𝑗}$ swaps rows $𝑖$ and $𝑗$ of $𝐼_{𝑛}$ ; for $𝑐 \neq 0$ , $𝐸_{𝑖 𝑐}$ scales row $𝑖$ of $𝐼_{𝑛}$ by $𝑐$ ; and $𝐸_{𝑖 𝑐 𝑗}$ adds $𝑐$ times row $𝑖$ of $𝐼_{𝑛}$ to row $𝑗$ , so it is $𝐼_{𝑛}$ with an extra entry $𝑐$ in position $(𝑗, 𝑖)$ . Multiplying by $𝐸$ on the left performs the row operation (Proposition 3.2.7). Multiplying on the right performs a column operation (Proposition 3.2.28): $𝐴 𝐸_{𝑖 𝑗}$ is $𝐴$ with columns $𝑖$ and $𝑗$ swapped, $𝐴 𝐸_{𝑖 𝑐}$ is $𝐴$ with column $𝑖$ scaled by $𝑐$ , and $𝐴 𝐸_{𝑖 𝑐 𝑗}$ is $𝐴$ with $𝑐$ times column $𝑗$ added to column $𝑖$ .

Intuition (Why columns first). Our axioms are statements about columns, and Section 5.1 already found the effect of each column operation on a multilinear alternating function. A swap negates it (Proposition 5.1.10), scaling a column by $𝑐$ multiplies it by $𝑐$ (multilinearity), and adding a multiple of one column to another does not change it (Lemma 5.1.8). So the products we can handle now are the products $𝐴 𝐸$ , in which $𝐸$ acts on the columns of $𝐴$ . The products $𝐸 𝐴$ , which act on rows, have to wait for the product formula (Theorem 5.4.10), and the row versions of the axioms for $det 𝐴^{𝖳} = det 𝐴$ (Theorem 5.4.14).

The lecture passes between the two kinds of products with a trick worth remembering. By Proposition 2.4.23, $𝐴 𝐸 = {(𝐸^{𝖳} 𝐴^{𝖳})}^{𝖳}$ . Here $𝐸^{𝖳} 𝐴^{𝖳}$ performs a row operation on $𝐴^{𝖳}$ , whose rows are the columns of $𝐴$ , and the outer transpose turns these rows back into columns. This is the first proof of Proposition 3.2.28.

Proposition 5.4.1 (Determinants of elementary matrices). Let

1 \leq 𝑖, 𝑗 \leq 𝑛

with

𝑖 \neq 𝑗

, and let

𝑐 \in 𝐹

. Then

det 𝐸_{𝑖 𝑗} = - 1

det 𝐸_{𝑖 𝑐 𝑗} = 1

, and

det 𝐸_{𝑖 𝑐} = 𝑐

𝑐 \neq 0

. In particular, every elementary matrix has a nonzero determinant.

Proof.routine

Uses. Definition 3.2.2 (Elementary matrices), Definition 5.1.1 (Determinant function), Proposition 5.1.10 (Alternating implies antisymmetric)

Hint 1. Each elementary matrix is

𝐼_{𝑛}

with a small change. Describe the change in terms of the columns of

𝐼_{𝑛}

, and use the axiom that fits it.

Hint 2.

𝐸_{𝑖 𝑗}

𝐼_{𝑛}

with columns

𝑖

and

𝑗

interchanged, and

𝐸_{𝑖 𝑐}

𝐼_{𝑛}

with column

𝑖

multiplied by

𝑐

. Column

𝑖

𝐸_{𝑖 𝑐 𝑗}

𝐞_{𝑖} + 𝑐 𝐞_{𝑗}

Hint 3. For

𝐸_{𝑖 𝑐 𝑗}

, expand by linearity in column

𝑖

. One of the two resulting matrices has two equal columns.

Sketch. Swapping rows

𝑖

and

𝑗

𝐼_{𝑛}

gives the same matrix as swapping its columns

𝑖

and

𝑗

, so

det 𝐸_{𝑖 𝑗} =

- det 𝐼_{𝑛} =

- 1

by antisymmetry.

𝐸_{𝑖 𝑐}

𝐼_{𝑛}

with column

𝑖

scaled by

𝑐

, so

det 𝐸_{𝑖 𝑐} = 𝑐

by linearity in column

𝑖

. Column

𝑖

𝐸_{𝑖 𝑐 𝑗}

𝐞_{𝑖} + 𝑐 𝐞_{𝑗}

, so linearity in column

𝑖

gives

det 𝐼_{𝑛} + 𝑐 det 𝐼^{'}

, where

𝐼^{'}

has

𝐞_{𝑗}

in columns

𝑖

and

𝑗

; the value is

1 + 𝑐 \cdot 0 = 1

Write $𝐞_{1}, \dots, 𝐞_{𝑛}$ for the columns of $𝐼_{𝑛}$ .

Swaps. Swapping rows $𝑖$ and $𝑗$ of $𝐼_{𝑛}$ moves the $1$ in position $(𝑖, 𝑖)$ to position $(𝑗, 𝑖)$ and the $1$ in position $(𝑗, 𝑗)$ to position $(𝑖, 𝑗)$ , and changes nothing else. So column $𝑖$ of $𝐸_{𝑖 𝑗}$ is $𝐞_{𝑗}$ , column $𝑗$ is $𝐞_{𝑖}$ , and every other column $𝑘$ is $𝐞_{𝑘}$ . That is, $𝐸_{𝑖 𝑗}$ is $𝐼_{𝑛}$ with columns $𝑖$ and $𝑗$ interchanged, and $det 𝐸_{𝑖 𝑗} =$ $- det 𝐼_{𝑛} =$ $- 1$ by Proposition 5.1.10.

Scalings. $𝐸_{𝑖 𝑐}$ is $𝐼_{𝑛}$ with column $𝑖$ replaced by $𝑐 𝐞_{𝑖}$ . By linearity in column $𝑖$ , $det 𝐸_{𝑖 𝑐} =$ $𝑐 det 𝐼_{𝑛} =$ $𝑐$ .

Replacements. $𝐸_{𝑖 𝑐 𝑗}$ is $𝐼_{𝑛}$ with an extra entry $𝑐$ in position $(𝑗, 𝑖)$ , so its column $𝑖$ is $𝐞_{𝑖} + 𝑐 𝐞_{𝑗}$ and its other columns are those of $𝐼_{𝑛}$ . Let $𝐼^{'}$ be $𝐼_{𝑛}$ with column $𝑖$ replaced by $𝐞_{𝑗}$ . By linearity in column $𝑖$ ,

det 𝐸_{𝑖 𝑐 𝑗} = det 𝐼_{𝑛} + 𝑐 det 𝐼^{'} = 1 + 𝑐 \cdot 0 = 1,

since columns $𝑖$ and $𝑗$ of $𝐼^{'}$ are both $𝐞_{𝑗}$ , and $det$ is alternating.

Finally, $- 1 \neq 0$ because $1 \neq 0$ , and $𝑐 \neq 0$ for a scaling, so all three values are nonzero. □

Over $ℝ$ these values are the signed areas observed in Section 3.2.6: a shear keeps the area of the unit square, the stretch $𝐸_{1 𝑐}$ multiplies its signed area by $𝑐$ (reflecting it when $𝑐 < 0$ ), and the swap keeps the area but reverses orientation.

The plane transformer, starting at the shear

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

. Sliding

𝐴 𝐞_{2}

along the line

𝑥_{2} = 1

gives the shears

𝐸_{2 𝑐 1}

, and the readout stays at

det 𝐴 = 1

. With

𝐴 𝐞_{2}

back at

𝐞_{2}

, moving

𝐴 𝐞_{1}

along the

𝑥_{1}

-axis gives the scalings

𝐸_{1 𝑐}

for

𝑐 \neq 0

, with

det 𝐴 = 𝑐

. Typing the entries

0, 1, 1, 0

gives the swap

𝐸_{12}

: the F is mirrored and

det 𝐴 = - 1

Lemma 5.4.2 (Multiplying by an elementary matrix). Let

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

, and suppose

𝐸

is elementary. Then

det (𝐴 𝐸) =

det 𝐴 det 𝐸

Proof.routine

Uses. Proposition 3.2.28 (Column operations are right multiplications), Proposition 5.1.10 (Alternating implies antisymmetric), Lemma 5.1.8 (Column replacement), Definition 5.1.1 (Determinant function), Proposition 5.4.1 (Determinants of elementary matrices)

Hint 1. By Proposition 3.2.28,

𝐴 𝐸

𝐴

with one column operation performed. Treat the three types of

𝐸

separately.

Hint 2. In each case, compare the factor by which the column operation changes

det 𝐴

with the value of

det 𝐸

in Proposition 5.4.1.

Sketch.

𝐴 𝐸_{𝑖 𝑗}

𝐴

with columns

𝑖

and

𝑗

swapped, so its determinant is

- det 𝐴

𝐴 𝐸_{𝑖 𝑐}

𝐴

with column

𝑖

scaled by

𝑐

, so its determinant is

𝑐 det 𝐴

𝐴 𝐸_{𝑖 𝑐 𝑗}

𝐴

with

𝑐

times column

𝑗

added to column

𝑖

, so its determinant is

det 𝐴

. The factors

- 1

𝑐

, and

1

are the determinants of the three types.

We consider the three types in turn, using Proposition 3.2.28 to describe $𝐴 𝐸$ and Proposition 5.4.1 for $det 𝐸$ .

Swaps. $𝐴 𝐸_{𝑖 𝑗}$ is $𝐴$ with columns $𝑖$ and $𝑗$ interchanged, so by Proposition 5.1.10,

det (𝐴 𝐸_{𝑖 𝑗}) = - det 𝐴 = det 𝐴 det 𝐸_{𝑖 𝑗} .

Scalings. $𝐴 𝐸_{𝑖 𝑐}$ is $𝐴$ with column $𝑖$ multiplied by $𝑐$ , so by linearity in column $𝑖$ ,

det (𝐴 𝐸_{𝑖 𝑐}) = 𝑐 det 𝐴 = det 𝐴 det 𝐸_{𝑖 𝑐} .

Replacements. $𝐴 𝐸_{𝑖 𝑐 𝑗}$ is $𝐴$ with $𝑐$ times column $𝑗$ added to column $𝑖$ , where $𝑖 \neq 𝑗$ . By Lemma 5.1.8,

det (𝐴 𝐸_{𝑖 𝑐 𝑗}) = det 𝐴 = det 𝐴 det 𝐸_{𝑖 𝑐 𝑗} .

□

Remark 5.4.3 (The values are no coincidence). In each case of the proof,

det (𝐴 𝐸) =

𝑐_{𝐸} det 𝐴

, where the factor

𝑐_{𝐸}

depends only on the column operation of

𝐸

and not on

𝐴

. Taking

𝐴 = 𝐼_{𝑛}

gives

det 𝐸 =

𝑐_{𝐸} det 𝐼_{𝑛} =

𝑐_{𝐸}

, because

𝐸 = 𝐼_{𝑛} 𝐸

is the result of performing its own column operation on

𝐼_{𝑛}

. So the lemma can be proved without computing

det 𝐸

first, and the computation of Proposition 5.4.1 then comes for free. (This is how LADW argues in its Lemma 3.6. We followed the lecture, which computes

det 𝐸

first.)

Corollary 5.4.4 (Products of elementary matrices). Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , and let $𝐸_{1},$ $\dots,$ $𝐸_{𝑘} \in$ $𝐹^{𝑛 \times 𝑛}$ be elementary. Then

det (𝐴 𝐸_{1} \dots 𝐸_{𝑘}) = det 𝐴 det 𝐸_{1} \dots det 𝐸_{𝑘} .

In particular, $det (𝐸_{1} \dots 𝐸_{𝑘}) =$ $det 𝐸_{1} \dots det 𝐸_{𝑘}$ , and this is nonzero.

Proof.routine

Uses. Lemma 5.4.2 (Multiplying by an elementary matrix), Proposition 5.4.1 (Determinants of elementary matrices), Proposition 1.1.17 (No zero divisors), induction on $𝑘$

Hint 1. Induct on

𝑘

. Group the product as

(𝐴 𝐸_{1} \dots 𝐸_{𝑘 - 1}) 𝐸_{𝑘}

Hint 2. For the last sentence, take

𝐴 = 𝐼_{𝑛}

, and recall that a field has no zero divisors.

Sketch. By Lemma 5.4.2 applied to the matrix

𝐴 𝐸_{1} \dots 𝐸_{𝑘 - 1}

and the induction hypothesis,

det (𝐴 𝐸_{1} \dots 𝐸_{𝑘}) =

det (𝐴 𝐸_{1} \dots 𝐸_{𝑘 - 1}) det 𝐸_{𝑘} =

det 𝐴 det 𝐸_{1} \dots det 𝐸_{𝑘}

. With

𝐴 = 𝐼_{𝑛}

this is the second formula; each factor is nonzero by Proposition 5.4.1, and so is the product.

We induct on $𝑘$ . For $𝑘 = 0$ the product of elementary matrices is empty, that is, equal to $𝐼_{𝑛}$ , and both sides equal $det 𝐴$ . For $𝑘 \geq 1$ , apply Lemma 5.4.2 to the matrix $𝐴 𝐸_{1} \dots 𝐸_{𝑘 - 1}$ and to $𝐸_{𝑘}$ , and then the induction hypothesis:

\begin{aligned} det (𝐴 𝐸_{1} \dots 𝐸_{𝑘}) & = det (𝐴 𝐸_{1} \dots 𝐸_{𝑘 - 1}) det 𝐸_{𝑘} \\ = det 𝐴 det 𝐸_{1} \dots det 𝐸_{𝑘 - 1} det 𝐸_{𝑘} . \end{aligned}

Taking $𝐴 = 𝐼_{𝑛}$ gives $det (𝐸_{1} \dots 𝐸_{𝑘}) =$ $det 𝐸_{1} \dots det 𝐸_{𝑘}$ . Each $det 𝐸_{𝑙}$ is nonzero by Proposition 5.4.1, and a product of nonzero elements of a field is nonzero (Proposition 1.1.17, and induction on the number of factors). □

Exercise 5.4.5.routine Let

𝐴 \in ℚ^{3 \times 3}

have

det 𝐴 = 5

, and let

𝐺 =

𝐸_{13} 𝐸_{2, 4} 𝐸_{3, - 7, 1}

, a product of

3 \times 3

elementary matrices. Find

det 𝐺

and

det (𝐴 𝐺)

. Which column operations turn

𝐴

into

𝐴 𝐺

, and in which order are they performed?

Solution.

Uses. Proposition 5.4.1 (Determinants of elementary matrices), Corollary 5.4.4 (Products of elementary matrices), Proposition 3.2.28 (Column operations are right multiplications), Remark 3.2.29 (One matrix, two operations)

Hint 1. Read off the type of each factor from its subscripts: two subscripts without a comma is a swap, two with a comma a scaling, three a replacement.

Hint 2.

𝐴 𝐺 =

((𝐴 𝐸_{13}) 𝐸_{2, 4}) 𝐸_{3, - 7, 1}

, so the leftmost factor acts first. As a right factor,

𝐸_{𝑖 𝑐 𝑗}

adds

𝑐

times column

𝑗

to column

𝑖

Sketch.

det 𝐺 = (- 1) \cdot 4 \cdot 1 = - 4

and

det (𝐴 𝐺) =

5 \cdot

(- 4) =

- 20

. The operations are: swap columns

1

and

3

, then scale column

2

4

, then add

- 7

times column

1

to column

3

$𝐸_{13}$ swaps, $𝐸_{2, 4}$ scales by $4$ , and $𝐸_{3, - 7, 1}$ is a replacement, so by Corollary 5.4.4 and Proposition 5.4.1,

\begin{matrix} det 𝐺 = det 𝐸_{13} det 𝐸_{2, 4} det 𝐸_{3, - 7, 1} \\ = (- 1) \cdot 4 \cdot 1 = - 4, \end{matrix}

and $det (𝐴 𝐺) =$ $det 𝐴 det 𝐺 =$ $- 20$ . Since $𝐴 𝐺 =$ $((𝐴 𝐸_{13}) 𝐸_{2, 4}) 𝐸_{3, - 7, 1}$ , the column operations are performed from the leftmost factor to the rightmost (Remark 3.2.29). By Proposition 3.2.28 they are: swap columns $1$ and $3$ ; scale column $2$ by $4$ ; add $- 7$ times column $1$ to column $3$ . Their effects on the determinant, $- 1$ , $4$ , and $1$ , multiply to $det 𝐺$ , as they should.

5.4.2Invertibility

We can now carry out the plan from the beginning of the section. The idea of building every invertible matrix out of elementary ones is used several times in this section, so we name it.

Technique 5.4.6 (Reduce to elementary matrices). Every invertible matrix is a product of elementary matrices (Theorem 3.5.19). So to prove a statement about all invertible matrices, it is often enough to

prove it for the three types of elementary matrices, by a direct computation; and
show that it survives multiplication: if it holds for $𝐴$ and $𝐸$ is elementary, then it holds for $𝐴 𝐸$ (or for $𝐸 𝐴$ ).

Induction on the number of factors then gives the statement for every invertible matrix. A statement about all square matrices needs a separate argument for the matrices that are not invertible. Often both sides of the claimed identity are $0$ there. Otherwise, write $𝐴 = 𝐺^{- 1} rref (𝐴)$ (Theorem 3.3.10) and use that $rref (𝐴)$ has a zero row.

Reach for it when a statement involves products, inverses, or transposes, and is easy to check on elementary matrices, which differ from $𝐼_{𝑛}$ in at most four entries. The fullest example is the first proof of Theorem 5.4.10; the first proof of Theorem 5.4.14 has the same shape. Remember the case split: a matrix that is not invertible is never a product of elementary matrices, since such products are invertible (Corollary 3.2.11). Forgetting this is a common error (Exercise 5.4.35).

Used in 9 places and 2 practice exercises

Corollary 3.5.22, Exercise 3.6.10, Problem 3.7, Theorem 5.4.7, Theorem 5.4.10, Theorem 5.4.14, Exercise 5.4.35, Exercise 5.4.49, Exercise 5.6.11; 2 practice exercises.

Theorem 5.4.7 (Invertibility and the determinant). Let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

. The following are equivalent.

(I) $𝐴$ is invertible.
(II) $det 𝐴 \neq 0$ .

Proof.standard

Uses. Corollary 5.1.18 (Non-invertible matrices), Theorem 3.5.19 (Invertible matrices are products of elementary matrices), Corollary 5.4.4 (Products of elementary matrices)

Techniques. Reduce to elementary matrices (Technique 5.4.6), Contrapositive (Technique 1.5.4)

Hint 1. One direction was proved in Section 5.1. For the other, which description of an invertible matrix makes its determinant computable?

Hint 2. Write an invertible

𝐴

as a product of elementary matrices.

Hint 3. By Corollary 5.4.4,

det 𝐴

is then a product of determinants of elementary matrices. Can such a product be

0

Sketch. (II)

\Rightarrow

(I) is the contrapositive of Corollary 5.1.18. For (I)

\Rightarrow

(II), write

𝐴 = 𝐸_{1} \dots 𝐸_{𝑘}

with elementary

𝐸_{𝑖}

. Then

det 𝐴 =

det 𝐸_{1} \dots det 𝐸_{𝑘}

, a product of the nonzero scalars

- 1

𝑐

, and

1

, which is nonzero.

(II) $\Rightarrow$ (I). We prove the contrapositive. If $𝐴$ is not invertible, then $det 𝐴 = 0$ by Corollary 5.1.18.

(I) $\Rightarrow$ (II). Suppose $𝐴$ is invertible. By Theorem 3.5.19 there are elementary matrices $𝐸_{1}, \dots, 𝐸_{𝑘}$ with $𝐴 = 𝐸_{1} \dots 𝐸_{𝑘}$ . By Corollary 5.4.4, $det 𝐴 =$ $det 𝐸_{1} \dots det 𝐸_{𝑘}$ , and this is nonzero. □

The two directions use different axioms. (II) $\Rightarrow$ (I) used only multilinearity and alternation. (I) $\Rightarrow$ (II) used normalization, through the computation $det 𝐸_{𝑖 𝑐} =$ $𝑐 det 𝐼_{𝑛} =$ $𝑐$ and its relatives in Proposition 5.4.1. This is as it must be: the zero function is multilinear and alternating, and (I) $\Rightarrow$ (II) fails for it. Combining the theorem with the Fundamental Theorems gives several equivalent ways to say that a determinant vanishes.

Corollary 5.4.8 (Vanishing determinants). Let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

. The following are equivalent.

(a) $det 𝐴 = 0$ .
(b) $𝐴$ is not invertible.
(c)The columns of $𝐴$ are linearly dependent.
(d) $𝐴 𝐱 = 𝟎$ for some nonzero $𝐱 \in 𝐹^{𝑛}$ .

Proof.routine

Uses. Theorem 5.4.7 (Invertibility and the determinant), Corollary 3.5.25 (The invertible matrix theorem), Theorem 3.5.12 (First Fundamental Theorem, completed), Definition 2.3.8 (Matrix–vector product), Theorem 1.5.5 (Independence is decided at zero)

Hint 1. (a)

\Leftrightarrow

(b) is Theorem 5.4.7. Relate both invertibility and independence of the columns to the rank.

Hint 2. For (c)

\Leftrightarrow

(d), write

𝐴 𝐱

as a linear combination of the columns of

𝐴

Sketch. (a)

\Leftrightarrow

(b) by Theorem 5.4.7. By Corollary 3.5.25 and Theorem 3.5.12,

𝐴

is invertible if and only if

rank 𝐴 = 𝑛

, if and only if its columns are independent, which gives (b)

\Leftrightarrow

(c). Since

𝐴 𝐱 =

𝑥_{1} 𝐚_{1} +

\dots +

𝑥_{𝑛} 𝐚_{𝑛}

, a nonzero solution of

𝐴 𝐱 = 𝟎

is the same thing as a nontrivial linear relation among the columns.

(a)

\Leftrightarrow

(b) is Theorem 5.4.7. By Corollary 3.5.25,

𝐴

is invertible if and only if

rank 𝐴 = 𝑛

, and by Theorem 3.5.12 this holds if and only if the columns of

𝐴

are linearly independent. Negating both sides gives (b)

\Leftrightarrow

(c). Finally,

𝐴 𝐱 =

𝑥_{1} 𝐚_{1} +

\dots +

𝑥_{𝑛} 𝐚_{𝑛}

by Definition 2.3.8, so a nonzero

𝐱

with

𝐴 𝐱 = 𝟎

is exactly a nontrivial linear relation among the columns of

𝐴

. By Theorem 1.5.5, such a relation exists if and only if the columns are linearly dependent, which is (c)

\Leftrightarrow

(d). □

For $det$ , the implication (c) $\Rightarrow$ (a) is Proposition 5.1.17, which holds for every multilinear alternating function. The implication (a) $\Rightarrow$ (c) is the converse that Exercise 5.1.22 warned about, and it needed normalization. Together with Proposition 5.3.19, the corollary also says that $𝐴 + 𝑡 𝐼_{𝑛}$ is invertible for all but at most $𝑛$ scalars $𝑡$ , and that the exceptional $𝑡$ are exactly the roots of $det (𝐴 + 𝑡 𝐼_{𝑛})$ . Their negatives reappear as eigenvalues in Section 7.3.

Exercise 5.4.9.routine Let

𝐴 (𝑡) =

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

. Find all

𝑡

for which

𝐴 (𝑡)

is invertible, when

𝑡

ranges over

ℝ

, over

ℚ

, over

𝔽_{3}

, and over

𝔽_{7}

Solution.

Uses. Corollary 5.3.9 (Rule of Sarrus), Theorem 5.4.7 (Invertibility and the determinant)

Hint 1. Compute

det 𝐴 (𝑡)

with the rule of Sarrus. It does not depend on the field.

Hint 2. You should get

1 - 2 𝑡^{2}

. In each field, decide when

2 𝑡^{2} = 1

has a solution.

Sketch.

det 𝐴 (𝑡) = 1 - 2 𝑡^{2}

. Over

ℝ

: invertible unless

𝑡 = \pm 1 / \sqrt{2}

. Over

ℚ

: always, since

\sqrt{2}

is irrational. Over

𝔽_{3}

1 -

2 𝑡^{2} =

1 +

𝑡^{2} \in

{1, 2}

, so always. Over

𝔽_{7}

2 𝑡^{2} = 1

means

𝑡^{2} = 4

, so invertible unless

𝑡 \in {2, 5}

The diagonals running down to the right have products $1$ , $𝑡 \cdot 𝑡 \cdot 0 = 0$ , and $0$ , and those running up to the right have products $0$ , $𝑡 \cdot 𝑡 \cdot 1 = 𝑡^{2}$ , and $1 \cdot 𝑡 \cdot 𝑡 = 𝑡^{2}$ . So $det 𝐴 (𝑡) = 1 - 2 𝑡^{2}$ by Corollary 5.3.9, and by Theorem 5.4.7, $𝐴 (𝑡)$ is invertible exactly when $2 𝑡^{2} \neq 1$ .

Over $ℝ$ , $2 𝑡^{2} = 1$ exactly for $𝑡 = \pm 1 / \sqrt{2}$ , so $𝐴 (𝑡)$ is invertible for all other $𝑡$ . Over $ℚ$ there is no solution, since $2 𝑡^{2} = 1$ would give ${(2 𝑡)}^{2} = 2$ with $2 𝑡$ rational; so $𝐴 (𝑡)$ is always invertible. Over $𝔽_{3}$ , $- 2 = 1$ , so $det 𝐴 (𝑡) = 1 + 𝑡^{2}$ , and $𝑡^{2} \in {0, 1}$ for $𝑡 \in {0, 1, 2}$ . So $det 𝐴 (𝑡) \in {1, 2}$ is never $0$ , and $𝐴 (𝑡)$ is always invertible. Over $𝔽_{7}$ , $2^{- 1} = 4$ , so $2 𝑡^{2} = 1$ means $𝑡^{2} = 4$ , that is, $𝑡 = 2$ or $𝑡 = - 2 = 5$ . So $𝐴 (𝑡)$ is invertible exactly when $𝑡 \notin {2, 5}$ .

5.4.3The product formula

Intuition (Areas multiply). Over

ℝ

, the absolute value of

det 𝐴

is the factor by which

𝑇_{𝐴}

scales areas in the plane (or volumes in space), and its sign records whether

𝑇_{𝐴}

preserves orientation (Section 5.1). Composition multiplies these factors. If

𝑇_{𝐵}

doubles areas and

𝑇_{𝐴}

triples them, then

𝑇_{𝐴} \circ 𝑇_{𝐵}

, which is

𝑇_{𝐴 𝐵}

(Theorem 2.4.2), multiplies them by six. If both reverse orientation, the composite preserves it, matching

(- 1) (- 1) = 1

. So signed area predicts

det (𝐴 𝐵) =

det 𝐴 det 𝐵

. Figure 5.4.1 shows an example.

Figure 5.4.1. The unit square

𝑄

with a letter F (left), its image under

𝑇_{𝐵}

for

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

(middle), and its image under

𝑇_{𝐴} \circ 𝑇_{𝐵} = 𝑇_{𝐴 𝐵}

for

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

(right), where

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

. The arrows are the images of

𝐞_{1}

(blue) and

𝐞_{2}

(ochre). Here

det 𝐵 = 2

and

det 𝐴 = 2

𝑇_{𝐵}

doubles the area of

𝑄

, and

𝑇_{𝐴}

, which rotates by

45 °

and stretches by

\sqrt{2}

, doubles it again, so

det (𝐴 𝐵) = 4

Theorem 5.4.10 (Multiplicativity). For all $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ ,

det (𝐴 𝐵) = det 𝐴 det 𝐵 .

Proof (by factoring into elementary matrices).standard

Uses. Theorem 3.5.19 (Invertible matrices are products of elementary matrices), Corollary 5.4.4 (Products of elementary matrices), Theorem 5.4.7 (Invertibility and the determinant), Theorem 3.5.23 (One-sided inverses of square matrices)

Techniques. Reduce to elementary matrices (Technique 5.4.6)

Hint 1. Suppose first that

𝐵

is invertible, and factor it into elementary matrices. Note that Corollary 5.4.4 allows an arbitrary matrix on the left.

Hint 2. If

𝐵

is not invertible, show that

𝐴 𝐵

is not invertible either. What are both sides then?

Hint 3. If

𝐴 𝐵

had an inverse

𝐶

, then

(𝐶 𝐴) 𝐵 = 𝐼_{𝑛}

. What does a one-sided inverse of a square matrix give?

Sketch. If

𝐵 = 𝐸_{1} \dots 𝐸_{𝑘}

, then Corollary 5.4.4 gives

det (𝐴 𝐵) =

det 𝐴 det 𝐸_{1} \dots det 𝐸_{𝑘} =

det 𝐴 det 𝐵

, the last step by the same corollary with

𝐼_{𝑛}

in place of

𝐴

. If

𝐵

is not invertible, neither is

𝐴 𝐵

, since an inverse

𝐶

𝐴 𝐵

would make

𝐶 𝐴

a left inverse of

𝐵

. So both sides are

0

by Theorem 5.4.7.

Case 1: $𝐵$ is invertible. By Theorem 3.5.19, $𝐵 = 𝐸_{1} \dots 𝐸_{𝑘}$ for some elementary matrices $𝐸_{1}, \dots, 𝐸_{𝑘}$ . Applying Corollary 5.4.4 first to $𝐴$ and then to $𝐼_{𝑛}$ ,

\begin{aligned} det (𝐴 𝐵) & = det (𝐴 𝐸_{1} \dots 𝐸_{𝑘}) = det 𝐴 det 𝐸_{1} \dots det 𝐸_{𝑘} \\ = det 𝐴 det (𝐸_{1} \dots 𝐸_{𝑘}) = det 𝐴 det 𝐵 . \end{aligned}

Case 2: $𝐵$ is not invertible. Then $det 𝐵 = 0$ by Theorem 5.4.7, so the right side is $0$ . We show that $𝐴 𝐵$ is not invertible, so that the left side is $0$ as well. Suppose instead that $𝐴 𝐵$ has an inverse $𝐶$ . Then $(𝐶 𝐴) 𝐵 =$ $𝐶 (𝐴 𝐵) =$ $𝐼_{𝑛}$ , so $𝐵$ has a left inverse. A square matrix with a one-sided inverse is invertible (Theorem 3.5.23), which contradicts our assumption on $𝐵$ . Hence $𝐴 𝐵$ is not invertible, and $det (𝐴 𝐵) =$ $0 =$ $det 𝐴 det 𝐵$ . □

The lecture splits into cases according to whether $𝐴$ and $𝐵$ are both invertible, and factors both. Since Corollary 5.4.4 allows any matrix on the left, only $𝐵$ needs to be factored. The second proof avoids factoring altogether. It rests on a move that was already used for block-diagonal matrices in Proposition 5.3.17.

Technique 5.4.11 (Recognize the determinant by its axioms). By Theorem 5.3.4, every multilinear alternating function $𝐷 : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ equals $𝐷 (𝐼_{𝑛}) det$ . So to prove an identity of the form $𝐷 (𝐵) = 𝑐 det 𝐵$ , where $𝐷 (𝐵)$ is some expression built from $𝐵$ , check two things about $𝐷$ as a function of the columns of $𝐵$ : that it is linear in each column, and that it vanishes when two columns are equal. Then evaluate at $𝐼_{𝑛}$ to find $𝑐 = 𝐷 (𝐼_{𝑛})$ . No formula for $det$ and no case analysis is needed.

Reach for it when an expression is visibly linear in each column of a matrix: $det (𝐴 𝐵)$ for a fixed $𝐴$ , $det (\begin{matrix} 𝑋 & 0 \\ 0 & 𝐵 \end{matrix})$ for a fixed $𝐵$ , or a function of $𝑛$ vectors in a space with a basis. The canonical example is the second proof of Theorem 5.4.10. The same move proved Proposition 5.3.17, and Section 13.4 uses it to define the determinant of an operator without choosing a basis.

Used in 4 places

Theorem 5.4.10, Exercise 5.6.8, Problem 5.2, Proposition 7.3.2.

Proof of Theorem 5.4.10 (by uniqueness).standard

Uses. Theorem 5.3.4 (Existence and uniqueness of the determinant), Definition 2.4.1 (Matrix product), Proposition 2.3.13 (Linearity of the product), Proposition 2.1.17 (Compositions of linear maps are linear), Definition 5.1.1 (Determinant function)

Techniques. Recognize the determinant by its axioms (Technique 5.4.11)

Hint 1. Fix

𝐴

, and regard

𝐷 (𝐵) = det (𝐴 𝐵)

as a function of the columns

𝐛_{1}, \dots, 𝐛_{𝑛}

𝐵

. What are the columns of

𝐴 𝐵

Hint 2. Column

𝑗

𝐴 𝐵

𝐴 𝐛_{𝑗}

. Check that

𝐷

is multilinear and alternating, and apply Theorem 5.3.4.

Sketch. Since column

𝑗

𝐴 𝐵

𝐴 𝐛_{𝑗}

𝐷 (𝐵) =

det (𝐴 𝐛_{1}, \dots, 𝐴 𝐛_{𝑛})

. In each column this is

det

composed with the linear map

𝐱 \mapsto 𝐴 𝐱

, so it is linear, and equal columns of

𝐵

give equal columns of

𝐴 𝐵

. So

𝐷

is multilinear and alternating, and

𝐷 (𝐵) =

𝐷 (𝐼_{𝑛}) det 𝐵 =

det 𝐴 det 𝐵

Fix $𝐴$ , and define $𝐷 : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ by $𝐷 (𝐵) = det (𝐴 𝐵)$ . By Definition 2.4.1, column $𝑗$ of $𝐴 𝐵$ is $𝐴 𝐛_{𝑗}$ , so

𝐷 (𝐛_{1}, \dots, 𝐛_{𝑛}) = det (𝐴 𝐛_{1}, \dots, 𝐴 𝐛_{𝑛}) .

Multilinear. Fix $𝑗$ and all columns of $𝐵$ except the $𝑗$ -th. Then $𝐱 \mapsto 𝐷 (\dots, 𝐱, \dots)$ , with $𝐱$ in column $𝑗$ , is the composite of $𝐱 \mapsto 𝐴 𝐱$ , which is linear (Proposition 2.3.13), and the map that puts a vector $𝐲$ in column $𝑗$ of the matrix with columns $𝐴 𝐛_{𝑘}$ ( $𝑘 \neq 𝑗$ ) and takes $det$ , which is linear because $det$ is linear in column $𝑗$ . So it is linear by Proposition 2.1.17.

Alternating. If $𝐛_{𝑖} = 𝐛_{𝑗}$ for some $𝑖 \neq 𝑗$ , then $𝐴 𝐛_{𝑖} = 𝐴 𝐛_{𝑗}$ , so $𝐴 𝐵$ has two equal columns and $𝐷 (𝐵) = 0$ .

By Theorem 5.3.4, $𝐷 (𝐵) =$ $𝐷 (𝐼_{𝑛}) det 𝐵 =$ $det (𝐴 𝐼_{𝑛}) det 𝐵 =$ $det 𝐴 det 𝐵$ for every $𝐵$ . □

For $𝑛 = 2$ the second proof is the first solution of Exercise 5.1.27.

Intuition (Two proofs compared). The two proofs are the two basic strategies of this chapter. The first, Technique 5.4.6, builds $𝐵$ out of simple pieces. It needs the computation for elementary matrices, the factorization theorem that comes out of Gauss–Jordan elimination (Theorem 3.5.19), and a separate argument for matrices that are not invertible. The second, Technique 5.4.11, never looks inside $𝐵$ . It notices that $𝐵 \mapsto det (𝐴 𝐵)$ satisfies two of the three axioms, so by uniqueness it is a multiple of $det$ , and it finds the multiple by setting $𝐵 = 𝐼_{𝑛}$ . It uses neither elimination nor a case split.

The second proof is shorter, and it works verbatim with any multilinear alternating function in place of $det$ , which is why the basis-free theory of Section 13.4 is built on it. It also gives (I) $\Rightarrow$ (II) in Theorem 5.4.7 without elementary matrices: if $𝐴$ is invertible, then $1 =$ $det 𝐼_{𝑛} =$ $det (𝐴 𝐴^{- 1}) =$ $det 𝐴 det 𝐴^{- 1}$ , so $det 𝐴 \neq 0$ . The first proof explains where the numbers come from: the factor that each elementary matrix contributes is the effect of its column operation. Its pattern also adapts to statements that are not about columns, such as $det 𝐴^{𝖳} = det 𝐴$ below, where the axioms give no direct handle.

Exercise 5.4.12.routine Let

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

. Show that

det (𝐴 𝐵) =

det (𝐵 𝐴)

, and that

det (𝐴^{𝑘}) =

{(det 𝐴)}^{𝑘}

for every integer

𝑘 \geq 0

. Show also that if

𝐴

is invertible, then

det (𝐴^{- 1}) =

{(det 𝐴)}^{- 1}

, and deduce that

det (𝐴^{𝑘}) =

{(det 𝐴)}^{𝑘}

for negative

𝑘

as well, where

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

Solution.

Uses. Theorem 5.4.10 (Multiplicativity), induction on $𝑘$

Hint 1. Determinants are elements of

𝐹

, so they commute even when the matrices do not.

Hint 2. For the inverse, take determinants of

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

Sketch.

det (𝐴 𝐵) =

det 𝐴 det 𝐵 =

det 𝐵 det 𝐴 =

det (𝐵 𝐴)

. Induction gives

det (𝐴^{𝑘 + 1}) =

det (𝐴^{𝑘}) det 𝐴 =

{(det 𝐴)}^{𝑘 + 1}

. From

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

det 𝐴 det 𝐴^{- 1} = 1

. For

𝑘 > 0

det (𝐴^{- 𝑘}) =

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

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

{(det 𝐴)}^{- 𝑘}

By Theorem 5.4.10 and commutativity of multiplication in $𝐹$ , $det (𝐴 𝐵) =$ $det 𝐴 det 𝐵 =$ $det 𝐵 det 𝐴 =$ $det (𝐵 𝐴)$ .

For powers, $det (𝐴^{0}) =$ $det 𝐼_{𝑛} =$ $1 =$ ${(det 𝐴)}^{0}$ , and if $det (𝐴^{𝑘}) =$ ${(det 𝐴)}^{𝑘}$ , then $det (𝐴^{𝑘 + 1}) =$ $det (𝐴^{𝑘} 𝐴) =$ $det (𝐴^{𝑘}) det 𝐴 =$ ${(det 𝐴)}^{𝑘 + 1}$ . By induction, $det (𝐴^{𝑘}) =$ ${(det 𝐴)}^{𝑘}$ for all $𝑘 \geq 0$ .

If $𝐴$ is invertible, then $det 𝐴 det (𝐴^{- 1}) =$ $det (𝐴 𝐴^{- 1}) =$ $det 𝐼_{𝑛} =$ $1$ , so $det (𝐴^{- 1}) =$ ${(det 𝐴)}^{- 1}$ . For $𝑘 > 0$ , the case already proved, applied to $𝐴^{- 1}$ , gives $det (𝐴^{- 𝑘}) =$ $det ({(𝐴^{- 1})}^{𝑘}) =$ ${(det 𝐴^{- 1})}^{𝑘} =$ ${(det 𝐴)}^{- 𝑘}$ .

So $det (𝐴 𝐵) =$ $det (𝐵 𝐴)$ even when $𝐴 𝐵 \neq 𝐵 𝐴$ . For example, $𝐴 = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ and $𝐵 = (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix})$ have $𝐴 𝐵 = (\begin{matrix} 2 & 1 \\ 1 & 1 \end{matrix})$ and $𝐵 𝐴 = (\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix})$ , which are different matrices, both with determinant $1$ . In the language of Section 14.1, Theorem 5.4.7 and Theorem 5.4.10 say that $det$ is a homomorphism from the group of invertible $𝑛 \times 𝑛$ matrices under multiplication to the group $𝐹 ∖ {0}$ under multiplication.

5.4.4The transpose

The axioms single out the columns of a matrix. The transpose exchanges rows and columns (Definition 2.4.21), and the next theorem says that the determinant does not notice the exchange. First, the elementary matrices.

Lemma 5.4.13 (Transposes of elementary matrices). If $𝐸 \in 𝐹^{𝑛 \times 𝑛}$ is elementary, then $𝐸^{𝖳}$ is an elementary matrix of the same type, and $det 𝐸^{𝖳} = det 𝐸$ . Explicitly,

𝐸_{𝑖 𝑗}^{𝖳} = 𝐸_{𝑖 𝑗}, 𝐸_{𝑖 𝑐}^{𝖳} = 𝐸_{𝑖 𝑐}, 𝐸_{𝑖 𝑐 𝑗}^{𝖳} = 𝐸_{𝑗 𝑐 𝑖} .

Proof.routine

Uses. Definition 3.2.2 (Elementary matrices), Definition 2.4.21 (Transpose), Proposition 5.4.1 (Determinants of elementary matrices)

Hint 1. Transposing reflects the entries in the diagonal. Which off-diagonal entries does each elementary matrix have?

Hint 2.

𝐸_{𝑖 𝑐 𝑗}

has a single off-diagonal entry,

𝑐

, in position

(𝑗, 𝑖)

. Which elementary matrix has

𝑐

in position

(𝑖, 𝑗)

Sketch.

𝐸_{𝑖 𝑐}

is diagonal. The off-diagonal entries of

𝐸_{𝑖 𝑗}

are

1

s in positions

(𝑖, 𝑗)

and

(𝑗, 𝑖)

, a symmetric pattern.

𝐸_{𝑖 𝑐 𝑗}

𝐼_{𝑛}

plus

𝑐

in position

(𝑗, 𝑖)

, so its transpose is

𝐼_{𝑛}

plus

𝑐

in position

(𝑖, 𝑗)

, which is

𝐸_{𝑗 𝑐 𝑖}

. Each pair has the same determinant by Proposition 5.4.1.

Transposing a matrix moves the entry in position

(𝑘, 𝑙)

to position

(𝑙, 𝑘)

(Definition 2.4.21), so it fixes the diagonal and the identity matrix.

𝐸_{𝑖 𝑐}

is diagonal, so

𝐸_{𝑖 𝑐}^{𝖳} = 𝐸_{𝑖 𝑐}

. By the proof of Proposition 5.4.1,

𝐸_{𝑖 𝑗}

agrees with

𝐼_{𝑛}

except that the entries in positions

(𝑖, 𝑖)

and

(𝑗, 𝑗)

are

0

and those in positions

(𝑖, 𝑗)

and

(𝑗, 𝑖)

are

1

. This pattern is unchanged by the reflection, so

𝐸_{𝑖 𝑗}^{𝖳} = 𝐸_{𝑖 𝑗}

. Finally,

𝐸_{𝑖 𝑐 𝑗}

𝐼_{𝑛}

with an extra entry

𝑐

in position

(𝑗, 𝑖)

, so

𝐸_{𝑖 𝑐 𝑗}^{𝖳}

𝐼_{𝑛}

with an extra entry

𝑐

in position

(𝑖, 𝑗)

. Since

𝑗 \neq 𝑖

, this is the elementary matrix

𝐸_{𝑗 𝑐 𝑖}

, which adds

𝑐

times row

𝑗

to row

𝑖

. In each case

𝐸

and

𝐸^{𝖳}

have the same type, so they have the same determinant (

- 1

𝑐

, or

1

) by Proposition 5.4.1. □

Theorem 5.4.14 (The transpose). For every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ ,

det 𝐴^{𝖳} = det 𝐴 .

Proof (via elementary matrices).standard

Uses. Theorem 3.5.19 (Invertible matrices are products of elementary matrices), Proposition 2.4.23 (Transpose of a product), Lemma 5.4.13 (Transposes of elementary matrices), Corollary 5.4.4 (Products of elementary matrices), Theorem 5.4.7 (Invertibility and the determinant), Definition 2.5.12 (Invertible)

Techniques. Reduce to elementary matrices (Technique 5.4.6), Transpose to trade rows for columns (Technique 3.2.27)

Hint 1. First dispose of the matrices that are not invertible: show that

𝐴^{𝖳}

is invertible exactly when

𝐴

is.

Hint 2. For invertible

𝐴

, factor

𝐴 = 𝐸_{1} \dots 𝐸_{𝑘}

. What is

𝐴^{𝖳}

, by Proposition 2.4.23?

Hint 3.

𝐴^{𝖳} = 𝐸_{𝑘}^{𝖳} \dots 𝐸_{1}^{𝖳}

is again a product of elementary matrices. Compare the two products of determinants using Lemma 5.4.13.

Sketch. If

𝐵

is an inverse of

𝐴

, then

𝐵^{𝖳}

is an inverse of

𝐴^{𝖳}

by Proposition 2.4.23, and conversely since

{(𝐴^{𝖳})}^{𝖳} = 𝐴

. So if

𝐴

is not invertible, both determinants are

0

. If

𝐴 = 𝐸_{1} \dots 𝐸_{𝑘}

, then

𝐴^{𝖳} = 𝐸_{𝑘}^{𝖳} \dots 𝐸_{1}^{𝖳}

, and Corollary 5.4.4 with Lemma 5.4.13 gives

det 𝐴^{𝖳} =

\prod det 𝐸_{𝑖}^{𝖳} =

\prod det 𝐸_{𝑖} =

det 𝐴

First, $𝐴$ is invertible if and only if $𝐴^{𝖳}$ is. Indeed, if $𝐴 𝐵 = 𝐵 𝐴 = 𝐼_{𝑛}$ , then by Proposition 2.4.23,

\begin{matrix} 𝐵^{𝖳} 𝐴^{𝖳} = {(𝐴 𝐵)}^{𝖳} = 𝐼_{𝑛}^{𝖳} = 𝐼_{𝑛}, \\ 𝐴^{𝖳} 𝐵^{𝖳} = {(𝐵 𝐴)}^{𝖳} = 𝐼_{𝑛}, \end{matrix}

so $𝐴^{𝖳}$ is invertible. Applying this to $𝐴^{𝖳}$ , whose transpose is $𝐴$ , gives the converse.

If $𝐴$ is not invertible, then neither is $𝐴^{𝖳}$ , and $det 𝐴 = 0 = det 𝐴^{𝖳}$ by Theorem 5.4.7. Suppose that $𝐴$ is invertible, and write $𝐴 = 𝐸_{1} 𝐸_{2} \dots 𝐸_{𝑘}$ with elementary $𝐸_{𝑖}$ (Theorem 3.5.19). By Proposition 2.4.23 and induction on $𝑘$ ,

𝐴^{𝖳} = 𝐸_{𝑘}^{𝖳} \dots 𝐸_{2}^{𝖳} 𝐸_{1}^{𝖳},

and each $𝐸_{𝑖}^{𝖳}$ is elementary by Lemma 5.4.13. So by Corollary 5.4.4 (with $𝐼_{𝑛}$ in place of $𝐴$ ), Lemma 5.4.13, and commutativity of multiplication in $𝐹$ ,

\begin{aligned} det 𝐴^{𝖳} & = det 𝐸_{𝑘}^{𝖳} \dots det 𝐸_{1}^{𝖳} = det 𝐸_{𝑘} \dots det 𝐸_{1} \\ = det 𝐸_{1} \dots det 𝐸_{𝑘} = det 𝐴 . \end{aligned}

□

Proof (via the Leibniz formula).standard

Uses. Definition 5.3.6 (Determinant), Definition 2.4.21 (Transpose), Proposition 5.2.25 (Multiplicativity of the sign), Proposition 5.2.8 (Reindexing sums over $𝑆_{𝑛}$ )

Hint 1. Write out the Leibniz formula for

𝐴^{𝖳}

, whose

(𝑖, 𝑗)

entry is

𝑎_{𝑗 𝑖}

Hint 2. You get

\sum_{𝜎} sgn (𝜎) 𝑎_{1 𝜎 (1)} \dots 𝑎_{𝑛 𝜎 (𝑛)}

. Reorder each product by the second index: if

𝑗 = 𝜎 (𝑖)

, then

𝑖 = 𝜎^{- 1} (𝑗)

Hint 3. Then use

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

, and reindex the sum by

𝜎 \mapsto 𝜎^{- 1}

Sketch. The term of

𝜎

det 𝐴^{𝖳}

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

. Reordering the factors by

𝑗 = 𝜎 (𝑖)

turns it into

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

, the term of

𝜎^{- 1}

det 𝐴

. As

𝜎

runs over

𝑆_{𝑛}

, so does

𝜎^{- 1}

, so the two sums agree.

Let $𝐵 = 𝐴^{𝖳}$ , so that $𝑏_{𝑖 𝑗} = 𝑎_{𝑗 𝑖}$ (Definition 2.4.21). By the Leibniz formula (Definition 5.3.6),

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

Fix $𝜎$ . As $𝑖$ runs over $[𝑛]$ , the index $𝑗 = 𝜎 (𝑖)$ runs over $[𝑛]$ , taking each value once, and $𝑖 = 𝜎^{- 1} (𝑗)$ . Reordering the factors by $𝑗$ , which is allowed since multiplication in $𝐹$ is commutative,

𝑎_{1 𝜎 (1)} \dots 𝑎_{𝑛 𝜎 (𝑛)} = 𝑎_{𝜎^{- 1} (1) 1} \dots 𝑎_{𝜎^{- 1} (𝑛) 𝑛} .

Also $sgn (𝜎) = sgn (𝜎^{- 1})$ by Proposition 5.2.25. So the term of $𝜎$ in $det 𝐴^{𝖳}$ is $𝑔 (𝜎^{- 1})$ , where

𝑔 (𝜌) = sgn (𝜌) 𝑎_{𝜌 (1) 1} \dots 𝑎_{𝜌 (𝑛) 𝑛}

is the term of $𝜌$ in $det 𝐴$ . By Proposition 5.2.8,

det 𝐴^{𝖳} = \sum_{𝜎 \in 𝑆_{𝑛}} 𝑔 (𝜎^{- 1}) = \sum_{𝜎 \in 𝑆_{𝑛}} 𝑔 (𝜎) = det 𝐴 .

□

The second proof is the computation of Exercise 5.3.8.

Intuition (What the two proofs see). The lecture calls the fact $det 𝐸^{𝖳} = det 𝐸$ dumb luck, and in a sense it is: the axioms never mention rows. But there is a reason behind it. $𝐸^{𝖳}$ performs the same kind of operation as $𝐸$ , on rows where $𝐸$ acts on columns, and the three kinds of operations scale signed volume by $- 1$ , $𝑐$ , and $1$ whichever way they act. The second proof gives a more symmetric reason. A term of the Leibniz formula picks one entry from each row and each column, like non-attacking rooks on a chessboard (Figure 5.3.1). Transposing reflects the board in its diagonal, which turns the term of $𝜎$ into the term of $𝜎^{- 1}$ , a permutation with the same sign.

As for strategy, the first proof is Technique 5.4.6 once more, with the same case split as the first proof of Theorem 5.4.10. Technique 5.4.11 does not apply directly. To use it on $𝐷 (𝐴) = det 𝐴^{𝖳}$ , we would need to know that $𝐷$ is multilinear and alternating in the columns of $𝐴$ , that is, that $det$ is multilinear and alternating in rows, which is what we are trying to establish. Exercise 5.3.27 proves exactly this from the Leibniz formula, and gives a third proof.

Every statement about the columns of a determinant now has a version for rows (Technique 3.2.27).

Corollary 5.4.15 (Rows). Let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

(a) $det 𝐴$ is multilinear and alternating as a function of the rows of $𝐴$ .
(b)Swapping two rows of $𝐴$ negates $det 𝐴$ , multiplying a row by $𝑐$ multiplies $det 𝐴$ by $𝑐$ , and adding a multiple of one row to a different row does not change $det 𝐴$ .
(c) $det 𝐴 = 0$ if and only if the rows of $𝐴$ are linearly dependent.

Proof.routine

Uses. Theorem 5.4.14 (The transpose), Definition 2.4.21 (Transpose), Definition 5.1.1 (Determinant function), Proposition 5.1.10 (Alternating implies antisymmetric), Lemma 5.1.8 (Column replacement), Corollary 5.4.8 (Vanishing determinants)

Techniques. Transpose to trade rows for columns (Technique 3.2.27)

Hint 1. Row

𝑖

𝐴

, written as a column, is column

𝑖

𝐴^{𝖳}

. Apply the column statements to

𝐴^{𝖳}

Hint 2. For (b) you can also use Theorem 5.4.10 with the elementary matrices of Proposition 5.4.1.

Sketch. The rows of

𝐴

, written as columns, are the columns of

𝐴^{𝖳}

, and

det 𝐴 = det 𝐴^{𝖳}

. So each statement about the rows of

𝐴

is the corresponding statement about the columns of

𝐴^{𝖳}

: the axioms for (a), Proposition 5.1.10, multilinearity, and Lemma 5.1.8 for (b), and Corollary 5.4.8 for (c).

For $𝐫_{1}, \dots, 𝐫_{𝑛} \in 𝐹^{𝑛}$ , let $𝑅$ be the matrix whose $𝑖$ -th row is $𝐫_{𝑖}^{𝖳}$ . Its transpose has columns $𝐫_{1}, \dots, 𝐫_{𝑛}$ , so by Theorem 5.4.14,

det 𝑅 = det (𝐫_{1}, \dots, 𝐫_{𝑛}) .

(a) The right side is multilinear and alternating in $𝐫_{1}, \dots, 𝐫_{𝑛}$ (Definition 5.1.1), hence so is the left side.

(b) Each row operation on $𝐴$ is the corresponding column operation on $𝐴^{𝖳}$ , and $det 𝐴 = det 𝐴^{𝖳}$ . By Proposition 5.1.10, linearity in a column, and Lemma 5.1.8, the three column operations multiply $det 𝐴^{𝖳}$ by $- 1$ , by $𝑐$ , and by $1$ . (Alternatively: a row operation multiplies $𝐴$ on the left by an elementary matrix $𝐸$ (Proposition 3.2.7), and $det (𝐸 𝐴) =$ $det 𝐸 det 𝐴$ with $det 𝐸$ given by Proposition 5.4.1.)

(c) The rows of $𝐴$ are linearly dependent if and only if the columns of $𝐴^{𝖳}$ are, which by Corollary 5.4.8 happens if and only if $det 𝐴^{𝖳} = det 𝐴$ is $0$ . □

In particular, a matrix with a zero row or two equal rows has determinant $0$ , and $det (𝐸 𝐴) =$ $det 𝐸 det 𝐴$ for elementary $𝐸$ , which is Lemma 5.4.2 with the factors in the other order.

Exercise 5.4.16.routine Suppose that $det (\begin{matrix} 𝑎 & 𝑏 & 𝑐 \\ 𝑑 & 𝑒 & 𝑓 \\ 𝑔 & ℎ & 𝑘 \end{matrix}) =$ $7$ , where the entries lie in a field $𝐹$ . Find

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

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

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

(d) det (\begin{matrix} 3 𝑎 & 3 𝑏 & 3 𝑐 \\ 3 𝑑 & 3 𝑒 & 3 𝑓 \\ 3 𝑔 & 3 ℎ & 3 𝑘 \end{matrix}) .

Solution.

Uses. Corollary 5.4.15 (Rows), Theorem 5.4.14 (The transpose), Exercise 5.1.5

Hint 1. Describe each matrix as the result of row operations on the original matrix, or on its transpose.

Hint 2. In (b), the new second row is

2

times the old one plus

- 3

times the first row. In (c), take the transpose first.

Sketch. (a) One swap:

- 7

. (b) Scale row

2

2

, then add

- 3

times row

1

14

. (c) The transpose is the original matrix with

5

times row

1

added to row

3

7

. (d)

3^{3} \cdot 7 = 189

Call the given matrix $𝑀$ .

(a) This is $𝑀$ with rows $1$ and $2$ swapped, so its determinant is $- 7$ by Corollary 5.4.15(b).

(b) Scaling row $2$ of $𝑀$ by $2$ gives determinant $14$ , and adding $- 3$ times row $1$ to the new row $2$ does not change it. The result is the given matrix, so its determinant is $14$ .

(c) The transpose of this matrix is $𝑀$ with $5$ times row $1$ added to row $3$ . By Theorem 5.4.14 and Corollary 5.4.15(b), its determinant is $det 𝑀 = 7$ .

(d) This is $3 𝑀$ , so by Exercise 5.1.5 its determinant is $3^{3} det 𝑀 = 189$ .

5.4.5Similar matrices and the determinant of an operator

Recall (Definition 4.5.23) that $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ are similar if $𝐵 = 𝑆^{- 1} 𝐴 𝑆$ for some invertible $𝑆 \in 𝐹^{𝑛 \times 𝑛}$ . Then also $𝐴 = 𝑆 𝐵 𝑆^{- 1}$ , so the relation is symmetric.

Proposition 5.4.17 (Similar matrices have equal determinants). If

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

are similar, then

det 𝐴 = det 𝐵

Proof.routine

Uses. Definition 4.5.23 (Similar matrices), Theorem 5.4.10 (Multiplicativity)

Hint 1. Write

𝐵 = 𝑆^{- 1} 𝐴 𝑆

and apply Theorem 5.4.10.

Hint 2. Determinants are scalars, so they commute even though matrices need not. Bring

det 𝑆^{- 1}

and

det 𝑆

together.

Sketch.

det 𝐵 =

det 𝑆^{- 1} det 𝐴 det 𝑆 =

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

det 𝐴 det 𝐼_{𝑛} =

det 𝐴

Write $𝐵 = 𝑆^{- 1} 𝐴 𝑆$ with $𝑆$ invertible. By Theorem 5.4.10, applied twice, and commutativity of multiplication in $𝐹$ ,

\begin{aligned} det 𝐵 & = det 𝑆^{- 1} det 𝐴 det 𝑆 = det 𝐴 (det 𝑆^{- 1} det 𝑆) \\ = det 𝐴 det (𝑆^{- 1} 𝑆) = det 𝐴 det 𝐼_{𝑛} = det 𝐴, \end{aligned}

as desired. □

The converse fails. $(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ and $𝐼_{2}$ both have determinant $1$ , but they are not similar, since $𝑆^{- 1} 𝐼_{2} 𝑆 = 𝐼_{2}$ for every invertible $𝑆$ . So the determinant can prove that two matrices are not similar, but not that they are. It joins the rank and the trace (Proposition 2.4.28) as a similarity invariant. Together with the trace, it appears among the coefficients of $det (𝐴 + 𝑡 𝐼_{𝑛})$ (Proposition 5.3.19), and in Section 7.3 this polynomial becomes a finer invariant.

The main use of Proposition 5.4.17 is to define the determinant of a linear operator. Let $𝑉$ be a vector space with $dim 𝑉 = 𝑛 \geq 1$ , let $𝑇 \in L (𝑉)$ , and let $ℬ︀$ and $\overset{̊}{ℬ︀}$ be bases of $𝑉$ . By Theorem 4.5.17,

{[𝑇]}_{\overset{̊}{ℬ︀} \overset{̊}{ℬ︀}} = {[{id}_{𝑉}]}_{\overset{̊}{ℬ︀} ℬ︀} {[𝑇]}_{ℬ︀ ℬ︀} {[{id}_{𝑉}]}_{ℬ︀ \overset{̊}{ℬ︀}} .

By Theorem 2.4.2, ${[{id}_{𝑉}]}_{\overset{̊}{ℬ︀} ℬ︀} {[{id}_{𝑉}]}_{ℬ︀ \overset{̊}{ℬ︀}} =$ ${[{id}_{𝑉}]}_{\overset{̊}{ℬ︀} \overset{̊}{ℬ︀}} =$ $𝐼_{𝑛}$ , and likewise in the other order. So with $𝑆 = {[{id}_{𝑉}]}_{ℬ︀ \overset{̊}{ℬ︀}}$ , we have ${[𝑇]}_{\overset{̊}{ℬ︀} \overset{̊}{ℬ︀}} =$ $𝑆^{- 1} {[𝑇]}_{ℬ︀ ℬ︀} 𝑆$ . The two matrices are similar and have the same determinant.

Definition 5.4.18 (Determinant of an operator). Let $𝑉$ be a finite-dimensional vector space with $dim 𝑉 \geq 1$ , and let $𝑇 \in L (𝑉)$ . The determinant of $𝑇$ is

det 𝑇 = det {[𝑇]}_{ℬ︀ ℬ︀},

where $ℬ︀$ is any basis of $𝑉$ . By the computation above and Proposition 5.4.17, this does not depend on the choice of $ℬ︀$ .

For $𝑉 = 𝐹^{𝑛}$ and $𝑇 = 𝑇_{𝐴}$ , the standard basis gives ${[𝑇_{𝐴}]}_{ℰ︀ ℰ︀} = 𝐴$ (Proposition 2.3.16), so $det 𝑇_{𝐴} = det 𝐴$ . Translating between maps and matrices (Technique 2.3.27), the results of this section carry over to operators.

Example 5.4.19 (Two operators on matrices and polynomials).

(a)Let $𝑇 \in L (𝐹^{2 \times 2})$ be the transpose, $𝑇 (𝑋) = 𝑋^{𝖳}$ . Use the basis
$\begin{matrix} 𝑈_{11} = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}), 𝑈_{12} = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}), \\ 𝑈_{21} = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}), 𝑈_{22} = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) . \end{matrix}$
Then $𝑇$ fixes $𝑈_{11}$ and $𝑈_{22}$ and exchanges $𝑈_{12}$ and $𝑈_{21}$ , so its matrix in this basis is the $4 \times 4$ swap $𝐸_{23}$ , and $det 𝑇 = - 1$ . Over $ℝ$ this is the expected sign: $𝑇$ fixes the three-dimensional subspace of symmetric matrices and negates the skew-symmetric matrix $𝑈_{12} - 𝑈_{21}$ , so it is a reflection of the four-dimensional space $ℝ^{2 \times 2}$ . Over $𝔽_{2}$ , $det 𝑇 = - 1 = 1$ .
(b)Let $𝐷 \in L ({𝐹 [𝑥]}_{\leq 2})$ be differentiation. Its matrix in the basis $1, 𝑥, 𝑥^{2}$ is upper triangular with zero diagonal (Example 2.3.4), so $det 𝐷 = 0$ . This agrees with Proposition 5.4.20 below, since $𝐷$ is not invertible: $𝐷 (1) = 𝟎$ . For $id + 𝐷$ , which sends $1, 𝑥, 𝑥^{2}$ to $1$ , $1 + 𝑥$ , and $2 𝑥 + 𝑥^{2}$ ,
${[id + 𝐷]}_{ℬ︀ ℬ︀} = (\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{matrix}), det (id + 𝐷) = 1$
by Proposition 5.3.15, where $ℬ︀ = 1, 𝑥, 𝑥^{2}$ .

Proposition 5.4.20 (Properties of the determinant of an operator). Let

𝑉

be a vector space with

𝑛 = dim 𝑉 \geq 1

, let

𝑆, 𝑇 \in L (𝑉)

, and let

𝑐 \in 𝐹

(a) $det {id}_{𝑉} = 1$ , and $det (𝑐 𝑇) =$ $𝑐^{𝑛} det 𝑇$ .
(b) $det (𝑆 𝑇) =$ $det 𝑆 det 𝑇$ .
(c) $𝑇$ is invertible if and only if $det 𝑇 \neq 0$ . In that case $det (𝑇^{- 1}) =$ ${(det 𝑇)}^{- 1}$ .

Proof.standard

Uses. Definition 5.4.18 (Determinant of an operator), Example 2.3.6 (The zero map and the identity map), Proposition 1.6.19 (Coordinates respect linear combinations), Exercise 5.1.5, Theorem 2.4.2 (The matrix of a composite), Theorem 5.4.10 (Multiplicativity), Theorem 5.4.7 (Invertibility and the determinant), Theorem 2.2.1 (Linear maps are determined by a basis), Definition 2.3.1 (Matrix of a linear map)

Techniques. Translate between maps and matrices (Technique 2.3.27)

Hint 1. Fix one basis

ℬ︀

and translate each statement into a statement about the matrices of the operators with respect to

ℬ︀

Hint 2. For (c), if

𝑇

is invertible, apply (b) to

𝑇 𝑇^{- 1} = {id}_{𝑉}

. Conversely, if

det 𝑇 \neq 0

, the matrix of

𝑇

has an inverse

𝐶

. Find a linear map whose matrix is

𝐶

Sketch. With one basis

ℬ︀

throughout,

[{id}_{𝑉}] = 𝐼_{𝑛}

[𝑐 𝑇] = 𝑐 [𝑇]

, and

[𝑆 𝑇] = [𝑆] [𝑇]

, so (a) and (b) follow from the matrix statements. If

𝑇

is invertible, (b) gives

det 𝑇 det 𝑇^{- 1} =

det {id}_{𝑉} =

1

. If

det 𝑇 \neq 0

, then

[𝑇]

has an inverse

𝐶

, and the linear map

𝑅

with

[𝑅] = 𝐶

has

[𝑅 𝑇] =

[𝑇 𝑅] =

𝐼_{𝑛} =

[{id}_{𝑉}]

, so

𝑅 𝑇 = 𝑇 𝑅 = {id}_{𝑉}

Fix a basis $ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}$ of $𝑉$ , and write $[𝑅]$ for ${[𝑅]}_{ℬ︀ ℬ︀}$ for every $𝑅 \in L (𝑉)$ . A linear map is determined by its matrix: if $[𝑅] = [𝑅^{'}]$ , then $𝑅 (𝐯_{𝑗})$ and $𝑅^{'} (𝐯_{𝑗})$ have the same coordinate vector for every $𝑗$ , so they are equal, and $𝑅 = 𝑅^{'}$ by the uniqueness in Theorem 2.2.1.

(a) $[{id}_{𝑉}] = 𝐼_{𝑛}$ (Example 2.3.6), so $det {id}_{𝑉} = 1$ . Column $𝑗$ of $[𝑐 𝑇]$ is ${[𝑐 𝑇 (𝐯_{𝑗})]}_{ℬ︀} =$ $𝑐 {[𝑇 (𝐯_{𝑗})]}_{ℬ︀}$ by Proposition 1.6.19, so $[𝑐 𝑇] = 𝑐 [𝑇]$ , and $det (𝑐 𝑇) =$ $𝑐^{𝑛} det 𝑇$ by Exercise 5.1.5.

(b) By Theorem 2.4.2, $[𝑆 𝑇] = [𝑆] [𝑇]$ , so by Theorem 5.4.10,

\begin{aligned} det (𝑆 𝑇) & = det ([𝑆] [𝑇]) \\ = det [𝑆] det [𝑇] = det 𝑆 det 𝑇 . \end{aligned}

(c) If $𝑇$ is invertible, then by (b) and (a), $det 𝑇 det (𝑇^{- 1}) =$ $det (𝑇 𝑇^{- 1}) =$ $det {id}_{𝑉} =$ $1$ . So $det 𝑇 \neq 0$ , and $det (𝑇^{- 1}) =$ ${(det 𝑇)}^{- 1}$ . Conversely, suppose that $det 𝑇 \neq 0$ . Then $[𝑇]$ is invertible by Theorem 5.4.7; let $𝐶$ be its inverse, with entries $𝑐_{𝑖 𝑗}$ . By Theorem 2.2.1 there is a linear map $𝑅 \in L (𝑉)$ with $𝑅 (𝐯_{𝑗}) =$ $\sum_{𝑖} 𝑐_{𝑖 𝑗} 𝐯_{𝑖}$ for every $𝑗$ , and then $[𝑅] = 𝐶$ by Definition 2.3.1. By Theorem 2.4.2, $[𝑅 𝑇] =$ $𝐶 [𝑇] =$ $𝐼_{𝑛} =$ $[{id}_{𝑉}]$ and $[𝑇 𝑅] =$ $[𝑇] 𝐶 =$ $𝐼_{𝑛}$ . Since a linear map is determined by its matrix, $𝑅 𝑇 = 𝑇 𝑅 = {id}_{𝑉}$ , and $𝑇$ is invertible. □

In Section 13.4 the determinant of an operator is defined directly, without a basis, and Definition 5.4.18 becomes a theorem.

5.4.6Computing determinants

The Leibniz formula has $𝑛!$ terms. Corollary 5.4.15 gives a much faster method: row reduce to a triangular matrix and keep track of how each operation changes the determinant.

Proposition 5.4.21 (Determinants by row reduction). Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , and suppose that $𝐸_{𝑡} \dots 𝐸_{2} 𝐸_{1} 𝐴 = 𝑈$ for elementary matrices $𝐸_{1}, \dots, 𝐸_{𝑡}$ . Suppose that $𝑠$ of the $𝐸_{𝑙}$ are swaps, $𝑟$ of them are scalings by $𝑐_{1}, \dots, 𝑐_{𝑟}$ , and the rest are replacements. Then

𝑐_{1} \dots 𝑐_{𝑟} det 𝐴 = {(- 1)}^{𝑠} det 𝑈 .

In particular, if $𝑈$ is triangular, then $det 𝐴 =$ ${(- 1)}^{𝑠} {(𝑐_{1} \dots 𝑐_{𝑟})}^{- 1} 𝑢_{11} \dots 𝑢_{𝑛 𝑛}$ .

Proof.routine

Uses. Theorem 5.4.10 (Multiplicativity), Proposition 5.4.1 (Determinants of elementary matrices), Proposition 5.3.15 (Triangular matrices)

Hint 1. Take determinants of both sides of

𝐸_{𝑡} \dots 𝐸_{1} 𝐴 = 𝑈

Hint 2. Proposition 5.4.1 gives each

det 𝐸_{𝑙}

Sketch. By Theorem 5.4.10,

det 𝑈 =

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

, and the product of the

det 𝐸_{𝑙}

{(- 1)}^{𝑠} 𝑐_{1} \dots 𝑐_{𝑟}

by Proposition 5.4.1. If

𝑈

is triangular,

det 𝑈

is the product of its diagonal entries.

By Theorem 5.4.10, applied

𝑡

times,

det 𝑈 =

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

. By Proposition 5.4.1,

det 𝐸_{𝑙}

- 1

for each swap,

𝑐_{𝑞}

for the scaling by

𝑐_{𝑞}

, and

1

for each replacement, so

det 𝑈 =

{(- 1)}^{𝑠} 𝑐_{1} \dots 𝑐_{𝑟} det 𝐴

. Multiplying by

{(- 1)}^{𝑠}

, which is its own inverse, gives the claim. If

𝑈

is triangular, then

det 𝑈 = 𝑢_{11} \dots 𝑢_{𝑛 𝑛}

by Proposition 5.3.15, and we may divide by

𝑐_{1} \dots 𝑐_{𝑟}

, which is nonzero. □

Scalings are never needed to reach a triangular matrix, so the simplest version of the method uses only swaps and replacements.

Algorithm 5.4.22 (Determinant by elimination)

Input: A square matrix $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ .
Output: $det 𝐴$ .

Set

𝑠 = 0

. For

𝑘 = 1, 2, \dots, 𝑛

in turn: if column

𝑘

of the current matrix has a nonzero entry in one of the rows

𝑘, \dots, 𝑛

, swap such a row with row

𝑘

(adding

1

𝑠

if the rows are different), and then add multiples of row

𝑘

to rows

𝑘 + 1, \dots, 𝑛

to make their entries in column

𝑘

equal to

0

. If there is no such entry, go on to the next

𝑘

Let

𝑈

be the final matrix. Output

{(- 1)}^{𝑠} 𝑢_{11} 𝑢_{22} \dots 𝑢_{𝑛 𝑛}

Proof.routine

Uses. Proposition 5.4.21 (Determinants by row reduction), Proposition 3.2.7 (Row operations are left multiplications), Definition 3.3.31 (Triangular matrices)

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. By Proposition 5.4.21 it is enough to show that

𝑈

is upper triangular. Which entries does stage

𝑘

make

0

Hint 2. Check that later stages never touch column

𝑘

below the diagonal: which rows do they swap, and which rows do they add?

Sketch. The algorithm uses only swaps and replacements, so by Proposition 5.4.21 it outputs

det 𝐴

provided

𝑈

is upper triangular. After stage

𝑘

the entries of column

𝑘

below the diagonal are

0

. A later stage

𝑘^{'} > 𝑘

only swaps rows numbered at least

𝑘^{'}

and adds multiples of row

𝑘^{'}

to rows below it, and all these rows have entry

0

in column

𝑘

, so column

𝑘

stays cleared.

Every operation is a swap or a replacement, so the final matrix is $𝑈 = 𝐸_{𝑡} \dots 𝐸_{1} 𝐴$ with $𝑠$ swaps among the $𝐸_{𝑙}$ and no scalings (Proposition 3.2.7). By Proposition 5.4.21, the output equals $det 𝐴$ provided $𝑈$ is upper triangular.

We show that after stage $𝑘$ , the entries of columns $1, \dots, 𝑘$ below the diagonal are $0$ . This holds after stage $1$ , since stage $1$ either clears column $1$ below row $1$ or finds it already zero there. Suppose it holds after stage $𝑘 - 1$ . Stage $𝑘$ only swaps two rows with indices at least $𝑘$ , and adds multiples of row $𝑘$ to rows with indices greater than $𝑘$ . For $𝑗 < 𝑘$ , all of these rows have entry $0$ in column $𝑗$ , by the induction hypothesis, so the entries of column $𝑗$ below the diagonal stay $0$ . And stage $𝑘$ makes the entries of column $𝑘$ below the diagonal $0$ , or finds them $0$ already. After stage $𝑛$ , $𝑈$ is upper triangular (Definition 3.3.31). □

If some stage finds no nonzero entry, say at column $𝑘$ , then $𝑢_{𝑘 𝑘} = 0$ , so $det 𝐴 = 0$ and $𝐴$ is not invertible. In practice one also uses scalings to pull a common factor out of a row, and one may mix in column operations freely: each row or column operation multiplies the determinant by the determinant of its elementary matrix (Corollary 5.4.15, Lemma 5.4.2).

Example 5.4.23 (A $4 \times 4$ determinant by elimination). Let

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

Stage $1$ adds $- 2$ , $1$ , and $- 3$ times row $1$ to rows $2$ , $3$ , and $4$ . In column $2$ , the new row $2$ has a $0$ , so stage $2$ swaps rows $2$ and $3$ and then adds $2$ times the new row $2$ to row $4$ :

𝐴 \overset{stage 1}{\to} (\begin{matrix} 1 & 2 & - 1 & 3 \\ 0 & 0 & 3 & - 2 \\ 0 & - 1 & 2 & 1 \\ 0 & 2 & 2 & 0 \end{matrix}),

\overset{stage 2}{\to} (\begin{matrix} 1 & 2 & - 1 & 3 \\ 0 & - 1 & 2 & 1 \\ 0 & 0 & 3 & - 2 \\ 0 & 0 & 6 & 2 \end{matrix}) .

Stage $3$ adds $- 2$ times row $3$ to row $4$ , and stage $4$ does nothing:

\overset{stage 3}{\to} (\begin{matrix} 1 & 2 & - 1 & 3 \\ 0 & - 1 & 2 & 1 \\ 0 & 0 & 3 & - 2 \\ 0 & 0 & 0 & 6 \end{matrix}) = 𝑈 .

There was one swap, so

det 𝐴 = {(- 1)}^{1} \cdot 1 \cdot (- 1) \cdot 3 \cdot 6 = 18 .

The Leibniz formula would have needed $24$ terms. Since $18 = 2 \cdot 3^{2}$ , Proposition 5.3.20 shows that the reduction of $𝐴$ modulo a prime $𝑝$ is invertible over $𝔽_{𝑝}$ for every $𝑝$ except $2$ and $3$ .

det 𝐴 = {(- 1)}^{1} \cdot 1 \cdot (- 1) \cdot 3 \cdot 6 = 18

Gauss–Jordan elimination on the matrix

𝐴

of Example 5.4.23, one elementary matrix at a time. It also scales each pivot to

1

, by the factor

1 / 𝑝

for a pivot

𝑝

, so by Proposition 5.4.21,

det 𝐴

{(- 1)}^{𝑠}

times the product of the pivots before scaling, where

𝑠

is the number of swaps. Here this is

(- 1) \cdot

1 \cdot

(- 1) \cdot

3 \cdot

6 =

18

. Edit the matrix to try others. When some column has no pivot,

rref (𝐴)

has a zero row and

det 𝐴 = 0

Structure in a matrix can often be exploited before any elimination. A common trick: if every row has the same sum, add all columns to the first, or all rows to the first if every column has the same sum.

Example 5.4.24 (A matrix with constant row sums). For $𝑛 \geq 1$ and $𝑥 \in 𝐹$ , let $𝑀_{𝑛} (𝑥) \in 𝐹^{𝑛 \times 𝑛}$ have every diagonal entry equal to $𝑥$ and every other entry equal to $1$ . Then

det 𝑀_{𝑛} (𝑥) = (𝑥 + 𝑛 - 1) {(𝑥 - 1)}^{𝑛 - 1} .

Every column of $𝑀_{𝑛} (𝑥)$ sums to $𝑥 + 𝑛 - 1$ . Adding rows $2, \dots, 𝑛$ to row $1$ does not change the determinant (Corollary 5.4.15), and makes every entry of row $1$ equal to $𝑥 + 𝑛 - 1$ . Pulling this factor out of row $1$ leaves the row $(1, 1, \dots, 1)$ . Now subtract the new row $1$ from each of rows $2, \dots, 𝑛$ . Row $𝑖$ had $𝑥$ in position $𝑖$ and $1$ elsewhere, so it becomes $(𝑥 - 1) 𝐞_{𝑖}^{𝖳}$ . The result is upper triangular with diagonal entries $1, 𝑥 - 1, \dots, 𝑥 - 1$ , so by Proposition 5.3.15,

det 𝑀_{𝑛} (𝑥) = (𝑥 + 𝑛 - 1) \cdot 1 \cdot {(𝑥 - 1)}^{𝑛 - 1} .

So for $𝑛 \geq 2$ , $𝑀_{𝑛} (𝑥)$ is invertible unless $𝑥 = 1$ or $𝑥 = 1 - 𝑛$ . These two values coincide when $𝑛 = 0$ in $𝐹$ : over $𝔽_{3}$ , $det 𝑀_{3} (𝑥) =$ $(𝑥 + 2) {(𝑥 - 1)}^{2} =$ ${(𝑥 - 1)}^{3}$ .

Remark 5.4.25 (How much faster). Each term of the Leibniz formula is a product of $𝑛$ entries, which takes $𝑛 - 1$ multiplications, so evaluating the formula term by term takes $(𝑛 - 1) 𝑛!$ multiplications. Algorithm 5.4.22 takes about $𝑛^{3} / 3$ : stage $𝑘$ computes a multiplier for each of the $𝑛 - 𝑘$ rows below row $𝑘$ and updates the $𝑛 - 𝑘$ remaining entries of each, for $(𝑛 - 𝑘) (𝑛 - 𝑘 + 1)$ multiplications and divisions, and summing over $𝑘$ gives $(𝑛^{3} - 𝑛) / 3$ (Remark 3.3.35). Multiplying the diagonal entries adds $𝑛 - 1$ more.

$𝑛$	Leibniz: $(𝑛 - 1) 𝑛!$	Elimination: $(𝑛^{3} - 𝑛) / 3$
$3$	$12$	$8$
$5$	$480$	$40$
$10$	$32 659 200$	$330$
$20$	$\approx 4.6 \cdot 10^{19}$	$2660$

Table 5.4.1. Multiplications (and divisions) needed to evaluate an

𝑛 \times 𝑛

determinant.

At $10^{9}$ multiplications per second, the Leibniz formula for a single $20 \times 20$ matrix would take about $1500$ years, while elimination takes a few microseconds. Cofactor expansion (Section 5.5) also takes on the order of $𝑛!$ operations for a general matrix, although it is convenient for matrices with many zeros. The Leibniz formula remains the tool for theory (Technique 5.3.12, Technique 5.3.18), and elimination the tool for computation.

5.4.7Block-triangular matrices

Proposition 5.3.17 computed the determinant of $(\begin{matrix} 𝐴 & 0 \\ 0 & 𝐷 \end{matrix})$ . Its second proof never used that the upper right block is $0$ , only the lower left one, which suggests the following theorem. Recall (Definition 2.4.33) that a square block matrix with square diagonal blocks is block upper triangular if all blocks below the diagonal blocks are $0$ ; it is block lower triangular if all blocks above them are $0$ .

Theorem 5.4.26 (Block-triangular matrices). Let $𝐴 \in 𝐹^{𝑘 \times 𝑘}$ , $𝐵 \in 𝐹^{𝑘 \times 𝑚}$ , $𝐶 \in 𝐹^{𝑚 \times 𝑘}$ , and $𝐷 \in 𝐹^{𝑚 \times 𝑚}$ . Then

\begin{matrix} det (\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 \end{matrix}) = det 𝐴 det 𝐷, \\ det (\begin{matrix} 𝐴 & 0 \\ 𝐶 & 𝐷 \end{matrix}) = det 𝐴 det 𝐷 . \end{matrix}

Proof (by factoring).standard

Uses. Theorem 2.4.34 (Block multiplication), Theorem 5.4.10 (Multiplicativity), Proposition 5.3.17 (Block-diagonal matrices), Lemma 5.1.8 (Column replacement), Theorem 5.4.14 (The transpose), Definition 2.4.21 (Transpose)

Techniques. Block decomposition (Technique 2.4.35)

Hint 1. Write

(\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 \end{matrix})

as a product of two block matrices, one of which is block diagonal.

Hint 2. Check that

(\begin{matrix} 𝐼_{𝑘} & 𝐵 \\ 0 & 𝐷 \end{matrix}) (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐼_{𝑚} \end{matrix}) =

(\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 \end{matrix})

Hint 3. To find

det (\begin{matrix} 𝐼_{𝑘} & 𝐵 \\ 0 & 𝐷 \end{matrix})

, use the first

𝑘

columns, which are standard basis vectors, to clear

𝐵

by column replacements.

Hint 4. For the second identity, take transposes.

Sketch. Block multiplication gives

(\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 \end{matrix}) =

(\begin{matrix} 𝐼_{𝑘} & 𝐵 \\ 0 & 𝐷 \end{matrix}) (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐼_{𝑚} \end{matrix})

. The second factor has determinant

det 𝐴

by Proposition 5.3.17. In the first, column

𝑘 + 𝑗

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

plus column

𝑗

𝐷

placed below, and subtracting

𝑏_{𝑖 𝑗}

times column

𝑖

for each

𝑖 \leq 𝑘

clears

𝐵

without changing the determinant, leaving

(\begin{matrix} 𝐼_{𝑘} & 0 \\ 0 & 𝐷 \end{matrix})

with determinant

det 𝐷

. For the lower block-triangular case, transpose.

Let $𝑛 = 𝑘 + 𝑚$ and $𝑀 = (\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 \end{matrix})$ . By block multiplication (Theorem 2.4.34),

\begin{aligned} (\begin{matrix} 𝐼_{𝑘} & 𝐵 \\ 0 & 𝐷 \end{matrix}) (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐼_{𝑚} \end{matrix}) & = (\begin{matrix} 𝐼_{𝑘} 𝐴 + 𝐵 0 & 𝐼_{𝑘} 0 + 𝐵 𝐼_{𝑚} \\ 0 𝐴 + 𝐷 0 & 00 + 𝐷 𝐼_{𝑚} \end{matrix}) \\ = (\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 \end{matrix}) . \end{aligned}

So by Theorem 5.4.10 and Proposition 5.3.17,

det 𝑀 = det 𝑁 det (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐼_{𝑚} \end{matrix}) = det 𝑁 det 𝐴,

where $𝑁 = (\begin{matrix} 𝐼_{𝑘} & 𝐵 \\ 0 & 𝐷 \end{matrix})$ . For $𝑖 \leq 𝑘$ , column $𝑖$ of $𝑁$ is $𝐞_{𝑖} \in 𝐹^{𝑛}$ . For $𝑗 \leq 𝑚$ , column $𝑘 + 𝑗$ of $𝑁$ is $\sum_{𝑖 = 1}^{𝑘} 𝑏_{𝑖 𝑗} 𝐞_{𝑖} +$ $𝐝_{𝑗}^{'}$ , where $𝐝_{𝑗}^{'} \in 𝐹^{𝑛}$ has $𝑘$ zeros followed by the entries of column $𝑗$ of $𝐷$ . Subtracting $𝑏_{𝑖 𝑗}$ times column $𝑖$ from column $𝑘 + 𝑗$ , for every $𝑖 \leq 𝑘$ and $𝑗 \leq 𝑚$ , does not change $det 𝑁$ (Lemma 5.1.8), does not change the first $𝑘$ columns, and turns column $𝑘 + 𝑗$ into $𝐝_{𝑗}^{'}$ . The result is $(\begin{matrix} 𝐼_{𝑘} & 0 \\ 0 & 𝐷 \end{matrix})$ , so by Proposition 5.3.17, $det 𝑁 =$ $det 𝐼_{𝑘} det 𝐷 =$ $det 𝐷$ . Hence $det 𝑀 = det 𝐴 det 𝐷$ .

For the second identity, transposing exchanges the entries in positions $(𝑖, 𝑗)$ and $(𝑗, 𝑖)$ (Definition 2.4.21), so the transpose of $(\begin{matrix} 𝐴 & 0 \\ 𝐶 & 𝐷 \end{matrix})$ is $(\begin{matrix} 𝐴^{𝖳} & 𝐶^{𝖳} \\ 0 & 𝐷^{𝖳} \end{matrix})$ . By Theorem 5.4.14 and the first identity,

\begin{aligned} det (\begin{matrix} 𝐴 & 0 \\ 𝐶 & 𝐷 \end{matrix}) & = det (\begin{matrix} 𝐴^{𝖳} & 𝐶^{𝖳} \\ 0 & 𝐷^{𝖳} \end{matrix}) \\ = det 𝐴^{𝖳} det 𝐷^{𝖳} = det 𝐴 det 𝐷 . \end{aligned}

□

Proof (via the Leibniz formula).standard

Uses. Definition 5.3.6 (Determinant), 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. Compare the Leibniz terms of

𝑀 = (\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 \end{matrix})

with those of

𝑀^{'} = (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐷 \end{matrix})

. For which

𝜎

can they differ?

Hint 2. If

𝜎

sends some

𝑗 \leq 𝑘

to a row below

𝑘

, the term of

𝜎

contains an entry of the lower left block, in both matrices. Otherwise

𝜎

maps

[𝑘]

onto

[𝑘]

, and its term never touches the upper right block.

Sketch. Let

𝑀^{'} = (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐷 \end{matrix})

. If

𝜎 (𝑗) > 𝑘

for some

𝑗 \leq 𝑘

, the terms of

𝜎

det 𝑀

and

det 𝑀^{'}

both contain a

0

from the lower left block. Otherwise

𝜎

maps

[𝑘]

onto

[𝑘]

, hence the rest onto the rest, and every factor of its term lies in

𝐴

or in

𝐷

, where

𝑀

and

𝑀^{'}

agree. So

det 𝑀 =

det 𝑀^{'} =

det 𝐴 det 𝐷

Let $𝑛 = 𝑘 + 𝑚$ , $𝐾 = {𝑘 + 1, \dots, 𝑛}$ , $𝑀 = (\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 \end{matrix})$ , and $𝑀^{'} = (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐷 \end{matrix})$ . Write $𝑐_{𝑖 𝑗}$ and $𝑐_{𝑖 𝑗}^{'}$ for the entries of $𝑀$ and $𝑀^{'}$ . They agree unless $𝑖 \leq 𝑘 < 𝑗$ , that is, unless position $(𝑖, 𝑗)$ lies in the upper right block. We compare the terms of a fixed $𝜎 \in 𝑆_{𝑛}$ in the Leibniz formulas for $det 𝑀$ and $det 𝑀^{'}$ .

If $𝜎 (𝑗) \in 𝐾$ for some $𝑗 \leq 𝑘$ , then position $(𝜎 (𝑗), 𝑗)$ lies in the lower left block, so $𝑐_{𝜎 (𝑗) 𝑗} =$ $𝑐_{𝜎 (𝑗) 𝑗}^{'} =$ $0$ , and both terms are $0$ . Otherwise $𝜎$ maps $[𝑘]$ into $[𝑘]$ , hence onto $[𝑘]$ since it is injective, and then it maps $𝐾$ onto $𝐾$ since it is a bijection. Then every position $(𝜎 (𝑗), 𝑗)$ lies in one of the two diagonal blocks, where $𝑀$ and $𝑀^{'}$ agree, so the two terms are equal. Hence $det 𝑀 =$ $det 𝑀^{'} =$ $det 𝐴 det 𝐷$ by Proposition 5.3.17. The second identity follows by transposing, as in the first proof. □

The first proof shows how block matrices can be manipulated like matrices of numbers, as long as the order of factors is respected (Technique 2.4.35). The second proof is the shorter one here, because the work was done in Proposition 5.3.17. Grouping the diagonal blocks two at a time extends the theorem to any number of blocks.

Corollary 5.4.27 (Several diagonal blocks). Let $𝑀$ be block upper triangular (or block lower triangular) with square diagonal blocks $𝐴_{1}, \dots, 𝐴_{𝑟}$ . Then

det 𝑀 = det 𝐴_{1} det 𝐴_{2} \dots det 𝐴_{𝑟} .

Proof.routine

Uses. Theorem 5.4.26 (Block-triangular matrices), Definition 2.4.33 (Block matrix), induction on $𝑟$

Techniques. Block decomposition (Technique 2.4.35)

Hint 1. Induct on

𝑟

. Regard

𝑀

as a

2 \times 2

block matrix whose upper left block is

𝐴_{1}

Hint 2. The lower right block is block triangular with diagonal blocks

𝐴_{2}, \dots, 𝐴_{𝑟}

Sketch. For

𝑟 \geq 2

, group the last

𝑟 - 1

block rows and columns:

𝑀 = (\begin{matrix} 𝐴_{1} & 𝑋 \\ 0 & 𝑀^{'} \end{matrix})

, where

𝑀^{'}

is block upper triangular with diagonal blocks

𝐴_{2}, \dots, 𝐴_{𝑟}

. Then

det 𝑀 =

det 𝐴_{1} det 𝑀^{'}

by Theorem 5.4.26, and induction finishes. The lower triangular case is the same with

(\begin{matrix} 𝐴_{1} & 0 \\ 𝑌 & 𝑀^{'} \end{matrix})

We induct on $𝑟$ ; for $𝑟 = 1$ there is nothing to prove. Let $𝑟 \geq 2$ , and suppose $𝑀$ is block upper triangular. Grouping the block rows and block columns $2, \dots, 𝑟$ together, $𝑀 = (\begin{matrix} 𝐴_{1} & 𝑋 \\ 0 & 𝑀^{'} \end{matrix})$ , where the lower left block is $0$ because all blocks below the diagonal are, and $𝑀^{'}$ is block upper triangular with diagonal blocks $𝐴_{2}, \dots, 𝐴_{𝑟}$ . By Theorem 5.4.26 and the induction hypothesis,

det 𝑀 = det 𝐴_{1} det 𝑀^{'} = det 𝐴_{1} det 𝐴_{2} \dots det 𝐴_{𝑟} .

The block lower triangular case is identical, with $𝑀 = (\begin{matrix} 𝐴_{1} & 0 \\ 𝑌 & 𝑀^{'} \end{matrix})$ . □

With $1 \times 1$ blocks this is Proposition 5.3.15. For example, the matrix

𝑀 = (\begin{matrix} 1 & 2 & 5 & 7 \\ 3 & 4 & 6 & 8 \\ 0 & 0 & 2 & 1 \\ 0 & 0 & 1 & 1 \end{matrix})

is block upper triangular with diagonal blocks $(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})$ and $(\begin{matrix} 2 & 1 \\ 1 & 1 \end{matrix})$ , so $det 𝑀 = (- 2) \cdot 1 = - 2$ . A $2 \times 2$ block matrix does not behave like a $2 \times 2$ matrix of numbers, though: in general $det (\begin{matrix} 𝐴 & 𝐵 \\ 𝐶 & 𝐷 \end{matrix})$ is neither $det 𝐴 det 𝐷 -$ $det 𝐵 det 𝐶$ (Exercise 5.4.36) nor $det (𝐴 𝐷 - 𝐵 𝐶)$ (the example in Exercise 5.4.50).

Block elimination Beyond 21-242

Schur complements are standard in numerical linear algebra and statistics, but they are not part of the course.

When the upper left block is invertible, a general $2 \times 2$ block matrix can be reduced to the block-triangular case by one step of elimination with blocks.

Technique 5.4.28 (Block elimination). Row reduction works with blocks in place of entries, as long as the order of the factors in each product is respected. By Theorem 2.4.34, multiplying $(\begin{matrix} 𝐴 & 𝐵 \\ 𝐶 & 𝐷 \end{matrix})$ on the left by $(\begin{matrix} 𝐼 & 0 \\ 𝑋 & 𝐼 \end{matrix})$ adds $𝑋$ times the first block row to the second, giving $(\begin{matrix} 𝐴 & 𝐵 \\ 𝑋 𝐴 + 𝐶 & 𝑋 𝐵 + 𝐷 \end{matrix})$ . Multiplying on the right by $(\begin{matrix} 𝐼 & 𝑌 \\ 0 & 𝐼 \end{matrix})$ adds the first block column times $𝑌$ to the second, giving $(\begin{matrix} 𝐴 & 𝐴 𝑌 + 𝐵 \\ 𝐶 & 𝐶 𝑌 + 𝐷 \end{matrix})$ . Both multipliers have determinant $1$ by Theorem 5.4.26, so these operations do not change the determinant. Choose $𝑋$ or $𝑌$ to create a zero block, and finish with Theorem 5.4.26.

Reach for it when you want the determinant or the inverse of a $2 \times 2$ block matrix and one of the blocks is invertible, or when two block matrices are related by such operations. The canonical example is Proposition 5.4.29.

Used in 3 places and 1 practice exercise

Proposition 5.4.29, Exercise 5.4.50, Theorem 5.5.27; 1 practice exercise.

Proposition 5.4.29 (Schur complement). Let $𝐴 \in 𝐹^{𝑘 \times 𝑘}$ be invertible, and let $𝐵 \in 𝐹^{𝑘 \times 𝑚}$ , $𝐶 \in 𝐹^{𝑚 \times 𝑘}$ , and $𝐷 \in 𝐹^{𝑚 \times 𝑚}$ . Then

det (\begin{matrix} 𝐴 & 𝐵 \\ 𝐶 & 𝐷 \end{matrix}) = det 𝐴 det (𝐷 - 𝐶 𝐴^{- 1} 𝐵) .

Proof.standard

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

Techniques. Block elimination (Technique 5.4.28)

Hint 1. Imitate the first stage of elimination, with the block

𝐴

as the pivot: clear the block

𝐶

below it.

Hint 2. Multiply on the left by

(\begin{matrix} 𝐼_{𝑘} & 0 \\ 𝑋 & 𝐼_{𝑚} \end{matrix})

, and choose

𝑋

so that the lower left block becomes

0

Sketch. With

𝑋 = - 𝐶 𝐴^{- 1}

, block multiplication gives

(\begin{matrix} 𝐼_{𝑘} & 0 \\ 𝑋 & 𝐼_{𝑚} \end{matrix}) (\begin{matrix} 𝐴 & 𝐵 \\ 𝐶 & 𝐷 \end{matrix}) =

(\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 - 𝐶 𝐴^{- 1} 𝐵 \end{matrix})

. The left factor has determinant

1

, and the right side has determinant

det 𝐴 det (𝐷 - 𝐶 𝐴^{- 1} 𝐵)

, both by Theorem 5.4.26.

Let $𝑀 = (\begin{matrix} 𝐴 & 𝐵 \\ 𝐶 & 𝐷 \end{matrix})$ and $𝑋 =$ $- 𝐶 𝐴^{- 1} \in$ $𝐹^{𝑚 \times 𝑘}$ . By Theorem 2.4.34,

\begin{aligned} (\begin{matrix} 𝐼_{𝑘} & 0 \\ 𝑋 & 𝐼_{𝑚} \end{matrix}) 𝑀 & = (\begin{matrix} 𝐴 & 𝐵 \\ 𝑋 𝐴 + 𝐶 & 𝑋 𝐵 + 𝐷 \end{matrix}) \\ = (\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 - 𝐶 𝐴^{- 1} 𝐵 \end{matrix}) . \end{aligned}

By Theorem 5.4.26, the left factor has determinant $det 𝐼_{𝑘} det 𝐼_{𝑚} = 1$ , and the right side has determinant $det 𝐴 det (𝐷 - 𝐶 𝐴^{- 1} 𝐵)$ . So Theorem 5.4.10 gives the claim. □

The matrix $𝐷 - 𝐶 𝐴^{- 1} 𝐵$ is the Schur complement of $𝐴$ in $𝑀$ . For $𝑘 = 𝑚 = 1$ the proposition reads $det (\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix}) =$ $𝑎 (𝑑 - 𝑐 𝑎^{- 1} 𝑏) =$ $𝑎 𝑑 -$ $𝑏 𝑐$ . If also $𝐴 𝐶 = 𝐶 𝐴$ , then $𝐴 (𝐷 - 𝐶 𝐴^{- 1} 𝐵) =$ $𝐴 𝐷 -$ $𝐶 𝐵$ , and the proposition becomes $det 𝑀 =$ $det (𝐴 𝐷 - 𝐶 𝐵)$ (Exercise 5.4.50).

Exercises

Exercise 5.4.30.routine Let

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

(a)Compute $det 𝐴$ with Algorithm 5.4.22.
(b)For which primes $𝑝$ is the reduction of $𝐴$ modulo $𝑝$ invertible over $𝔽_{𝑝}$ ?

Solution.

Uses. Algorithm 5.4.22 (Determinant by elimination), Proposition 5.3.20 (Reduction modulo $𝑝$ ), Theorem 5.4.7 (Invertibility and the determinant)

Hint 1. Stage

1

clears column

1

using row

1

. Check the

(2, 2)

entry afterwards.

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

𝑝

(Proposition 5.3.20).

Sketch. After stage

1

the rows below row

1

are

(0, 0, 2, 1)

(0, 1, - 1, 3)

(0, - 2, 4, 10)

. Swap rows

2

and

3

, add

2

times row

2

to row

4

, then subtract row

3

from row

4

. The diagonal is

1, 1, 2, 15

with one swap, so

det 𝐴 = - 30

. The reduction is invertible exactly for

𝑝 \notin {2, 3, 5}

(a) Stage $1$ adds $2$ , $- 3$ , and $- 1$ times row $1$ to rows $2$ , $3$ , and $4$ . Stage $2$ finds a $0$ in position $(2, 2)$ , swaps rows $2$ and $3$ , and adds $2$ times the new row $2$ to row $4$ . Stage $3$ adds $- 1$ times row $3$ to row $4$ :

𝐴 \overset{stage 1}{\to} (\begin{matrix} 1 & 3 & 0 & 2 \\ 0 & 0 & 2 & 1 \\ 0 & 1 & - 1 & 3 \\ 0 & - 2 & 4 & 10 \end{matrix}),

\overset{stage 2}{\to} (\begin{matrix} 1 & 3 & 0 & 2 \\ 0 & 1 & - 1 & 3 \\ 0 & 0 & 2 & 1 \\ 0 & 0 & 2 & 16 \end{matrix}) \overset{stage 3}{\to} (\begin{matrix} 1 & 3 & 0 & 2 \\ 0 & 1 & - 1 & 3 \\ 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 15 \end{matrix}) .

There was one swap, so $det 𝐴 =$ $(- 1) \cdot$ $1 \cdot$ $1 \cdot$ $2 \cdot$ $15 =$ $- 30$ .

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

Exercise 5.4.31.routine Let $𝐴, 𝐵 \in ℝ^{3 \times 3}$ with $det 𝐴 = 2$ and $det 𝐵 = - 3$ . Compute

\begin{matrix} det (𝐴 𝐵), det (𝐴^{- 1} 𝐵^{2}), det (2 𝐴^{𝖳}), \\ det (𝐵 𝐴 𝐵^{- 1}), det (𝐴^{𝖳} 𝐴), det (- 𝐴^{3}) . \end{matrix}

Solution.

Uses. Theorem 5.4.10 (Multiplicativity), Theorem 5.4.14 (The transpose), Exercise 5.1.5, Exercise 5.4.12, Theorem 5.4.7 (Invertibility and the determinant)

Hint 1. Both matrices are invertible by Theorem 5.4.7, so the inverses make sense.

Hint 2. Use

det (𝑐 𝐴) =

𝑐^{3} det 𝐴

for

3 \times 3

matrices, and

det (𝐴^{- 1}) =

{(det 𝐴)}^{- 1}

Sketch.

- 6

9 / 2

16

2

4

- 8

Since $det 𝐴$ and $det 𝐵$ are nonzero, $𝐴$ and $𝐵$ are invertible (Theorem 5.4.7). By Theorem 5.4.10, Theorem 5.4.14, Exercise 5.4.12, and Exercise 5.1.5 (with $𝑛 = 3$ ):

$det (𝐴 𝐵) =$ $2 \cdot$ $(- 3) =$ $- 6$ ;
$det (𝐴^{- 1} 𝐵^{2}) =$ $(1 / 2) \cdot$ $9 =$ $9 / 2$ ;
$det (2 𝐴^{𝖳}) =$ $2^{3} det 𝐴 =$ $16$ ;
$det (𝐵 𝐴 𝐵^{- 1}) =$ $det 𝐵 det 𝐴 {(det 𝐵)}^{- 1} =$ $2$ ;
$det (𝐴^{𝖳} 𝐴) =$ ${(det 𝐴)}^{2} =$ $4$ ;
$det (- 𝐴^{3}) =$ ${(- 1)}^{3} {(det 𝐴)}^{3} =$ $- 8$ .

Exercise 5.4.32.standard For which

𝑛 \geq 1

is there a matrix

𝐴 \in 𝐹^{𝑛 \times 𝑛}

with

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

, when (a)

𝐹 = ℝ

, (b)

𝐹 = ℂ

, (c)

𝐹 = 𝔽_{3}

, (d)

𝐹 = 𝔽_{5}

Solution.

Uses. Theorem 5.4.10 (Multiplicativity), Exercise 5.1.5, Theorem 2.4.34 (Block multiplication)

Hint 1. Take determinants: what does

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

say about

{(det 𝐴)}^{2}

Hint 2. For odd

𝑛

you need

- 1

to be a square in

𝐹

. For even

𝑛

, find a

2 \times 2

example and place copies of it along the diagonal.

Sketch.

{(det 𝐴)}^{2} =

det (- 𝐼_{𝑛}) =

{(- 1)}^{𝑛}

. If

𝑛

is odd this needs a square root of

- 1

𝐹

, which

ℝ

and

𝔽_{3}

lack. For even

𝑛

, the block diagonal matrix with blocks

𝐽 = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})

works over every field, as

𝐽^{2} = - 𝐼_{2}

. Over

ℂ

and

𝔽_{5}

𝑖 𝐼_{𝑛}

and

2 𝐼_{𝑛}

work for every

𝑛

. So: (a), (c) exactly the even

𝑛

; (b), (d) every

𝑛

If $𝐴^{2} = - 𝐼_{𝑛}$ , then by Theorem 5.4.10 and Exercise 5.1.5,

{(det 𝐴)}^{2} = det (𝐴^{2}) = det (- 𝐼_{𝑛}) = {(- 1)}^{𝑛} .

So if $𝑛$ is odd, $det 𝐴$ is a square root of $- 1$ in $𝐹$ .

Conversely, let $𝐽 = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ . Then $𝐽^{2} = (\begin{matrix} - 1 & 0 \\ 0 & - 1 \end{matrix}) = - 𝐼_{2}$ over every field. If $𝑛 = 2 𝑙$ is even, let $𝐴$ be block diagonal with $𝑙$ diagonal blocks equal to $𝐽$ . Block diagonal matrices multiply block by block (Theorem 2.4.34), so $𝐴^{2}$ is block diagonal with blocks $𝐽^{2} = - 𝐼_{2}$ , that is, $𝐴^{2} = - 𝐼_{𝑛}$ .

(a) Squares of real numbers are nonnegative, so ${(det 𝐴)}^{2} = - 1$ is impossible: there is no such $𝐴$ for odd $𝑛$ . For even $𝑛$ there is. Answer: exactly the even $𝑛$ .

(b) $𝐴 = 𝑖 𝐼_{𝑛}$ has $𝐴^{2} = 𝑖^{2} 𝐼_{𝑛} = - 𝐼_{𝑛}$ , for every $𝑛$ .

(c) In $𝔽_{3}$ , $0^{2} = 0$ , $1^{2} = 1$ , and $2^{2} = 4 = 1$ , so $- 1 = 2$ is not a square. As in (a), the answer is exactly the even $𝑛$ .

(d) In $𝔽_{5}$ , $2^{2} = 4 = - 1$ , so $𝐴 = 2 𝐼_{𝑛}$ has $𝐴^{2} = - 𝐼_{𝑛}$ for every $𝑛$ .

Exercise 5.4.33.standard A matrix $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ is skew-symmetric if $𝐴^{𝖳} = - 𝐴$ .

(a)Suppose that $1 + 1 \neq 0$ in $𝐹$ and that $𝑛$ is odd. Show that every skew-symmetric $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ has $det 𝐴 = 0$ .
(b)Keep the assumption $1 + 1 \neq 0$ . Show that the skew-symmetric $3 \times 3$ matrices are exactly the matrices $(\begin{matrix} 0 & 𝑎 & 𝑏 \\ - 𝑎 & 0 & 𝑐 \\ - 𝑏 & - 𝑐 & 0 \end{matrix})$ with $𝑎, 𝑏, 𝑐 \in 𝐹$ , and for such a matrix $𝐴 \neq 0$ , find a nonzero $𝐱$ with $𝐴 𝐱 = 𝟎$ .
(c)Show that (a) fails over $𝔽_{2}$ .

Solution.

Uses. Theorem 5.4.14 (The transpose), Exercise 5.1.5, Proposition 1.1.17 (No zero divisors), Definition 2.4.21 (Transpose), Corollary 5.4.8 (Vanishing determinants)

Hint 1. Compute

det 𝐴^{𝖳}

in two ways: by Theorem 5.4.14 and from

𝐴^{𝖳} = - 𝐴

Hint 2. For (b), read off what

𝑎_{𝑗 𝑖} = - 𝑎_{𝑖 𝑗}

says on the diagonal and off it. For the kernel vector, try a vector built from

𝑎

𝑏

𝑐

Hint 3. Over

𝔽_{2}

- 1 = 1

. What does skew-symmetric mean there?

Sketch. (a)

det 𝐴 =

det 𝐴^{𝖳} =

det (- 𝐴) =

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

- det 𝐴

, so

(1 + 1) det 𝐴 = 0

. (b)

𝑎_{𝑖 𝑖} = - 𝑎_{𝑖 𝑖}

forces

𝑎_{𝑖 𝑖} = 0

, and the entries below the diagonal are the negatives of those above;

𝐱 = (𝑐, - 𝑏, 𝑎)

. (c) Over

𝔽_{2}

skew-symmetric means symmetric, and

𝐼_{3}

is symmetric with determinant

1

(a) By Theorem 5.4.14 and Exercise 5.1.5,

\begin{matrix} det 𝐴 = det 𝐴^{𝖳} = det (- 𝐴) \\ = {(- 1)}^{𝑛} det 𝐴 = - det 𝐴, \end{matrix}

since $𝑛$ is odd. So $(1 + 1) det 𝐴 = 0$ , and as $1 + 1 \neq 0$ , $det 𝐴 = 0$ (Proposition 1.1.17).

(b) $𝐴^{𝖳} = - 𝐴$ says $𝑎_{𝑗 𝑖} = - 𝑎_{𝑖 𝑗}$ for all $𝑖, 𝑗$ (Definition 2.4.21). For $𝑖 = 𝑗$ this is $(1 + 1) 𝑎_{𝑖 𝑖} = 0$ , so $𝑎_{𝑖 𝑖} = 0$ . For $𝑖 \neq 𝑗$ it says that the entries below the diagonal are the negatives of those above it. With $𝑎 = 𝑎_{12}$ , $𝑏 = 𝑎_{13}$ , and $𝑐 = 𝑎_{23}$ , $𝐴$ has the stated form, and conversely every matrix of that form satisfies $𝐴^{𝖳} = - 𝐴$ . Let $𝐱 = (𝑐, - 𝑏, 𝑎)$ . Then

𝐴 𝐱 = (- 𝑎 𝑏 + 𝑏 𝑎, - 𝑎 𝑐 + 𝑐 𝑎, - 𝑏 𝑐 + 𝑐 𝑏) = 𝟎,

and $𝐱 \neq 𝟎$ because $𝐴 \neq 0$ means that $𝑎$ , $𝑏$ , $𝑐$ are not all $0$ . So the columns of $𝐴$ are dependent, and $det 𝐴 = 0$ by Corollary 5.4.8, as (a) predicts.

(c) In $𝔽_{2}$ , $- 1 = 1$ , so $𝐴^{𝖳} = - 𝐴$ means $𝐴^{𝖳} = 𝐴$ . The identity matrix $𝐼_{3}$ is symmetric, hence skew-symmetric over $𝔽_{2}$ , and $det 𝐼_{3} = 1 \neq 0$ . So the hypothesis $1 + 1 \neq 0$ in (a) cannot be dropped.

Exercise 5.4.34.standard Let $𝑛 \geq 1$ . In each case, find all possible values of $det 𝐴$ , and show that each of them occurs.

(a) $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ with $𝐴^{2} = 𝐴$ .
(b) $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ with $𝐴^{𝑘} = 0$ for some $𝑘 \geq 1$ .
(c) $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ with $𝐴^{2} = 𝐼_{𝑛}$ .
(d) $𝐴 \in ℝ^{𝑛 \times 𝑛}$ with $𝐴^{𝖳} 𝐴 = 𝐼_{𝑛}$ .

Solution.

Uses. Theorem 5.4.10 (Multiplicativity), Theorem 5.4.14 (The transpose), Exercise 5.4.12, Proposition 1.1.17 (No zero divisors), Proposition 5.4.1 (Determinants of elementary matrices)

Hint 1. Apply

det

to the defining equation. You get a polynomial equation for

𝑑 = det 𝐴

Hint 2. Factor:

𝑑^{2} - 𝑑 = 𝑑 (𝑑 - 1)

and

𝑑^{2} -

1 =

(𝑑 - 1) (𝑑 + 1)

. For the examples, try

0

𝐼_{𝑛}

, and a scaling matrix.

Sketch. (a)

𝑑^{2} = 𝑑

, so

𝑑 \in {0, 1}

: the zero matrix and

𝐼_{𝑛}

. (b)

𝑑^{𝑘} = 0

, so

𝑑 = 0

: the zero matrix. (c)

𝑑^{2} = 1

, so

𝑑 = \pm 1

𝐼_{𝑛}

and

𝐸_{1, - 1}

. (d)

𝑑^{2} = 1

: again

𝐼_{𝑛}

and

𝐸_{1, - 1}

Write $𝑑 = det 𝐴$ , and use Exercise 5.4.12 for $det (𝐴^{𝑘}) = 𝑑^{𝑘}$ . The zero matrix has determinant $0$ (it has a zero column), and $𝐼_{𝑛}$ has determinant $1$ .

(a) $𝑑^{2} = 𝑑$ , so $𝑑 (𝑑 - 1) = 0$ and $𝑑 \in {0, 1}$ (Proposition 1.1.17). Both occur: $0^{2} = 0$ and $𝐼_{𝑛}^{2} = 𝐼_{𝑛}$ .

(b) $𝑑^{𝑘} = det 0 = 0$ , and a product of nonzero scalars is nonzero, so $𝑑 = 0$ . It occurs for the zero matrix.

(c) $𝑑^{2} = det 𝐼_{𝑛} = 1$ , so $(𝑑 - 1) (𝑑 + 1) = 0$ and $𝑑 = \pm 1$ . Both occur: $𝐼_{𝑛}^{2} = 𝐼_{𝑛}$ , and the scaling $𝐸_{1, - 1}$ satisfies $𝐸_{1, - 1}^{2} =$ $𝐸_{1, 1} =$ $𝐼_{𝑛}$ and has determinant $- 1$ (Proposition 5.4.1). (If $1 + 1 = 0$ , the two values coincide.)

(d) $𝑑^{2} =$ $det 𝐴^{𝖳} det 𝐴 =$ $det (𝐴^{𝖳} 𝐴) =$ $1$ by Theorem 5.4.14, so $𝑑 = \pm 1$ . Both occur: $𝐼_{𝑛}$ , and $𝐸_{1, - 1}$ , which is diagonal, so $𝐸_{1, - 1}^{𝖳} 𝐸_{1, - 1} =$ $𝐸_{1, - 1}^{2} =$ $𝐼_{𝑛}$ .

Exercise 5.4.35.standard Find the error in the following argument, and repair it.

Claim. $det (𝐴 𝐵) =$ $det 𝐴 det 𝐵$ for all $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ .

Proof. By Theorem 3.5.19, we can write $𝐴 = 𝐸_{1} \dots 𝐸_{𝑘}$ and $𝐵 = 𝐸_{1}^{'} \dots 𝐸_{𝑙}^{'}$ with elementary matrices $𝐸_{𝑖}$ and $𝐸_{𝑗}^{'}$ . By Corollary 5.4.4,

\begin{aligned} det (𝐴 𝐵) & = det (𝐸_{1} \dots 𝐸_{𝑘} 𝐸_{1}^{'} \dots 𝐸_{𝑙}^{'}) \\ = det 𝐸_{1} \dots det 𝐸_{𝑘} det 𝐸_{1}^{'} \dots det 𝐸_{𝑙}^{'} \\ = det 𝐴 det 𝐵 . \end{aligned}

Solution.

Uses. Theorem 3.5.19 (Invertible matrices are products of elementary matrices), Corollary 3.2.11 (Products of elementary matrices), Theorem 3.5.23 (One-sided inverses of square matrices), Theorem 5.4.7 (Invertibility and the determinant)

Techniques. Reduce to elementary matrices (Technique 5.4.6)

Hint 1. What is the hypothesis of Theorem 3.5.19? Is the zero matrix a product of elementary matrices?

Hint 2. To repair the proof, show that if

𝐴

𝐵

is not invertible, then neither is

𝐴 𝐵

Sketch. The factorization exists only for invertible matrices; a product of elementary matrices is always invertible, so for example

0

is not one. The argument proves the claim when

𝐴

and

𝐵

are both invertible. If

𝐴

𝐵

is not invertible, then

𝐴 𝐵

is not invertible (an inverse

𝐶

𝐴 𝐵

would give

𝐴

the right inverse

𝐵 𝐶

and

𝐵

the left inverse

𝐶 𝐴

), so both sides are

0

The claim is true, but the proof covers only invertible $𝐴$ and $𝐵$ . Theorem 3.5.19 applies to invertible matrices, and it cannot apply to any other matrix, since a product of elementary matrices is invertible (Corollary 3.2.11). For instance, the zero matrix is not a product of elementary matrices.

To repair the argument, it remains to treat the case where $𝐴$ or $𝐵$ is not invertible; then $det 𝐴 det 𝐵 = 0$ by Theorem 5.4.7. Suppose $𝐴 𝐵$ were invertible, with inverse $𝐶$ . Then $𝐴 (𝐵 𝐶) = 𝐼_{𝑛}$ and $(𝐶 𝐴) 𝐵 = 𝐼_{𝑛}$ , so $𝐴$ has a right inverse and $𝐵$ has a left inverse, and both are invertible by Theorem 3.5.23. So if $𝐴$ or $𝐵$ is not invertible, then $𝐴 𝐵$ is not invertible, and $det (𝐴 𝐵) =$ $0 =$ $det 𝐴 det 𝐵$ . (The first proof of Theorem 5.4.10 avoids factoring $𝐴$ at all.)

Exercise 5.4.36.standard Let $𝐴,$ $𝐵,$ $𝐶,$ $𝐷 \in$ $𝐹^{𝑚 \times 𝑚}$ and $𝑀 = (\begin{matrix} 𝐴 & 𝐵 \\ 𝐶 & 𝐷 \end{matrix})$ .

(a)Find the error in the following argument.
Claim. $det 𝑀 =$ $det 𝐴 det 𝐷 -$ $det 𝐵 det 𝐶$ .
Proof. By Theorem 2.4.34, block matrices multiply like $2 \times 2$ matrices whose entries are the blocks. So $𝑀$ is a $2 \times 2$ matrix with entries $𝐴, 𝐵, 𝐶, 𝐷$ , and Theorem 5.1.13 gives $det 𝑀 =$ $det 𝐴 det 𝐷 -$ $det 𝐵 det 𝐶$ .
(b)Show that the claim is false for $𝑚 = 2$ , over every field.
(c)Show that the claim is true when $𝐶 = 0$ .

Solution.

Uses. Theorem 5.1.13 (The $2 \times 2$ determinant), Theorem 5.2.31 (Alternating functions and permutations), Theorem 5.4.26 (Block-triangular matrices), Definition 5.2.29 (Permutation matrix)

Hint 1. What kind of object is Theorem 5.1.13 about? Are the blocks elements of

𝐹

Hint 2. For (b), look for blocks that each have a zero column, while

𝑀

is a permutation matrix.

Sketch. (a) Theorem 5.1.13 is about

2 \times 2

matrices with entries in the field

𝐹

. Blocks are not elements of

𝐹

, and

𝑀

is a

2 𝑚 \times 2 𝑚

matrix, whose determinant is defined through its

2 𝑚

columns; that blocks multiply like entries says nothing about determinants. (b)

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

𝐵 = 𝐶 = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix})

make

𝑀

the permutation matrix of

(2 4)

, with determinant

- 1

, while every block has determinant

0

. (c) This is Theorem 5.4.26, since

det 0 = 0

(a) Theorem 5.1.13 is about functions on $𝐹^{2 \times 2}$ , matrices whose four entries are elements of the field $𝐹$ . The blocks are matrices, not elements of $𝐹$ (their products do not even commute), and $𝑀$ is a $2 𝑚 \times 2 𝑚$ matrix whose determinant is defined through its $2 𝑚$ columns. Theorem 2.4.34 says only how products of block matrices are computed. It says nothing about determinants, so the formula of Theorem 5.1.13 cannot simply be transplanted.

(b) Let $𝐴 = 𝐷 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ and $𝐵 = 𝐶 = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix})$ . Then

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

whose columns are $𝐞_{1}, 𝐞_{4}, 𝐞_{3}, 𝐞_{2}$ . So $𝑀 = 𝐸_{𝜎}$ for the transposition $𝜎 = (2 4)$ (Definition 5.2.29), and $det 𝑀 = sgn (𝜎) = - 1$ by Theorem 5.2.31. Each of $𝐴$ , $𝐵$ , $𝐶$ , $𝐷$ has a zero column, hence determinant $0$ , so the claimed formula gives $0$ . Since $- 1 \neq 0$ in every field, the claim is false.

(c) If $𝐶 = 0$ , then $det 𝐶 = 0$ (as $𝑚 \geq 1$ , $𝐶$ has a zero column), so the claim reads $det 𝑀 = det 𝐴 det 𝐷$ , which is Theorem 5.4.26.

Exercise 5.4.37.standard For $𝑛 \geq 1$ , let $𝑃_{𝑛}, 𝑄_{𝑛} \in ℚ^{𝑛 \times 𝑛}$ have entries $min (𝑖, 𝑗)$ and $max (𝑖, 𝑗)$ , respectively, in position $(𝑖, 𝑗)$ . For example,

𝑃_{3} = (\begin{matrix} 1 & 1 & 1 \\ 1 & 2 & 2 \\ 1 & 2 & 3 \end{matrix}), 𝑄_{3} = (\begin{matrix} 1 & 2 & 3 \\ 2 & 2 & 3 \\ 3 & 3 & 3 \end{matrix}) .

Show that $det 𝑃_{𝑛} = 1$ and $det 𝑄_{𝑛} =$ ${(- 1)}^{𝑛 - 1} 𝑛$ .

Solution.

Uses. Corollary 5.4.15 (Rows), Proposition 5.3.15 (Triangular matrices), Theorem 5.2.31 (Alternating functions and permutations), Definition 5.2.29 (Permutation matrix), Proposition 5.2.26 (Sign of a cycle)

Hint 1. Subtract each row from the row below it, starting at the bottom, so that every subtraction uses an original row.

Hint 2. For

𝑃_{𝑛}

you get an upper triangular matrix. For

𝑄_{𝑛}

you get rows of the form

(1, \dots, 1, 0, \dots, 0)

; subtract again, starting at the bottom.

Sketch. For

𝑖 = 𝑛, \dots, 2

, replace row

𝑖

by row

𝑖

minus row

𝑖 - 1

. In

𝑃_{𝑛}

, row

𝑖

becomes

(0, \dots, 0, 1, \dots, 1)

with its first

1

in column

𝑖

: upper triangular with

1

s on the diagonal. In

𝑄_{𝑛}

, row

𝑖

becomes

(1, \dots, 1, 0, \dots, 0)

with

𝑖 - 1

ones; repeating the subtraction turns row

𝑖

into

𝐞_{𝑖 - 1}^{𝖳}

, and clearing row

1

with these leaves

𝑛 𝐞_{𝑛}^{𝖳}

. The rows

𝑛 𝐞_{𝑛}^{𝖳},

𝐞_{1}^{𝖳},

\dots,

𝐞_{𝑛 - 1}^{𝖳}

give

𝑛

times a cyclic permutation matrix of sign

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

Row replacements do not change the determinant (Corollary 5.4.15). In both cases, first replace row $𝑖$ by row $𝑖$ minus row $𝑖 - 1$ for $𝑖 = 𝑛, 𝑛 - 1, \dots, 2$ , in this order, so that row $𝑖 - 1$ is still the original row when it is used.

$𝑃_{𝑛}$ . The new row $𝑖$ (for $𝑖 \geq 2$ ) has entries $min (𝑖, 𝑗) -$ $min (𝑖 - 1, 𝑗)$ , which is $0$ for $𝑗 \leq 𝑖 - 1$ and $1$ for $𝑗 \geq 𝑖$ . Row $1$ is $(1, \dots, 1)$ . The result is upper triangular with every diagonal entry $1$ , so $det 𝑃_{𝑛} = 1$ by Proposition 5.3.15.

$𝑄_{𝑛}$ . The new row $𝑖$ (for $𝑖 \geq 2$ ) has entries $max (𝑖, 𝑗) -$ $max (𝑖 - 1, 𝑗)$ , which is $1$ for $𝑗 \leq 𝑖 - 1$ and $0$ for $𝑗 \geq 𝑖$ . Row $1$ is $(1, 2, \dots, 𝑛)$ . Repeat the procedure on rows $2, \dots, 𝑛$ : for $𝑖 = 𝑛, \dots, 3$ , subtract the current row $𝑖 - 1$ from row $𝑖$ . Since row $𝑖$ has $𝑖 - 1$ leading ones and row $𝑖 - 1$ has $𝑖 - 2$ , row $𝑖$ becomes $𝐞_{𝑖 - 1}^{𝖳}$ , and row $2$ is $𝐞_{1}^{𝖳}$ already. Finally subtract $𝑗$ times row $𝑗 + 1$ (which is $𝐞_{𝑗}^{𝖳}$ ) from row $1$ , for $𝑗 = 1, \dots, 𝑛 - 1$ ; this leaves row $1$ equal to $𝑛 𝐞_{𝑛}^{𝖳}$ . None of these steps changes the determinant. Pulling the factor $𝑛$ out of row $1$ (Corollary 5.4.15), $det 𝑄_{𝑛} = 𝑛 det 𝑅$ , where $𝑅$ has rows $𝐞_{𝑛}^{𝖳},$ $𝐞_{1}^{𝖳},$ $\dots,$ $𝐞_{𝑛 - 1}^{𝖳}$ . The columns of $𝑅$ are $𝐞_{2},$ $𝐞_{3},$ $\dots,$ $𝐞_{𝑛},$ $𝐞_{1}$ , so $𝑅 = 𝐸_{𝜎}$ for the $𝑛$ -cycle $𝜎$ with $𝜎 (𝑗) = 𝑗 + 1$ for $𝑗 < 𝑛$ and $𝜎 (𝑛) = 1$ (Definition 5.2.29). By Theorem 5.2.31 and Proposition 5.2.26, $det 𝑅 =$ $sgn (𝜎) =$ ${(- 1)}^{𝑛 - 1}$ . Hence $det 𝑄_{𝑛} =$ ${(- 1)}^{𝑛 - 1} 𝑛$ . (For $𝑛 = 1$ there is nothing to do: $𝑄_{1} = (1)$ .)

Exercise 5.4.38.standard Let

𝑚 < 𝑛

𝐴 \in 𝐹^{𝑛 \times 𝑚}

, and

𝐵 \in 𝐹^{𝑚 \times 𝑛}

. Show that

det (𝐴 𝐵) = 0

. Does the same hold when

𝑚 \geq 𝑛

Solution.

Uses. Theorem 2.4.34 (Block multiplication), Theorem 5.4.10 (Multiplicativity), Exercise 5.1.5

Hint 1.

𝐴

and

𝐵

are not square, so Theorem 5.4.10 does not apply directly. Make them square without changing

𝐴 𝐵

Hint 2. Add

𝑛 - 𝑚

zero columns to

𝐴

and

𝑛 - 𝑚

zero rows to

𝐵

Sketch. With

𝐴^{'} = (\begin{matrix} 𝐴 & 0 \end{matrix}) \in 𝐹^{𝑛 \times 𝑛}

and

𝐵^{'} = (\begin{matrix} 𝐵 \\ 0 \end{matrix}) \in 𝐹^{𝑛 \times 𝑛}

, block multiplication gives

𝐴^{'} 𝐵^{'} =

𝐴 𝐵 +

0 =

𝐴 𝐵

. Since

𝐴^{'}

has a zero column,

det (𝐴 𝐵) =

det 𝐴^{'} det 𝐵^{'} =

0

. For

𝑚 \geq 𝑛

the conclusion fails:

𝐴 =

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

𝐹^{𝑛 \times 𝑚}

and

𝐵 = 𝐴^{𝖳}

give

𝐴 𝐵 = 𝐼_{𝑛}

Let $𝐴^{'} = (\begin{matrix} 𝐴 & 0 \end{matrix}) \in 𝐹^{𝑛 \times 𝑛}$ be $𝐴$ followed by $𝑛 - 𝑚$ zero columns, and let $𝐵^{'} = (\begin{matrix} 𝐵 \\ 0 \end{matrix}) \in 𝐹^{𝑛 \times 𝑛}$ be $𝐵$ followed by $𝑛 - 𝑚$ zero rows. By Theorem 2.4.34, $𝐴^{'} 𝐵^{'} =$ $𝐴 𝐵 +$ $0 \cdot$ $0 =$ $𝐴 𝐵$ . Since $𝑚 < 𝑛$ , $𝐴^{'}$ has a zero column, so $det 𝐴^{'} = 0$ (Exercise 5.1.5), and by Theorem 5.4.10,

det (𝐴 𝐵) = det (𝐴^{'} 𝐵^{'}) = det 𝐴^{'} det 𝐵^{'} = 0 .

For $𝑚 \geq 𝑛$ the conclusion fails. If $𝑚 = 𝑛$ , take $𝐴 = 𝐵 = 𝐼_{𝑛}$ . If $𝑚 > 𝑛$ , let $𝐴 \in 𝐹^{𝑛 \times 𝑚}$ be $𝐼_{𝑛}$ followed by $𝑚 - 𝑛$ zero columns, and $𝐵 = 𝐴^{𝖳} \in 𝐹^{𝑚 \times 𝑛}$ . Then $𝐴 𝐵 = 𝐼_{𝑛}$ by Theorem 2.4.34, so $det (𝐴 𝐵) = 1$ .

Exercise 5.4.39.standard Let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

, and define

𝐿_{𝐴},

𝑅_{𝐴} \in

L (𝐹^{𝑛 \times 𝑛})

𝐿_{𝐴} (𝑋) = 𝐴 𝑋

and

𝑅_{𝐴} (𝑋) = 𝑋 𝐴

. Show that

det 𝐿_{𝐴} =

det 𝑅_{𝐴} =

{(det 𝐴)}^{𝑛}

Solution.

Uses. Definition 5.4.18 (Determinant of an operator), Definition 2.3.1 (Matrix of a linear map), Definition 2.4.1 (Matrix product), Corollary 5.4.27 (Several diagonal blocks), Theorem 5.4.14 (The transpose)

Hint 1. Let

𝑈_{𝑖 𝑗}

be the matrix with

1

in position

(𝑖, 𝑗)

and

0

elsewhere. These

𝑛^{2}

matrices form a basis of

𝐹^{𝑛 \times 𝑛}

; the order in which you list them matters.

Hint 2.

𝐴 𝑈_{𝑖 𝑗}

has column

𝑗

equal to column

𝑖

𝐴

, and zeros elsewhere. List the

𝑈_{𝑖 𝑗}

column by column, that is,

𝑈_{11},

𝑈_{21},

\dots,

𝑈_{𝑛 1},

𝑈_{12},

\dots

Hint 3. For

𝑅_{𝐴}

, list them row by row instead. You should get a block diagonal matrix with blocks

𝐴^{𝖳}

Sketch. With the basis

𝑈_{11},

\dots,

𝑈_{𝑛 1},

𝑈_{12},

\dots,

𝑈_{𝑛 𝑛}

, the coordinates of

𝑋

are its columns stacked, and

𝐿_{𝐴}

multiplies each column by

𝐴

: its matrix is block diagonal with

𝑛

blocks

𝐴

. With the basis listed row by row,

𝑅_{𝐴}

replaces each row

𝐫^{𝖳}

𝐫^{𝖳} 𝐴 = {(𝐴^{𝖳} 𝐫)}^{𝖳}

, so its matrix is block diagonal with

𝑛

blocks

𝐴^{𝖳}

. Then use Corollary 5.4.27 and

det 𝐴^{𝖳} = det 𝐴

For $𝑖, 𝑗 \in [𝑛]$ , let $𝑈_{𝑖 𝑗}$ have $1$ in position $(𝑖, 𝑗)$ and $0$ elsewhere. Every $𝑋 \in 𝐹^{𝑛 \times 𝑛}$ is $\sum_{𝑖, 𝑗} 𝑥_{𝑖 𝑗} 𝑈_{𝑖 𝑗}$ , and the coefficients are the entries of $𝑋$ , so they are unique. Hence the $𝑈_{𝑖 𝑗}$ , in any order, form a basis of $𝐹^{𝑛 \times 𝑛}$ , and the coordinates of $𝑋$ are its entries in the corresponding order.

$𝐿_{𝐴}$ . List the basis column by column: $ℬ︀ =$ $𝑈_{11},$ $𝑈_{21},$ $\dots,$ $𝑈_{𝑛 1},$ $𝑈_{12},$ $\dots,$ $𝑈_{𝑛 𝑛}$ , so that $𝑈_{𝑘 𝑗}$ is the basis vector number $(𝑗 - 1) 𝑛 + 𝑘$ . By Definition 2.4.1, column $𝑙$ of $𝐴 𝑈_{𝑖 𝑗}$ is $𝐴$ times column $𝑙$ of $𝑈_{𝑖 𝑗}$ , which is $𝐴 𝐞_{𝑖} = 𝐚_{𝑖}$ for $𝑙 = 𝑗$ and $𝟎$ otherwise. So

𝐿_{𝐴} (𝑈_{𝑖 𝑗}) = 𝐴 𝑈_{𝑖 𝑗} = \sum_{𝑘 = 1}^{𝑛} 𝑎_{𝑘 𝑖} 𝑈_{𝑘 𝑗} .

Hence the column of ${[𝐿_{𝐴}]}_{ℬ︀ ℬ︀}$ belonging to $𝑈_{𝑖 𝑗}$ has the entries $𝑎_{1 𝑖}, \dots, 𝑎_{𝑛 𝑖}$ in the positions $(𝑗 - 1) 𝑛 + 1, \dots, 𝑗 𝑛$ , and zeros elsewhere (Definition 2.3.1). That is, ${[𝐿_{𝐴}]}_{ℬ︀ ℬ︀}$ is block diagonal with $𝑛$ diagonal blocks, each equal to $𝐴$ . By Corollary 5.4.27, $det 𝐿_{𝐴} = {(det 𝐴)}^{𝑛}$ .

$𝑅_{𝐴}$ . List the basis row by row: ${ℬ︀}^{'} =$ $𝑈_{11},$ $𝑈_{12},$ $\dots,$ $𝑈_{1 𝑛},$ $𝑈_{21},$ $\dots,$ $𝑈_{𝑛 𝑛}$ , so that $𝑈_{𝑖 𝑘}$ is number $(𝑖 - 1) 𝑛 + 𝑘$ . The $(𝑟, 𝑘)$ entry of $𝑈_{𝑖 𝑗} 𝐴$ is $\sum_{𝑙} {(𝑈_{𝑖 𝑗})}_{𝑟 𝑙} 𝑎_{𝑙 𝑘}$ , which is $𝑎_{𝑗 𝑘}$ if $𝑟 = 𝑖$ and $0$ otherwise. So

𝑅_{𝐴} (𝑈_{𝑖 𝑗}) = 𝑈_{𝑖 𝑗} 𝐴 = \sum_{𝑘 = 1}^{𝑛} 𝑎_{𝑗 𝑘} 𝑈_{𝑖 𝑘},

and the column of ${[𝑅_{𝐴}]}_{{ℬ︀}^{'} {ℬ︀}^{'}}$ belonging to $𝑈_{𝑖 𝑗}$ has the entries $𝑎_{𝑗 1}, \dots, 𝑎_{𝑗 𝑛}$ in the positions $(𝑖 - 1) 𝑛 + 1, \dots, 𝑖 𝑛$ , and zeros elsewhere. So ${[𝑅_{𝐴}]}_{{ℬ︀}^{'} {ℬ︀}^{'}}$ is block diagonal with $𝑛$ diagonal blocks, each the matrix whose column $𝑗$ is $(𝑎_{𝑗 1}, \dots, 𝑎_{𝑗 𝑛})$ , that is, $𝐴^{𝖳}$ . By Corollary 5.4.27 and Theorem 5.4.14, $det 𝑅_{𝐴} =$ ${(det 𝐴^{𝖳})}^{𝑛} =$ ${(det 𝐴)}^{𝑛}$ .

Exercise 5.4.40.standard Let

𝑇 \in L (𝐹^{𝑛 \times 𝑛})

be the transpose,

𝑇 (𝑋) = 𝑋^{𝖳}

. Show that

det 𝑇 =

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

. For which

𝑛

det 𝑇 = 1

, when

1 + 1 \neq 0

𝐹

Solution.

Uses. Definition 5.4.18 (Determinant of an operator), Definition 5.2.29 (Permutation matrix), Theorem 5.2.31 (Alternating functions and permutations), Definition 5.2.23 (Sign of a permutation), Example 5.4.19 (Two operators on matrices and polynomials)

Hint 1. Use the basis of matrices

𝑈_{𝑖 𝑗}

with a single

1

, as in Example 5.4.19. What does

𝑇

do to it?

Hint 2.

𝑇

permutes the basis, so its matrix is a permutation matrix. Count the transpositions in that permutation.

Sketch.

𝑇 (𝑈_{𝑖 𝑗}) = 𝑈_{𝑗 𝑖}

, so

𝑇

permutes the basis by the permutation

𝜋

[𝑛^{2}]

exchanging the positions of

𝑈_{𝑖 𝑗}

and

𝑈_{𝑗 𝑖}

for

𝑖 < 𝑗

. Its matrix is

𝐸_{𝜋}

, and

𝜋

is a product of

𝑛 (𝑛 - 1) / 2

disjoint transpositions, so

det 𝑇 =

sgn (𝜋) =

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

. This is

1

exactly when

𝑛 \equiv 0

1

modulo

4

Let $𝑈_{𝑖 𝑗}$ be the matrix with $1$ in position $(𝑖, 𝑗)$ and $0$ elsewhere, and list these $𝑛^{2}$ matrices in some order $𝐛_{1}, \dots, 𝐛_{𝑛^{2}}$ ; they form a basis of $𝐹^{𝑛 \times 𝑛}$ , as in Exercise 5.4.39. Since $𝑈_{𝑖 𝑗}^{𝖳} = 𝑈_{𝑗 𝑖}$ , there is a permutation $𝜋$ of $[𝑛^{2}]$ with $𝑇 (𝐛_{𝑙}) = 𝐛_{𝜋 (𝑙)}$ for every $𝑙$ : $𝜋$ exchanges the positions of $𝑈_{𝑖 𝑗}$ and $𝑈_{𝑗 𝑖}$ for $𝑖 \neq 𝑗$ and fixes the positions of the $𝑈_{𝑖 𝑖}$ . So column $𝑙$ of the matrix of $𝑇$ is $𝐞_{𝜋 (𝑙)}$ , that is, the matrix is the permutation matrix $𝐸_{𝜋}$ (Definition 5.2.29), and $det 𝑇 = sgn (𝜋)$ by Theorem 5.2.31.

The permutation $𝜋$ is the product of the transpositions exchanging the positions of $𝑈_{𝑖 𝑗}$ and $𝑈_{𝑗 𝑖}$ , one for each pair $𝑖 < 𝑗$ . There are $𝑛 (𝑛 - 1) / 2$ such pairs, so $sgn (𝜋) =$ ${(- 1)}^{𝑛 (𝑛 - 1) / 2}$ by Definition 5.2.23. Hence $det 𝑇 =$ ${(- 1)}^{𝑛 (𝑛 - 1) / 2}$ , in agreement with Example 5.4.19 for $𝑛 = 2$ .

If $1 + 1 \neq 0$ , then $- 1 \neq 1$ , and $det 𝑇 = 1$ exactly when $𝑛 (𝑛 - 1) / 2$ is even, that is, when $𝑛 (𝑛 - 1)$ is divisible by $4$ . One of $𝑛$ and $𝑛 - 1$ is odd, so this happens exactly when $𝑛$ or $𝑛 - 1$ is divisible by $4$ : $𝑛 \equiv 0$ or $1$ modulo $4$ . For instance, $det 𝑇 = - 1$ for $𝑛 = 2, 3$ and $det 𝑇 = 1$ for $𝑛 = 4, 5$ .

Exercise 5.4.41.standard Prove or disprove each statement, where $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ and $𝑛 \geq 2$ .

(a)If $det 𝐴 = det 𝐵$ and $tr 𝐴 = tr 𝐵$ , then $𝐴$ and $𝐵$ are similar.
(b)If $𝐴$ and $𝐵$ are invertible, then $det (𝐴 𝐵 𝐴^{- 1} 𝐵^{- 1}) =$ $1$ .
(c)If $𝐹 = ℝ$ , $𝑛$ is odd, and $𝐴 𝐵 = - 𝐵 𝐴$ , then $𝐴$ or $𝐵$ is not invertible.
(d)If $det 𝐴 = det 𝐵$ , then $det (𝐴 + 𝐶) =$ $det (𝐵 + 𝐶)$ for every $𝐶 \in 𝐹^{𝑛 \times 𝑛}$ .

Solution.

Uses. Theorem 5.4.10 (Multiplicativity), Exercise 5.4.12, Exercise 5.1.5, Theorem 5.4.7 (Invertibility and the determinant), Definition 4.5.23 (Similar matrices), Definition 2.4.26 (Trace)

Hint 1. (a)

𝐼_{2}

is similar only to itself. (d) Try matrices with a zero column.

Hint 2. (c) Take determinants of

𝐴 𝐵 = - 𝐵 𝐴

, and remember that

𝑛

is odd.

Sketch. (a) False:

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

and

𝐼_{2}

. (b) True:

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

1

. (c) True:

det 𝐴 det 𝐵 =

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

- det 𝐴 det 𝐵

, so

det 𝐴 det 𝐵 = 0

. (d) False:

𝐴 = 0

𝐵 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})

𝐶 = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix})

(a) False. $𝐴 = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ and $𝐵 = 𝐼_{2}$ have determinant $1$ and trace $2$ . But $𝑆^{- 1} 𝐼_{2} 𝑆 = 𝐼_{2} \neq 𝐴$ for every invertible $𝑆$ , so $𝐴$ is not similar to $𝐼_{2}$ .

(b) True. By Theorem 5.4.10 and Exercise 5.4.12,

\begin{matrix} det (𝐴 𝐵 𝐴^{- 1} 𝐵^{- 1}) \\ = det 𝐴 det 𝐵 {(det 𝐴)}^{- 1} {(det 𝐵)}^{- 1} = 1, \end{matrix}

because scalars commute.

(c) True. Taking determinants, with Exercise 5.1.5 for the factor $- 1$ ,

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

So $2 det 𝐴 det 𝐵 = 0$ , hence $det 𝐴 = 0$ or $det 𝐵 = 0$ , and the corresponding matrix is not invertible (Theorem 5.4.7). (For even $𝑛$ the statement fails: $𝐴 = (\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ are invertible, and $𝐴 𝐵 =$ $(\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix}) =$ $- 𝐵 𝐴$ .)

(d) False. Let $𝑛 = 2$ , $𝐴 = 0$ , $𝐵 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ , and $𝐶 = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix})$ . Then $det 𝐴 = det 𝐵 = 0$ , but $det (𝐴 + 𝐶) =$ $det 𝐶 =$ $0$ while $det (𝐵 + 𝐶) =$ $det 𝐼_{2} =$ $1$ .

Exercise 5.4.42.routine Let

𝐴 \in ℚ^{𝑛 \times 𝑛}

have integer entries. Show that if

𝐴

is invertible and

𝐴^{- 1}

also has integer entries, then

det 𝐴 = \pm 1

. (The converse holds as well; see Section 5.5.)

Solution.

Uses. Proposition 5.3.20 (Reduction modulo $𝑝$ ), Theorem 5.4.10 (Multiplicativity)

Hint 1. The determinant of a matrix with integer entries is an integer.

Hint 2. Which integers have an integer reciprocal?

Sketch.

det 𝐴

and

det 𝐴^{- 1}

are integers whose product is

det 𝐼_{𝑛} = 1

, so both are

\pm 1

By Proposition 5.3.20, the determinant of a matrix with integer entries is an integer, so

det 𝐴

and

det (𝐴^{- 1})

are integers. By Theorem 5.4.10, their product is

det (𝐴 𝐴^{- 1}) =

det 𝐼_{𝑛} =

1

. The only integers

𝑢

with

𝑢 𝑣 = 1

for some integer

𝑣

are

\pm 1

, since

| 𝑢 | \geq 2

would give

| 𝑢 𝑣 | \geq 2

for

𝑣 \neq 0

. Hence

det 𝐴 = \pm 1

Exercise 5.4.43.standard Let $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑚}$ . Show that

det (\begin{matrix} 𝐴 & 𝐵 \\ 𝐵 & 𝐴 \end{matrix}) = det (𝐴 + 𝐵) det (𝐴 - 𝐵) .

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. Imitate what you would do for a

2 \times 2

matrix

(\begin{matrix} 𝑎 & 𝑏 \\ 𝑏 & 𝑎 \end{matrix})

: add the second column to the first, then subtract the first row from the second.

Hint 2. With blocks, these operations are multiplications by

𝑄 = (\begin{matrix} 𝐼 & 0 \\ 𝐼 & 𝐼 \end{matrix})

on the right and

𝑃 = (\begin{matrix} 𝐼 & 0 \\ - 𝐼 & 𝐼 \end{matrix})

on the left.

Sketch. With

𝑃 = (\begin{matrix} 𝐼 & 0 \\ - 𝐼 & 𝐼 \end{matrix})

and

𝑄 = (\begin{matrix} 𝐼 & 0 \\ 𝐼 & 𝐼 \end{matrix})

, block multiplication gives

𝑃 𝑀 𝑄 =

(\begin{matrix} 𝐴 + 𝐵 & 𝐵 \\ 0 & 𝐴 - 𝐵 \end{matrix})

. Both

𝑃

and

𝑄

have determinant

1

, so

det 𝑀 =

det (𝐴 + 𝐵) det (𝐴 - 𝐵)

by Theorem 5.4.26.

Let $𝑀 = (\begin{matrix} 𝐴 & 𝐵 \\ 𝐵 & 𝐴 \end{matrix})$ , $𝑃 =$ $(\begin{matrix} 𝐼_{𝑚} & 0 \\ - 𝐼_{𝑚} & 𝐼_{𝑚} \end{matrix})$ , and $𝑄 =$ $(\begin{matrix} 𝐼_{𝑚} & 0 \\ 𝐼_{𝑚} & 𝐼_{𝑚} \end{matrix})$ . By Theorem 2.4.34,

𝑀 𝑄 = (\begin{matrix} 𝐴 + 𝐵 & 𝐵 \\ 𝐵 + 𝐴 & 𝐴 \end{matrix}),

\begin{aligned} 𝑃 𝑀 𝑄 & = (\begin{matrix} 𝐴 + 𝐵 & 𝐵 \\ - (𝐴 + 𝐵) + (𝐵 + 𝐴) & - 𝐵 + 𝐴 \end{matrix}) \\ = (\begin{matrix} 𝐴 + 𝐵 & 𝐵 \\ 0 & 𝐴 - 𝐵 \end{matrix}) . \end{aligned}

$𝑃$ and $𝑄$ are block lower triangular with diagonal blocks $𝐼_{𝑚}$ , so $det 𝑃 = det 𝑄 = 1$ by Theorem 5.4.26. By Theorem 5.4.10 and Theorem 5.4.26,

\begin{matrix} det 𝑀 = det 𝑃 det 𝑀 det 𝑄 = det (𝑃 𝑀 𝑄) \\ = det (𝐴 + 𝐵) det (𝐴 - 𝐵) . \end{matrix}

Exercise 5.4.44.standard Let

𝐶 (𝑧) = (\begin{matrix} 1 & 𝑧 & 𝑧^{2} \\ 𝑧^{2} & 1 & 𝑧 \\ 𝑧 & 𝑧^{2} & 1 \end{matrix}) .

(a)Show that $det 𝐶 (𝑧) =$ ${(1 - 𝑧^{3})}^{2}$ , for $𝑧$ in any field.
(b)Find all $𝑧$ for which $𝐶 (𝑧)$ is not invertible, for $𝑧 \in ℂ$ , for $𝑧 \in ℝ$ , and for $𝑧 \in 𝔽_{7}$ .

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)

Hint 1. Every row sums to

𝑠 = 1 + 𝑧 + 𝑧^{2}

. Add the second and third columns to the first, and pull out

𝑠

Hint 2. Then subtract row

1

from rows

2

and

3

, and look for the factor

1 - 𝑧

in the new rows. Recall

(1 - 𝑧) 𝑠 = 1 - 𝑧^{3}

Sketch. Adding columns

2

and

3

to column

1

and pulling out

𝑠 = 1 + 𝑧 + 𝑧^{2}

leaves first column

(1, 1, 1)

. Subtracting row

1

from rows

2

3

gives rows

(1 - 𝑧) (0, 1, 𝑧)

and

(1 - 𝑧) (0, - 𝑧, 1 + 𝑧)

. So

det 𝐶 (𝑧) =

𝑠 {(1 - 𝑧)}^{2} (1 + 𝑧 + 𝑧^{2}) =

{(1 - 𝑧^{3})}^{2}

. Non-invertible exactly when

𝑧^{3} = 1

𝑧 = 1, 𝜔, 𝜔^{2}

ℂ

;

𝑧 = 1

ℝ

;

𝑧 \in {1, 2, 4}

𝔽_{7}

(a) Let $𝑠 = 1 + 𝑧 + 𝑧^{2}$ . Adding columns $2$ and $3$ to column $1$ does not change the determinant (Lemma 5.1.8), and makes every entry of column $1$ equal to $𝑠$ . Pulling out $𝑠$ , and then subtracting row $1$ from rows $2$ and $3$ (Corollary 5.4.15),

\begin{aligned} det 𝐶 (𝑧) & = 𝑠 det (\begin{matrix} 1 & 𝑧 & 𝑧^{2} \\ 1 & 1 & 𝑧 \\ 1 & 𝑧^{2} & 1 \end{matrix}) \\ = 𝑠 det (\begin{matrix} 1 & 𝑧 & 𝑧^{2} \\ 0 & 1 - 𝑧 & 𝑧 - 𝑧^{2} \\ 0 & 𝑧^{2} - 𝑧 & 1 - 𝑧^{2} \end{matrix}) . \end{aligned}

Row $2$ of the last matrix is $(1 - 𝑧) (0, 1, 𝑧)$ , and row $3$ is $(1 - 𝑧) (0, - 𝑧, 1 + 𝑧)$ . Pulling out both factors $1 - 𝑧$ and using Theorem 5.4.26 with a $1 \times 1$ upper left block,

\begin{aligned} det 𝐶 (𝑧) & = 𝑠 {(1 - 𝑧)}^{2} det (\begin{matrix} 1 & 𝑧 \\ - 𝑧 & 1 + 𝑧 \end{matrix}) \\ = 𝑠 {(1 - 𝑧)}^{2} (1 + 𝑧 + 𝑧^{2}) = {((1 - 𝑧) 𝑠)}^{2} = {(1 - 𝑧^{3})}^{2}, \end{aligned}

since $(1 - 𝑧) (1 + 𝑧 + 𝑧^{2}) =$ $1 -$ $𝑧^{3}$ . Every step is valid over any field.

(b) By Theorem 5.4.7, $𝐶 (𝑧)$ fails to be invertible exactly when ${(1 - 𝑧^{3})}^{2} = 0$ , that is, when $𝑧^{3} = 1$ . Over $ℂ$ the solutions are the cube roots of unity $1$ , $𝜔 = (- 1 + 𝑖 \sqrt{3}) / 2$ , and $𝜔^{2} = 𝜔$ . Over $ℝ$ , only $𝑧 = 1$ . Over $𝔽_{7}$ , cubing the nonzero elements gives $1^{3} = 1$ , $2^{3} = 8 = 1$ , $3^{3} = 27 = 6$ , $4^{3} = 64 = 1$ , $5^{3} = 125 = 6$ , and $6^{3} = 216 = 6$ , so $𝑧 \in {1, 2, 4}$ .

Exercise 5.4.45.hard Let $𝐵, 𝐶 \in ℝ^{𝑛 \times 𝑛}$ , and let $𝐴 = 𝐵 + 𝑖 𝐶 \in ℂ^{𝑛 \times 𝑛}$ . Show that

det (\begin{matrix} 𝐵 & - 𝐶 \\ 𝐶 & 𝐵 \end{matrix}) = {| det 𝐴 |}^{2} .

In particular, the real $2 𝑛 \times 2 𝑛$ matrix on the left has a nonnegative determinant. (For $𝑛 = 1$ and $𝐴 = (𝑎 + 𝑏 𝑖)$ , the matrix $(\begin{matrix} 𝑎 & - 𝑏 \\ 𝑏 & 𝑎 \end{matrix})$ is the matrix of multiplication by $𝑎 + 𝑏 𝑖$ on $ℂ$ , regarded as a real vector space with basis $1, 𝑖$ .)

Solution.

Uses. Theorem 2.4.34 (Block multiplication), Proposition 5.4.17 (Similar matrices have equal determinants), Theorem 5.4.26 (Block-triangular matrices), Exercise 5.3.28, Definition 5.3.6 (Determinant)

Hint 1. Regard

𝑀 = (\begin{matrix} 𝐵 & - 𝐶 \\ 𝐶 & 𝐵 \end{matrix})

as a complex matrix. Its determinant is the same whether computed over

ℝ

or over

ℂ

Hint 2. Conjugate by

𝑃 = (\begin{matrix} 𝐼 & 0 \\ 𝑖 𝐼 & 𝐼 \end{matrix})

, whose inverse is

(\begin{matrix} 𝐼 & 0 \\ - 𝑖 𝐼 & 𝐼 \end{matrix})

, and simplify

𝑃^{- 1} 𝑀 𝑃

with block multiplication.

Hint 3.

𝐵 - 𝑖 𝐶

is the entrywise complex conjugate of

𝐴

. Use Exercise 5.3.28.

Sketch. Over

ℂ

𝑃^{- 1} 𝑀 𝑃 =

(\begin{matrix} 𝐵 - 𝑖 𝐶 & - 𝐶 \\ 0 & 𝐵 + 𝑖 𝐶 \end{matrix})

with

𝑃 = (\begin{matrix} 𝐼 & 0 \\ 𝑖 𝐼 & 𝐼 \end{matrix})

. So

det 𝑀 =

det (𝐵 - 𝑖 𝐶) det (𝐵 + 𝑖 𝐶) =

det 𝐴 det 𝐴 =

{| det 𝐴 |}^{2}

Let $𝑀 = (\begin{matrix} 𝐵 & - 𝐶 \\ 𝐶 & 𝐵 \end{matrix})$ . Its determinant is given by the Leibniz formula (Definition 5.3.6), which involves only sums and products of the (real) entries, so it is the same whether we regard $𝑀$ as a real or a complex matrix. We work over $ℂ$ . Let $𝑃 =$ $(\begin{matrix} 𝐼_{𝑛} & 0 \\ 𝑖 𝐼_{𝑛} & 𝐼_{𝑛} \end{matrix})$ and $𝑃^{'} =$ $(\begin{matrix} 𝐼_{𝑛} & 0 \\ - 𝑖 𝐼_{𝑛} & 𝐼_{𝑛} \end{matrix})$ . By Theorem 2.4.34, $𝑃 𝑃^{'} = 𝑃^{'} 𝑃 = 𝐼_{2 𝑛}$ , so $𝑃^{'} = 𝑃^{- 1}$ , and

𝑀 𝑃 = (\begin{matrix} 𝐵 - 𝑖 𝐶 & - 𝐶 \\ 𝐶 + 𝑖 𝐵 & 𝐵 \end{matrix}),

\begin{aligned} 𝑃^{- 1} 𝑀 𝑃 & = (\begin{matrix} 𝐵 - 𝑖 𝐶 & - 𝐶 \\ - 𝑖 (𝐵 - 𝑖 𝐶) + 𝐶 + 𝑖 𝐵 & 𝑖 𝐶 + 𝐵 \end{matrix}) \\ = (\begin{matrix} 𝐵 - 𝑖 𝐶 & - 𝐶 \\ 0 & 𝐵 + 𝑖 𝐶 \end{matrix}), \end{aligned}

using $- 𝑖 (- 𝑖 𝐶) =$ $𝑖^{2} 𝐶 =$ $- 𝐶$ . By Proposition 5.4.17 and Theorem 5.4.26,

\begin{matrix} det 𝑀 = det (𝑃^{- 1} 𝑀 𝑃) \\ = det (𝐵 - 𝑖 𝐶) det (𝐵 + 𝑖 𝐶) . \end{matrix}

Since $𝐵$ and $𝐶$ are real, $𝐵 - 𝑖 𝐶 = 𝐴$ , the entrywise complex conjugate of $𝐴$ , and $det 𝐴 = det 𝐴$ by Exercise 5.3.28. Hence $det 𝑀 =$ $det 𝐴 det 𝐴 =$ ${| det 𝐴 |}^{2} \geq$ $0$ .

Exercise 5.4.46.hard Let

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

with

𝐴 𝐵 = 𝐵 𝐴

. Show that

det (𝐴^{2} + 𝐵^{2}) \geq 0

. Show by an example that the hypothesis

𝐴 𝐵 = 𝐵 𝐴

cannot be dropped.

Solution.

Uses. Theorem 5.4.10 (Multiplicativity), Exercise 5.3.28

Hint 1. Over

ℂ

, the scalar

𝑎^{2} + 𝑏^{2}

factors as

(𝑎 + 𝑖 𝑏) (𝑎 - 𝑖 𝑏)

. Does the same factorization work for commuting matrices?

Hint 2.

det (𝐴 - 𝑖 𝐵)

is the complex conjugate of

det (𝐴 + 𝑖 𝐵)

, by Exercise 5.3.28.

Hint 3. For the example, take

𝑛 = 2

and look for

𝐴

and

𝐵

with small entries such that

𝐴^{2} + 𝐵^{2}

has determinant

- 1

Sketch.

(𝐴 + 𝑖 𝐵) (𝐴 - 𝑖 𝐵) =

𝐴^{2} -

𝑖 𝐴 𝐵 +

𝑖 𝐵 𝐴 +

𝐵^{2} =

𝐴^{2} +

𝐵^{2}

when

𝐴 𝐵 = 𝐵 𝐴

. So

det (𝐴^{2} + 𝐵^{2}) =

𝑧 𝑧 =

{| 𝑧 |}^{2} \geq

0

with

𝑧 = det (𝐴 + 𝑖 𝐵)

. Without commuting:

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

𝐵 = (\begin{matrix} 1 & 1 \\ - 1 & 0 \end{matrix})

give

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

, with determinant

- 1

Regard $𝐴$ and $𝐵$ as complex matrices; this does not change $det (𝐴^{2} + 𝐵^{2})$ , which is computed from the entries by the Leibniz formula. Since $𝐴 𝐵 = 𝐵 𝐴$ ,

\begin{matrix} (𝐴 + 𝑖 𝐵) (𝐴 - 𝑖 𝐵) = 𝐴^{2} - 𝑖 𝐴 𝐵 + 𝑖 𝐵 𝐴 - 𝑖^{2} 𝐵^{2} \\ = 𝐴^{2} + 𝐵^{2} . \end{matrix}

Let $𝑧 = det (𝐴 + 𝑖 𝐵)$ . Since $𝐴$ and $𝐵$ are real, $𝐴 - 𝑖 𝐵$ is the entrywise conjugate of $𝐴 + 𝑖 𝐵$ , so $det (𝐴 - 𝑖 𝐵) = 𝑧$ by Exercise 5.3.28. By Theorem 5.4.10,

det (𝐴^{2} + 𝐵^{2}) = 𝑧 𝑧 = {| 𝑧 |}^{2} \geq 0 .

Without the hypothesis, let $𝐴 = (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})$ and $𝐵 = (\begin{matrix} 1 & 1 \\ - 1 & 0 \end{matrix})$ . Then $𝐴^{2} = (\begin{matrix} 2 & 2 \\ 2 & 2 \end{matrix})$ and $𝐵^{2} = (\begin{matrix} 0 & 1 \\ - 1 & - 1 \end{matrix})$ , so $𝐴^{2} + 𝐵^{2} = (\begin{matrix} 2 & 3 \\ 1 & 1 \end{matrix})$ , whose determinant is $2 - 3 = - 1 < 0$ . Indeed $𝐴 𝐵 = (\begin{matrix} 0 & 1 \\ 0 & 1 \end{matrix})$ and $𝐵 𝐴 = (\begin{matrix} 2 & 2 \\ - 1 & - 1 \end{matrix})$ are different.

Exercise 5.4.47.hard Let $𝑝$ be a prime, let $𝐺$ be the set of invertible matrices in $𝔽_{𝑝}^{𝑛 \times 𝑛}$ , and let $𝐻 =$ ${𝐴 \in 𝐺 | det 𝐴 = 1}$ .

(a)For $𝑐 \in 𝔽_{𝑝}$ with $𝑐 \neq 0$ , show that $𝑋 \mapsto 𝑋 𝐸_{1 𝑐}$ is a bijection from $𝐻$ onto ${𝐴 \in 𝐺 | det 𝐴 = 𝑐}$ . Deduce that $| 𝐻 | = | 𝐺 | / (𝑝 - 1)$ .
(b)For $𝑛 = 2$ , show that $| 𝐺 | =$ $(𝑝^{2} - 1) (𝑝^{2} - 𝑝)$ , and conclude that $| 𝐻 | = 𝑝 (𝑝^{2} - 1)$ .
(c)Check (b) for $𝑝 = 2$ by listing $𝐻$ .

Solution.

Uses. Lemma 5.4.2 (Multiplying by an elementary matrix), Proposition 5.4.1 (Determinants of elementary matrices), Theorem 5.4.7 (Invertibility and the determinant), Corollary 5.4.8 (Vanishing determinants), Proposition 1.2.35 (Zero products)

Hint 1. (a) Compute

det (𝑋 𝐸_{1 𝑐})

, and write down the inverse map. Which values can the determinant of an invertible matrix take?

Hint 2. (b) A

2 \times 2

matrix is invertible exactly when its columns are independent. Count the choices of the first column, then of the second.

Sketch. (a)

det (𝑋 𝐸_{1 𝑐}) =

𝑐 det 𝑋

, and

𝑌 \mapsto 𝑌 𝐸_{1, 𝑐^{- 1}}

is the inverse map.

𝐺

is the disjoint union of the

𝑝 - 1

sets

{det = 𝑐}

𝑐 \neq 0

, each in bijection with

𝐻

. (b) The first column is any of the

𝑝^{2} - 1

nonzero vectors, and the second any of the

𝑝^{2} - 𝑝

vectors that are not multiples of the first. (c) For

𝑝 = 2

𝐻 = 𝐺

has the

6

matrices

𝐼_{2}

𝐸_{12}

, and the four with exactly three entries

1

(a) For $𝑋 \in 𝐻$ , $det (𝑋 𝐸_{1 𝑐}) =$ $det 𝑋 det 𝐸_{1 𝑐} =$ $𝑐$ by Lemma 5.4.2 and Proposition 5.4.1, and $𝑋 𝐸_{1 𝑐}$ is invertible. So the map sends $𝐻$ into $𝐻_{𝑐} =$ ${𝐴 \in 𝐺 | det 𝐴 = 𝑐}$ . Similarly $𝑌 \mapsto 𝑌 𝐸_{1, 𝑐^{- 1}}$ sends $𝐻_{𝑐}$ into $𝐻$ , and the two maps are inverse to each other, since $𝐸_{1 𝑐} 𝐸_{1, 𝑐^{- 1}} =$ $𝐸_{1, 𝑐^{- 1}} 𝐸_{1 𝑐} =$ $𝐼_{𝑛}$ . So $| 𝐻_{𝑐} | = | 𝐻 |$ . By Theorem 5.4.7, every $𝐴 \in 𝐺$ has $det 𝐴 \neq 0$ , so $𝐺$ is the disjoint union of the $𝑝 - 1$ sets $𝐻_{𝑐}$ with $𝑐 \neq 0$ . Hence $| 𝐺 | = (𝑝 - 1) | 𝐻 |$ .

(b) By Corollary 5.4.8, $𝐴 \in 𝔽_{𝑝}^{2 \times 2}$ is invertible exactly when its columns $𝐚_{1}, 𝐚_{2}$ are linearly independent. This holds exactly when $𝐚_{1} \neq 𝟎$ and $𝐚_{2}$ is not a multiple of $𝐚_{1}$ . Indeed, if $𝑥 𝐚_{1} + 𝑦 𝐚_{2} = 𝟎$ with $(𝑥, 𝑦) \neq (0, 0)$ , then either $𝑦 \neq 0$ and $𝐚_{2} = - 𝑦^{- 1} 𝑥 𝐚_{1}$ , or $𝑦 = 0$ , $𝑥 \neq 0$ , and $𝐚_{1} = 𝟎$ ; conversely, $𝐚_{1} = 𝟎$ or $𝐚_{2} = 𝑡 𝐚_{1}$ gives a nontrivial relation. There are $𝑝^{2} - 1$ nonzero vectors in $𝔽_{𝑝}^{2}$ . For each of them, the multiples $𝑡 𝐚_{1}$ with $𝑡 \in 𝔽_{𝑝}$ are $𝑝$ distinct vectors, since $𝑡 𝐚_{1} = 𝑡^{'} 𝐚_{1}$ forces $𝑡 = 𝑡^{'}$ (Proposition 1.2.35), so there are $𝑝^{2} - 𝑝$ choices of $𝐚_{2}$ . Hence $| 𝐺 | =$ $(𝑝^{2} - 1) (𝑝^{2} - 𝑝)$ , and by (a),

| 𝐻 | = \frac{(𝑝^{2} - 1) (𝑝^{2} - 𝑝)}{𝑝 - 1} = 𝑝 (𝑝^{2} - 1) .

(c) For $𝑝 = 2$ the formula gives $2 \cdot 3 = 6$ . Over $𝔽_{2}$ the only nonzero scalar is $1$ , so $𝐻 = 𝐺$ . The invertible $2 \times 2$ matrices over $𝔽_{2}$ are those with $𝑎 𝑑 -$ $𝑏 𝑐 =$ $𝑎 𝑑 +$ $𝑏 𝑐 =$ $1$ , that is, with exactly one of the products $𝑎 𝑑$ and $𝑏 𝑐$ equal to $1$ :

\begin{matrix} (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}), (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}), \\ (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}), (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}), (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) . \end{matrix}

Exercise 5.4.48.hard Let $𝑛 \geq 2$ .

(a)Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ be invertible. Show that there are elementary matrices $𝐸_{1}, \dots, 𝐸_{𝑡}$ of type 3 (replacements) with $𝐸_{𝑡} \dots 𝐸_{1} 𝐴 =$ $diag (1, \dots, 1, det 𝐴)$ .
(b)Deduce that every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ with $det 𝐴 = 1$ is a product of elementary matrices of type 3, and that every invertible $𝐴$ is such a product times the single scaling $𝐸_{𝑛, det 𝐴}$ .

Solution.

Uses. Exercise 3.2.53, Proposition 3.2.7 (Row operations are left multiplications), Proposition 5.4.1 (Determinants of elementary matrices), Theorem 5.4.10 (Multiplicativity), Proposition 5.1.17 (Dependent columns), Proposition 5.3.15 (Triangular matrices), Proposition 3.2.10 (Inverses of elementary matrices)

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. Imitate Exercise 3.2.53, column by column: for

𝑘 = 1, \dots, 𝑛 - 1

, use replacements to make column

𝑘

equal to

𝐞_{𝑘}

without disturbing columns

1, \dots, 𝑘 - 1

Hint 2. To make the

(𝑘, 𝑘)

entry equal to

1

, you need a nonzero entry in column

𝑘

below row

𝑘

. If there is none, first add row

𝑘

to row

𝑘 + 1

. Why is the

(𝑘, 𝑘)

entry then nonzero?

Hint 3. Replacements do not change the determinant. After column

𝑛 - 1

, read off the last diagonal entry, and clear the last column above it.

Sketch. Keep the invariant that columns

1, \dots, 𝑘 - 1

are

𝐞_{1}, \dots, 𝐞_{𝑘 - 1}

; then rows

𝑘, \dots, 𝑛

vanish in those columns, so adding them to other rows does not break the invariant. Column

𝑘

has a nonzero entry in rows

𝑘, \dots, 𝑛

(else the columns are dependent); arrange one in a row

𝑗 > 𝑘

, add

(1 - 𝑚_{𝑘 𝑘}) / 𝑚_{𝑗 𝑘}

times row

𝑗

to row

𝑘

to get a

1

, and clear the rest of column

𝑘

. At the end the matrix is upper triangular with diagonal

1, \dots, 1, 𝑑

, where

𝑑 = det 𝐴

because replacements preserve

det

; clearing column

𝑛

above

𝑑

gives

diag (1, \dots, 1, 𝑑)

. Then

𝐴 =

𝐸_{1}^{- 1} \dots 𝐸_{𝑡}^{- 1} 𝐸_{𝑛, 𝑑}

(a) Every matrix below is obtained from $𝐴$ by replacements, so it is invertible with determinant $det 𝐴$ (Proposition 3.2.7, Proposition 5.4.1, Theorem 5.4.10). We process $𝑘 = 1, \dots, 𝑛 - 1$ in turn, keeping the following invariant: before step $𝑘$ , columns $1, \dots, 𝑘 - 1$ of the current matrix $𝑀$ are $𝐞_{1}, \dots, 𝐞_{𝑘 - 1}$ . Then for $𝑙 < 𝑘$ , every row other than row $𝑙$ has entry $0$ in column $𝑙$ . In particular rows $𝑘, \dots, 𝑛$ vanish in columns $1, \dots, 𝑘 - 1$ , so adding a multiple of one of these rows to another row does not change columns $1, \dots, 𝑘 - 1$ . All replacements in step $𝑘$ add multiples of rows numbered at least $𝑘$ .

Step $𝑘$ . Column $𝑘$ of $𝑀$ has a nonzero entry in one of the rows $𝑘, \dots, 𝑛$ : otherwise column $𝑘$ would be a combination of $𝐞_{1}, \dots, 𝐞_{𝑘 - 1}$ , that is, of columns $1, \dots, 𝑘 - 1$ , and $det 𝑀 = 0$ by Proposition 5.1.17. If $𝑚_{𝑗 𝑘} = 0$ for every $𝑗 > 𝑘$ , then $𝑚_{𝑘 𝑘} \neq 0$ , and we add row $𝑘$ to row $𝑘 + 1$ (possible as $𝑘 + 1 \leq 𝑛$ ); now $𝑚_{𝑘 + 1, 𝑘} =$ $𝑚_{𝑘 𝑘} \neq$ $0$ . So we may choose $𝑗 > 𝑘$ with $𝑐 = 𝑚_{𝑗 𝑘} \neq 0$ . Adding $(1 - 𝑚_{𝑘 𝑘}) 𝑐^{- 1}$ times row $𝑗$ to row $𝑘$ changes the $(𝑘, 𝑘)$ entry to $𝑚_{𝑘 𝑘} +$ $(1 - 𝑚_{𝑘 𝑘}) =$ $1$ . Finally, for each $𝑖 \neq 𝑘$ , add $- 𝑚_{𝑖 𝑘}$ times row $𝑘$ to row $𝑖$ ; this makes column $𝑘$ equal to $𝐞_{𝑘}$ . The invariant now holds before step $𝑘 + 1$ .

After step $𝑛 - 1$ , columns $1, \dots, 𝑛 - 1$ are $𝐞_{1}, \dots, 𝐞_{𝑛 - 1}$ , so the matrix is upper triangular with diagonal entries $1, \dots, 1, 𝑚_{𝑛 𝑛}$ , and $𝑚_{𝑛 𝑛} = det 𝐴$ by Proposition 5.3.15. In particular $𝑚_{𝑛 𝑛} \neq 0$ . Row $𝑛$ is $(0, \dots, 0, 𝑚_{𝑛 𝑛})$ , so adding $- 𝑚_{𝑖 𝑛} 𝑚_{𝑛 𝑛}^{- 1}$ times row $𝑛$ to row $𝑖$ , for each $𝑖 < 𝑛$ , clears column $𝑛$ above the diagonal and changes nothing else. The result is $diag (1, \dots, 1, det 𝐴)$ , reached by replacements $𝐸_{1}, \dots, 𝐸_{𝑡}$ .

(b) By (a), $𝐴 =$ $𝐸_{1}^{- 1} \dots 𝐸_{𝑡}^{- 1} diag (1, \dots, 1, det 𝐴)$ , and each $𝐸_{𝑙}^{- 1}$ is a replacement by Proposition 3.2.10. If $det 𝐴 = 1$ , the last factor is $𝐼_{𝑛}$ , and $𝐴$ is a product of replacements. In general the last factor is the scaling $𝐸_{𝑛, det 𝐴}$ .

Exercise 5.4.49.challenge Let

𝑛 \geq 2

, and let

𝑓 : 𝐹^{𝑛 \times 𝑛} \to 𝐹

satisfy

𝑓 (𝐴 𝐵) =

𝑓 (𝐴) 𝑓 (𝐵)

for all

𝐴, 𝐵

, and

𝑓 (diag (𝑡, 1, \dots, 1)) =

𝑡

for all

𝑡 \in 𝐹

. Show that

𝑓 = det

. (This extends Exercise 5.1.42 to all

𝑛

and all fields.)

Solution.

Uses. Exercise 5.4.48, Proposition 5.2.30 (Algebra of permutation matrices), Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Theorem 3.3.23 (Invertibility and RREF), Proposition 3.3.8 (Properties of the output), Theorem 5.4.7 (Invertibility and the determinant)

Techniques. Reduce to elementary matrices (Technique 5.4.6)

Hint 1. First show

𝑓 (𝐼_{𝑛}) = 1

, that

𝑓 (𝐺) \neq 0

for invertible

𝐺

, and that

𝑓 (𝐺 𝑋 𝐺^{- 1}) =

𝑓 (𝑋)

Hint 2. Show that all replacements are conjugate to

𝐸_{1, 1, 2}

, using a scaling and a permutation matrix. Then compare

𝐸_{1, 1, 2}^{2}

with

𝐸_{1, 2, 2}

; treat

1 + 1 = 0

separately.

Hint 3. For invertible

𝐴

, use Exercise 5.4.48. For

𝐴

not invertible, write

𝐴 = 𝐺^{- 1} rref (𝐴)

, and note that

rref (𝐴)

is unchanged by left multiplication with

diag (1, \dots, 1, 0)

Sketch.

𝑓

is invariant under conjugation by invertible matrices. Conjugating

𝐸_{𝑖, 1, 𝑗}

𝐸_{𝑗 𝑐}

gives

𝐸_{𝑖 𝑐 𝑗}

, and conjugating by a permutation matrix moves it to

𝐸_{1, 1, 2}

; so all replacements have the same value

𝑠 \neq 0

. From

𝐸_{1, 1, 2}^{2} = 𝐸_{1, 2, 2}

we get

𝑠^{2} = 𝑠

(or

𝑠^{2} = 1

1 + 1 = 0

), so

𝑠 = 1

. Conjugating

diag (𝑡, 1, \dots, 1)

𝐸_{1 𝑛}

gives

𝑓 (diag (1, \dots, 1, 𝑡)) =

𝑡

, so

𝑓 (𝐴) = det 𝐴

for invertible

𝐴

by Exercise 5.4.48. If

𝐴

is not invertible,

rref (𝐴) =

𝑍 rref (𝐴)

with

𝑍 = diag (1, \dots, 1, 0)

and

𝑓 (𝑍) = 0

Throughout, let $𝑈_{𝑗 𝑖}$ be the matrix with $1$ in position $(𝑗, 𝑖)$ and $0$ elsewhere, so that $𝐸_{𝑖 𝑐 𝑗} =$ $𝐼_{𝑛} +$ $𝑐 𝑈_{𝑗 𝑖}$ for $𝑖 \neq 𝑗$ .

Step 0. $𝑓 (𝐼_{𝑛}) =$ $𝑓 (diag (1, \dots, 1)) =$ $1$ . If $𝐺$ is invertible, then $𝑓 (𝐺) 𝑓 (𝐺^{- 1}) =$ $𝑓 (𝐼_{𝑛}) =$ $1$ , so $𝑓 (𝐺) \neq 0$ and $𝑓 (𝐺^{- 1}) = {𝑓 (𝐺)}^{- 1}$ . Hence $𝑓 (𝐺 𝑋 𝐺^{- 1}) =$ $𝑓 (𝐺) 𝑓 (𝑋) {𝑓 (𝐺)}^{- 1} =$ $𝑓 (𝑋)$ for every $𝑋$ , because values of $𝑓$ commute.

Step 1: replacements. Let $𝑖 \neq 𝑗$ and $𝑐 \neq 0$ , and let $𝐷 = 𝐸_{𝑗 𝑐}$ , so $𝐷^{- 1} = 𝐸_{𝑗, 𝑐^{- 1}}$ . Multiplying $𝑈_{𝑗 𝑖}$ on the left by $𝐷$ scales its row $𝑗$ by $𝑐$ . Multiplying on the right by $𝐷^{- 1}$ scales its column $𝑗$ by $𝑐^{- 1}$ , and that column is zero since $𝑖 \neq 𝑗$ . So $𝐷 𝑈_{𝑗 𝑖} 𝐷^{- 1} =$ $𝑐 𝑈_{𝑗 𝑖}$ , hence $𝐷 𝐸_{𝑖, 1, 𝑗} 𝐷^{- 1} =$ $𝐸_{𝑖 𝑐 𝑗}$ , and $𝑓 (𝐸_{𝑖 𝑐 𝑗}) =$ $𝑓 (𝐸_{𝑖, 1, 𝑗})$ by Step 0. Next choose $𝜎 \in 𝑆_{𝑛}$ with $𝜎 (𝑖) = 1$ and $𝜎 (𝑗) = 2$ , possible as $𝑖 \neq 𝑗$ and $𝑛 \geq 2$ . By Proposition 5.2.30, $𝐸_{𝜎}^{- 1} = 𝐸_{𝜎^{- 1}}$ , and $𝑋 𝐸_{𝜎^{- 1}}$ has column $𝑙$ equal to column $𝜎^{- 1} (𝑙)$ of $𝑋$ . So $𝑈_{𝑗 𝑖} 𝐸_{𝜎^{- 1}}$ has its only nonzero column in position $𝜎 (𝑖)$ , equal to $𝐞_{𝑗}$ ; multiplying by $𝐸_{𝜎}$ on the left turns this column into $𝐸_{𝜎} 𝐞_{𝑗} = 𝐞_{𝜎 (𝑗)}$ . Hence $𝐸_{𝜎} 𝑈_{𝑗 𝑖} 𝐸_{𝜎}^{- 1} =$ $𝑈_{𝜎 (𝑗) 𝜎 (𝑖)} =$ $𝑈_{21}$ , and $𝐸_{𝜎} 𝐸_{𝑖, 1, 𝑗} 𝐸_{𝜎}^{- 1} =$ $𝐼_{𝑛} +$ $𝑈_{21} =$ $𝐸_{1, 1, 2}$ . So every replacement $𝐸_{𝑖 𝑐 𝑗}$ with $𝑐 \neq 0$ has the value $𝑠 = 𝑓 (𝐸_{1, 1, 2})$ , and $𝑠 \neq 0$ by Step 0. (A replacement with $𝑐 = 0$ is $𝐼_{𝑛}$ , with $𝑓 (𝐼_{𝑛}) = 1$ .)

Since $𝑈_{21}^{2} = 0$ , we have $𝐸_{1, 1, 2}^{2} =$ $𝐼_{𝑛} +$ $2 𝑈_{21}$ , where $2 = 1 + 1$ . If $1 + 1 \neq 0$ , this is the replacement $𝐸_{1, 2, 2}$ , so $𝑠^{2} = 𝑠$ , and $𝑠 = 1$ because $𝑠 \neq 0$ . If $1 + 1 = 0$ , then $𝐸_{1, 1, 2}^{2} = 𝐼_{𝑛}$ , so $𝑠^{2} = 1$ , and ${(𝑠 - 1)}^{2} =$ $𝑠^{2} -$ $(1 + 1) 𝑠 +$ $1 =$ $𝑠^{2} +$ $1 =$ $1 +$ $1 =$ $0$ , so again $𝑠 = 1$ . Thus $𝑓 (𝐸) = 1 = det 𝐸$ for every replacement $𝐸$ .

Step 2: invertible matrices. $𝐸_{1 𝑛}$ is its own inverse, and $𝐸_{1 𝑛} diag (𝑡, 1, \dots, 1) 𝐸_{1 𝑛} =$ $diag (1, \dots, 1, 𝑡) =$ $𝐸_{𝑛, 𝑡}$ , as conjugating by $𝐸_{1 𝑛}$ swaps rows $1$ and $𝑛$ and then columns $1$ and $𝑛$ . So $𝑓 (diag (1, \dots, 1, 𝑡)) =$ $𝑡$ for every $𝑡 \in 𝐹$ , by Step 0; for $𝑡 \neq 0$ this matrix is the scaling $𝐸_{𝑛 𝑡}$ . If $𝐴$ is invertible, then by Exercise 5.4.48(b), $𝐴 =$ $𝑅_{1} \dots 𝑅_{𝑞} 𝐸_{𝑛, det 𝐴}$ with replacements $𝑅_{𝑙}$ , and

𝑓 (𝐴) = 𝑓 (𝑅_{1}) \dots 𝑓 (𝑅_{𝑞}) 𝑓 (𝐸_{𝑛, det 𝐴}) = det 𝐴 .

Step 3: matrices that are not invertible. Let $𝐴$ be not invertible, so $det 𝐴 = 0$ (Theorem 5.4.7). By Theorem 3.3.10, $𝐴 = 𝐺^{- 1} 𝑅$ with $𝐺$ invertible and $𝑅 = rref (𝐴)$ , and $𝑅 \neq 𝐼_{𝑛}$ by Theorem 3.3.23. So $𝑅$ has fewer than $𝑛$ pivots, and its last row is zero by Proposition 3.3.8. Let $𝑍 = diag (1, \dots, 1, 0)$ . Multiplying by $𝑍$ on the left replaces the last row by zeros, so $𝑍 𝑅 = 𝑅$ . By the computation in Step 2 with $𝑡 = 0$ , $𝑓 (𝑍) = 0$ . Hence $𝑓 (𝑅) =$ $𝑓 (𝑍) 𝑓 (𝑅) =$ $0$ , and $𝑓 (𝐴) =$ $𝑓 (𝐺^{- 1}) 𝑓 (𝑅) =$ $0 =$ $det 𝐴$ .

So $𝑓 (𝐴) = det 𝐴$ for every $𝐴$ .

Exercise 5.4.50.hardBeyond 21-242 Let $𝐴,$ $𝐵,$ $𝐶,$ $𝐷 \in$ $𝐹^{𝑚 \times 𝑚}$ with $𝐴$ invertible and $𝐴 𝐶 = 𝐶 𝐴$ . Show that

det (\begin{matrix} 𝐴 & 𝐵 \\ 𝐶 & 𝐷 \end{matrix}) = det (𝐴 𝐷 - 𝐶 𝐵) .

Then show by an example with $𝑚 = 2$ that the formula can fail when $𝐴$ is invertible but $𝐴 𝐶 \neq 𝐶 𝐴$ .

Solution.

Uses. Proposition 5.4.29 (Schur complement), Theorem 5.4.10 (Multiplicativity)

Techniques. Block elimination (Technique 5.4.28)

Hint 1. Start from Proposition 5.4.29, and combine the two determinants on the right into one.

Hint 2.

𝐴 𝐶 𝐴^{- 1} = 𝐶

when

𝐴

and

𝐶

commute. For the example, a zero row in

𝑀

is an easy way to make

det 𝑀 = 0

Sketch.

det 𝑀 =

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

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

det (𝐴 𝐷 - 𝐶 𝐵)

. Example:

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

𝐵 = 𝐶 = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix})

𝐷 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})

; then

𝑀

has a zero row, while

𝐴 𝐷 - 𝐶 𝐵 = (\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix})

By Proposition 5.4.29 and Theorem 5.4.10,

\begin{aligned} det (\begin{matrix} 𝐴 & 𝐵 \\ 𝐶 & 𝐷 \end{matrix}) & = det 𝐴 det (𝐷 - 𝐶 𝐴^{- 1} 𝐵) \\ = det (𝐴 (𝐷 - 𝐶 𝐴^{- 1} 𝐵)) \\ = det (𝐴 𝐷 - 𝐴 𝐶 𝐴^{- 1} 𝐵) . \end{aligned}

Since $𝐴 𝐶 = 𝐶 𝐴$ , we have $𝐴 𝐶 𝐴^{- 1} =$ $𝐶 𝐴 𝐴^{- 1} =$ $𝐶$ , so the right side is $det (𝐴 𝐷 - 𝐶 𝐵)$ .

For the example, let $𝐴 = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ , $𝐵 = 𝐶 = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix})$ , and $𝐷 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ . Then $𝐴$ is invertible, and $𝐴 𝐶 =$ $(\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}) \neq$ $(\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}) =$ $𝐶 𝐴$ . The third row of $(\begin{matrix} 𝐴 & 𝐵 \\ 𝐶 & 𝐷 \end{matrix})$ is the first row of $𝐶$ followed by the first row of $𝐷$ , which is zero, so $det (\begin{matrix} 𝐴 & 𝐵 \\ 𝐶 & 𝐷 \end{matrix}) = 0$ . But $𝐴 𝐷 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ and $𝐶 𝐵 = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix})$ , so $det (𝐴 𝐷 - 𝐶 𝐵) =$ $det (\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix}) =$ $- 1$ .

More practice

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