5.3 Existence and uniqueness

Theorem 5.1.13 showed that the determinant axioms leave exactly one function on $𝐹^{2 \times 2}$ . Intuition (What the proof did, and where it leads) outlined the same argument for $𝑛 \times 𝑛$ matrices and left two questions open. The first, whether an ordering of $𝐞_{1}, \dots, 𝐞_{𝑛}$ could be sorted both by an even and by an odd number of interchanges, was settled in Section 5.2: it cannot (Theorem 5.2.18), and $𝐷 (𝐞_{𝜎 (1)}, \dots, 𝐞_{𝜎 (𝑛)}) =$ $sgn (𝜎) 𝐷 (𝐼_{𝑛})$ (Theorem 5.2.31). The second, whether the resulting formula satisfies the axioms, is answered here, and this section finishes the argument. Carrying out the expansion shows that a determinant function must be given by an explicit formula, the Leibniz formula, so there is at most one. Checking that the formula satisfies the axioms shows that there is one. The formula has $𝑛!$ terms and is a poor way to compute, but it displays $det 𝐴$ as an explicit function of the entries of $𝐴$ , and the rest of the section reads several facts off it: the $3 \times 3$ formula, the determinants of triangular and block-diagonal matrices, and the fact that $det 𝐴$ is a polynomial in the entries.

Throughout, $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ has entries $𝑎_{𝑖 𝑗}$ and columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ , so that $𝐚_{𝑗} =$ $\sum_{𝑖 = 1}^{𝑛} 𝑎_{𝑖 𝑗} 𝐞_{𝑖}$ .

5.3.1The axioms force a formula

Intuition (Strategy). As in the

2 \times 2

case, we break

𝐷 (𝐴)

into values of

𝐷

at matrices of

0

s and

1

s. Write each column in the standard basis and expand by multilinearity in every column (Technique 5.1.7). Each column contributes

𝑛

terms, so there are

𝑛^{𝑛}

terms, one for each way of choosing a row index in every column. Written with

𝑛

nested sums,

\sum_{𝑖_{1}} \dots \sum_{𝑖_{𝑛}}

, this quickly becomes unreadable. The better bookkeeping indexes a choice of row indices by a single object: a function

𝑓 : [𝑛] \to [𝑛]

, where

𝑓 (𝑗)

is the row chosen in column

𝑗

. Alternation then kills every term whose

𝑓

takes some value twice, the survivors are indexed by permutations, and Theorem 5.2.31 evaluates them.

Notation 5.3.1. We write

{[𝑛]}^{[𝑛]}

for the set of all functions

𝑓 : [𝑛] \to [𝑛]

. It has

𝑛^{𝑛}

elements, since each of

𝑓 (1), \dots, 𝑓 (𝑛)

can be any element of

[𝑛]

. For

𝑓 \in {[𝑛]}^{[𝑛]}

, let

𝐸_{𝑓} \in 𝐹^{𝑛 \times 𝑛}

be the matrix with columns

𝐞_{𝑓 (1)},

𝐞_{𝑓 (2)},

\dots,

𝐞_{𝑓 (𝑛)}

. When

𝑓 = 𝜎

is a permutation,

𝐸_{𝜎}

is the permutation matrix of Definition 5.2.29.

For example, the function $𝑓 : [3] \to [3]$ of Non-example 5.2.3, with $𝑓 (1) = 𝑓 (2) = 2$ and $𝑓 (3) = 1$ , gives the matrix $𝐸_{𝑓}$ with columns $𝐞_{2}, 𝐞_{2}, 𝐞_{1}$ .

Lemma 5.3.2 (Expanding every column). Let $𝐷 : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ be multilinear. Then for every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ ,

𝐷 (𝐴) = \sum_{𝑓 \in {[𝑛]}^{[𝑛]}} 𝑎_{𝑓 (1) 1} 𝑎_{𝑓 (2) 2} \dots 𝑎_{𝑓 (𝑛) 𝑛} 𝐷 (𝐸_{𝑓}) .

Proof.standard

Uses. Definition 5.1.1 (Determinant function), Definition 1.6.8 (Standard bases), induction on the number $𝑘$ of expanded columns

Techniques. Expand by multilinearity (Technique 5.1.7)

Hint 1. Expand one column at a time. After the first

𝑘

columns have been expanded, what does a single term look like?

Hint 2. For

0 \leq 𝑘 \leq 𝑛

and

𝑔 : [𝑘] \to [𝑛]

, let

𝐴_{𝑔}

be the matrix with columns

𝐞_{𝑔 (1)},

\dots,

𝐞_{𝑔 (𝑘)},

𝐚_{𝑘 + 1},

\dots,

𝐚_{𝑛}

. Prove by induction on

𝑘

that

𝐷 (𝐴) =

\sum_{𝑔} 𝑎_{𝑔 (1) 1} \dots 𝑎_{𝑔 (𝑘) 𝑘} 𝐷 (𝐴_{𝑔})

, the sum running over all

𝑔 : [𝑘] \to [𝑛]

Hint 3. For the inductive step, expand column

𝑘 + 1

𝐴_{𝑔}

\sum_{𝑖} 𝑎_{𝑖, 𝑘 + 1} 𝐞_{𝑖}

. A function

[𝑘 + 1] \to [𝑛]

is the same thing as a function

𝑔 : [𝑘] \to [𝑛]

together with a value

𝑖 \in [𝑛]

𝑘 + 1

Sketch. Induct on the number

𝑘

of columns already expanded. The statement for

𝑘

writes

𝐷 (𝐴)

as the sum, over

𝑔 : [𝑘] \to [𝑛]

, of

𝑎_{𝑔 (1) 1} \dots 𝑎_{𝑔 (𝑘) 𝑘}

times

𝐷

at the matrix whose first

𝑘

columns are

𝐞_{𝑔 (1)},

\dots,

𝐞_{𝑔 (𝑘)}

and whose other columns are those of

𝐴

. Expanding column

𝑘 + 1

of each such matrix by linearity gives the statement for

𝑘 + 1

, because extending

𝑔

by a value at

𝑘 + 1

produces each function

[𝑘 + 1] \to [𝑛]

exactly once. For

𝑘 = 𝑛

these matrices are the

𝐸_{𝑓}

For $0 \leq 𝑘 \leq 𝑛$ and a function $𝑔 : [𝑘] \to [𝑛]$ , let $𝐴_{𝑔}$ be the matrix with columns $𝐞_{𝑔 (1)},$ $\dots,$ $𝐞_{𝑔 (𝑘)},$ $𝐚_{𝑘 + 1},$ $\dots,$ $𝐚_{𝑛}$ . For $𝑘 = 0$ there is exactly one function $𝑔 : \emptyset \to [𝑛]$ , and $𝐴_{𝑔} = 𝐴$ . We show by induction on $𝑘$ that

𝐷 (𝐴) = \sum_{𝑔 : [𝑘] \to [𝑛]} 𝑎_{𝑔 (1) 1} \dots 𝑎_{𝑔 (𝑘) 𝑘} 𝐷 (𝐴_{𝑔}),

the sum running over all functions $𝑔 : [𝑘] \to [𝑛]$ . For $𝑘 = 0$ the sum has the single term $𝐷 (𝐴)$ , whose coefficient is the empty product $1$ .

Suppose the identity holds for some $𝑘 < 𝑛$ , and fix $𝑔 : [𝑘] \to [𝑛]$ . For $𝑖 \in [𝑛]$ , let $𝑔_{𝑖} : [𝑘 + 1] \to [𝑛]$ agree with $𝑔$ on $[𝑘]$ and send $𝑘 + 1$ to $𝑖$ . Column $𝑘 + 1$ of $𝐴_{𝑔}$ is $𝐚_{𝑘 + 1} =$ $\sum_{𝑖 = 1}^{𝑛} 𝑎_{𝑖, 𝑘 + 1} 𝐞_{𝑖}$ , and replacing it by $𝐞_{𝑖}$ gives $𝐴_{𝑔_{𝑖}}$ . So by linearity in column $𝑘 + 1$ ,

𝐷 (𝐴_{𝑔}) = \sum_{𝑖 = 1}^{𝑛} 𝑎_{𝑖, 𝑘 + 1} 𝐷 (𝐴_{𝑔_{𝑖}}) .

Substituting this into the identity for $𝑘$ ,

𝐷 (𝐴) = \sum_{𝑔 : [𝑘] \to [𝑛]} \sum_{𝑖 = 1}^{𝑛} 𝑎_{𝑔 (1) 1} \dots 𝑎_{𝑔 (𝑘) 𝑘} 𝑎_{𝑖, 𝑘 + 1} 𝐷 (𝐴_{𝑔_{𝑖}}) .

Every function $ℎ : [𝑘 + 1] \to [𝑛]$ equals $𝑔_{𝑖}$ for exactly one pair $(𝑔, 𝑖)$ , namely $𝑔 = ℎ ↾_{[𝑘]}$ and $𝑖 = ℎ (𝑘 + 1)$ , and the coefficient of that term is $𝑎_{ℎ (1) 1} \dots 𝑎_{ℎ (𝑘 + 1), 𝑘 + 1}$ . So the double sum equals $\sum_{ℎ} 𝑎_{ℎ (1) 1} \dots 𝑎_{ℎ (𝑘 + 1), 𝑘 + 1} 𝐷 (𝐴_{ℎ})$ , the sum over all $ℎ : [𝑘 + 1] \to [𝑛]$ , which is the identity for $𝑘 + 1$ . For $𝑘 = 𝑛$ we have $𝐴_{𝑓} = 𝐸_{𝑓}$ , and the identity is the claim. □

The lemma uses only multilinearity: it is Technique 5.1.7 carried out in all $𝑛$ columns at once. Alternation now removes most of the $𝑛^{𝑛}$ terms.

Theorem 5.3.3 (The Leibniz formula). Let $𝐷 : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ be multilinear and alternating. Then for every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ ,

𝐷 (𝐴) = 𝐷 (𝐼_{𝑛}) \sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) 𝑎_{𝜎 (1) 1} 𝑎_{𝜎 (2) 2} \dots 𝑎_{𝜎 (𝑛) 𝑛} .

In particular, every determinant function $𝐷$ on $𝐹^{𝑛 \times 𝑛}$ satisfies

𝐷 (𝐴) = \sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) 𝑎_{𝜎 (1) 1} 𝑎_{𝜎 (2) 2} \dots 𝑎_{𝜎 (𝑛) 𝑛} .

Proof.routine

Uses. Lemma 5.3.2 (Expanding every column), Definition 5.1.1 (Determinant function), Definition 5.2.1 (Permutation), Theorem 5.2.31 (Alternating functions and permutations), an injective function $[𝑛] \to [𝑛]$ is a bijection (Section A.1)

Techniques. Expand by multilinearity (Technique 5.1.7)

Hint 1. Start from Lemma 5.3.2. For which

𝑓

does alternation force

𝐷 (𝐸_{𝑓}) = 0

Hint 2. If

𝑓

is not injective, two columns of

𝐸_{𝑓}

are the same standard basis vector. The injective functions

[𝑛] \to [𝑛]

are exactly the permutations.

Hint 3. For a permutation

𝜎

, Theorem 5.2.31 gives

𝐷 (𝐸_{𝜎})

Sketch. By Lemma 5.3.2,

𝐷 (𝐴) =

\sum_{𝑓} 𝑎_{𝑓 (1) 1} \dots 𝑎_{𝑓 (𝑛) 𝑛} 𝐷 (𝐸_{𝑓})

. If

𝑓 (𝑝) = 𝑓 (𝑞)

with

𝑝 \neq 𝑞

, then

𝐸_{𝑓}

has two equal columns and

𝐷 (𝐸_{𝑓}) = 0

. The remaining

𝑓

are injective, hence permutations, and

𝐷 (𝐸_{𝜎}) =

sgn (𝜎) 𝐷 (𝐼_{𝑛})

By Lemma 5.3.2,

𝐷 (𝐴) = \sum_{𝑓 \in {[𝑛]}^{[𝑛]}} 𝑎_{𝑓 (1) 1} \dots 𝑎_{𝑓 (𝑛) 𝑛} 𝐷 (𝐸_{𝑓}) .

Suppose $𝑓$ is not injective, say $𝑓 (𝑝) = 𝑓 (𝑞)$ with $𝑝 \neq 𝑞$ . Then columns $𝑝$ and $𝑞$ of $𝐸_{𝑓}$ are both $𝐞_{𝑓 (𝑝)}$ , so $𝐷 (𝐸_{𝑓}) = 0$ because $𝐷$ is alternating, and the term of $𝑓$ is $0$ . An injective function from the finite set $[𝑛]$ to itself is a bijection, so the remaining terms are indexed by the permutations $𝜎 \in 𝑆_{𝑛}$ . For these, $𝐷 (𝐸_{𝜎}) =$ $sgn (𝜎) 𝐷 (𝐼_{𝑛})$ by Theorem 5.2.31. Hence

𝐷 (𝐴) = \sum_{𝜎 \in 𝑆_{𝑛}} 𝑎_{𝜎 (1) 1} \dots 𝑎_{𝜎 (𝑛) 𝑛} sgn (𝜎) 𝐷 (𝐼_{𝑛}),

which is the claim after pulling out the common factor $𝐷 (𝐼_{𝑛})$ . If $𝐷$ is a determinant function, then $𝐷 (𝐼_{𝑛}) = 1$ . □

For $𝑛 = 2$ , the permutations are $id$ and $(1 2)$ , with signs $1$ and $- 1$ , and the formula reads $𝐷 (𝐴) =$ $(𝑎_{11} 𝑎_{22} - 𝑎_{21} 𝑎_{12}) 𝐷 (𝐼_{2})$ . This is part (a) of Theorem 5.1.13. For $𝑛 = 1$ it reads $𝐷 (𝑎) = 𝑎 𝐷 (1)$ , as in Example 5.1.2.

Theorem 5.3.3 proves uniqueness: any two determinant functions on $𝐹^{𝑛 \times 𝑛}$ are given by the same formula, so they are equal. It does not prove existence. Its hypothesis is that $𝐷$ is multilinear and alternating, and its conclusion describes such a $𝐷$ if there is one. For $𝑛 = 2$ we checked separately that $𝑎 𝑑 - 𝑏 𝑐$ satisfies the axioms (part (b) of Theorem 5.1.13). For general $𝑛$ that check is the next subsection.

5.3.2The formula satisfies the axioms

By Theorem 5.3.3, if a determinant function on $𝐹^{𝑛 \times 𝑛}$ exists, it is the function $𝐿 : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ given by

𝐿 (𝐴) = \sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) 𝑎_{𝜎 (1) 1} 𝑎_{𝜎 (2) 2} \dots 𝑎_{𝜎 (𝑛) 𝑛} .

(5.3.1)

(The name $𝐿$ is temporary, until we know that $𝐿$ is a determinant function.) For $𝜎 \in 𝑆_{𝑛}$ we write

𝑡_{𝜎} (𝐴) = sgn (𝜎) 𝑎_{𝜎 (1) 1} 𝑎_{𝜎 (2) 2} \dots 𝑎_{𝜎 (𝑛) 𝑛}

for the term of $𝜎$ , so that $𝐿 (𝐴) =$ $\sum_{𝜎} 𝑡_{𝜎} (𝐴)$ . Realize that $𝑡_{𝜎} (𝐴)$ contains exactly one entry from each column of $𝐴$ , namely $𝑎_{𝜎 (𝑗) 𝑗}$ from column $𝑗$ . This makes normalization and multilinearity routine to check. Alternation is the delicate axiom: when two columns of $𝐴$ are equal, no single term needs to vanish, and the terms have to cancel against each other.

Theorem 5.3.4 (Existence and uniqueness of the determinant). Let

𝑛 \geq 1

. The function

𝐿

of (5.3.1) is a determinant function on

𝐹^{𝑛 \times 𝑛}

, and it is the only one. Moreover, every multilinear alternating function

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

satisfies

𝐷 (𝐴) =

𝐷 (𝐼_{𝑛}) 𝐿 (𝐴)

for all

𝐴 \in 𝐹^{𝑛 \times 𝑛}

Proof, part 1 of 3: uniqueness.routine

Uses. Theorem 5.3.3 (The Leibniz formula), Definition 5.1.1 (Determinant function)

Hint 1. This half is already done. Which result expresses every multilinear alternating

𝐷

through the formula (5.3.1)?

Hint 2. Theorem 5.3.3 says that

𝐷 (𝐴) =

𝐷 (𝐼_{𝑛}) 𝐿 (𝐴)

. What is

𝐷 (𝐼_{𝑛})

for a determinant function?

Sketch. By Theorem 5.3.3, every multilinear alternating

𝐷

equals

𝐷 (𝐼_{𝑛}) 𝐿

, and a determinant function has

𝐷 (𝐼_{𝑛}) = 1

, so it equals

𝐿

Let

𝐷

be multilinear and alternating. By Theorem 5.3.3,

𝐷 (𝐴) =

𝐷 (𝐼_{𝑛}) 𝐿 (𝐴)

for every

𝐴

, which is the last sentence of the theorem. If

𝐷

is a determinant function, then

𝐷 (𝐼_{𝑛}) = 1

, so

𝐷 = 𝐿

. Hence there is at most one determinant function, and if there is one, it is

𝐿

. It remains to show that

𝐿

is a determinant function.

Proof, part 2 of 3: $𝐿$ is normalized and multilinear.routine

Uses. Definition 5.1.1 (Determinant function), Definition 5.2.23 (Sign of a permutation)

Hint 1. For normalization, the

(𝑖, 𝑗)

entry of

𝐼_{𝑛}

1

𝑖 = 𝑗

and

0

otherwise. Which terms of

𝐿 (𝐼_{𝑛})

can be nonzero?

Hint 2. For linearity in column

𝑘

, each term contains exactly one entry of column

𝑘

, namely

𝑎_{𝜎 (𝑘) 𝑘}

. Separate it from the other factors.

Sketch. In

𝐿 (𝐼_{𝑛})

, a term with

𝜎 \neq id

contains a factor

𝑎_{𝜎 (𝑗) 𝑗} = 0

for some

𝑗

with

𝜎 (𝑗) \neq 𝑗

, so only

𝑡_{id} (𝐼_{𝑛}) = 1

survives. If column

𝑘

𝐱

, then

𝐿 =

\sum_{𝜎} 𝑏_{𝜎} 𝑥_{𝜎 (𝑘)}

, where

𝑏_{𝜎} =

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

does not depend on

𝐱

, and such a function of

𝐱

is linear.

Normalized. The $(𝑖, 𝑗)$ entry of $𝐼_{𝑛}$ is $1$ if $𝑖 = 𝑗$ and $0$ otherwise. If $𝜎 \neq id$ , choose $𝑗$ with $𝜎 (𝑗) \neq 𝑗$ ; then the factor $𝑎_{𝜎 (𝑗) 𝑗}$ of $𝑡_{𝜎} (𝐼_{𝑛})$ is $0$ , so $𝑡_{𝜎} (𝐼_{𝑛}) = 0$ . Hence $𝐿 (𝐼_{𝑛}) =$ $𝑡_{id} (𝐼_{𝑛}) =$ $sgn (id) \cdot$ $1 \cdot$ $\dots \cdot$ $1 =$ $1$ .

Multilinear. Fix $𝑘 \in [𝑛]$ and the columns $𝐚_{𝑗}$ for $𝑗 \neq 𝑘$ . For $𝐱 \in 𝐹^{𝑛}$ , let $𝐴_{𝐱}$ be the matrix with $𝐱$ in column $𝑘$ and $𝐚_{𝑗}$ in column $𝑗$ for every $𝑗 \neq 𝑘$ . The only factor of $𝑡_{𝜎} (𝐴_{𝐱})$ that comes from column $𝑘$ is $𝑥_{𝜎 (𝑘)}$ , so

𝐿 (𝐴_{𝐱}) = \sum_{𝜎 \in 𝑆_{𝑛}} 𝑏_{𝜎} 𝑥_{𝜎 (𝑘)}, where 𝑏_{𝜎} = sgn (𝜎) \prod_{𝑗 \neq 𝑘} 𝑎_{𝜎 (𝑗) 𝑗}

does not depend on $𝐱$ . Hence, for $𝐱, 𝐲 \in 𝐹^{𝑛}$ and $𝑐 \in 𝐹$ ,

\begin{aligned} 𝐿 (𝐴_{𝑐 𝐱 + 𝐲}) & = \sum_{𝜎} 𝑏_{𝜎} (𝑐 𝑥_{𝜎 (𝑘)} + 𝑦_{𝜎 (𝑘)}) \\ = 𝑐 \sum_{𝜎} 𝑏_{𝜎} 𝑥_{𝜎 (𝑘)} + \sum_{𝜎} 𝑏_{𝜎} 𝑦_{𝜎 (𝑘)} = 𝑐 𝐿 (𝐴_{𝐱}) + 𝐿 (𝐴_{𝐲}) . \end{aligned}

So $𝐿$ is linear in column $𝑘$ , and $𝑘$ was arbitrary.

Intuition (Why alternation needs care). Suppose columns $𝑘$ and $𝑙$ of $𝐴$ are equal, where $𝑘 \neq 𝑙$ , and let $𝜏 = (𝑘 𝑙)$ . The permutation $𝜎 𝜏$ uses the row $𝜎 (𝑙)$ in column $𝑘$ and the row $𝜎 (𝑘)$ in column $𝑙$ , and otherwise agrees with $𝜎$ . Since columns $𝑘$ and $𝑙$ are equal, the product of entries in $𝑡_{𝜎 𝜏} (𝐴)$ is the same as in $𝑡_{𝜎} (𝐴)$ , while the sign is opposite. So $𝑡_{𝜎 𝜏} (𝐴) =$ $- 𝑡_{𝜎} (𝐴)$ .

The quickest way to use this is to reindex the whole sum: by Proposition 5.2.8, $𝐿 (𝐴) =$ $\sum_{𝜎} 𝑡_{𝜎 𝜏} (𝐴) =$ $- \sum_{𝜎} 𝑡_{𝜎} (𝐴) =$ $- 𝐿 (𝐴)$ . But this only shows $(1 + 1) 𝐿 (𝐴) = 0$ , which gives $𝐿 (𝐴) = 0$ when $1 + 1 \neq 0$ (compare Proposition 5.1.11). Over $𝔽_{2}$ it says nothing, since $- 𝐿 (𝐴) = 𝐿 (𝐴)$ there.

The fix is to cancel the terms two at a time instead of summing them all at once. The permutations $𝜎$ and $𝜎 𝜏$ are different, one is even and the other odd, and their terms are negatives of each other. Grouping the $𝑛!$ terms into $𝑛! / 2$ such pairs writes $𝐿 (𝐴)$ as a sum of zeros, and no division is involved.

Technique 5.3.5 (Cancel terms in pairs). To show that a finite sum $\sum_{𝑥 \in 𝑋} 𝑡 (𝑥)$ is $0$ , find a bijection $𝜑 : 𝑋 \to 𝑋$ with $𝜑 (𝜑 (𝑥)) = 𝑥$ and $𝜑 (𝑥) \neq 𝑥$ for every $𝑥$ , such that $𝑡 (𝜑 (𝑥)) =$ $- 𝑡 (𝑥)$ . Then $𝑋$ splits into two-element sets ${𝑥, 𝜑 (𝑥)}$ , and the two terms in each set cancel. To write this down, choose a set $𝑃 \subseteq 𝑋$ containing exactly one element of each pair, so that $𝜑$ maps $𝑃$ bijectively onto $𝑋 ∖ 𝑃$ ; then $\sum_{𝑥 \in 𝑋} 𝑡 (𝑥) =$ $\sum_{𝑥 \in 𝑃} (𝑡 (𝑥) + 𝑡 (𝜑 (𝑥))) =$ $0$ . If $𝜑$ has fixed points, and $𝑡 (𝜑 (𝑥)) =$ $- 𝑡 (𝑥)$ holds for the other $𝑥$ , the same argument shows that the sum equals the sum over the fixed points, which is often easy to evaluate.

This is not the same as the shortcut “reindexing by $𝜑$ shows $𝑆 = - 𝑆$ , so $𝑆 = 0$ ”. The shortcut divides by $1 + 1$ , which is impossible in characteristic $2$ , while pairing never divides. Reach for pairing when the terms of a sum come with signs and a natural operation flips the sign: for sums over $𝑆_{𝑛}$ , composing with a fixed transposition. The canonical example is the alternation of the Leibniz formula in Theorem 5.3.4. Counting is a special case: an involution with no fixed points shows that a finite set has an even number of elements, and in general $| 𝑋 |$ has the same parity as the number of fixed points of $𝜑$ (Exercise 5.3.40).

Used in 8 places

Theorem 5.3.4, Exercise 5.3.27, Exercise 5.3.39, Exercise 5.3.40, Exercise 5.6.13, Problem 5.1, Problem 5.15, Proposition 7.3.2.

Proof of Theorem 5.3.4, part 3 of 3: $𝐿$ is alternating.standard

Uses. Remark 5.2.11 (Composing with a transposition), Proposition 5.2.25 (Multiplicativity of the sign), Proposition 5.2.27 (Half of all permutations are even), Proposition 5.2.8 (Reindexing sums over $𝑆_{𝑛}$ ), Proposition 5.2.13 (Products of transpositions), Theorem 5.2.18 (Parity is well defined)

Techniques. Cancel terms in pairs (Technique 5.3.5)

Hint 1. Suppose columns

𝑘 \neq 𝑙

𝐴

are equal, and let

𝜏 = (𝑘 𝑙)

. Compare the terms

𝑡_{𝜎} (𝐴)

and

𝑡_{𝜎 𝜏} (𝐴)

Hint 2.

(𝜎 𝜏) (𝑘) = 𝜎 (𝑙)

(𝜎 𝜏) (𝑙) = 𝜎 (𝑘)

, and

𝜎 𝜏

agrees with

𝜎

elsewhere. Because columns

𝑘

and

𝑙

are equal, the products of entries agree, while the signs are opposite.

Hint 3. Split

𝑆_{𝑛}

into the even and the odd permutations. The map

𝜎 \mapsto 𝜎 𝜏

is a bijection from the even ones to the odd ones. Pair each even

𝜎

with

𝜎 𝜏

Sketch. Let columns

𝑘 \neq 𝑙

be equal and

𝜏 = (𝑘 𝑙)

. The permutation

𝜎 𝜏

differs from

𝜎

only by exchanging the rows used in columns

𝑘

and

𝑙

, and these columns are equal, so the products of entries agree; since

sgn (𝜎 𝜏) =

- sgn (𝜎)

𝑡_{𝜎 𝜏} (𝐴) =

- 𝑡_{𝜎} (𝐴)

. The map

𝜎 \mapsto 𝜎 𝜏

is a bijection from the even permutations to the odd ones, so

𝐿 (𝐴) =

\sum_{𝜎 even} (𝑡_{𝜎} (𝐴) + 𝑡_{𝜎 𝜏} (𝐴)) =

0

Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ with $𝐚_{𝑘} = 𝐚_{𝑙}$ for some $𝑘 \neq 𝑙$ , so that $𝑛 \geq 2$ and $𝑎_{𝑖 𝑘} = 𝑎_{𝑖 𝑙}$ for every $𝑖 \in [𝑛]$ . Let $𝜏 = (𝑘 𝑙)$ .

Step 1: $𝑡_{𝜎 𝜏} (𝐴) =$ $- 𝑡_{𝜎} (𝐴)$ for every $𝜎 \in 𝑆_{𝑛}$ . By Remark 5.2.11, $(𝜎 𝜏) (𝑘) = 𝜎 (𝑙)$ , $(𝜎 𝜏) (𝑙) = 𝜎 (𝑘)$ , and $(𝜎 𝜏) (𝑗) = 𝜎 (𝑗)$ for $𝑗 \notin {𝑘, 𝑙}$ . So the product of entries in $𝑡_{𝜎 𝜏} (𝐴)$ is

\begin{aligned} \prod_{𝑗 = 1}^{𝑛} 𝑎_{(𝜎 𝜏) (𝑗) 𝑗} & = 𝑎_{𝜎 (𝑙) 𝑘} 𝑎_{𝜎 (𝑘) 𝑙} \prod_{𝑗 \notin {𝑘, 𝑙}} 𝑎_{𝜎 (𝑗) 𝑗} \\ = 𝑎_{𝜎 (𝑙) 𝑙} 𝑎_{𝜎 (𝑘) 𝑘} \prod_{𝑗 \notin {𝑘, 𝑙}} 𝑎_{𝜎 (𝑗) 𝑗} = \prod_{𝑗 = 1}^{𝑛} 𝑎_{𝜎 (𝑗) 𝑗}, \end{aligned}

where the second equality uses $𝑎_{𝜎 (𝑙) 𝑘} =$ $𝑎_{𝜎 (𝑙) 𝑙}$ and $𝑎_{𝜎 (𝑘) 𝑙} =$ $𝑎_{𝜎 (𝑘) 𝑘}$ , which hold because columns $𝑘$ and $𝑙$ are equal. By Proposition 5.2.25, $sgn (𝜎 𝜏) =$ $sgn (𝜎) sgn (𝜏) =$ $- sgn (𝜎)$ . Hence $𝑡_{𝜎 𝜏} (𝐴) =$ $- 𝑡_{𝜎} (𝐴)$ .

Step 2: pairing. Let $𝑆_{𝑛}^{+}$ and $𝑆_{𝑛}^{-}$ be the sets of even and of odd permutations. By Proposition 5.2.13 and Theorem 5.2.18, $𝑆_{𝑛}$ is the disjoint union of $𝑆_{𝑛}^{+}$ and $𝑆_{𝑛}^{-}$ . Let $𝜑 (𝜎) = 𝜎 𝜏$ . As in the proof of Proposition 5.2.27, $𝜑$ maps $𝑆_{𝑛}^{+}$ into $𝑆_{𝑛}^{-}$ and $𝑆_{𝑛}^{-}$ into $𝑆_{𝑛}^{+}$ , because $sgn (𝜎 𝜏) =$ $- sgn (𝜎)$ , and $𝜑 (𝜑 (𝜎)) =$ $𝜎 𝜏^{2} =$ $𝜎$ . So the restrictions $𝑆_{𝑛}^{+} \to 𝑆_{𝑛}^{-}$ and $𝑆_{𝑛}^{-} \to 𝑆_{𝑛}^{+}$ of $𝜑$ are inverse to each other, and in particular $𝜑$ maps $𝑆_{𝑛}^{+}$ bijectively onto $𝑆_{𝑛}^{-}$ . Reindexing the sum over $𝑆_{𝑛}^{-}$ along this bijection (the argument of Proposition 5.2.8 applies to any bijection between finite sets) and then using Step 1,

\begin{aligned} 𝐿 (𝐴) & = \sum_{𝜎 \in 𝑆_{𝑛}^{+}} 𝑡_{𝜎} (𝐴) + \sum_{𝜌 \in 𝑆_{𝑛}^{-}} 𝑡_{𝜌} (𝐴) = \sum_{𝜎 \in 𝑆_{𝑛}^{+}} 𝑡_{𝜎} (𝐴) + \sum_{𝜎 \in 𝑆_{𝑛}^{+}} 𝑡_{𝜎 𝜏} (𝐴) \\ = \sum_{𝜎 \in 𝑆_{𝑛}^{+}} (𝑡_{𝜎} (𝐴) + 𝑡_{𝜎 𝜏} (𝐴)) = \sum_{𝜎 \in 𝑆_{𝑛}^{+}} 0 = 0 . \end{aligned}

So $𝐿$ is alternating. By Part 2, $𝐿$ is a determinant function, and by Part 1 it is the only one. □

Step 2 never divides by $1 + 1$ , so the proof works over every field. Over $𝔽_{2}$ , where $sgn (𝜎) = 1$ for every $𝜎$ , Step 1 says that the two terms of each pair are equal, and they cancel because $𝑥 + 𝑥 = 0$ in $𝔽_{2}$ .

Definition 5.3.6 (Determinant). The determinant is the unique determinant function $det : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ of Theorem 5.3.4. By Theorem 5.3.3,

det 𝐴 = \sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) 𝑎_{𝜎 (1) 1} 𝑎_{𝜎 (2) 2} \dots 𝑎_{𝜎 (𝑛) 𝑛}

for every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , and every multilinear alternating $𝐷 : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ satisfies $𝐷 = 𝐷 (𝐼_{𝑛}) det$ . As for $𝐷$ , we also write $det (𝐚_{1}, \dots, 𝐚_{𝑛})$ for the determinant of the matrix with columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ .

For $𝑛 = 2$ this is the function $𝑎 𝑑 - 𝑏 𝑐$ of Definition 5.1.14. From now on every result about multilinear alternating functions in Section 5.1 and Section 5.2 applies to $det$ . For instance, $det 𝐴 = 0$ whenever the columns of $𝐴$ are linearly dependent (Proposition 5.1.17), and $det (𝐴 𝐸_{𝜎}) =$ $sgn (𝜎) det 𝐴$ (Theorem 5.2.31).

Exercise 5.3.7.routine Let

{Alt}_{𝑛}

be the vector space of multilinear alternating functions

𝐹^{𝑛 \times 𝑛} \to 𝐹

(Exercise 5.1.34). Show that

{Alt}_{𝑛} = span (det)

and

dim {Alt}_{𝑛} = 1

. Deduce that if

𝐷 \in {Alt}_{𝑛}

and

𝐷 (𝐴) \neq 0

for some

𝐴

, then

𝐷 = 𝑐 det

for some

𝑐 \neq 0

, and

det 𝐴 \neq 0

Solution.

Uses. Theorem 5.3.4 (Existence and uniqueness of the determinant), Exercise 5.1.34, Definition 1.5.1 (Linear independence), Definition 4.1.5 (Dimension), Proposition 1.1.15 (Multiplying by zero)

Hint 1. The last sentence of Theorem 5.3.4 writes every

𝐷 \in {Alt}_{𝑛}

as a scalar multiple of

det

Hint 2. For the dimension, the list consisting of

det

alone is independent because

det \neq 0

. For the last claim, write

𝐷 = 𝑐 det

and evaluate at

𝐴

Sketch. Every

𝐷 \in {Alt}_{𝑛}

equals

𝐷 (𝐼_{𝑛}) det

, and

det \in {Alt}_{𝑛}

, so

{Alt}_{𝑛} = span (det)

. Since

det (𝐼_{𝑛}) = 1

det

is not the zero function, so it alone is a basis. If

𝐷 (𝐴) \neq 0

, then

𝐷 = 𝑐 det

with

𝑐 det 𝐴 \neq 0

, which forces

𝑐 \neq 0

and

det 𝐴 \neq 0

By Theorem 5.3.4, every $𝐷 \in {Alt}_{𝑛}$ satisfies $𝐷 =$ $𝐷 (𝐼_{𝑛}) det \in$ $span (det)$ . Conversely, $det \in {Alt}_{𝑛}$ and ${Alt}_{𝑛}$ is a subspace (Exercise 5.1.34), so $span (det) \subseteq {Alt}_{𝑛}$ . Hence ${Alt}_{𝑛} = span (det)$ . Since $det (𝐼_{𝑛}) = 1$ , $det$ is not the zero function, so the one-element list $det$ is linearly independent and is a basis of ${Alt}_{𝑛}$ . Thus $dim {Alt}_{𝑛} = 1$ .

Now let $𝐷 \in {Alt}_{𝑛}$ with $𝐷 (𝐴) \neq 0$ , and let $𝑐 = 𝐷 (𝐼_{𝑛})$ , so $𝐷 = 𝑐 det$ . If $𝑐 = 0$ or $det 𝐴 = 0$ , then $𝐷 (𝐴) = 𝑐 det 𝐴 = 0$ by Proposition 1.1.15, which is false. So $𝑐 \neq 0$ and $det 𝐴 \neq 0$ .

Exercise 5.3.8.standard Show that for every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ ,

det 𝐴 = \sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) 𝑎_{1 𝜎 (1)} 𝑎_{2 𝜎 (2)} \dots 𝑎_{𝑛 𝜎 (𝑛)} .

Here each term takes one entry from each row: row $𝑖$ contributes the entry in column $𝜎 (𝑖)$ .

Solution.

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

Hint 1. Fix

𝜎

and reorder the product

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

by its row index. If

𝑖 = 𝜎 (𝑗)

, what is

𝑗

in terms of

𝑖

Hint 2. You should get

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

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

. Then use

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

and substitute

𝜎^{- 1}

for

𝜎

in the sum.

Sketch. As

𝑗

runs over

[𝑛]

𝑖 = 𝜎 (𝑗)

runs over

[𝑛]

once each, with

𝑗 = 𝜎^{- 1} (𝑖)

, so

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

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

. With

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

det 𝐴 = \sum_{𝜎} 𝑔 (𝜎^{- 1})

for

𝑔 (𝜌) =

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

, and reindexing by

𝜎 \mapsto 𝜎^{- 1}

gives

\sum_{𝜎} 𝑔 (𝜎)

Fix $𝜎 \in 𝑆_{𝑛}$ . As $𝑗$ runs over $[𝑛]$ , the row index $𝑖 = 𝜎 (𝑗)$ runs over $[𝑛]$ , taking each value once, and $𝑗 = 𝜎^{- 1} (𝑖)$ . Since multiplication in $𝐹$ is commutative, we may reorder the factors by their row index:

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

Let $𝑔 (𝜌) =$ $sgn (𝜌) 𝑎_{1 𝜌 (1)} \dots 𝑎_{𝑛 𝜌 (𝑛)}$ for $𝜌 \in 𝑆_{𝑛}$ . Since $sgn (𝜎) = sgn (𝜎^{- 1})$ by Proposition 5.2.25, the term of $𝜎$ in the Leibniz formula is $𝑔 (𝜎^{- 1})$ . By Proposition 5.2.8,

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

which is the claim. The right side is the Leibniz formula for the transpose $𝐴^{𝖳}$ , whose $(𝑗, 𝑖)$ entry is $𝑎_{𝑖 𝑗}$ . So this exercise shows $det 𝐴^{𝖳} = det 𝐴$ ; Theorem 5.4.14 records this and draws the consequences.

5.3.3The $3 \times 3$ determinant

For $𝑛 = 3$ the Leibniz formula has $3! = 6$ terms, one for each permutation in Table 5.2.1. Listing the even permutations first,

\begin{aligned} det 𝐴 = & 𝑎_{11} 𝑎_{22} 𝑎_{33} + 𝑎_{21} 𝑎_{32} 𝑎_{13} + 𝑎_{31} 𝑎_{12} 𝑎_{23} \\ - 𝑎_{21} 𝑎_{12} 𝑎_{33} - 𝑎_{11} 𝑎_{32} 𝑎_{23} - 𝑎_{31} 𝑎_{22} 𝑎_{13} . \end{aligned}

(5.3.2)

Expanding the triple product of Exercise 5.1.32 gives the same six terms, as it must by Theorem 5.3.4. Each term takes one entry from each column, and since $𝜎$ is a bijection, the rows $𝜎 (1), 𝜎 (2), 𝜎 (3)$ are also different. Figure 5.3.1 marks the chosen entries. In general a term of the Leibniz formula is a choice of $𝑛$ entries, one in each row and one in each column, like $𝑛$ rooks on an $𝑛 \times 𝑛$ chessboard of which no two attack each other, together with the sign of the corresponding permutation.

Figure 5.3.1. The six terms of (5.3.2). Each grid stands for a

3 \times 3

matrix, and the dots mark the entries

𝑎_{𝜎 (1) 1},

𝑎_{𝜎 (2) 2},

𝑎_{𝜎 (3) 3}

multiplied in the term of

𝜎

. Top row (blue): the even permutations

id

(1 2 3)

(1 3 2)

. Bottom row (red): the odd permutations

(1 2)

(2 3)

(1 3)

In the top row the dots run along the main diagonal and along its two parallels, wrapped around from the right edge to the left. In the bottom row they run along the other diagonal and its two wrapped parallels. Writing the first two columns again to the right of $𝐴$ unwraps these lines, as in Figure 5.3.2.

Figure 5.3.2. The rule of Sarrus. The three columns of

𝐴

are followed by its first two columns again (grey). Products along the blue diagonals are added, and products along the red diagonals are subtracted.

Corollary 5.3.9 (Rule of Sarrus). Let

𝐴 \in 𝐹^{3 \times 3}

, and write its three columns followed by its first two columns again, as in Figure 5.3.2. Then

det 𝐴

is the sum of the products along the three diagonals that run down and to the right from

𝑎_{11}

𝑎_{12}

𝑎_{13}

, minus the sum of the products along the three diagonals that run up and to the right from

𝑎_{31}

𝑎_{32}

𝑎_{33}

Proof.routine

Uses. Definition 5.3.6 (Determinant)

Hint 1. List the six diagonal products and compare them with the six terms of (5.3.2).

Hint 2. The diagonal down from

𝑎_{12}

passes through

𝑎_{23}

and then

𝑎_{31}

, in the repeated first column.

Sketch. The down-right diagonals give

𝑎_{11} 𝑎_{22} 𝑎_{33}

𝑎_{12} 𝑎_{23} 𝑎_{31}

𝑎_{13} 𝑎_{21} 𝑎_{32}

, the terms of the even permutations. The up-right diagonals give

𝑎_{31} 𝑎_{22} 𝑎_{13}

𝑎_{32} 𝑎_{23} 𝑎_{11}

𝑎_{33} 𝑎_{21} 𝑎_{12}

, the terms of the transpositions.

The diagonals running down and to the right from $𝑎_{11}$ , $𝑎_{12}$ , $𝑎_{13}$ have products

𝑎_{11} 𝑎_{22} 𝑎_{33}, 𝑎_{12} 𝑎_{23} 𝑎_{31}, 𝑎_{13} 𝑎_{21} 𝑎_{32},

and the diagonals running up and to the right from $𝑎_{31}$ , $𝑎_{32}$ , $𝑎_{33}$ have products

𝑎_{31} 𝑎_{22} 𝑎_{13}, 𝑎_{32} 𝑎_{23} 𝑎_{11}, 𝑎_{33} 𝑎_{21} 𝑎_{12} .

After reordering the factors, the first three are the terms of $id$ , $(1 3 2)$ , and $(1 2 3)$ in (5.3.2), which enter with sign $+$ , and the last three are the terms of $(1 3)$ , $(2 3)$ , and $(1 2)$ , which enter with sign $-$ . So the rule computes exactly (5.3.2). □

Example 5.3.10 (A $3 \times 3$ determinant). Let $𝐴 =$ $(\begin{matrix} 2 & - 1 & 3 \\ 1 & 4 & 0 \\ - 2 & 1 & 5 \end{matrix}) \in$ $ℚ^{3 \times 3}$ . The diagonals running down to the right have products $2 \cdot 4 \cdot 5 = 40$ , $(- 1) \cdot 0 \cdot (- 2) = 0$ , and $3 \cdot 1 \cdot 1 = 3$ . The diagonals running up to the right have products $(- 2) \cdot 4 \cdot 3 = - 24$ , $1 \cdot 0 \cdot 2 = 0$ , and $5 \cdot 1 \cdot (- 1) = - 5$ . So

det 𝐴 = (40 + 0 + 3) - (- 24 + 0 - 5) = 43 + 29 = 72 .

Since $det 𝐴 \neq 0$ , $𝐴$ is invertible by Corollary 5.1.18.

Remark 5.3.11 (Sarrus does not generalize). The rule of Sarrus works because for

𝑛 = 3

the six diagonals happen to be the six permutations. For

𝑛 = 4

, the same picture (the four columns followed by the first three again) has four diagonals running down and four running up, so it produces

8

products, while the Leibniz formula has

4! = 24

terms. The signs go wrong as well (Exercise 5.3.25). For

𝑛 \geq 4

there is no shortcut of this kind. Section 5.4 computes determinants by elimination, and Section 5.5 by expanding along a row or column.

5.3.4Triangular and block-diagonal matrices

A term of the Leibniz formula vanishes as soon as one of its $𝑛$ entries is $0$ . So a matrix with a pattern of zeros can have very few nonzero terms, and the formula becomes a practical tool.

Technique 5.3.12 (Read structure off the Leibniz expansion). A term of the Leibniz formula is $sgn (𝜎)$ times $𝑛$ entries of $𝐴$ , one in each column and one in each row, and it vanishes if one of these entries is $0$ . So to evaluate or analyze $det 𝐴$ for a matrix with a pattern of zeros, ask which permutations $𝜎$ satisfy $𝑎_{𝜎 (𝑗) 𝑗} \neq 0$ for every $𝑗$ . Often the pattern confines $𝜎$ to a small, explicit set, and only those terms need to be computed. The same question asked about entries that depend on a parameter, instead of entries that vanish, tells you how $det 𝐴$ depends on the parameter (Technique 5.3.18).

Reach for it when the matrix is sparse or structured (triangular, block-diagonal, banded, mostly zeros), or when a question asks which products of entries can occur in $det 𝐴$ . Expect to prove a small lemma about permutations along the way, such as Lemma 5.3.14. The canonical example is Proposition 5.3.15, where only the identity survives.

Used in 16 places and 6 practice exercises

Proposition 5.3.15, Proposition 5.3.17, Proposition 5.3.19, Exercise 5.3.24, Exercise 5.3.29, Exercise 5.3.33, Exercise 5.3.34, Exercise 5.3.38, Theorem 5.4.26, Theorem 5.5.3, Exercise 5.6.6, Exercise 5.6.13, Problem 5.14, Proposition 7.3.18, Theorem 7.3.24, Theorem 7.5.22; 6 practice exercises.

Recall (Definition 3.3.31) that $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ is upper triangular if $𝑎_{𝑖 𝑗} = 0$ whenever $𝑖 > 𝑗$ , lower triangular if $𝑎_{𝑖 𝑗} = 0$ whenever $𝑖 < 𝑗$ , and diagonal if it is both. We call $𝐴$ triangular if it is upper or lower triangular. The entries $𝑎_{11}, \dots, 𝑎_{𝑛 𝑛}$ are the diagonal entries of $𝐴$ , and $diag (𝑑_{1}, \dots, 𝑑_{𝑛})$ denotes the diagonal matrix with diagonal entries $𝑑_{1}, \dots, 𝑑_{𝑛}$ .

Example 5.3.13 (Triangular and not). The matrices

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

are upper triangular, lower triangular, and neither, respectively. The transpose of an upper triangular matrix is lower triangular. $𝐼_{𝑛}$ and the zero matrix are diagonal, and every elementary matrix that adds a multiple of one row to another (Definition 3.2.2) is triangular. The third matrix has determinant $- 1$ , while the product of its diagonal entries is $0$ , so the hypothesis of Proposition 5.3.15 below cannot be dropped.

For an upper triangular $𝐴$ , the entry $𝑎_{𝜎 (𝑗) 𝑗}$ can be nonzero only if $𝜎 (𝑗) \leq 𝑗$ . So the question of Technique 5.3.12 becomes: which permutations satisfy $𝜎 (𝑗) \leq 𝑗$ for every $𝑗$ ?

Lemma 5.3.14 (Permutations with

𝜎 (𝑗) \leq 𝑗

). Let

𝜎 \in 𝑆_{𝑛}

. If

𝜎 (𝑗) \leq 𝑗

for every

𝑗 \in [𝑛]

, then

𝜎 = id

. Likewise, if

𝜎 (𝑗) \geq 𝑗

for every

𝑗 \in [𝑛]

, then

𝜎 = id

Proof (by induction).routine

Uses. Definition 5.2.1 (Permutation), Proposition 5.2.5 (Composition and inverses)

Techniques. Strong induction and well-ordering (Technique 5.2.12)

Hint 1. Under the first hypothesis, what can

𝜎 (1)

be? Then

𝜎 (2)

Hint 2. Show by induction on

𝑗

that

𝜎 (𝑗) = 𝑗

: the value

𝜎 (𝑗)

is at most

𝑗

, and it differs from

𝜎 (1), \dots, 𝜎 (𝑗 - 1)

Hint 3. For the second hypothesis, show that

𝜎^{- 1}

satisfies the first.

Sketch. If

𝜎 (𝑗) \leq 𝑗

for all

𝑗

, then

𝜎 (1) = 1

, and once

𝜎 (𝑖) = 𝑖

for all

𝑖 < 𝑗

, injectivity rules out

𝜎 (𝑗) \in {1, \dots, 𝑗 - 1}

, leaving

𝜎 (𝑗) = 𝑗

. If

𝜎 (𝑗) \geq 𝑗

for all

𝑗

, then

𝜎^{- 1} (𝑖) \leq 𝑖

for all

𝑖

, so

𝜎^{- 1} = id

Suppose $𝜎 (𝑗) \leq 𝑗$ for every $𝑗$ . We show by strong induction on $𝑗$ that $𝜎 (𝑗) = 𝑗$ . Let $𝑗 \in [𝑛]$ , and assume $𝜎 (𝑖) = 𝑖$ for every $𝑖 < 𝑗$ . Since $𝜎$ is injective, $𝜎 (𝑗) \neq 𝜎 (𝑖) = 𝑖$ for each $𝑖 < 𝑗$ , so $𝜎 (𝑗) \notin {1, \dots, 𝑗 - 1}$ . Together with $𝜎 (𝑗) \leq 𝑗$ this gives $𝜎 (𝑗) = 𝑗$ . Hence $𝜎 = id$ .

Now suppose $𝜎 (𝑗) \geq 𝑗$ for every $𝑗$ . Let $𝑖 \in [𝑛]$ and $𝑗 = 𝜎^{- 1} (𝑖)$ . Then $𝜎^{- 1} (𝑖) =$ $𝑗 \leq$ $𝜎 (𝑗) =$ $𝑖$ . So $𝜎^{- 1}$ satisfies the first hypothesis, $𝜎^{- 1} = id$ , and $𝜎 = id$ . □

Proof (by summing).routine

Uses. Definition 5.2.1 (Permutation)

Hint 1. Compare

\sum_{𝑗} 𝜎 (𝑗)

with

\sum_{𝑗} 𝑗

Hint 2. Since

𝜎

is a bijection of

[𝑛]

, the numbers

𝜎 (1), \dots, 𝜎 (𝑛)

are

1, \dots, 𝑛

in some order, so

\sum_{𝑗} (𝑗 - 𝜎 (𝑗)) = 0

. What do the hypotheses say about the signs of the terms?

Sketch.

\sum_{𝑗 = 1}^{𝑛} (𝑗 - 𝜎 (𝑗)) =

0

because

𝜎 (1), \dots, 𝜎 (𝑛)

is a rearrangement of

1, \dots, 𝑛

. Under either hypothesis all terms have the same sign, so all of them are

0

Since $𝜎$ is a bijection $[𝑛] \to [𝑛]$ , the list $𝜎 (1), \dots, 𝜎 (𝑛)$ is a rearrangement of $1, \dots, 𝑛$ , so $\sum_{𝑗} 𝜎 (𝑗) = \sum_{𝑗} 𝑗$ , that is,

\sum_{𝑗 = 1}^{𝑛} (𝑗 - 𝜎 (𝑗)) = 0 .

Under the first hypothesis every term $𝑗 - 𝜎 (𝑗)$ is a nonnegative integer, and a sum of nonnegative integers is $0$ only if every term is $0$ . So $𝜎 (𝑗) = 𝑗$ for every $𝑗$ . Under the second hypothesis every term is a nonpositive integer, and the same argument applied to the negatives of the terms gives the same conclusion. □

The second proof handles both hypotheses at once and uses only that $𝜎$ rearranges $1, \dots, 𝑛$ . The first uses injectivity one value at a time, which is the kind of argument Technique 5.3.12 usually calls for.

Intuition (Triangular matrices in the plane). Let

𝐴 =

(\begin{matrix} 𝑎_{11} & 𝑎_{12} \\ 0 & 𝑎_{22} \end{matrix}) \in

ℝ^{2 \times 2}

. Then

𝐴 𝐞_{1} = (𝑎_{11}, 0)

lies on the horizontal axis, and

𝐴 𝐞_{2} = (𝑎_{12}, 𝑎_{22})

lies on the horizontal line at height

𝑎_{22}

. The parallelogram spanned by them has base

| 𝑎_{11} |

and height

| 𝑎_{22} |

, so its area is

| 𝑎_{11} 𝑎_{22} |

whatever

𝑎_{12}

is. In terms of the axioms, when

𝑎_{11} \neq 0

, changing

𝑎_{12}

slides

𝐴 𝐞_{2}

parallel to

𝐴 𝐞_{1}

, which is a column replacement (Lemma 5.1.8). Sliding all the way to

(0, 𝑎_{22})

turns the parallelogram into a rectangle, the image of the unit square under

diag (𝑎_{11}, 𝑎_{22})

. This is the second proof below, in the smallest case.

The upper triangular matrix

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

, with

det 𝐴 = 2 \cdot 3 / 2 = 3

. Drag

𝐴 𝐞_{2}

left or right, or focus it and use the arrow keys:

𝐴

stays upper triangular, and neither the base nor the height changes, so neither does

det 𝐴

. Moving

𝐴 𝐞_{1}

off the horizontal axis makes

𝐴

not triangular.

Proposition 5.3.15 (Triangular matrices). Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ be upper triangular or lower triangular. Then

det 𝐴 = 𝑎_{11} 𝑎_{22} \dots 𝑎_{𝑛 𝑛} .

More generally, $𝐷 (𝐴) =$ $𝑎_{11} 𝑎_{22} \dots 𝑎_{𝑛 𝑛} 𝐷 (𝐼_{𝑛})$ for every multilinear alternating $𝐷 : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ .

Proof (via the Leibniz formula).routine

Uses. Definition 5.3.6 (Determinant), Lemma 5.3.14 (Permutations with $𝜎 (𝑗) \leq 𝑗$ ), Definition 3.3.31 (Triangular matrices), Theorem 5.3.4 (Existence and uniqueness of the determinant)

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

Hint 1. For an upper triangular

𝐴

, when can the entry

𝑎_{𝜎 (𝑗) 𝑗}

be nonzero?

Hint 2. Only when

𝜎 (𝑗) \leq 𝑗

. If

𝜎 \neq id

, Lemma 5.3.14 gives a

𝑗

with

𝜎 (𝑗) > 𝑗

Hint 3. For the statement about

𝐷

, use the last sentence of Theorem 5.3.4.

Sketch. Let

𝐴

be upper triangular. If

𝜎 \neq id

, then

𝜎 (𝑗) > 𝑗

for some

𝑗

by Lemma 5.3.14, so

𝑎_{𝜎 (𝑗) 𝑗} = 0

and the term of

𝜎

vanishes. Only

𝜎 = id

survives, giving

𝑎_{11} \dots 𝑎_{𝑛 𝑛}

. For lower triangular

𝐴

, use

𝜎 (𝑗) < 𝑗

instead. Then

𝐷 = 𝐷 (𝐼_{𝑛}) det

Suppose $𝐴$ is upper triangular, and let $𝜎 \in 𝑆_{𝑛}$ with $𝜎 \neq id$ . By Lemma 5.3.14, $𝜎 (𝑗) \leq 𝑗$ fails for some $𝑗$ , that is, $𝜎 (𝑗) > 𝑗$ . Then $𝑎_{𝜎 (𝑗) 𝑗} = 0$ because $𝐴$ is upper triangular, so the term of $𝜎$ in the Leibniz formula is $0$ . Only the term of the identity remains:

det 𝐴 = sgn (id) 𝑎_{11} 𝑎_{22} \dots 𝑎_{𝑛 𝑛} = 𝑎_{11} 𝑎_{22} \dots 𝑎_{𝑛 𝑛} .

If $𝐴$ is lower triangular and $𝜎 \neq id$ , then Lemma 5.3.14 gives some $𝑗$ with $𝜎 (𝑗) < 𝑗$ , so $𝑎_{𝜎 (𝑗) 𝑗} = 0$ , and the same conclusion follows. Finally, every multilinear alternating $𝐷$ equals $𝐷 (𝐼_{𝑛}) det$ by Theorem 5.3.4. □

Proof (by column replacement).standard

Uses. Lemma 5.1.8 (Column replacement), Definition 5.1.1 (Determinant function), Exercise 5.1.5, Definition 3.3.31 (Triangular matrices)

Hint 1. Column

𝑗

of an upper triangular matrix is

𝑎_{𝑗 𝑗} 𝐞_{𝑗}

plus a combination of

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

. If

𝑎_{11} \neq 0

, how can you clear the first row outside the diagonal without changing

𝐷

Hint 2. Work from left to right. Once columns

1, \dots, 𝑗 - 1

have become

𝑎_{11} 𝐞_{1},

\dots,

𝑎_{𝑗 - 1, 𝑗 - 1} 𝐞_{𝑗 - 1}

, subtract suitable multiples of them from column

𝑗

. This needs

𝑎_{𝑖 𝑖} \neq 0

for

𝑖 < 𝑗

Hint 3. If some diagonal entry is

0

, let

𝑘

be the least such index and stop after processing column

𝑘

. What is column

𝑘

then?

Sketch. If all diagonal entries are nonzero, column replacements turn columns

1, 2, \dots, 𝑛

in turn into

𝑎_{𝑗 𝑗} 𝐞_{𝑗}

without changing

𝐷

, so

𝐷 (𝐴) =

𝐷 (diag (𝑎_{11}, \dots, 𝑎_{𝑛 𝑛})) =

𝑎_{11} \dots 𝑎_{𝑛 𝑛} 𝐷 (𝐼_{𝑛})

. If

𝑎_{𝑘 𝑘} = 0

with

𝑘

least, the same replacements in columns

2, \dots, 𝑘

make column

𝑘

equal to

𝟎

, so

𝐷 (𝐴) = 0

. For lower triangular matrices, work from right to left.

Let $𝐷$ be multilinear and alternating, and let $𝐴$ be upper triangular. Column $𝑗$ of $𝐴$ is

𝐚_{𝑗} = 𝑎_{𝑗 𝑗} 𝐞_{𝑗} + \sum_{𝑖 < 𝑗} 𝑎_{𝑖 𝑗} 𝐞_{𝑖} .

For $𝑗 \geq 2$ , consider the following step, which may be performed when columns $1, \dots, 𝑗 - 1$ of the current matrix are $𝑎_{11} 𝐞_{1},$ $\dots,$ $𝑎_{𝑗 - 1, 𝑗 - 1} 𝐞_{𝑗 - 1}$ , column $𝑗$ is still $𝐚_{𝑗}$ , and $𝑎_{11},$ $\dots,$ $𝑎_{𝑗 - 1, 𝑗 - 1}$ are nonzero: for each $𝑖 < 𝑗$ , add $- 𝑎_{𝑖 𝑗} 𝑎_{𝑖 𝑖}^{- 1}$ times column $𝑖$ to column $𝑗$ . Since column $𝑖$ is $𝑎_{𝑖 𝑖} 𝐞_{𝑖}$ , this subtracts $𝑎_{𝑖 𝑗} 𝐞_{𝑖}$ from column $𝑗$ . After the step, column $𝑗$ is $𝑎_{𝑗 𝑗} 𝐞_{𝑗}$ , the other columns are unchanged, and $𝐷$ has not changed, by Lemma 5.1.8.

Column $1$ of $𝐴$ is already $𝑎_{11} 𝐞_{1}$ . Suppose first that all diagonal entries are nonzero. Performing the step for $𝑗 = 2, 3, \dots, 𝑛$ in turn, we reach $diag (𝑎_{11}, \dots, 𝑎_{𝑛 𝑛})$ , whose columns are $𝑎_{𝑗 𝑗} 𝐞_{𝑗}$ . Pulling the scalar $𝑎_{𝑗 𝑗}$ out of each column $𝑗$ by multilinearity,

𝐷 (𝐴) = 𝐷 (diag (𝑎_{11}, \dots, 𝑎_{𝑛 𝑛})) = 𝑎_{11} 𝑎_{22} \dots 𝑎_{𝑛 𝑛} 𝐷 (𝐼_{𝑛}) .

Suppose instead that some diagonal entry is $0$ , and let $𝑘$ be the least index with $𝑎_{𝑘 𝑘} = 0$ . If $𝑘 = 1$ , column $1$ of $𝐴$ is $𝟎$ . Otherwise, perform the step for $𝑗 = 2, \dots, 𝑘$ ; this uses only $𝑎_{11},$ $\dots,$ $𝑎_{𝑘 - 1, 𝑘 - 1}$ , which are nonzero. Afterwards column $𝑘$ is $𝑎_{𝑘 𝑘} 𝐞_{𝑘} = 𝟎$ . In both cases $𝐷 (𝐴)$ equals the value of $𝐷$ at a matrix with a zero column, which is $0$ by Exercise 5.1.5. And $𝑎_{11} \dots 𝑎_{𝑛 𝑛} 𝐷 (𝐼_{𝑛}) =$ $0$ as well, since the factor $𝑎_{𝑘 𝑘}$ is $0$ .

If $𝐴$ is lower triangular, the same argument works with the columns processed from right to left. Column $𝑛$ is $𝑎_{𝑛 𝑛} 𝐞_{𝑛}$ , column $𝑗$ is $𝑎_{𝑗 𝑗} 𝐞_{𝑗}$ plus a combination of $𝐞_{𝑗 + 1}, \dots, 𝐞_{𝑛}$ , and the step for $𝑗 = 𝑛 - 1, \dots, 1$ subtracts multiples of the columns to its right; if some diagonal entry is $0$ , take $𝑘$ to be the largest such index. □

The first proof is shorter, given the Leibniz formula. The second uses neither the formula nor permutations, only the axioms. It is the first instance of computing a determinant by column operations, which Section 5.4 turns into an algorithm.

In particular, $det diag (𝑑_{1}, \dots, 𝑑_{𝑛}) =$ $𝑑_{1} 𝑑_{2} \dots 𝑑_{𝑛}$ . If a triangular matrix has no zero diagonal entries, its determinant is nonzero, so it is invertible by Corollary 5.1.18. If it has a zero diagonal entry, its determinant is $0$ , and Theorem 5.4.7 will show that it is not invertible.

Exercise 5.3.16.routine

(a)Compute the determinants of
$(\begin{matrix} 2 & 7 & - 1 & 4 \\ 0 & - 1 & 3 & 5 \\ 0 & 0 & 3 & 8 \\ 0 & 0 & 0 & 1 / 2 \end{matrix}) \in ℚ^{4 \times 4}$
and
$(\begin{matrix} 𝑖 & 0 & 0 \\ 2 & 1 + 𝑖 & 0 \\ - 1 & 5 & 1 - 𝑖 \end{matrix}) \in ℂ^{3 \times 3} .$
(b)A matrix $𝑁 \in 𝐹^{𝑛 \times 𝑛}$ is strictly upper triangular if its $(𝑖, 𝑗)$ entry is $0$ whenever $𝑖 \geq 𝑗$ . Show that $det 𝑁 = 0$ and $det (𝑐 𝐼_{𝑛} + 𝑁) =$ $𝑐^{𝑛}$ for every $𝑐 \in 𝐹$ .

Solution.

Uses. Proposition 5.3.15 (Triangular matrices)

Hint 1. Both matrices in (a) are triangular. Multiply the diagonal entries.

Hint 2. In (b),

𝑁

and

𝑐 𝐼_{𝑛} + 𝑁

are upper triangular. What are their diagonal entries?

Sketch. (a)

2 \cdot (- 1) \cdot 3 \cdot 1 / 2 = - 3

and

𝑖 (1 + 𝑖) (1 - 𝑖) =

2 𝑖

. (b)

𝑁

is upper triangular with zero diagonal, and

𝑐 𝐼_{𝑛} + 𝑁

is upper triangular with every diagonal entry

𝑐

(a) The first matrix is upper triangular, so by Proposition 5.3.15 its determinant is $2 \cdot (- 1) \cdot 3 \cdot 1 / 2 = - 3$ . The second is lower triangular, so its determinant is $𝑖 (1 + 𝑖) (1 - 𝑖) =$ $𝑖 (1 - 𝑖^{2}) =$ $2 𝑖$ .

(b) A strictly upper triangular $𝑁$ is upper triangular with all diagonal entries $0$ , so $det 𝑁 = 0 \cdot \dots \cdot 0 = 0$ by Proposition 5.3.15 (here $𝑛 \geq 1$ ). The matrix $𝑐 𝐼_{𝑛} + 𝑁$ has $(𝑖, 𝑗)$ entry equal to that of $𝑁$ , which is $0$ , for $𝑖 > 𝑗$ , and $𝑐 + 0 = 𝑐$ on the diagonal, so it is upper triangular with all diagonal entries $𝑐$ , and $det (𝑐 𝐼_{𝑛} + 𝑁) =$ $𝑐^{𝑛}$ .

The same reading of the Leibniz formula handles matrices built from square blocks along the diagonal.

Proposition 5.3.17 (Block-diagonal matrices). Let $𝐴 \in 𝐹^{𝑘 \times 𝑘}$ and $𝐵 \in 𝐹^{𝑚 \times 𝑚}$ , and let

𝑀 = (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐵 \end{matrix}) \in 𝐹^{(𝑘 + 𝑚) \times (𝑘 + 𝑚)},

where the zero blocks are $𝑘 \times 𝑚$ and $𝑚 \times 𝑘$ (Definition 2.4.33). Then $det 𝑀 = det 𝐴 det 𝐵$ .

Proof (via uniqueness).standard

Uses. Theorem 5.3.4 (Existence and uniqueness of the determinant), Definition 5.1.1 (Determinant function), Proposition 2.1.17 (Compositions of linear maps are linear), Definition 2.4.33 (Block matrix)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. Fix

𝐵

and regard

det (\begin{matrix} 𝑋 & 0 \\ 0 & 𝐵 \end{matrix})

as a function of

𝑋 \in 𝐹^{𝑘 \times 𝑘}

. Which axioms does it satisfy?

Hint 2. It is multilinear and alternating in the columns of

𝑋

, so by Theorem 5.3.4 it equals its value at

𝐼_{𝑘}

times

det 𝑋

Hint 3. Then show that

𝑌 \mapsto det (\begin{matrix} 𝐼_{𝑘} & 0 \\ 0 & 𝑌 \end{matrix})

is a determinant function on

𝐹^{𝑚 \times 𝑚}

Sketch. For fixed

𝐵

𝑋 \mapsto det (\begin{matrix} 𝑋 & 0 \\ 0 & 𝐵 \end{matrix})

is multilinear and alternating in the columns of

𝑋

, whose columns enter as

(𝐱_{𝑗}, 𝟎)

. So it equals

det 𝑋 \cdot

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

. In turn

𝑌 \mapsto det (\begin{matrix} 𝐼_{𝑘} & 0 \\ 0 & 𝑌 \end{matrix})

is multilinear, alternating, and

1

𝐼_{𝑚}

, so it is

det

by uniqueness.

Fix $𝐵$ , and for $𝑋 \in 𝐹^{𝑘 \times 𝑘}$ let $𝐷 (𝑋) =$ $det (\begin{matrix} 𝑋 & 0 \\ 0 & 𝐵 \end{matrix})$ . For $𝑗 \leq 𝑘$ , column $𝑗$ of $(\begin{matrix} 𝑋 & 0 \\ 0 & 𝐵 \end{matrix})$ is $𝜄 (𝐱_{𝑗})$ , where $𝜄 : 𝐹^{𝑘} \to 𝐹^{𝑘 + 𝑚}$ , $𝐱 \mapsto (𝐱, 𝟎)$ , is linear; the other columns do not depend on $𝑋$ . So when all columns of $𝑋$ but the $𝑗$ -th are fixed, $𝐱 \mapsto 𝐷 (\dots, 𝐱, \dots)$ is the composite of $𝜄$ with a map that is linear because $det$ is linear in column $𝑗$ , and it is linear by Proposition 2.1.17. If two columns $𝐱_{𝑖}, 𝐱_{𝑗}$ of $𝑋$ are equal, then columns $𝑖$ and $𝑗$ of $(\begin{matrix} 𝑋 & 0 \\ 0 & 𝐵 \end{matrix})$ are equal, so $𝐷 (𝑋) = 0$ . Thus $𝐷$ is multilinear and alternating, and Theorem 5.3.4 gives

det 𝑀 = 𝐷 (𝐴) = 𝐷 (𝐼_{𝑘}) det 𝐴 = det (\begin{matrix} 𝐼_{𝑘} & 0 \\ 0 & 𝐵 \end{matrix}) \cdot det 𝐴 .

Now for $𝑌 \in 𝐹^{𝑚 \times 𝑚}$ let $𝐸 (𝑌) =$ $det (\begin{matrix} 𝐼_{𝑘} & 0 \\ 0 & 𝑌 \end{matrix})$ . For $𝑗 \leq 𝑚$ , column $𝑘 + 𝑗$ of this matrix is $(𝟎, 𝐲_{𝑗})$ , the image of $𝐲_{𝑗}$ under the linear map $𝐲 \mapsto (𝟎, 𝐲)$ , and the first $𝑘$ columns do not depend on $𝑌$ . The argument above shows that $𝐸$ is multilinear and alternating, and $𝐸 (𝐼_{𝑚}) =$ $det 𝐼_{𝑘 + 𝑚} =$ $1$ . So $𝐸$ is a determinant function on $𝐹^{𝑚 \times 𝑚}$ , and $𝐸 = det$ by Theorem 5.3.4. Hence $det 𝑀 = det 𝐵 det 𝐴$ , as desired. □

Proof (via the Leibniz formula).standard

Uses. Definition 5.3.6 (Determinant), Definition 5.2.23 (Sign of a permutation), Proposition 5.2.13 (Products of transpositions), Definition 5.2.10 (Transposition)

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

Hint 1. Write

𝑐_{𝑖 𝑗}

for the entries of

𝑀

and

𝑛 = 𝑘 + 𝑚

. If the term of

𝜎

is nonzero, where can

𝜎

send

1, \dots, 𝑘

Hint 2. Such a

𝜎

maps

[𝑘]

onto itself and

{𝑘 + 1, \dots, 𝑛}

onto itself, so it is made of a permutation

𝛼

[𝑘]

and a permutation

𝛽

[𝑚]

. Show that

sgn (𝜎) =

sgn (𝛼) sgn (𝛽)

by factoring

𝛼

and

𝛽

into transpositions.

Hint 3. Then the sum over these

𝜎

is a sum over pairs

(𝛼, 𝛽)

, and it factors.

Sketch. A nonzero term needs

𝜎 (𝑗) \leq 𝑘

for every

𝑗 \leq 𝑘

, so

𝜎

maps

[𝑘]

onto

[𝑘]

and the rest onto the rest. Such

𝜎

correspond to pairs

(𝛼, 𝛽) \in 𝑆_{𝑘} \times 𝑆_{𝑚}

, and factoring

𝛼

and

𝛽

into transpositions gives a factorization of

𝜎

, so

sgn (𝜎) =

sgn (𝛼) sgn (𝛽)

. The term of

𝜎

sgn (𝛼) \prod 𝑎_{𝛼 (𝑗) 𝑗} \cdot

sgn (𝛽) \prod 𝑏_{𝛽 (𝑖) 𝑖}

, and the double sum factors as

det 𝐴 det 𝐵

Let $𝑛 = 𝑘 + 𝑚$ , and write $𝑐_{𝑖 𝑗}$ for the $(𝑖, 𝑗)$ entry of $𝑀$ . So $𝑐_{𝑖 𝑗} = 𝑎_{𝑖 𝑗}$ for $𝑖, 𝑗 \leq 𝑘$ , $𝑐_{𝑘 + 𝑖, 𝑘 + 𝑗} =$ $𝑏_{𝑖 𝑗}$ for $𝑖, 𝑗 \leq 𝑚$ , and $𝑐_{𝑖 𝑗} = 0$ otherwise.

Let $𝜎 \in 𝑆_{𝑛}$ have a nonzero term. For $𝑗 \leq 𝑘$ , the entry $𝑐_{𝜎 (𝑗) 𝑗}$ is nonzero, so $𝜎 (𝑗) \leq 𝑘$ . Thus $𝜎$ maps $[𝑘]$ into $[𝑘]$ , hence onto $[𝑘]$ , being injective, and since $𝜎$ is a bijection it maps $𝐾 = {𝑘 + 1, \dots, 𝑛}$ onto $𝐾$ . Call such permutations block-preserving. A block-preserving $𝜎$ determines $𝛼 \in 𝑆_{𝑘}$ and $𝛽 \in 𝑆_{𝑚}$ by

𝛼 (𝑗) = 𝜎 (𝑗) (𝑗 \leq 𝑘), 𝛽 (𝑖) = 𝜎 (𝑘 + 𝑖) - 𝑘 (𝑖 \leq 𝑚),

and conversely every pair $(𝛼, 𝛽) \in 𝑆_{𝑘} \times 𝑆_{𝑚}$ arises from exactly one block-preserving $𝜎$ , namely the one given by these formulas.

Signs. Write $𝛼 = 𝜏_{1} \dots 𝜏_{𝑟}$ and $𝛽 = 𝜏_{1}^{'} \dots 𝜏_{𝑠}^{'}$ as products of transpositions (Proposition 5.2.13). If $𝜏_{𝑞} = (𝑝 𝑝^{'})$ in $𝑆_{𝑘}$ , let $𝜌_{𝑞} = (𝑝 𝑝^{'})$ in $𝑆_{𝑛}$ , and if $𝜏_{𝑞}^{'} = (𝑝 𝑝^{'})$ in $𝑆_{𝑚}$ , let $𝜌_{𝑞}^{'} =$ $(𝑘 + 𝑝 𝑘 + 𝑝^{'})$ in $𝑆_{𝑛}$ . Let $\hat{𝛼} = 𝜌_{1} \dots 𝜌_{𝑟}$ and $\hat{𝛽} = 𝜌_{1}^{'} \dots 𝜌_{𝑠}^{'}$ . Each $𝜌_{𝑞}$ fixes every point of $𝐾$ and acts on $[𝑘]$ as $𝜏_{𝑞}$ does, so $\hat{𝛼}$ agrees with $𝛼$ on $[𝑘]$ and fixes $𝐾$ . Similarly, $\hat{𝛽}$ fixes $[𝑘]$ and sends $𝑘 + 𝑖$ to $𝑘 + 𝛽 (𝑖)$ . Hence $\hat{𝛼} \hat{𝛽} = 𝜎$ : for $𝑗 \leq 𝑘$ , $\hat{𝛼} (\hat{𝛽} (𝑗)) =$ $𝛼 (𝑗) =$ $𝜎 (𝑗)$ , and for $𝑖 \leq 𝑚$ , $\hat{𝛼} (\hat{𝛽} (𝑘 + 𝑖)) =$ $\hat{𝛼} (𝑘 + 𝛽 (𝑖)) =$ $𝑘 +$ $𝛽 (𝑖) =$ $𝜎 (𝑘 + 𝑖)$ . So $𝜎$ is a product of $𝑟 + 𝑠$ transpositions, and $sgn (𝜎) =$ ${(- 1)}^{𝑟 + 𝑠} =$ $sgn (𝛼) sgn (𝛽)$ .

The sum. For block-preserving $𝜎$ , the entries in its term are $𝑐_{𝜎 (𝑗) 𝑗} =$ $𝑎_{𝛼 (𝑗) 𝑗}$ for $𝑗 \leq 𝑘$ and $𝑐_{𝜎 (𝑘 + 𝑖), 𝑘 + 𝑖} =$ $𝑐_{𝑘 + 𝛽 (𝑖), 𝑘 + 𝑖} =$ $𝑏_{𝛽 (𝑖) 𝑖}$ for $𝑖 \leq 𝑚$ . Since all other terms vanish,

\begin{aligned} det 𝑀 & = \sum_{𝛼 \in 𝑆_{𝑘}} \sum_{𝛽 \in 𝑆_{𝑚}} sgn (𝛼) sgn (𝛽) \prod_{𝑗 = 1}^{𝑘} 𝑎_{𝛼 (𝑗) 𝑗} \prod_{𝑖 = 1}^{𝑚} 𝑏_{𝛽 (𝑖) 𝑖} \\ = (\sum_{𝛼 \in 𝑆_{𝑘}} sgn (𝛼) \prod_{𝑗 = 1}^{𝑘} 𝑎_{𝛼 (𝑗) 𝑗}) (\sum_{𝛽 \in 𝑆_{𝑚}} sgn (𝛽) \prod_{𝑖 = 1}^{𝑚} 𝑏_{𝛽 (𝑖) 𝑖}) \\ = det 𝐴 det 𝐵 . \end{aligned}

□

The first proof is an instance of a pattern we will use repeatedly: to identify a function with $det$ , check that it is multilinear and alternating, and evaluate it at the identity. The second proof never used the upper right block of $𝑀$ , a point that Section 5.4 takes up for block-triangular matrices. Applying the proposition repeatedly, a block-diagonal matrix with any number of square diagonal blocks has determinant equal to the product of the determinants of the blocks.

5.3.5The determinant as a polynomial in the entries

The Leibniz formula computes $det 𝐴$ from the entries of $𝐴$ using only additions, subtractions, and multiplications: it is a sum of $𝑛!$ terms, each $\pm 1$ times a product of $𝑛$ entries. No division occurs. This has two useful consequences.

Technique 5.3.18 ( $det$ is a polynomial in the entries). By the Leibniz formula, $det 𝐴$ is a polynomial in the $𝑛^{2}$ entries of $𝐴$ with integer coefficients $\pm 1$ , each of whose monomials has degree $𝑛$ and uses one entry from each row and each column. So if the entries of a matrix depend polynomially on a parameter $𝑡$ , then so does its determinant, and the degree and the leading coefficients can be read off the formula with Technique 5.3.12. Similarly, any map that respects sums and products can be applied to $det 𝐴$ entry by entry: for example, complex conjugation (Exercise 5.3.28) and reduction modulo a prime (Technique 5.3.21).

Reach for it when a question asks how $det$ varies with a parameter, as for $det (𝐴 + 𝑡 𝐼_{𝑛})$ or $det (𝐴 + 𝑡 𝐵)$ , for how many values of $𝑡$ a matrix can fail to be invertible, or how $det$ interacts with an operation on the entries. The canonical example is Proposition 5.3.19.

Used in 11 places and 2 practice exercises

Proposition 5.3.19, Proposition 5.3.20, Exercise 5.3.28, Exercise 5.6.9, Exercise 5.6.12, Problem 5.11, Problem 5.16, Problem 5.17, Problem 5.18, Proposition 7.3.22, Lemma 7.6.21; 2 practice exercises.

Proposition 5.3.19 ( $det (𝐴 + 𝑡 𝐼_{𝑛})$ as a function of $𝑡$ ). Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . There are scalars $𝑐_{0},$ $𝑐_{1},$ $\dots,$ $𝑐_{𝑛 - 1} \in$ $𝐹$ , depending only on $𝐴$ , with $𝑐_{𝑛 - 1} = tr 𝐴$ and $𝑐_{0} = det 𝐴$ , such that

det (𝐴 + 𝑡 𝐼_{𝑛}) = 𝑡^{𝑛} + 𝑐_{𝑛 - 1} 𝑡^{𝑛 - 1} + \dots + 𝑐_{1} 𝑡 + 𝑐_{0}

for every $𝑡 \in 𝐹$ .

Proof.standard

Uses. Definition 5.3.6 (Determinant), Definition 2.4.26 (Trace), distributivity in $𝐹$

Techniques. Read structure off the Leibniz expansion (Technique 5.3.12), $det$ is a polynomial in the entries (Technique 5.3.18)

Hint 1. The

(𝑖, 𝑗)

entry of

𝐴 + 𝑡 𝐼_{𝑛}

𝑎_{𝑖 𝑗}

𝑖 \neq 𝑗

and

𝑎_{𝑗 𝑗} + 𝑡

𝑖 = 𝑗

. In the term of

𝜎

, which factors contain

𝑡

Hint 2. Only the factors

𝑎_{𝑗 𝑗} + 𝑡

with

𝜎 (𝑗) = 𝑗

. Show that a permutation

𝜎 \neq id

fixes at most

𝑛 - 2

points.

Hint 3. So only the identity contributes to

𝑡^{𝑛}

and

𝑡^{𝑛 - 1}

. Expand

(𝑎_{11} + 𝑡) \dots (𝑎_{𝑛 𝑛} + 𝑡)

. For

𝑐_{0}

, set

𝑡 = 0

Sketch. The term of

𝜎

has a factor

𝑎_{𝑗 𝑗} + 𝑡

for each fixed point

𝑗

𝜎

and constant factors otherwise, so expanding it gives powers of

𝑡

up to the number of fixed points. If

𝜎 \neq id

moves

𝑗

, it also moves

𝜎 (𝑗)

, so it fixes at most

𝑛 - 2

points. Hence

𝑡^{𝑛}

and

𝑡^{𝑛 - 1}

come only from

(𝑎_{11} + 𝑡) \dots (𝑎_{𝑛 𝑛} + 𝑡) =

𝑡^{𝑛} +

(𝑎_{11} + \dots + 𝑎_{𝑛 𝑛}) 𝑡^{𝑛 - 1} +

\dots

. Setting

𝑡 = 0

gives

𝑐_{0} = det 𝐴

The $(𝑖, 𝑗)$ entry of $𝐴 + 𝑡 𝐼_{𝑛}$ is $𝑎_{𝑖 𝑗}$ if $𝑖 \neq 𝑗$ and $𝑎_{𝑗 𝑗} + 𝑡$ if $𝑖 = 𝑗$ . For $𝜎 \in 𝑆_{𝑛}$ , let $Fix (𝜎) =$ ${𝑗 \in [𝑛] | 𝜎 (𝑗) = 𝑗}$ and $𝑓_{𝜎} = | Fix (𝜎) |$ . The term of $𝜎$ in $det (𝐴 + 𝑡 𝐼_{𝑛})$ is

𝑇_{𝜎} (𝑡) = sgn (𝜎) \prod_{𝑗 \notin Fix (𝜎)} 𝑎_{𝜎 (𝑗) 𝑗} \prod_{𝑗 \in Fix (𝜎)} (𝑎_{𝑗 𝑗} + 𝑡) .

Expanding the second product by distributivity, choosing either $𝑎_{𝑗 𝑗}$ or $𝑡$ from each factor, gives

\prod_{𝑗 \in Fix (𝜎)} (𝑎_{𝑗 𝑗} + 𝑡) = \sum_{𝑆 \subseteq Fix (𝜎)} (\prod_{𝑗 \in 𝑆} 𝑎_{𝑗 𝑗}) 𝑡^{𝑓_{𝜎} - | 𝑆 |} .

So $𝑇_{𝜎} (𝑡) =$ $\sum_{𝑝 = 0}^{𝑓_{𝜎}} 𝑒_{𝜎, 𝑝} 𝑡^{𝑝}$ , where

𝑒_{𝜎, 𝑝} = sgn (𝜎) \prod_{𝑗 \notin Fix (𝜎)} 𝑎_{𝜎 (𝑗) 𝑗} \sum_{𝑆 \subseteq Fix (𝜎), | 𝑆 | = 𝑓_{𝜎} - 𝑝} \prod_{𝑗 \in 𝑆} 𝑎_{𝑗 𝑗}

does not depend on $𝑡$ . Set $𝑒_{𝜎, 𝑝} = 0$ for $𝑓_{𝜎} < 𝑝 \leq 𝑛$ .

If $𝜎 \neq id$ , choose $𝑗$ with $𝜎 (𝑗) \neq 𝑗$ , and let $𝑖 = 𝜎 (𝑗)$ . Then $𝜎 (𝑖) \neq 𝑖$ , since otherwise $𝜎 (𝑖) = 𝑖 = 𝜎 (𝑗)$ with $𝑖 \neq 𝑗$ , contradicting injectivity. So $𝜎$ moves the two points $𝑖$ and $𝑗$ , and $𝑓_{𝜎} \leq 𝑛 - 2$ . Hence $𝑒_{𝜎, 𝑛} =$ $𝑒_{𝜎, 𝑛 - 1} =$ $0$ for $𝜎 \neq id$ . For $𝜎 = id$ we have $𝑓_{id} = 𝑛$ , and the subsets $𝑆 = \emptyset$ and $𝑆 = {𝑗}$ show that $𝑒_{id, 𝑛} = 1$ and $𝑒_{id, 𝑛 - 1} =$ $𝑎_{11} +$ $\dots +$ $𝑎_{𝑛 𝑛} =$ $tr 𝐴$ .

Summing over $𝜎$ , $det (𝐴 + 𝑡 𝐼_{𝑛}) =$ $\sum_{𝑝 = 0}^{𝑛} 𝑐_{𝑝} 𝑡^{𝑝}$ with $𝑐_{𝑝} = \sum_{𝜎} 𝑒_{𝜎, 𝑝}$ , and these scalars depend only on $𝐴$ . By the previous paragraph, $𝑐_{𝑛} = 1$ and $𝑐_{𝑛 - 1} = tr 𝐴$ . Finally, setting $𝑡 = 0$ gives $𝑐_{0} =$ $det (𝐴 + 0 𝐼_{𝑛}) =$ $det 𝐴$ . □

In particular, $𝐴 + 𝑡 𝐼_{𝑛}$ fails to be invertible for at most $𝑛$ values of $𝑡 \in 𝐹$ . Indeed, if $𝐴 + 𝑡 𝐼_{𝑛}$ is not invertible, then $det (𝐴 + 𝑡 𝐼_{𝑛}) = 0$ by Corollary 5.1.18, so $𝑡$ is a root of the polynomial $𝑥^{𝑛} +$ $𝑐_{𝑛 - 1} 𝑥^{𝑛 - 1} +$ $\dots +$ $𝑐_{0} \in$ $𝐹 [𝑥]$ , which has degree $𝑛$ and therefore at most $𝑛$ roots (Proposition 7.1.22). For $𝑛 = 2$ the proposition is Exercise 5.1.38. In Section 7.3, the values of $𝑡$ for which $det (𝐴 + 𝑡 𝐼_{𝑛}) = 0$ become, after a change of sign, the eigenvalues of $𝐴$ .

The proposition is about the coefficients $𝑐_{𝑝} = \sum_{𝜎} 𝑒_{𝜎, 𝑝}$ built in the proof, not about “the” coefficients of the function $𝑡 \mapsto det (𝐴 + 𝑡 𝐼_{𝑛})$ . Over a small field the function does not determine its coefficients: over $𝔽_{2}$ , $𝑡^{3} = 𝑡^{3} + 𝑡^{2} + 𝑡$ for both elements $𝑡$ . From Section 7.1 on, $det (𝐴 + 𝑥 𝐼_{𝑛})$ is a polynomial in $𝐹 [𝑥]$ with the coefficients $𝑐_{𝑝}$ .

The second consequence concerns matrices with integer entries. We regard such a matrix as an element of $ℚ^{𝑛 \times 𝑛}$ , and for a prime $𝑝$ we write $𝐴 \in 𝔽_{𝑝}^{𝑛 \times 𝑛}$ for the matrix with entries $𝑎_{𝑖 𝑗} mod 𝑝$ .

Proposition 5.3.20 (Reduction modulo

𝑝

). Let

𝐴 \in ℚ^{𝑛 \times 𝑛}

have integer entries, and let

𝑝

be a prime. Then

det 𝐴

is an integer, and

(det 𝐴) mod 𝑝 =

det 𝐴

, the determinant of

𝐴

computed in

𝔽_{𝑝}

Proof.routine

Uses. Definition 5.3.6 (Determinant), Lemma 1.1.21 (Arithmetic in $ℤ / 𝑛 ℤ$ ), Definition 1.1.19 (Integers modulo $𝑛$ )

Techniques. $det$ is a polynomial in the entries (Technique 5.3.18)

Hint 1. The Leibniz formula uses only sums, negatives, and products of the entries.

Hint 2. By Lemma 1.1.21, taking remainders modulo

𝑝

respects sums and products of two integers. Extend this to sums and products of many integers, and to negatives.

Sketch. Each term of

det 𝐴

\pm

a product of integers, so

det 𝐴 \in ℤ

. Reduction modulo

𝑝

respects sums, products, and negatives (Lemma 1.1.21, extended by induction), so reducing the Leibniz sum for

𝐴

term by term gives the Leibniz sum for

𝐴

𝔽_{𝑝}

Each term $sgn (𝜎) 𝑎_{𝜎 (1) 1} \dots 𝑎_{𝜎 (𝑛) 𝑛}$ is $\pm$ a product of integers, so $det 𝐴$ is an integer. Write $𝑟 (𝑥) = 𝑥 mod 𝑝$ for $𝑥 \in ℤ$ . By part (a) of Lemma 1.1.21, $𝑟 (𝑥 + 𝑦) =$ $𝑟 (𝑥) +$ $𝑟 (𝑦)$ and $𝑟 (𝑥 𝑦) =$ $𝑟 (𝑥) 𝑟 (𝑦)$ , with the operations on the right taken in $𝔽_{𝑝}$ . By induction on the number of terms or factors, $𝑟$ respects sums and products of any finite number of integers. It also respects negatives: $𝑟 (𝑥) +$ $𝑟 (- 𝑥) =$ $𝑟 (𝑥 + (- 𝑥)) =$ $𝑟 (0) =$ $0$ , so $𝑟 (- 𝑥) = - 𝑟 (𝑥)$ in $𝔽_{𝑝}$ . Applying $𝑟$ to the Leibniz formula for $𝐴$ therefore gives

𝑟 (det 𝐴) = \sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) 𝑟 (𝑎_{𝜎 (1) 1}) \dots 𝑟 (𝑎_{𝜎 (𝑛) 𝑛}),

where $sgn (𝜎) = \pm 1$ is now read in $𝔽_{𝑝}$ . The right side is the Leibniz formula for $𝐴$ , so $𝑟 (det 𝐴) = det 𝐴$ . □

Technique 5.3.21 (Reduce modulo $𝑝$ ). To show that a matrix with integer entries has nonzero determinant, and hence is invertible (Corollary 5.1.18), it is enough to find one prime $𝑝$ for which $det 𝐴 \neq 0$ in $𝔽_{𝑝}$ : then $(det 𝐴) mod 𝑝 \neq 0$ by Proposition 5.3.20, so $det 𝐴 \neq 0$ . Choose $𝑝$ so that $𝐴$ is simple, for instance triangular with nonzero diagonal entries or a permutation matrix, and there is no need to compute $det 𝐴$ itself. The converse inference is not available: $det 𝐴 = 0$ only says that $𝑝$ divides $det 𝐴$ .

Reach for it when an integer matrix has a recognizable pattern modulo a small prime, most often modulo $2$ , where the entries are just their parities and $sgn (𝜎) = 1$ for every $𝜎$ . The canonical example is Example 5.3.22.

Used in 5 places and 1 practice exercise

Exercise 5.3.23, Exercise 5.3.36, Exercise 5.3.40, Exercise 5.6.12, Problem 5.15; 1 practice exercise.

Example 5.3.22 (Odd diagonal, even elsewhere). Let $𝐴 \in ℚ^{𝑛 \times 𝑛}$ have integer entries, with $𝑎_{𝑖 𝑖}$ odd for every $𝑖$ and $𝑎_{𝑖 𝑗}$ even for $𝑖 \neq 𝑗$ . Then $𝐴 = 𝐼_{𝑛}$ in $𝔽_{2}^{𝑛 \times 𝑛}$ , so by Proposition 5.3.20, $(det 𝐴) mod 2 =$ $det 𝐼_{𝑛} =$ $1$ . So $det 𝐴$ is odd, in particular nonzero, and $𝐴$ is invertible by Corollary 5.1.18. For instance,

det (\begin{matrix} 3 & 2 & - 4 \\ 6 & 1 & 2 \\ 0 & 8 & 5 \end{matrix}) = - 285,

which is odd, as predicted.

Exercises

Exercise 5.3.23.routine Let

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

(a)Compute $det 𝐴$ over $ℚ$ with the rule of Sarrus.
(b)Find $det 𝐴$ for the reductions $𝐴$ of $𝐴$ modulo $2$ , $3$ , $5$ , and $7$ .
(c)Over $𝔽_{5}$ , find a nonzero $𝐱 \in 𝔽_{5}^{3}$ with $𝐴 𝐱 = 𝟎$ , and explain why this is consistent with (b).

Solution.

Uses. Corollary 5.3.9 (Rule of Sarrus), Proposition 5.3.20 (Reduction modulo $𝑝$ ), Proposition 5.1.17 (Dependent columns)

Techniques. Reduce modulo $𝑝$ (Technique 5.3.21)

Hint 1. The down-right diagonals give

1 \cdot 1 \cdot 1

0 \cdot 1 \cdot 1

, and

3 \cdot 3 \cdot 4

Hint 2. For (b), reduce the answer to (a) instead of recomputing (Proposition 5.3.20).

Hint 3. For (c), solve the system row by row over

𝔽_{5}

, starting with

𝑥_{1} + 3 𝑥_{3} = 0

Sketch. (a)

(1 + 0 + 36) -

(3 + 4 + 0) =

30

. (b)

30 = 2 \cdot 3 \cdot 5

, so

det 𝐴

0

modulo

2

3

5

, and

2

modulo

7

. (c)

𝐱 = (2, 3, 1)

; a dependence among the columns forces

det 𝐴 = 0

, matching

5 ∣ 30

(a) The diagonals running down to the right have products $1 \cdot 1 \cdot 1 = 1$ , $0 \cdot 1 \cdot 1 = 0$ , and $3 \cdot 3 \cdot 4 = 36$ ; the diagonals running up to the right have products $1 \cdot 1 \cdot 3 = 3$ , $4 \cdot 1 \cdot 1 = 4$ , and $1 \cdot 3 \cdot 0 = 0$ . By Corollary 5.3.9, $det 𝐴 = 37 - 7 = 30$ .

(b) By Proposition 5.3.20, $det 𝐴 = 30 mod 𝑝$ . Since $30 = 2 \cdot 3 \cdot 5$ , we get $det 𝐴 = 0$ for $𝑝 = 2, 3, 5$ , and $det 𝐴 = 30 mod 7 = 2$ for $𝑝 = 7$ .

(c) Over $𝔽_{5}$ , the rows of $𝐴 𝐱 = 𝟎$ read $𝑥_{1} + 3 𝑥_{3} = 0$ , $3 𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 0$ , and $𝑥_{1} + 4 𝑥_{2} + 𝑥_{3} = 0$ . The first gives $𝑥_{1} = - 3 𝑥_{3} = 2 𝑥_{3}$ , and then the second gives $𝑥_{2} = - 7 𝑥_{3} = 3 𝑥_{3}$ . With $𝑥_{3} = 1$ , $𝐱 = (2, 3, 1)$ , and the third row checks: $2 + 12 + 1 = 15 = 0$ . So $2 𝐚_{1} + 3 𝐚_{2} + 𝐚_{3} = 𝟎$ is a nontrivial dependence among the columns of $𝐴$ , which forces $det 𝐴 = 0$ by Proposition 5.1.17. This agrees with (b), since $5 ∣ 30$ .

Exercise 5.3.24.routine Let

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

Each column of $𝐵$ has exactly two nonzero entries. Find the permutations $𝜎 \in 𝑆_{4}$ whose terms in the Leibniz formula are nonzero, and compute $det 𝐵$ .

Solution.

Uses. Definition 5.3.6 (Determinant), Proposition 5.2.26 (Sign of a cycle), Proposition 5.2.25 (Multiplicativity of the sign)

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

Hint 1. The term of

𝜎

is nonzero exactly when

𝜎 (𝑗)

is one of the two rows where column

𝑗

is nonzero, for every

𝑗

Hint 2. Columns

1

and

3

are nonzero only in rows

2

and

4

, and columns

2

and

4

only in rows

1

and

3

. So

𝜎

must send

{1, 3}

onto

{2, 4}

and

{2, 4}

onto

{1, 3}

Sketch. The surviving

𝜎

, written as bottom rows, are

2, 1, 4, 3

(even, product

120

2, 3, 4, 1

4

-cycle, product

15

4, 1, 2, 3

4

-cycle, product

8

), and

4, 3, 2, 1

(even, product

1

). So

det 𝐵 =

120 -

15 -

8 +

1 =

98

The term of $𝜎$ is nonzero exactly when $𝑏_{𝜎 (𝑗) 𝑗} \neq 0$ for every $𝑗$ . Column $1$ is nonzero in rows $2$ and $4$ , column $2$ in rows $1$ and $3$ , column $3$ in rows $2$ and $4$ , and column $4$ in rows $1$ and $3$ . Since $𝜎$ is injective, $𝜎 (1)$ and $𝜎 (3)$ are the two rows $2$ and $4$ in some order, and $𝜎 (2)$ and $𝜎 (4)$ are $1$ and $3$ in some order. So exactly $2 \cdot 2 = 4$ permutations survive. Writing $𝜎$ by its bottom row $𝜎 (1),$ $𝜎 (2),$ $𝜎 (3),$ $𝜎 (4)$ :

$2, 1, 4, 3$ , that is, $(1 2) (3 4)$ , which is even, with product $𝑏_{21} 𝑏_{12} 𝑏_{43} 𝑏_{34} =$ $3 \cdot$ $2 \cdot$ $5 \cdot$ $4 =$ $120$ ;
$2, 3, 4, 1$ , that is, $(1 2 3 4)$ , which is odd by Proposition 5.2.26, with product $𝑏_{21} 𝑏_{32} 𝑏_{43} 𝑏_{14} =$ $3 \cdot$ $1 \cdot$ $5 \cdot$ $1 =$ $15$ ;
$4, 1, 2, 3$ , that is, $(1 4 3 2)$ , which is odd, with product $𝑏_{41} 𝑏_{12} 𝑏_{23} 𝑏_{34} =$ $1 \cdot$ $2 \cdot$ $1 \cdot$ $4 =$ $8$ ;
$4, 3, 2, 1$ , that is, $(1 4) (2 3)$ , which is even, with product $𝑏_{41} 𝑏_{32} 𝑏_{23} 𝑏_{14} =$ $1$ .

(The products of two disjoint transpositions are even by Proposition 5.2.25.) Hence $det 𝐵 =$ $120 -$ $15 -$ $8 +$ $1 =$ $98$ .

Exercise 5.3.25.routine Find the errors in the following argument, and give a matrix for which the claim fails.

Claim. For $𝐴 \in 𝐹^{4 \times 4}$ , write the four columns of $𝐴$ followed by its first three columns again. Then $det 𝐴$ is the sum of the products along the four diagonals running down and to the right from $𝑎_{11},$ $𝑎_{12},$ $𝑎_{13},$ $𝑎_{14}$ , minus the sum of the products along the four diagonals running up and to the right from $𝑎_{41},$ $𝑎_{42},$ $𝑎_{43},$ $𝑎_{44}$ .

Proof. By the Leibniz formula, $det 𝐴$ is a signed sum of products of four entries, one from each row and one from each column. Each of the eight diagonals is such a product. The diagonals running down correspond to cyclic shifts of the columns, which have sign $+ 1$ , and the diagonals running up have sign $- 1$ , exactly as in the rule of Sarrus.

Solution.

Uses. Definition 5.3.6 (Determinant), Proposition 5.2.26 (Sign of a cycle), Theorem 5.2.31 (Alternating functions and permutations), Remark 5.3.11 (Sarrus does not generalize)

Hint 1. How many terms does the Leibniz formula have for

𝑛 = 4

? How many products does the claim produce?

Hint 2. The diagonal from

𝑎_{12}

𝑎_{12} 𝑎_{23} 𝑎_{34} 𝑎_{41}

. Which permutation is this the term of, and what is its sign?

Hint 3. Try a permutation matrix whose nonzero entries are not all on one diagonal, such as

𝐼_{4}

with its first two columns interchanged.

Sketch. The argument shows that each diagonal is a term, not that each term is a diagonal:

8

diagonals cover only

8

of the

24

terms. And the signs are not those of the permutations: the downward diagonals from

𝑎_{12}

and

𝑎_{14}

are terms of

4

-cycles, which are odd, and the upward diagonals from

𝑎_{41}

and

𝑎_{43}

are terms of even products of two transpositions. For

𝐼_{4}

with columns

1

and

2

interchanged, every diagonal contains a

0

, so the claim gives

0

, but

det = - 1

There are two errors. First, the argument shows that each diagonal is a term of the Leibniz formula, but not that each term is a diagonal. There are $4! = 24$ terms and only $8$ diagonals, so $16$ terms are missing. For example, the term $𝑎_{21} 𝑎_{12} 𝑎_{33} 𝑎_{44}$ of $(1 2)$ lies on no diagonal. Second, the signs are wrong. The diagonal from $𝑎_{12}$ is $𝑎_{12} 𝑎_{23} 𝑎_{34} 𝑎_{41}$ , the term of the permutation $𝜎$ with $𝜎 (2) = 1$ , $𝜎 (3) = 2$ , $𝜎 (4) = 3$ , $𝜎 (1) = 4$ , which is the $4$ -cycle $(1 4 3 2)$ . By Proposition 5.2.26 it is odd, so this product enters $det 𝐴$ with sign $- 1$ , while the claim adds it. The same happens for the downward diagonal from $𝑎_{14}$ , the term of the $4$ -cycle $(1 2 3 4)$ , and in the other direction for the upward diagonals from $𝑎_{41}$ and $𝑎_{43}$ , the terms of the even permutations $(1 4) (2 3)$ and $(1 2) (3 4)$ , which the claim subtracts. Only the four diagonals from $𝑎_{11}$ , $𝑎_{13}$ , $𝑎_{42}$ , and $𝑎_{44}$ get the right sign. For $𝑛 = 3$ the downward diagonals are $id$ and two $3$ -cycles, which are even, and the upward ones are transpositions; that is why the rule of Sarrus works (Remark 5.3.11).

Each error gives a counterexample. Let $𝐴$ be $𝐼_{4}$ with columns $1$ and $2$ interchanged, so its nonzero entries are $𝑎_{21} =$ $𝑎_{12} =$ $𝑎_{33} =$ $𝑎_{44} =$ $1$ . Then $det 𝐴 = - det 𝐼_{4} = - 1$ by Theorem 5.2.31. But every diagonal contains a zero entry: the downward diagonals start at $𝑎_{11} = 0$ , $𝑎_{12}$ (followed by $𝑎_{23} = 0$ ), $𝑎_{13} = 0$ , and $𝑎_{14} = 0$ , and the upward ones start at $𝑎_{41} = 𝑎_{42} = 𝑎_{43} = 0$ and at $𝑎_{44}$ (followed by $𝑎_{31} = 0$ ). So the claim gives $0$ . If $1 + 1 \neq 0$ in $𝐹$ , the sign error gives a second counterexample: let $𝐴$ be the permutation matrix whose nonzero entries are exactly $𝑎_{12},$ $𝑎_{23},$ $𝑎_{34},$ $𝑎_{41}$ . Then $det 𝐴 =$ $sgn ((1 4 3 2)) =$ $- 1$ , while every diagonal except the one from $𝑎_{12}$ contains a $0$ , so the claim gives $+ 1 \neq - 1$ .

Exercise 5.3.26.standard

(a)Find the error in the following argument.
Claim. $det (𝐴 + 𝐵) =$ $det 𝐴 +$ $det 𝐵$ for all $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ .
Proof. By the Leibniz formula,
$\begin{aligned} det (𝐴 + 𝐵) & = \sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) \prod_{𝑗 = 1}^{𝑛} (𝑎_{𝜎 (𝑗) 𝑗} + 𝑏_{𝜎 (𝑗) 𝑗}) \\ = \sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) (\prod_{𝑗 = 1}^{𝑛} 𝑎_{𝜎 (𝑗) 𝑗} + \prod_{𝑗 = 1}^{𝑛} 𝑏_{𝜎 (𝑗) 𝑗}) = det 𝐴 + det 𝐵 . \end{aligned}$
(b)For $𝑆 \subseteq [𝑛]$ , let $𝐶_{𝑆}$ be the matrix whose column $𝑗$ is $𝐚_{𝑗}$ if $𝑗 \in 𝑆$ and $𝐛_{𝑗}$ if $𝑗 \notin 𝑆$ . Show that $det (𝐴 + 𝐵) =$ $\sum_{𝑆 \subseteq [𝑛]} det 𝐶_{𝑆}$ .

Solution.

Uses. Definition 5.3.6 (Determinant), Lemma 5.3.2 (Expanding every column), Proposition 5.3.15 (Triangular matrices)

Techniques. Expand by multilinearity (Technique 5.1.7)

Hint 1. Is

(𝑥_{1} + 𝑦_{1}) (𝑥_{2} + 𝑦_{2}) =

𝑥_{1} 𝑥_{2} +

𝑦_{1} 𝑦_{2}

? Test the claim with two diagonal matrices that add up to

𝐼_{𝑛}

Hint 2. For (b), expand the product

\prod_{𝑗} (𝑎_{𝜎 (𝑗) 𝑗} + 𝑏_{𝜎 (𝑗) 𝑗})

by choosing one of the two summands in each factor, and record the set

𝑆

𝑗

where you chose

𝑎

Sketch. The second equality replaces a product of sums by the sum of two products; a product of

𝑛

sums expands into

2^{𝑛}

terms. With

𝐴 =

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

and

𝐵 =

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

det 𝐴 = det 𝐵 = 0

but

det (𝐴 + 𝐵) =

det 𝐼_{𝑛} =

1

. For (b),

\prod_{𝑗} (𝑎_{𝜎 (𝑗) 𝑗} + 𝑏_{𝜎 (𝑗) 𝑗}) =

\sum_{𝑆} \prod_{𝑗 \in 𝑆} 𝑎_{𝜎 (𝑗) 𝑗} \prod_{𝑗 \notin 𝑆} 𝑏_{𝜎 (𝑗) 𝑗}

, and exchanging the sums over

𝜎

and

𝑆

gives

\sum_{𝑆} det 𝐶_{𝑆}

(a) The second equality is false. A product of $𝑛$ sums is not the sum of the two “pure” products: by distributivity, $\prod_{𝑗 = 1}^{𝑛} (𝑥_{𝑗} + 𝑦_{𝑗})$ is a sum of $2^{𝑛}$ terms, one for each way of choosing $𝑥_{𝑗}$ or $𝑦_{𝑗}$ in each factor, and the argument keeps only the two terms that choose $𝑥$ every time or $𝑦$ every time. For every $𝑛 \geq 2$ and every field the claim is false: let $𝐴 =$ $diag (1, 0, 1, \dots, 1)$ and $𝐵 =$ $diag (0, 1, 0, \dots, 0)$ . Each has a zero diagonal entry, so $det 𝐴 = det 𝐵 = 0$ by Proposition 5.3.15, while $𝐴 + 𝐵 = 𝐼_{𝑛}$ has determinant $1$ . (For $𝑛 = 1$ the claim is true, since then each product has a single factor.)

(b) For each $𝜎$ , distributivity gives

\prod_{𝑗 = 1}^{𝑛} (𝑎_{𝜎 (𝑗) 𝑗} + 𝑏_{𝜎 (𝑗) 𝑗}) = \sum_{𝑆 \subseteq [𝑛]} \prod_{𝑗 \in 𝑆} 𝑎_{𝜎 (𝑗) 𝑗} \prod_{𝑗 \notin 𝑆} 𝑏_{𝜎 (𝑗) 𝑗},

where $𝑆$ records the factors in which $𝑎_{𝜎 (𝑗) 𝑗}$ was chosen. The $(𝑖, 𝑗)$ entry of $𝐶_{𝑆}$ is $𝑎_{𝑖 𝑗}$ if $𝑗 \in 𝑆$ and $𝑏_{𝑖 𝑗}$ if $𝑗 \notin 𝑆$ , so the term for $𝑆$ is $\prod_{𝑗} {(𝐶_{𝑆})}_{𝜎 (𝑗) 𝑗}$ . Multiplying by $sgn (𝜎)$ , summing over $𝜎$ , and exchanging the two finite sums,

det (𝐴 + 𝐵) = \sum_{𝑆 \subseteq [𝑛]} \sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) \prod_{𝑗 = 1}^{𝑛} {(𝐶_{𝑆})}_{𝜎 (𝑗) 𝑗} = \sum_{𝑆 \subseteq [𝑛]} det 𝐶_{𝑆} .

The same identity follows from multilinearity alone, by expanding each column $𝐚_{𝑗} + 𝐛_{𝑗}$ as in Lemma 5.3.2. So it holds for every multilinear $𝐷$ in place of $det$ ; the terms $𝑆 = [𝑛]$ and $𝑆 = \emptyset$ are $det 𝐴$ and $det 𝐵$ , and the other $2^{𝑛} - 2$ terms are what the argument in (a) dropped.

Exercise 5.3.27.standard The axioms concern columns. This exercise shows, directly from the Leibniz formula, that $det$ behaves the same way with respect to rows.

(a)Show that $det$ is linear in each row of $𝐴$ when the other rows are held fixed.
(b)Show that $det 𝐴 = 0$ if two rows of $𝐴$ are equal.
(c)Let $𝑑_{1}, \dots, 𝑑_{𝑛} \in 𝐹$ and $Λ =$ $diag (𝑑_{1}, \dots, 𝑑_{𝑛})$ . Show that $det (Λ 𝐴) =$ $det (𝐴 Λ) =$ $𝑑_{1} \dots 𝑑_{𝑛} det 𝐴$ .

Solution.

Uses. Definition 5.3.6 (Determinant), Proposition 5.2.25 (Multiplicativity of the sign), Proposition 5.2.27 (Half of all permutations are even), Definition 5.1.1 (Determinant function), Theorem 5.3.4 (Existence and uniqueness of the determinant)

Techniques. Cancel terms in pairs (Technique 5.3.5)

Hint 1. (a) In the term of

𝜎

, which entry comes from row

𝑟

? Imitate the multilinearity part of the proof of Theorem 5.3.4.

Hint 2. (b) If rows

𝑟

and

𝑠

are equal, compare the terms of

𝜎

and

𝜏 𝜎

, where

𝜏 = (𝑟 𝑠)

; note that the transposition now acts on the left.

Hint 3. (c) Row

𝑖

Λ 𝐴

𝑑_{𝑖}

times row

𝑖

𝐴

, and column

𝑗

𝐴 Λ

𝑑_{𝑗} 𝐚_{𝑗}

Sketch. (a) The term of

𝜎

contains exactly one entry of row

𝑟

, namely

𝑎_{𝑟 𝜎^{- 1} (𝑟)}

, so

det

is a fixed linear combination of the entries of row

𝑟

. (b) If rows

𝑟, 𝑠

are equal and

𝜏 = (𝑟 𝑠)

, then

𝑎_{𝜏 (𝜎 (𝑗)) 𝑗} =

𝑎_{𝜎 (𝑗) 𝑗}

for all

𝑗

and

sgn (𝜏 𝜎) =

- sgn (𝜎)

; pair each even

𝜎

with

𝜏 𝜎

. (c) Pull

𝑑_{𝑖}

out of each row by (a), and out of each column by multilinearity.

(a) Fix $𝑟 \in [𝑛]$ and all rows except row $𝑟$ , and let $𝐱 = (𝑥_{1}, \dots, 𝑥_{𝑛})$ be row $𝑟$ , so $𝑎_{𝑟 𝑗} = 𝑥_{𝑗}$ . In the term of $𝜎$ , the entry from row $𝑟$ is $𝑎_{𝜎 (𝑗) 𝑗}$ for the unique $𝑗$ with $𝜎 (𝑗) = 𝑟$ , that is, $𝑗 = 𝜎^{- 1} (𝑟)$ . So

det 𝐴 = \sum_{𝜎 \in 𝑆_{𝑛}} 𝑏_{𝜎} 𝑥_{𝜎^{- 1} (𝑟)}, where 𝑏_{𝜎} = sgn (𝜎) \prod_{𝑗 \neq 𝜎^{- 1} (𝑟)} 𝑎_{𝜎 (𝑗) 𝑗}

does not depend on $𝐱$ . As in the proof of Theorem 5.3.4, a function of this form is linear in $𝐱$ .

(b) Suppose rows $𝑟 \neq 𝑠$ are equal, so $𝑎_{𝑟 𝑗} = 𝑎_{𝑠 𝑗}$ for every $𝑗$ , and let $𝜏 = (𝑟 𝑠)$ . For every $𝑗$ , $𝜏 (𝜎 (𝑗))$ equals $𝜎 (𝑗)$ unless $𝜎 (𝑗) \in {𝑟, 𝑠}$ , in which case it is the other element of ${𝑟, 𝑠}$ ; since rows $𝑟$ and $𝑠$ are equal, $𝑎_{𝜏 (𝜎 (𝑗)) 𝑗} =$ $𝑎_{𝜎 (𝑗) 𝑗}$ in all cases. Also $sgn (𝜏 𝜎) =$ $- sgn (𝜎)$ by Proposition 5.2.25. So the term of $𝜏 𝜎$ is the negative of the term of $𝜎$ . The map $𝜎 \mapsto 𝜏 𝜎$ maps even permutations to odd ones and odd ones to even ones, and it is its own inverse, so it maps the set $𝑆_{𝑛}^{+}$ of even permutations bijectively onto the set of odd ones (as in the proof of Proposition 5.2.27). Hence

det 𝐴 = \sum_{𝜎 \in 𝑆_{𝑛}^{+}} (𝑡_{𝜎} (𝐴) + 𝑡_{𝜏 𝜎} (𝐴)) = 0,

where $𝑡_{𝜎} (𝐴)$ denotes the term of $𝜎$ .

(c) Row $𝑖$ of $Λ 𝐴$ is $𝑑_{𝑖}$ times row $𝑖$ of $𝐴$ . Pulling the factor $𝑑_{𝑖}$ out of row $𝑖$ for each $𝑖$ , by (a), gives $det (Λ 𝐴) =$ $𝑑_{1} \dots 𝑑_{𝑛} det 𝐴$ . Column $𝑗$ of $𝐴 Λ$ is $𝑑_{𝑗} 𝐚_{𝑗}$ , and pulling the factors out of the columns by multilinearity gives $det (𝐴 Λ) =$ $𝑑_{1} \dots 𝑑_{𝑛} det 𝐴$ .

Here is what (a) and (b) mean. Let $𝐷 (𝐴) = det 𝐴^{𝖳}$ . The columns of $𝐴$ are the rows of $𝐴^{𝖳}$ , so by (a) and (b), $𝐷$ is multilinear and alternating, and $𝐷 (𝐼_{𝑛}) = 1$ . By Theorem 5.3.4, $𝐷 = det$ , that is, $det 𝐴^{𝖳} = det 𝐴$ ; Theorem 5.4.14 records this.

Exercise 5.3.28.routine For $𝑧 = 𝑥 + 𝑦 𝑖 \in ℂ$ with $𝑥, 𝑦 \in ℝ$ , let $𝑧 = 𝑥 - 𝑦 𝑖$ , and for $𝐴 \in ℂ^{𝑛 \times 𝑛}$ let $𝐴$ be the matrix with entries $𝑎_{𝑖 𝑗}$ .

(a)Show that $det 𝐴 = det 𝐴$ . Deduce that a matrix with real entries has a real determinant.
(b)Suppose every entry of $𝐴 \in ℂ^{𝑛 \times 𝑛}$ is purely imaginary, that is, $𝐴 = - 𝐴$ . Show that $det 𝐴$ is real if $𝑛$ is even and purely imaginary if $𝑛$ is odd.

Solution.

Uses. Definition 5.3.6 (Determinant), Definition 1.1.29 (Complex numbers), Exercise 5.1.5

Techniques. $det$ is a polynomial in the entries (Technique 5.3.18)

Hint 1. Check that

𝑧 + 𝑤 = 𝑧 + 𝑤

and

𝑧 𝑤 = 𝑧 \cdot 𝑤

, and apply this to the Leibniz formula.

Hint 2. For (b), compute

det 𝐴

in two ways: by (a), and as

det (- 𝐴)

Sketch. Conjugation respects sums and products, and fixes

\pm 1

, so conjugating the Leibniz formula for

𝐴

term by term gives the formula for

𝐴

. A real

𝐴

has

𝐴 = 𝐴

, so

det 𝐴 = det 𝐴

is real. In (b),

det 𝐴 =

det (- 𝐴) =

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

(a) For $𝑧 = 𝑥 + 𝑦 𝑖$ and $𝑤 = 𝑢 + 𝑣 𝑖$ , we have $𝑧 + 𝑤 =$ $(𝑥 + 𝑢) -$ $(𝑦 + 𝑣) 𝑖 =$ $𝑧 +$ $𝑤$ , and

𝑧 \cdot 𝑤 = (𝑥 - 𝑦 𝑖) (𝑢 - 𝑣 𝑖) = (𝑥 𝑢 - 𝑦 𝑣) - (𝑥 𝑣 + 𝑦 𝑢) 𝑖 = 𝑧 𝑤,

since $𝑧 𝑤 =$ $(𝑥 𝑢 - 𝑦 𝑣) +$ $(𝑥 𝑣 + 𝑦 𝑢) 𝑖$ . By induction, conjugation respects finite sums and products, and it fixes the real numbers $\pm 1$ . Conjugating the Leibniz formula term by term,

det 𝐴 = \sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) 𝑎_{𝜎 (1) 1} \dots 𝑎_{𝜎 (𝑛) 𝑛} = det 𝐴 .

If every entry of $𝐴$ is real, then $𝐴 = 𝐴$ , so $det 𝐴 = det 𝐴$ , which says that $det 𝐴$ is real.

(b) By (a) and Exercise 5.1.5, $det 𝐴 =$ $det 𝐴 =$ $det (- 𝐴) =$ ${(- 1)}^{𝑛} det 𝐴$ . If $𝑛$ is even, $det 𝐴 = det 𝐴$ , so $det 𝐴$ is real. If $𝑛$ is odd, $det 𝐴 = - det 𝐴$ , so the real part of $det 𝐴$ is $0$ : $det 𝐴$ is purely imaginary.

Exercise 5.3.29.standard Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , and suppose there are sets $𝑅, 𝐶 \subseteq [𝑛]$ with $| 𝑅 | + | 𝐶 | > 𝑛$ such that $𝑎_{𝑖 𝑗} = 0$ for all $𝑖 \in 𝑅$ and $𝑗 \in 𝐶$ . (So $𝐴$ has an $| 𝑅 | \times | 𝐶 |$ block of zeros, after rearranging rows and columns.)

(a)Show that $det 𝐴 = 0$ .
(b)Deduce from (a) that an upper triangular matrix with a zero diagonal entry has determinant $0$ .
(c)Show that the hypothesis $| 𝑅 | + | 𝐶 | > 𝑛$ cannot be weakened to $| 𝑅 | + | 𝐶 | = 𝑛$ , for any $𝑛 \geq 2$ and any $| 𝑅 | = 𝑟$ with $1 \leq 𝑟 \leq 𝑛 - 1$ .

Solution.

Uses. Definition 5.3.6 (Determinant), Theorem 5.2.31 (Alternating functions and permutations), Definition 5.2.29 (Permutation matrix)

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

Hint 1. Fix

𝜎

. The rows

𝜎 (𝑗)

for

𝑗 \in 𝐶

are

| 𝐶 |

different rows. Can they all avoid

𝑅

Hint 2. For (b), if

𝑎_{𝑘 𝑘} = 0

, take

𝑅 = {𝑘, \dots, 𝑛}

and

𝐶 = {1, \dots, 𝑘}

Hint 3. For (c), look for a permutation matrix whose first

𝑠 = 𝑛 - 𝑟

columns have their

1

s below row

𝑟

Sketch. (a) The

| 𝐶 |

distinct rows

𝜎 (𝑗)

𝑗 \in 𝐶

, cannot all lie in

[𝑛] ∖ 𝑅

, which has fewer than

| 𝐶 |

elements; so some

𝑎_{𝜎 (𝑗) 𝑗}

with

𝑗 \in 𝐶

lies in the zero block, and every term vanishes. (b) A zero at

(𝑘, 𝑘)

in an upper triangular matrix gives a zero block on rows

𝑘, \dots, 𝑛

and columns

1, \dots, 𝑘

, of total size

𝑛 + 1

. (c) The permutation matrix with columns

𝐞_{𝑟 + 1},

\dots,

𝐞_{𝑛},

𝐞_{1},

\dots,

𝐞_{𝑟}

has a zero

𝑟 \times (𝑛 - 𝑟)

block in its upper left corner and determinant

\pm 1

(a) Let $𝜎 \in 𝑆_{𝑛}$ . The rows $𝜎 (𝑗)$ for $𝑗 \in 𝐶$ are $| 𝐶 |$ distinct elements of $[𝑛]$ . The set $[𝑛] ∖ 𝑅$ has $𝑛 - | 𝑅 | < | 𝐶 |$ elements, so not all of these rows lie in it: there is $𝑗 \in 𝐶$ with $𝜎 (𝑗) \in 𝑅$ . Then $𝑎_{𝜎 (𝑗) 𝑗} = 0$ , and the term of $𝜎$ vanishes. Since every term vanishes, $det 𝐴 = 0$ .

(b) Let $𝐴$ be upper triangular with $𝑎_{𝑘 𝑘} = 0$ , and let $𝑅 = {𝑘, 𝑘 + 1, \dots, 𝑛}$ and $𝐶 = {1, 2, \dots, 𝑘}$ . For $𝑖 \in 𝑅$ and $𝑗 \in 𝐶$ we have $𝑖 \geq 𝑘 \geq 𝑗$ , so either $𝑖 > 𝑗$ , and $𝑎_{𝑖 𝑗} = 0$ because $𝐴$ is upper triangular, or $𝑖 = 𝑗 = 𝑘$ , and $𝑎_{𝑖 𝑗} = 𝑎_{𝑘 𝑘} = 0$ . Since $| 𝑅 | +$ $| 𝐶 | =$ $(𝑛 - 𝑘 + 1) +$ $𝑘 =$ $𝑛 +$ $1 >$ $𝑛$ , part (a) gives $det 𝐴 = 0$ , in agreement with Proposition 5.3.15.

(c) Let $1 \leq 𝑟 \leq 𝑛 - 1$ and $𝑠 = 𝑛 - 𝑟$ . Let $𝐴$ be the matrix with columns $𝐞_{𝑟 + 1},$ $\dots,$ $𝐞_{𝑛},$ $𝐞_{1},$ $\dots,$ $𝐞_{𝑟}$ , that is, the permutation matrix $𝐸_{𝜎}$ with $𝜎 (𝑗) = 𝑟 + 𝑗$ for $𝑗 \leq 𝑠$ and $𝜎 (𝑗) = 𝑗 - 𝑠$ for $𝑗 > 𝑠$ (Definition 5.2.29). For $𝑖 \in 𝑅 = {1, \dots, 𝑟}$ and $𝑗 \in 𝐶 = {1, \dots, 𝑠}$ , the column $𝐞_{𝑟 + 𝑗}$ has a $0$ in row $𝑖 \leq 𝑟$ , so $𝑎_{𝑖 𝑗} = 0$ , and $| 𝑅 | + | 𝐶 | = 𝑛$ . But $det 𝐴 =$ $sgn (𝜎) =$ $\pm 1 \neq$ $0$ by Theorem 5.2.31.

Exercise 5.3.30.standard Prove or disprove each statement.

(a)If every entry of $𝐴 \in ℝ^{𝑛 \times 𝑛}$ is nonzero, then $det 𝐴 \neq 0$ .
(b)If $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ has exactly $𝑛$ nonzero entries and $det 𝐴 \neq 0$ , then each row and each column of $𝐴$ contains exactly one nonzero entry.
(c)If $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ is upper triangular, then $det 𝐴^{𝖳} = det 𝐴$ .
(d)If $𝑁 \in 𝐹^{𝑛 \times 𝑛}$ is strictly upper triangular (Exercise 5.3.16), then $det (𝐴 + 𝑁) = det 𝐴$ for every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ .

Solution.

Uses. Definition 5.3.6 (Determinant), Proposition 5.3.15 (Triangular matrices), Proposition 5.3.17 (Block-diagonal matrices), Proposition 5.1.17 (Dependent columns), Definition 2.4.21 (Transpose)

Hint 1. (a) Try a matrix with two equal columns.

Hint 2. (b) If

det 𝐴 \neq 0

, some term

𝑡_{𝜎} (𝐴)

is nonzero. Where are its

𝑛

nonzero entries?

Hint 3. (c) What kind of matrix is

𝐴^{𝖳}

, and what are its diagonal entries? (d) Try

𝑛 = 2

and

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

Sketch. (a) False: the all-ones matrix with

𝑛 \geq 2

. (b) True: a nonzero term uses

𝑛

nonzero entries, one in each row and each column, and these must be all of them. (c) True:

𝐴^{𝖳}

is lower triangular with the same diagonal. (d) False for

𝑛 \geq 2

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

has determinant

- 1

, but

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

(a) False for every $𝑛 \geq 2$ . The matrix with every entry $1$ has two equal columns, so its determinant is $0$ . (For $𝑛 = 1$ the statement is true.)

(b) True. Since $det 𝐴 \neq 0$ , some term of the Leibniz formula is nonzero, so the $𝑛$ entries $𝑎_{𝜎 (1) 1},$ $\dots,$ $𝑎_{𝜎 (𝑛) 𝑛}$ are nonzero for some $𝜎$ . They lie in $𝑛$ different positions, and $𝐴$ has only $𝑛$ nonzero entries, so these are all of them. They lie one in each column, and, since $𝜎$ is a bijection, one in each row.

(c) True. The $(𝑖, 𝑗)$ entry of $𝐴^{𝖳}$ is $𝑎_{𝑗 𝑖}$ , which is $0$ when $𝑗 > 𝑖$ , that is, when $𝑖 < 𝑗$ . So $𝐴^{𝖳}$ is lower triangular, with the same diagonal entries $𝑎_{𝑗 𝑗}$ as $𝐴$ . By Proposition 5.3.15, both determinants equal $𝑎_{11} \dots 𝑎_{𝑛 𝑛}$ .

(d) False for every $𝑛 \geq 2$ . For $𝑛 = 2$ , take $𝐴 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ and $𝑁 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ . Then $det 𝐴 = 0$ (a zero column), while $det (𝐴 + 𝑁) =$ $det (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) =$ $- 1$ . For $𝑛 > 2$ , take $𝐴^{'} = (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐼_{𝑛 - 2} \end{matrix})$ and $𝑁^{'} = (\begin{matrix} 𝑁 & 0 \\ 0 & 0 \end{matrix})$ , which is still strictly upper triangular. By Proposition 5.3.17, $det 𝐴^{'} = det 𝐴 = 0$ and $det (𝐴^{'} + 𝑁^{'}) =$ $det (𝐴 + 𝑁) =$ $- 1$ . (For $𝑛 = 1$ , $𝑁 = 0$ and the statement is true.)

Exercise 5.3.31.standard The permanent of $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ is the Leibniz formula without signs:

per 𝐴 = \sum_{𝜎 \in 𝑆_{𝑛}} 𝑎_{𝜎 (1) 1} 𝑎_{𝜎 (2) 2} \dots 𝑎_{𝜎 (𝑛) 𝑛} .

(a)Show that $per$ is normalized and multilinear, and that $per (𝐴 𝐸_{𝜋}) = per 𝐴$ for every $𝜋 \in 𝑆_{𝑛}$ .
(b)Let $𝑛 \geq 2$ . Show that $per$ is a determinant function on $𝐹^{𝑛 \times 𝑛}$ if and only if $1 + 1 = 0$ in $𝐹$ , and that in this case $per = det$ .
(c)Let $𝐴 \in ℚ^{𝑛 \times 𝑛}$ have all entries in ${0, 1}$ . Show that $per 𝐴$ is the number of permutations $𝜎$ with $𝑎_{𝜎 (𝑗) 𝑗} = 1$ for every $𝑗$ , and that $det 𝐴$ and $per 𝐴$ are both even or both odd.

Solution.

Uses. Theorem 5.3.4 (Existence and uniqueness of the determinant), Proposition 5.2.8 (Reindexing sums over $𝑆_{𝑛}$ ), Proposition 5.2.30 (Algebra of permutation matrices), Definition 1.1.28 (Characteristic), Proposition 5.3.20 (Reduction modulo $𝑝$ )

Hint 1. For (a), the proof of Theorem 5.3.4 for normalization and multilinearity did not use the signs. For the last claim, the columns of

𝐴 𝐸_{𝜋}

are

𝐚_{𝜋 (1)},

\dots,

𝐚_{𝜋 (𝑛)}

; reindex the sum.

Hint 2. For (b), if

1 + 1 = 0

, compare

per

with

det

term by term. If

1 + 1 \neq 0

, evaluate

per

at the matrix with columns

𝐞_{1} +

𝐞_{2},

𝐞_{1} +

𝐞_{2},

𝐞_{3},

\dots,

𝐞_{𝑛}

Hint 3. For (c), reduce both

det 𝐴

and

per 𝐴

modulo

2

Sketch. (a) Part 2 of the proof of Theorem 5.3.4 works without signs. The term of

𝜎

per (𝐴 𝐸_{𝜋})

is the term of

𝜎 𝜋^{- 1}

per 𝐴

, and

𝜎 \mapsto 𝜎 𝜋^{- 1}

is a bijection. (b) If

1 + 1 = 0

, then

sgn (𝜎) = 1

𝐹

, so

per = det

. Otherwise the matrix with two equal columns

𝐞_{1} + 𝐞_{2}

has permanent

1 + 1 \neq 0

. (c) Each term is

0

1

; modulo

2

the signs disappear, so

det 𝐴 \equiv per 𝐴

(a) $per$ is $𝐿$ with every sign replaced by $1$ , and the proof that $𝐿$ is normalized and multilinear (Part 2 of the proof of Theorem 5.3.4) never used the signs. So $per$ is normalized and multilinear. By Proposition 5.2.30, the $(𝑖, 𝑗)$ entry of $𝐴 𝐸_{𝜋}$ is $𝑎_{𝑖 𝜋 (𝑗)}$ , so

per (𝐴 𝐸_{𝜋}) = \sum_{𝜎 \in 𝑆_{𝑛}} \prod_{𝑗 = 1}^{𝑛} 𝑎_{𝜎 (𝑗) 𝜋 (𝑗)} = \sum_{𝜎 \in 𝑆_{𝑛}} \prod_{𝑗 = 1}^{𝑛} 𝑎_{𝜎 (𝜋^{- 1} (𝑗)) 𝑗},

after reordering the product by $𝑗^{'} = 𝜋 (𝑗)$ . The last sum is $\sum_{𝜎} 𝑔 (𝜎 𝜋^{- 1})$ with $𝑔 (𝜌) =$ $\prod_{𝑗} 𝑎_{𝜌 (𝑗) 𝑗}$ , which equals $\sum_{𝜎} 𝑔 (𝜎) = per 𝐴$ by Proposition 5.2.8.

(b) If $1 + 1 = 0$ , then $- 1 = 1$ in $𝐹$ , so $sgn (𝜎) = 1$ in $𝐹$ for every $𝜎$ , and $per 𝐴 = det 𝐴$ for every $𝐴$ . In particular $per$ is a determinant function. Conversely, suppose $1 + 1 \neq 0$ , and let $𝐴$ have columns $𝐞_{1} +$ $𝐞_{2},$ $𝐞_{1} +$ $𝐞_{2},$ $𝐞_{3},$ $\dots,$ $𝐞_{𝑛}$ . A term of $per 𝐴$ is nonzero exactly when $𝜎 (1), 𝜎 (2) \in {1, 2}$ and $𝜎 (𝑗) = 𝑗$ for $𝑗 \geq 3$ , which leaves $𝜎 = id$ and $𝜎 = (1 2)$ , each with product $1$ . So $per 𝐴 = 1 + 1 \neq 0$ , although $𝐴$ has two equal columns, and $per$ is not alternating. (By (a) and Theorem 5.3.4, when $1 + 1 = 0$ the determinant function $per$ must equal $det$ , as we saw directly.)

(c) Each product $𝑎_{𝜎 (1) 1} \dots 𝑎_{𝜎 (𝑛) 𝑛}$ is $1$ if all its factors are $1$ and $0$ otherwise, so $per 𝐴$ counts the permutations with $𝑎_{𝜎 (𝑗) 𝑗} = 1$ for every $𝑗$ . For $𝑛 = 1$ , $det 𝐴 = per 𝐴 = 𝑎_{11}$ . For $𝑛 \geq 2$ , reducing modulo $2$ with Proposition 5.3.20 gives $(det 𝐴) mod 2 = det 𝐴$ , and $det 𝐴 = per 𝐴$ by (b), since $1 + 1 = 0$ in $𝔽_{2}$ . Reducing the sum $per 𝐴$ term by term in the same way gives $per 𝐴 = (per 𝐴) mod 2$ . So $det 𝐴$ and $per 𝐴$ have the same remainder modulo $2$ .

Exercise 5.3.32.standard Let

𝐴 \in ℚ^{𝑛 \times 𝑛}

have every entry equal to

1

- 1

. Show that

det 𝐴

is an integer divisible by

2^{𝑛 - 1}

Solution.

Uses. Lemma 5.1.8 (Column replacement), Definition 5.1.1 (Determinant function), Proposition 5.3.20 (Reduction modulo $𝑝$ )

Hint 1. What are the possible entries of

𝐚_{𝑗} - 𝐚_{1}

Hint 2. Subtract column

1

from every other column. This does not change

det 𝐴

, and afterwards columns

2, \dots, 𝑛

have even entries.

Hint 3. Pull a factor

2

out of each of the columns

2, \dots, 𝑛

. What is left is an integer matrix.

Sketch. For

𝑗 \geq 2

𝑎_{𝑖 𝑗} -

𝑎_{𝑖 1} \in

{- 2, 0, 2}

. Subtracting column

1

from each other column leaves

det 𝐴

unchanged (Lemma 5.1.8) and makes columns

2, \dots, 𝑛

equal to

2

times integer vectors. Pulling out the

𝑛 - 1

factors of

2

leaves the determinant of an integer matrix, which is an integer.

For $𝑗 \geq 2$ , add $- 1$ times column $1$ to column $𝑗$ . By Lemma 5.1.8 none of these steps changes the determinant, and since column $1$ is never changed, the result is the matrix $𝐴^{'}$ with columns $𝐚_{1},$ $𝐚_{2} -$ $𝐚_{1},$ $\dots,$ $𝐚_{𝑛} -$ $𝐚_{1}$ . Each entry $𝑎_{𝑖 𝑗} - 𝑎_{𝑖 1}$ with $𝑗 \geq 2$ is a difference of two elements of ${1, - 1}$ , so it lies in ${- 2, 0, 2}$ . Hence $𝐚_{𝑗} - 𝐚_{1} = 2 𝐜_{𝑗}$ for a vector $𝐜_{𝑗}$ with integer entries. Pulling the factor $2$ out of each of the columns $2, \dots, 𝑛$ by multilinearity,

det 𝐴 = det 𝐴^{'} = 2^{𝑛 - 1} det (𝐚_{1}, 𝐜_{2}, \dots, 𝐜_{𝑛}) .

The last matrix has integer entries, so its determinant is an integer (Proposition 5.3.20). Hence $2^{𝑛 - 1}$ divides $det 𝐴$ .

Exercise 5.3.33.routine Let $𝐴 = (\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$ .

(a)Compute $det (𝐴 + 𝑡 𝐼_{3})$ from the Leibniz formula, listing the nonzero terms, and check the coefficients against Proposition 5.3.19.
(b)Find all $𝑡$ with $det (𝐴 + 𝑡 𝐼_{3}) = 0$ , for $𝑡 \in ℂ$ , for $𝑡 \in ℝ$ , and for $𝑡 \in 𝔽_{2}$ (regarding $𝐴$ as a matrix over $𝔽_{2}$ ).

Solution.

Uses. Definition 5.3.6 (Determinant), Proposition 5.3.19 ( $det (𝐴 + 𝑡 𝐼_{𝑛})$ as a function of $𝑡$ ), Proposition 5.2.26 (Sign of a cycle), Proposition 1.1.17 (No zero divisors)

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

Hint 1.

𝐴 +

𝑡 𝐼_{3} =

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

. Which permutations avoid the zero entries?

Hint 2. Only

id

and

(1 2 3)

survive. For (b), factor

𝑡^{3} +

1 =

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

Sketch. The surviving terms are

𝑡^{3}

(identity) and

𝑎_{21} 𝑎_{32} 𝑎_{13} = 1

for the even permutation

(1 2 3)

, so

det (𝐴 + 𝑡 𝐼_{3}) =

𝑡^{3} +

1

, with

𝑐_{2} = 0 = tr 𝐴

and

𝑐_{0} = 1 = det 𝐴

. Roots:

- 1, (1 \pm 𝑖 \sqrt{3}) / 2

over

ℂ

; only

- 1

over

ℝ

;

𝑡 = 1

over

𝔽_{2}

(a) $𝐴 +$ $𝑡 𝐼_{3} =$ $(\begin{matrix} 𝑡 & 0 & 1 \\ 1 & 𝑡 & 0 \\ 0 & 1 & 𝑡 \end{matrix})$ , whose zero entries are in positions $(1, 2)$ , $(2, 3)$ , and $(3, 1)$ . A term is nonzero only if $𝜎 (2) \neq 1$ , $𝜎 (3) \neq 2$ , and $𝜎 (1) \neq 3$ . Checking the six permutations, only $id$ (with product $𝑡 \cdot 𝑡 \cdot 𝑡$ ) and $(1 2 3)$ (with $𝜎 (1) = 2$ , $𝜎 (2) = 3$ , $𝜎 (3) = 1$ and product $𝑎_{21} 𝑎_{32} 𝑎_{13} = 1$ ) survive; for instance the term of $(1 3 2)$ contains $𝑎_{31} = 0$ . The $3$ -cycle is even (Proposition 5.2.26), so

det (𝐴 + 𝑡 𝐼_{3}) = 𝑡^{3} + 1 .

This matches Proposition 5.3.19: $𝑐_{2} = 0 = tr 𝐴$ , and $𝑐_{0} = 1 = det 𝐴$ , since $𝐴 = 𝐸_{(1 2 3)}$ has determinant $sgn ((1 2 3)) = 1$ .

(b) $𝑡^{3} +$ $1 =$ $(𝑡 + 1) (𝑡^{2} - 𝑡 + 1)$ , as multiplying out confirms. Over $ℂ$ , let $𝑧_{\pm} = (1 \pm 𝑖 \sqrt{3}) / 2$ . Then $𝑧_{+} + 𝑧_{-} = 1$ and $𝑧_{+} 𝑧_{-} = (1 + 3) / 4 = 1$ , so $𝑡^{2} -$ $𝑡 +$ $1 =$ $(𝑡 - 𝑧_{+}) (𝑡 - 𝑧_{-})$ , and $𝑡^{3} +$ $1 =$ $(𝑡 + 1) (𝑡 - 𝑧_{+}) (𝑡 - 𝑧_{-})$ . A product in a field is $0$ only if a factor is $0$ (Proposition 1.1.17), so the roots are $𝑡 = - 1$ and $𝑡 = 𝑧_{\pm}$ . Over $ℝ$ , $𝑡^{2} -$ $𝑡 +$ $1 =$ ${(𝑡 - 1 / 2)}^{2} +$ $3 / 4 >$ $0$ , so $𝑡 = - 1$ is the only root. Over $𝔽_{2}$ , $0^{3} + 1 = 1$ and $1^{3} + 1 = 0$ , so $𝑡 = 1$ is the only root (consistent with the real root $- 1$ , since $- 1 = 1$ in $𝔽_{2}$ ).

Exercise 5.3.34.standard Let $𝑛 \geq 2$ and $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . Show that the coefficient $𝑐_{𝑛 - 2} =$ $\sum_{𝜎} 𝑒_{𝜎, 𝑛 - 2}$ constructed in the proof of Proposition 5.3.19 is

𝑐_{𝑛 - 2} = \sum_{1 \leq 𝑖 < 𝑗 \leq 𝑛} (𝑎_{𝑖 𝑖} 𝑎_{𝑗 𝑗} - 𝑎_{𝑖 𝑗} 𝑎_{𝑗 𝑖}),

the sum of the determinants of the $2 \times 2$ matrices formed by rows $𝑖, 𝑗$ and columns $𝑖, 𝑗$ of $𝐴$ .

Solution.

Uses. Proposition 5.3.19 ( $det (𝐴 + 𝑡 𝐼_{𝑛})$ as a function of $𝑡$ ), Definition 5.2.10 (Transposition), Definition 5.1.14 (The $2 \times 2$ determinant)

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

Hint 1. In the proof of Proposition 5.3.19, the term of

𝜎

involves powers of

𝑡

only up to the number of fixed points of

𝜎

. Which

𝜎

fix at least

𝑛 - 2

points?

Hint 2. A permutation that moves exactly two points is a transposition. So only

id

and the transpositions contribute to

𝑡^{𝑛 - 2}

Sketch. Only

𝜎

with at least

𝑛 - 2

fixed points contribute to

𝑡^{𝑛 - 2}

: the identity and the transpositions. From

\prod_{𝑘} (𝑎_{𝑘 𝑘} + 𝑡)

the coefficient is

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

. The term of

(𝑖 𝑗)

- 𝑎_{𝑗 𝑖} 𝑎_{𝑖 𝑗} \prod_{𝑘 \neq 𝑖, 𝑗} (𝑎_{𝑘 𝑘} + 𝑡)

, contributing

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

We use the notation of the proof of Proposition 5.3.19. The term $𝑇_{𝜎} (𝑡)$ involves only the powers $𝑡^{𝑝}$ with $𝑝 \leq 𝑓_{𝜎}$ , the number of fixed points of $𝜎$ . So only permutations with at least $𝑛 - 2$ fixed points contribute to $𝑐_{𝑛 - 2}$ . Such a $𝜎$ is either $id$ or moves exactly two points $𝑖, 𝑗$ ; in the second case $𝜎 (𝑖)$ is a moved point different from $𝑖$ , so $𝜎 (𝑖) = 𝑗$ , and likewise $𝜎 (𝑗) = 𝑖$ , so $𝜎 = (𝑖 𝑗)$ .

For $𝜎 = id$ , $𝑇_{id} (𝑡) =$ $\prod_{𝑘 = 1}^{𝑛} (𝑎_{𝑘 𝑘} + 𝑡)$ . A product of $𝑡^{𝑛 - 2}$ arises by choosing $𝑎_{𝑘 𝑘}$ in exactly two factors, $𝑘 = 𝑖$ and $𝑘 = 𝑗$ , so the coefficient of $𝑡^{𝑛 - 2}$ is $\sum_{𝑖 < 𝑗} 𝑎_{𝑖 𝑖} 𝑎_{𝑗 𝑗}$ .

For $𝜎 = (𝑖 𝑗)$ with $𝑖 < 𝑗$ , which is odd,

𝑇_{𝜎} (𝑡) = - 𝑎_{𝑗 𝑖} 𝑎_{𝑖 𝑗} \prod_{𝑘 \notin {𝑖, 𝑗}} (𝑎_{𝑘 𝑘} + 𝑡),

and the coefficient of $𝑡^{𝑛 - 2}$ is $- 𝑎_{𝑖 𝑗} 𝑎_{𝑗 𝑖}$ , from choosing $𝑡$ in all $𝑛 - 2$ factors. Adding up,

𝑐_{𝑛 - 2} = \sum_{𝑖 < 𝑗} 𝑎_{𝑖 𝑖} 𝑎_{𝑗 𝑗} - \sum_{𝑖 < 𝑗} 𝑎_{𝑖 𝑗} 𝑎_{𝑗 𝑖} = \sum_{𝑖 < 𝑗} (𝑎_{𝑖 𝑖} 𝑎_{𝑗 𝑗} - 𝑎_{𝑖 𝑗} 𝑎_{𝑗 𝑖}),

and $𝑎_{𝑖 𝑖} 𝑎_{𝑗 𝑗} -$ $𝑎_{𝑖 𝑗} 𝑎_{𝑗 𝑖} =$ $det (\begin{matrix} 𝑎_{𝑖 𝑖} & 𝑎_{𝑖 𝑗} \\ 𝑎_{𝑗 𝑖} & 𝑎_{𝑗 𝑗} \end{matrix})$ . For $𝑛 = 2$ this gives $𝑐_{0} = det 𝐴$ , as it should.

Exercise 5.3.35.standard Let $𝑉$ be a vector space with a basis $ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}$ . Show that there is exactly one multilinear alternating function $𝑓 : 𝑉 \times \dots \times 𝑉 \to 𝐹$ of $𝑛$ vectors (Remark 5.1.6) with $𝑓 (𝐯_{1}, \dots, 𝐯_{𝑛}) = 1$ , and that it is given by

𝑓 (𝐰_{1}, \dots, 𝐰_{𝑛}) = det ({[𝐰_{1}]}_{ℬ︀}, \dots, {[𝐰_{𝑛}]}_{ℬ︀}) .

Solution.

Uses. Theorem 5.3.4 (Existence and uniqueness of the determinant), Definition 1.6.14 (Coordinates), Proposition 1.6.19 (Coordinates respect linear combinations), Proposition 2.1.17 (Compositions of linear maps are linear), Remark 5.1.6

Hint 1. For existence, the coordinate map

𝐰 \mapsto {[𝐰]}_{ℬ︀}

is linear and

{[𝐯_{𝑗}]}_{ℬ︀} = 𝐞_{𝑗}

Hint 2. For uniqueness, given

𝑔

, define

𝐷 (𝐱_{1}, \dots, 𝐱_{𝑛}) =

𝑔 (Φ (𝐱_{1}), \dots, Φ (𝐱_{𝑛}))

for

𝐱_{𝑗} \in 𝐹^{𝑛}

, where

Φ (𝐱) =

𝑥_{1} 𝐯_{1} +

\dots +

𝑥_{𝑛} 𝐯_{𝑛}

. Show

𝐷 = det

Sketch. The given

𝑓

det

composed with the linear coordinate map in each slot, so it is multilinear; equal vectors have equal coordinates, so it is alternating; and

𝑓 (𝐯_{1}, \dots, 𝐯_{𝑛}) =

det 𝐼_{𝑛} =

1

. If

𝑔

is another, then

𝐷 = 𝑔 \circ (Φ, \dots, Φ)

is a determinant function on

𝐹^{𝑛 \times 𝑛}

, so

𝐷 = det

, and

𝑔 (𝐰_{1}, \dots) =

𝐷 ({[𝐰_{1}]}_{ℬ︀}, \dots) =

𝑓 (𝐰_{1}, \dots)

Existence. Fix $𝑗$ and the vectors $𝐰_{𝑖}$ for $𝑖 \neq 𝑗$ . The map $𝐰 \mapsto$ $𝑓 (𝐰_{1}, \dots, 𝐰, \dots, 𝐰_{𝑛})$ is the composite of the coordinate map $𝐰 \mapsto {[𝐰]}_{ℬ︀}$ , which is linear (Proposition 1.6.19), with the map $𝐱 \mapsto det (\dots, 𝐱, \dots)$ , which is linear because $det$ is multilinear. So it is linear (Proposition 2.1.17), and $𝑓$ is multilinear. If $𝐰_{𝑖} = 𝐰_{𝑗}$ with $𝑖 \neq 𝑗$ , then ${[𝐰_{𝑖}]}_{ℬ︀} = {[𝐰_{𝑗}]}_{ℬ︀}$ , so $𝑓 (𝐰_{1}, \dots, 𝐰_{𝑛}) = 0$ because $det$ is alternating. Finally, ${[𝐯_{𝑗}]}_{ℬ︀} = 𝐞_{𝑗}$ , so $𝑓 (𝐯_{1}, \dots, 𝐯_{𝑛}) =$ $det 𝐼_{𝑛} =$ $1$ .

Uniqueness. Let $𝑔$ be multilinear and alternating with $𝑔 (𝐯_{1}, \dots, 𝐯_{𝑛}) = 1$ . Let $Φ : 𝐹^{𝑛} \to 𝑉$ , $Φ (𝐱) =$ $𝑥_{1} 𝐯_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐯_{𝑛}$ , which is linear, and define $𝐷 : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ by $𝐷 (𝐱_{1}, \dots, 𝐱_{𝑛}) =$ $𝑔 (Φ (𝐱_{1}), \dots, Φ (𝐱_{𝑛}))$ . As in the existence part, $𝐷$ is multilinear and alternating, and $𝐷 (𝐼_{𝑛}) =$ $𝑔 (Φ (𝐞_{1}), \dots, Φ (𝐞_{𝑛})) =$ $𝑔 (𝐯_{1}, \dots, 𝐯_{𝑛}) =$ $1$ . So $𝐷$ is a determinant function, and $𝐷 = det$ by Theorem 5.3.4. Now let $𝐰_{1}, \dots, 𝐰_{𝑛} \in 𝑉$ . By the definition of coordinates (Definition 1.6.14), $Φ ({[𝐰_{𝑗}]}_{ℬ︀}) = 𝐰_{𝑗}$ , so

\begin{aligned} 𝑔 (𝐰_{1}, \dots, 𝐰_{𝑛}) & = 𝐷 ({[𝐰_{1}]}_{ℬ︀}, \dots, {[𝐰_{𝑛}]}_{ℬ︀}) \\ = det ({[𝐰_{1}]}_{ℬ︀}, \dots, {[𝐰_{𝑛}]}_{ℬ︀}) = 𝑓 (𝐰_{1}, \dots, 𝐰_{𝑛}) . \end{aligned}

Hence $𝑔 = 𝑓$ . Section 13.4 uses this to define the determinant of an operator without choosing a basis.

Exercise 5.3.36.standard

(a)Show, without computing its determinant, that
$𝐴 = (\begin{matrix} 2 & 1 & 4 & 6 \\ 3 & 2 & 0 & 2 \\ 4 & 6 & 2 & 1 \\ 0 & 2 & 5 & 4 \end{matrix})$
is invertible over $ℚ$ .
(b)Let $𝐵 = (\begin{matrix} 4 & 1 & 3 \\ 0 & 2 & 6 \\ 3 & 3 & 1 \end{matrix})$ . Explain why reducing $𝐵$ modulo $2$ cannot show that $𝐵$ is invertible, and show that $𝐵$ is invertible by reducing modulo $3$ .

Solution.

Uses. Proposition 5.3.20 (Reduction modulo $𝑝$ ), Theorem 5.2.31 (Alternating functions and permutations), Proposition 5.3.15 (Triangular matrices), Corollary 5.1.18 (Non-invertible matrices)

Techniques. Reduce modulo $𝑝$ (Technique 5.3.21)

Hint 1. Reduce

𝐴

modulo

2

. What kind of matrix do you get?

Hint 2. Modulo

2

𝐴

becomes a permutation matrix, whose determinant is

\pm 1 = 1

𝔽_{2}

Hint 3. Modulo

2

𝐵

has a zero row. Modulo

3

, it is upper triangular.

Sketch. (a) Modulo

2

𝐴

is the permutation matrix with columns

𝐞_{2}, 𝐞_{1}, 𝐞_{4}, 𝐞_{3}

, of determinant

1

𝔽_{2}

, so

det 𝐴

is odd. (b) Modulo

2

𝐵

has a zero row, so

det 𝐵 = 0

, which only says

det 𝐵

is even. Modulo

3

𝐵

is upper triangular with diagonal

1, 2, 1

, so

det 𝐵 \equiv 2 mod 3

and

det 𝐵 \neq 0

(a) Modulo $2$ , the entries of $𝐴$ become

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

the permutation matrix with columns $𝐞_{2}, 𝐞_{1}, 𝐞_{4}, 𝐞_{3}$ , that is, $𝐸_{𝜎}$ for $𝜎 = (1 2) (3 4)$ . By Theorem 5.2.31, $det 𝐴 = sgn (𝜎) = 1$ in $𝔽_{2}$ . By Proposition 5.3.20, $det 𝐴$ is odd, so $det 𝐴 \neq 0$ , and $𝐴$ is invertible by Corollary 5.1.18. (In fact $det 𝐴 = 39$ .)

(b) Modulo $2$ , the second row of $𝐵$ becomes $(0, 0, 0)$ . Every term of the Leibniz formula contains an entry of the second row, so $det 𝐵 = 0$ in $𝔽_{2}$ . By Proposition 5.3.20 this only says that $det 𝐵$ is even, which is compatible with $det 𝐵 = 0$ and with $det 𝐵 \neq 0$ . Modulo $3$ ,

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

which is upper triangular, so $det 𝐵 = 1 \cdot 2 \cdot 1 = 2 \neq 0$ in $𝔽_{3}$ by Proposition 5.3.15. By Proposition 5.3.20, $det 𝐵$ is not divisible by $3$ , so $det 𝐵 \neq 0$ and $𝐵$ is invertible by Corollary 5.1.18. (In fact $det 𝐵 = - 64$ .)

Exercise 5.3.37.standard Let $𝐴 \in 𝐹^{𝑘 \times 𝑘}$ and $𝐵 \in 𝐹^{𝑚 \times 𝑚}$ . Show that

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

where the upper left zero block is $𝑘 \times 𝑚$ and the lower right one is $𝑚 \times 𝑘$ .

Solution.

Uses. Proposition 5.2.30 (Algebra of permutation matrices), Theorem 5.2.31 (Alternating functions and permutations), Proposition 5.3.17 (Block-diagonal matrices), Corollary 5.2.24 (Formulas for the sign), Definition 5.2.21 (Inversion)

Hint 1. Rearrange the columns: moving the last

𝑘

columns to the front turns the matrix into

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

Hint 2. This rearrangement is

𝑀 \mapsto 𝑀 𝐸_{𝜋}

for a permutation

𝜋

. Count the inversions of

𝜋

Sketch. Let

𝑀

be the given matrix,

𝑛 = 𝑘 + 𝑚

, and

𝜋 (𝑗) = 𝑚 + 𝑗

for

𝑗 \leq 𝑘

𝜋 (𝑘 + 𝑖) = 𝑖

for

𝑖 \leq 𝑚

. Then

𝑀 𝐸_{𝜋} = (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐵 \end{matrix})

. The inversions of

𝜋

are exactly the

𝑘 𝑚

pairs

(𝑗, 𝑘 + 𝑖)

, so

sgn (𝜋) = {(- 1)}^{𝑘 𝑚}

, and

det 𝑀 =

sgn (𝜋) det (𝑀 𝐸_{𝜋}) =

{(- 1)}^{𝑘 𝑚} det 𝐴 det 𝐵

Let $𝑀$ be the given matrix and $𝑛 = 𝑘 + 𝑚$ . Its first $𝑚$ columns are $(𝟎, 𝐛_{𝑖})$ for $𝑖 \leq 𝑚$ , and its last $𝑘$ columns are $(𝐚_{𝑗}, 𝟎)$ for $𝑗 \leq 𝑘$ . Define $𝜋 \in 𝑆_{𝑛}$ by $𝜋 (𝑗) = 𝑚 + 𝑗$ for $𝑗 \leq 𝑘$ and $𝜋 (𝑘 + 𝑖) = 𝑖$ for $𝑖 \leq 𝑚$ . By Proposition 5.2.30, the matrix $𝑀 𝐸_{𝜋}$ has columns $𝐜_{𝜋 (1)},$ $\dots,$ $𝐜_{𝜋 (𝑛)}$ , where $𝐜_{𝑝}$ denotes column $𝑝$ of $𝑀$ ; that is, $(𝐚_{1}, 𝟎),$ $\dots,$ $(𝐚_{𝑘}, 𝟎),$ $(𝟎, 𝐛_{1}),$ $\dots,$ $(𝟎, 𝐛_{𝑚})$ . So $𝑀 𝐸_{𝜋} = (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐵 \end{matrix})$ , and $det (𝑀 𝐸_{𝜋}) =$ $sgn (𝜋) det 𝑀$ by Theorem 5.2.31.

The bottom row of $𝜋$ is $𝑚 +$ $1,$ $\dots,$ $𝑚 +$ $𝑘,$ $1,$ $\dots,$ $𝑚$ . Two positions that both lie among the first $𝑘$ , or both among the last $𝑚$ , carry increasing entries, so they are not inversions. A position $𝑗 \leq 𝑘$ and a position $𝑘 + 𝑖$ form an inversion, since $𝜋 (𝑗) =$ $𝑚 +$ $𝑗 >$ $𝑖 =$ $𝜋 (𝑘 + 𝑖)$ . So $𝜋$ has exactly $𝑘 𝑚$ inversions, and $sgn (𝜋) = {(- 1)}^{𝑘 𝑚}$ by Corollary 5.2.24. Using Proposition 5.3.17 and ${sgn (𝜋)}^{2} = 1$ ,

det 𝑀 = sgn (𝜋) det (𝑀 𝐸_{𝜋}) = {(- 1)}^{𝑘 𝑚} det 𝐴 det 𝐵 .

Exercise 5.3.38.hard

(a)Find a $3 \times 3$ matrix with all entries in ${0, 1}$ whose determinant (over $ℚ$ ) is $2$ .
(b)Show that no $3 \times 3$ matrix with all entries in ${0, 1}$ has determinant greater than $2$ .

Solution.

Uses. Definition 5.3.6 (Determinant), Figure 5.3.1, Proposition 5.1.17 (Dependent columns)

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

Hint 1. Write

det 𝐴 = 𝑃 - 𝑁

, where

𝑃

is the sum of the three products for even permutations and

𝑁

the sum for odd ones. Each product is

0

1

Hint 2. So

det 𝐴 \leq 3

, with equality only if all three even products are

1

. Look at the top row of Figure 5.3.1: which positions do the three even permutations use together?

Sketch. (a)

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

has determinant

1 + 1 - 0 = 2

. (b) Each of the six products in (5.3.2) is

0

1

, so

det 𝐴 \leq 3

, and

det 𝐴 = 3

forces all three even products to be

1

. The three even permutations together use each of the nine positions exactly once, so then every entry is

1

, and

det 𝐴 = 0

, a contradiction.

(a) Let $𝐴 = (\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix})$ . In (5.3.2), the even terms are $𝑎_{11} 𝑎_{22} 𝑎_{33} = 1$ , $𝑎_{21} 𝑎_{32} 𝑎_{13} = 0$ , and $𝑎_{31} 𝑎_{12} 𝑎_{23} = 1$ , and the odd terms are $𝑎_{21} 𝑎_{12} 𝑎_{33} = 0$ , $𝑎_{11} 𝑎_{32} 𝑎_{23} = 0$ , and $𝑎_{31} 𝑎_{22} 𝑎_{13} = 0$ . So $det 𝐴 = 2$ .

(b) Let $𝐴$ have entries in ${0, 1}$ . In (5.3.2), $det 𝐴 = 𝑃 - 𝑁$ , where $𝑃$ is the sum of the three products for the even permutations and $𝑁$ is the sum of the three for the odd ones. Each product is $0$ or $1$ , so $𝑃 \leq 3$ and $𝑁 \geq 0$ , and $det 𝐴 \leq 3$ . Suppose $det 𝐴 = 3$ . Then $𝑃 = 3$ , so all three even products equal $1$ , and all the entries they use equal $1$ . The three even permutations $id$ , $(1 2 3)$ , $(1 3 2)$ use the positions $(𝑗, 𝑗)$ , $(𝑗 + 1, 𝑗)$ , and $(𝑗 + 2, 𝑗)$ in column $𝑗$ , with row indices read modulo $3$ ; in each column these are the three different rows. So together they use all nine positions (the top row of Figure 5.3.1), and every entry of $𝐴$ is $1$ . But then $𝐴$ has equal columns and $det 𝐴 = 0 \neq 3$ , a contradiction. Since $det 𝐴$ is an integer, $det 𝐴 \leq 2$ .

Exercise 5.3.39.hard This exercise constructs a determinant function by induction on $𝑛$ , without permutations. For $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ with $𝑛 \geq 2$ and $𝑖 \in [𝑛]$ , let $𝐴^{(𝑖)} \in$ $𝐹^{(𝑛 - 1) \times (𝑛 - 1)}$ be $𝐴$ with row $𝑖$ and column $1$ deleted. Define $𝐷_{1} (𝑎) = 𝑎$ and, for $𝑛 \geq 2$ ,

𝐷_{𝑛} (𝐴) = \sum_{𝑖 = 1}^{𝑛} {(- 1)}^{𝑖 + 1} 𝑎_{𝑖 1} 𝐷_{𝑛 - 1} (𝐴^{(𝑖)}) .

(a)Show by induction on $𝑛$ that $𝐷_{𝑛}$ is normalized and multilinear.
(b)Show by induction on $𝑛$ that $𝐷_{𝑛} (𝐴) = 0$ whenever two adjacent columns of $𝐴$ are equal. Deduce that $𝐷_{𝑛}$ is a determinant function, so $𝐷_{𝑛} = det$ .
(c)Explain why, with Remark 5.2.32, this gives a third proof of Theorem 5.2.18.

Solution.

Uses. Definition 5.1.1 (Determinant function), Exercise 5.1.35, Theorem 5.3.4 (Existence and uniqueness of the determinant), Remark 5.2.32 (Two comments on the theorem), Proposition 2.1.17 (Compositions of linear maps are linear)

Techniques. Cancel terms in pairs (Technique 5.3.5)

Hint 1. (a) For column

1

, the minors

𝐴^{(𝑖)}

do not involve column

1

. For column

𝑘 \geq 2

, the entries

𝑎_{𝑖 1}

are fixed, and column

𝑘 - 1

𝐴^{(𝑖)}

is column

𝑘

𝐴

with its

𝑖

-th entry deleted.

Hint 2. (b) If columns

𝑘, 𝑘 + 1

are equal with

𝑘 \geq 2

, every minor

𝐴^{(𝑖)}

has two equal adjacent columns. The case

𝑘 = 1

is the real work: expand each

𝐷_{𝑛 - 1} (𝐴^{(𝑖)})

once more along its first column.

Hint 3. For

𝑘 = 1

with

𝑥_{𝑖} = 𝑎_{𝑖 1} = 𝑎_{𝑖 2}

, you get a double sum over

𝑖 \neq 𝑙

\pm 𝑥_{𝑖} 𝑥_{𝑙} 𝐷_{𝑛 - 2} (𝐴^{{𝑖, 𝑙}})

, where

𝐴^{{𝑖, 𝑙}}

deletes rows

𝑖, 𝑙

and columns

1, 2

. Compare the signs of the

(𝑖, 𝑙)

and

(𝑙, 𝑖)

terms. Then use Exercise 5.1.35.

Sketch. (a)

𝐷_{𝑛 (𝐼_{𝑛})} =

𝐷_{𝑛 - 1} (𝐼_{𝑛 - 1}) =

1

; in column

1

𝐷_{𝑛}

\sum {(- 1)}^{𝑖 + 1} 𝑎_{𝑖 1} \cdot

(const)

; in column

𝑘 \geq 2

each summand is a constant times

𝐷_{𝑛 - 1}

of a matrix depending linearly on column

𝑘

. (b) Equal columns

𝑘, 𝑘 + 1

with

𝑘 \geq 2

make every minor vanish. For

𝑘 = 1

, expanding twice gives

\sum_{𝑖 \neq 𝑙} 𝜀_{𝑖 𝑙} 𝑥_{𝑖} 𝑥_{𝑙} 𝐷_{𝑛 - 2} (𝐴^{{𝑖, 𝑙}})

, with

𝜀_{𝑖 𝑙} = {(- 1)}^{𝑖 + 𝑙}

for

𝑙 < 𝑖

and

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

for

𝑙 > 𝑖

; the terms

(𝑖, 𝑙)

and

(𝑙, 𝑖)

cancel. With Exercise 5.1.35,

𝐷_{𝑛}

is alternating. (c)

𝐷_{𝑛}

is a nonzero multilinear alternating function on

ℚ^{𝑛 \times 𝑛}

built without

sgn

We write $𝐚_{𝑘}^{(𝑖)}$ for column $𝑘$ of $𝐴$ with its $𝑖$ -th entry deleted, so $𝐴^{(𝑖)}$ has columns $𝐚_{2}^{(𝑖)},$ $\dots,$ $𝐚_{𝑛}^{(𝑖)}$ .

(a) We show by induction on $𝑛$ that $𝐷_{𝑛}$ is normalized and multilinear. For $𝑛 = 1$ , $𝐷_{1} (1) = 1$ and $𝐷_{1}$ is linear. Let $𝑛 \geq 2$ and assume the claim for $𝑛 - 1$ .

Normalized. The first column of $𝐼_{𝑛}$ is $𝐞_{1}$ , so only $𝑖 = 1$ contributes, and $𝐼_{𝑛}^{(1)} = 𝐼_{𝑛 - 1}$ . Hence $𝐷_{𝑛} (𝐼_{𝑛}) =$ $𝐷_{𝑛 - 1} (𝐼_{𝑛 - 1}) =$ $1$ .

Linear in column $1$ . The minors $𝐴^{(𝑖)}$ do not involve column $1$ , so for fixed columns $2, \dots, 𝑛$ , $𝐷_{𝑛} (𝐴) =$ $\sum_{𝑖} {(- 1)}^{𝑖 + 1} 𝑎_{𝑖 1} 𝛾_{𝑖}$ with constants $𝛾_{𝑖}$ . This is linear in $(𝑎_{11}, \dots, 𝑎_{𝑛 1})$ .

Linear in column $𝑘 \geq 2$ . Fix all columns except column $𝑘$ . Each $𝑎_{𝑖 1}$ is then constant, and $𝐴^{(𝑖)}$ has column $𝑘 - 1$ equal to $𝐚_{𝑘}^{(𝑖)}$ , which depends linearly on $𝐚_{𝑘}$ (deleting an entry is a linear map $𝐹^{𝑛} \to 𝐹^{𝑛 - 1}$ ), while its other columns are fixed. By the induction hypothesis $𝐷_{𝑛 - 1}$ is linear in column $𝑘 - 1$ , so $𝐚_{𝑘} \mapsto$ $𝐷_{𝑛 - 1} (𝐴^{(𝑖)})$ is a composite of linear maps, hence linear (Proposition 2.1.17). A linear combination of linear maps is linear, so $𝐷_{𝑛}$ is linear in column $𝑘$ .

(b) We show by induction on $𝑛 \geq 2$ that $𝐷_{𝑛} (𝐴) = 0$ whenever two adjacent columns of $𝐴$ are equal. For $𝑛 = 2$ , $𝐷_{2} (𝐴) =$ $𝑎_{11} 𝑎_{22} -$ $𝑎_{21} 𝑎_{12}$ , which vanishes when the two columns are equal. Let $𝑛 \geq 3$ , assume the claim for $𝑛 - 1$ , and suppose $𝐚_{𝑘} = 𝐚_{𝑘 + 1}$ .

Case $𝑘 \geq 2$ . Each $𝐴^{(𝑖)}$ has equal adjacent columns $𝐚_{𝑘}^{(𝑖)} =$ $𝐚_{𝑘 + 1}^{(𝑖)}$ , in positions $𝑘 - 1$ and $𝑘$ . By the induction hypothesis, $𝐷_{𝑛 - 1} (𝐴^{(𝑖)}) = 0$ for every $𝑖$ , so $𝐷_{𝑛} (𝐴) = 0$ .

Case $𝑘 = 1$ . Write $𝑥_{𝑖} = 𝑎_{𝑖 1} = 𝑎_{𝑖 2}$ . For $𝑖 \neq 𝑙$ , let $𝐴^{{𝑖, 𝑙}}$ be $𝐴$ with rows $𝑖, 𝑙$ and columns $1, 2$ deleted; it depends only on the set ${𝑖, 𝑙}$ . The first column of $𝐴^{(𝑖)}$ is $𝐚_{2}^{(𝑖)}$ , whose entries are $𝑥_{𝑙}$ for $𝑙 \neq 𝑖$ , with $𝑥_{𝑙}$ in position $𝑙$ if $𝑙 < 𝑖$ and in position $𝑙 - 1$ if $𝑙 > 𝑖$ . Deleting that position and the first column of $𝐴^{(𝑖)}$ leaves $𝐴^{{𝑖, 𝑙}}$ . So the definition of $𝐷_{𝑛 - 1}$ gives

\begin{aligned} 𝐷_{𝑛 - 1} (𝐴^{(𝑖)}) = & \sum_{𝑙 < 𝑖} {(- 1)}^{𝑙 + 1} 𝑥_{𝑙} 𝐷_{𝑛 - 2} (𝐴^{{𝑖, 𝑙}}) \\ + \sum_{𝑙 > 𝑖} {(- 1)}^{𝑙} 𝑥_{𝑙} 𝐷_{𝑛 - 2} (𝐴^{{𝑖, 𝑙}}) . \end{aligned}

Substituting into the definition of $𝐷_{𝑛}$ ,

𝐷_{𝑛} (𝐴) = \sum_{𝑖 \neq 𝑙} 𝜀_{𝑖 𝑙} 𝑥_{𝑖} 𝑥_{𝑙} 𝐷_{𝑛 - 2} (𝐴^{{𝑖, 𝑙}}),

where the sum runs over ordered pairs $(𝑖, 𝑙)$ of distinct indices and

𝜀_{𝑖 𝑙} = {\begin{cases} {(- 1)}^{𝑖 + 1} {(- 1)}^{𝑙 + 1} = {(- 1)}^{𝑖 + 𝑙} & if 𝑙 < 𝑖 \\ {(- 1)}^{𝑖 + 1} {(- 1)}^{𝑙} = - {(- 1)}^{𝑖 + 𝑙} & if 𝑙 > 𝑖 . \end{cases}

For $𝑖 < 𝑙$ , the ordered pairs $(𝑖, 𝑙)$ and $(𝑙, 𝑖)$ give the same product $𝑥_{𝑖} 𝑥_{𝑙} 𝐷_{𝑛 - 2} (𝐴^{{𝑖, 𝑙}})$ with the signs $𝜀_{𝑖 𝑙} = - {(- 1)}^{𝑖 + 𝑙}$ and $𝜀_{𝑙 𝑖} = {(- 1)}^{𝑖 + 𝑙}$ , so they cancel. Grouping the terms in these pairs (Technique 5.3.5), $𝐷_{𝑛} (𝐴) = 0$ .

By (a) and the above, $𝐷_{𝑛}$ is multilinear and vanishes whenever two adjacent columns are equal, so it is alternating by Exercise 5.1.35 (for $𝑛 = 1$ there is nothing to check). Together with $𝐷_{𝑛} (𝐼_{𝑛}) = 1$ , $𝐷_{𝑛}$ is a determinant function, and $𝐷_{𝑛} = det$ by Theorem 5.3.4.

(c) The construction of $𝐷_{𝑛}$ and parts (a) and (b) never mention permutations or signs. Over $𝐹 = ℚ$ , $𝐷_{𝑛}$ is a multilinear alternating function with $𝐷_{𝑛} (𝐼_{𝑛}) = 1 \neq 0$ . By part (2) of Remark 5.2.32, if $𝜎$ were a product of $𝑟$ transpositions and also of $𝑠$ transpositions, then ${(- 1)}^{𝑟} =$ $𝐷_{𝑛} (𝐸_{𝜎}) =$ ${(- 1)}^{𝑠}$ , so $𝑟$ and $𝑠$ would have the same parity. This proves Theorem 5.2.18 without Approach 1: a product of differences or Approach 2: counting inversions. Expanding along the first column is the subject of Section 5.5.

Exercise 5.3.40.challenge Let

𝑛

be even, and let

𝐴 \in ℚ^{𝑛 \times 𝑛}

have

𝑎_{𝑖 𝑖} = 0

for every

𝑖

and

𝑎_{𝑖 𝑗} \in {1, - 1}

for

𝑖 \neq 𝑗

. Show that

𝐴

is invertible. Show by an example that the conclusion can fail for odd

𝑛

Solution.

Uses. Proposition 5.3.20 (Reduction modulo $𝑝$ ), Exercise 5.3.31, Proposition 5.2.16 (Cycle decomposition), Corollary 5.1.18 (Non-invertible matrices), Proposition 5.1.17 (Dependent columns)

Techniques. Reduce modulo $𝑝$ (Technique 5.3.21), Cancel terms in pairs (Technique 5.3.5)

Hint 1. Work modulo

2

. What is

𝐴

, and what does the Leibniz formula over

𝔽_{2}

count?

Hint 2. Over

𝔽_{2}

det 𝐴

is the number of permutations with no fixed points (derangements), modulo

2

. To find its parity, pair each derangement

𝜎

with

𝜎^{- 1}

Hint 3. The unpaired derangements satisfy

𝜎^{2} = id

, so they are products of

𝑛 / 2

disjoint transpositions. Count them: how many choices are there for the partner of

1

Sketch. Modulo

2

𝐴

has

0

on the diagonal and

1

elsewhere, and

det 𝐴

is the number of derangements of

[𝑛]

modulo

2

. The involution

𝜎 \mapsto 𝜎^{- 1}

on derangements shows that this number has the parity of the number of fixed-point-free involutions, which is

(𝑛 - 1) (𝑛 - 3) \dots 3 \cdot 1

, an odd number. So

det 𝐴

is odd. For

𝑛 = 3

, the matrix

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

has determinant

0

Reduce modulo $2$ : $𝐴$ has $0$ on the diagonal and $1$ off the diagonal, since $- 1 = 1$ in $𝔽_{2}$ . In $𝔽_{2}$ , $sgn (𝜎) = 1$ for every $𝜎$ , and the term of $𝜎$ is $1$ if $𝜎 (𝑗) \neq 𝑗$ for every $𝑗$ and $0$ otherwise. So $det 𝐴$ is the number $𝑑$ of derangements of $[𝑛]$ , the permutations without fixed points, reduced modulo $2$ (compare part (c) of Exercise 5.3.31).

Pairing. If $𝜎$ is a derangement, so is $𝜎^{- 1}$ , and ${(𝜎^{- 1})}^{- 1} = 𝜎$ . So $𝜎 \mapsto 𝜎^{- 1}$ is an involution of the set of derangements, and the derangements with $𝜎^{- 1} \neq 𝜎$ fall into pairs ${𝜎, 𝜎^{- 1}}$ . Hence $𝑑$ has the same parity as the number $𝑚_{𝑛}$ of derangements with $𝜎^{- 1} = 𝜎$ , that is, with $𝜎^{2} = id$ (Technique 5.3.5).

Counting involutions. Let $𝜎$ be a derangement with $𝜎^{2} = id$ . Every orbit of $𝜎$ has size $2$ : for each $𝑖$ , $𝜎 (𝑖) \neq 𝑖$ but $𝜎^{2} (𝑖) = 𝑖$ . By Proposition 5.2.16, $𝜎$ is a product of $𝑛 / 2$ disjoint transpositions, so it pairs up the elements of $[𝑛]$ . Conversely, every way of splitting $[𝑛]$ into $𝑛 / 2$ pairs gives such a $𝜎$ . We count these by induction on the even number $𝑛$ : there are $𝑛 - 1$ choices for the partner $𝑝$ of $1$ , and then the remaining $𝑛 - 2$ elements must be split into pairs, in $𝑚_{𝑛 - 2}$ ways. With $𝑚_{2} = 1$ , we get $𝑚_{𝑛} =$ $(𝑛 - 1) (𝑛 - 3) \dots 3 \cdot$ $1$ , a product of odd numbers, which is odd.

So $𝑑$ is odd, $det 𝐴 = 1$ in $𝔽_{2}$ , and $det 𝐴$ is odd by Proposition 5.3.20. In particular $det 𝐴 \neq 0$ , and $𝐴$ is invertible by Corollary 5.1.18.

For odd $𝑛$ the conclusion can fail. With $𝑛 = 3$ and $𝐴 = (\begin{matrix} 0 & 1 & - 1 \\ - 1 & 0 & 1 \\ 1 & - 1 & 0 \end{matrix})$ , every row sums to $0$ , so $𝐚_{1} + 𝐚_{2} + 𝐚_{3} = 𝟎$ and $det 𝐴 = 0$ by Proposition 5.1.17. Here the argument breaks down because $𝑚_{3} = 0$ : a permutation of an odd number of points cannot pair them all up.

More practice

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

5.3.1The axioms force a formula

5.3.2The formula satisfies the axioms

5.3.3The 3×3 determinant

5.3.4Triangular and block-diagonal matrices

5.3.5The determinant as a polynomial in the entries

Exercises

More practice

5.3.3The $3 \times 3$ determinant