Books
Theme
Text size
Width

[ and ] go to the previous and next page.

These problems combine the sections of Chapter 5 with each other and with earlier chapters. The first three are review prompts: state the result, prove it without looking, and then answer a follow-up question that the text did not ask. The rest are ordered roughly by difficulty. Problems of kind “competition” are harder than anything the course expects. Section 5.6 compares the methods these problems call for.

Review: state and prove

Problem 5.1.standard
  1. (a)State the theorem on the existence and uniqueness of determinant functions, including its description of all multilinear alternating functions on 𝐹𝑛×𝑛.
  2. (b)Prove that the function 𝐿 of (5.3.1) is alternating, by an argument that works over every field.
  3. (c)Let 𝑛≥2 and 𝐹=𝔽2, and define 𝐷(𝐴)=det𝐴+𝑎11𝑎12⋯𝑎1𝑛 for 𝐴∈𝔽2𝑛×𝑛. Show that 𝐷 is normalized, multilinear, and antisymmetric (Definition 5.1.9), but not alternating. Explain why no such 𝐷 exists over a field in which 1+1≠0.

Solution.

Uses. Theorem 5.3.4 (Existence and uniqueness of the determinant), Theorem 5.3.3 (The Leibniz formula), Proposition 5.2.25 (Multiplicativity of the sign), Proposition 5.1.11 (Antisymmetric implies alternating when 1+1≠0), Definition 5.1.1 (Determinant function)

Techniques. Cancel terms in pairs (Technique 5.3.5)

Hint 1. For (b), suppose columns 𝑘≠𝑙 are equal and let 𝜏=(𝑘𝑙). Compare the terms of 𝜎 and 𝜎𝜏, and do not reindex the whole sum.
Hint 2. For (c), the product 𝑎11⋯𝑎1𝑛 takes one entry from each column, and permuting the columns only permutes its factors. To break alternation, use a matrix whose columns are all equal but whose first row is not zero.
Sketch. (a) There is exactly one determinant function on 𝐹𝑛×𝑛, the Leibniz formula 𝐿, and every multilinear alternating 𝐷 equals 𝐷(𝐼𝑛)𝐿. (b) If columns 𝑘≠𝑙 agree and 𝜏=(𝑘𝑙), then 𝜎𝜏 uses the same entries as 𝜎 with the opposite sign, so 𝑡𝜎𝜏=−𝑡𝜎; grouping each even 𝜎 with 𝜎𝜏 writes 𝐿(𝐴) as a sum of zeros. (c) det is antisymmetric, and the product of the first-row entries is multilinear, invariant under column permutations, and 0 at 𝐼𝑛; over 𝔽2, invariance is antisymmetry. On the matrix with first row all 1s and other rows 0, 𝐷=0+1. When 1+1≠0, antisymmetry implies alternation, and uniqueness leaves only det.

(a) Statement (Theorem 5.3.4). Let 𝑛≥1. The function

𝐿(𝐴)=∑𝜎∈𝑆𝑛sgn(𝜎)𝑎𝜎(1)1𝑎𝜎(2)2⋯𝑎𝜎(𝑛)𝑛

is a determinant function on 𝐹𝑛×𝑛, and it is the only one. Moreover, every multilinear alternating 𝐷:𝐹𝑛×𝑛→𝐹 satisfies 𝐷=𝐷(𝐼𝑛)𝐿.

(b) Let 𝐴 have equal columns 𝑘 and 𝑙, where 𝑘≠𝑙, and let 𝜏=(𝑘𝑙). Write 𝑡𝜎(𝐴)=sgn(𝜎)∏𝑗𝑎𝜎(𝑗)𝑗. The permutation 𝜎𝜏 agrees with 𝜎 except that (𝜎𝜏)(𝑘)=𝜎(𝑙) and (𝜎𝜏)(𝑙)=𝜎(𝑘). So

∏𝑗𝑎(𝜎𝜏)(𝑗)𝑗=(∏𝑗∉{𝑘,𝑙}𝑎𝜎(𝑗)𝑗)𝑎𝜎(𝑙)𝑘𝑎𝜎(𝑘)𝑙,

and since columns 𝑘 and 𝑙 are equal, 𝑎𝜎(𝑙)𝑘=𝑎𝜎(𝑙)𝑙 and 𝑎𝜎(𝑘)𝑙=𝑎𝜎(𝑘)𝑘. So the products of entries in 𝑡𝜎𝜏(𝐴) and 𝑡𝜎(𝐴) agree, while sgn(𝜎𝜏)=−sgn(𝜎) by Proposition 5.2.25. Hence 𝑡𝜎𝜏(𝐴)=−𝑡𝜎(𝐴).

The map 𝜎↦𝜎𝜏 is its own inverse and changes the sign, so it maps the even permutations bijectively onto the odd ones. Therefore

𝐿(𝐴)=∑𝜎even(𝑡𝜎(𝐴)+𝑡𝜎𝜏(𝐴))=∑𝜎even0=0.

No step divides by 1+1: over 𝔽2 the two terms of a pair are equal and cancel because 𝑥+𝑥=0.

(c) Write 𝑔(𝐴)=𝑎11𝑎12⋯𝑎1𝑛, so 𝐷=det+𝑔.

Normalized. det𝐼𝑛=1, and 𝑔(𝐼𝑛) contains the factor 𝑎12=0 (as 𝑛≥2). So 𝐷(𝐼𝑛)=1.

Multilinear. 𝑔 contains exactly one entry of each column, namely 𝑎1𝑘 from column 𝑘. With the other columns fixed, 𝑔 is a constant times 𝑎1𝑘, a linear function of column 𝑘. So 𝑔 is multilinear, and so is 𝐷=det+𝑔.

Antisymmetric. Interchanging two columns negates det (Proposition 5.1.10) and permutes the factors of 𝑔, so it leaves 𝑔 unchanged. In 𝔽2, −1=1, so both det and 𝑔 are unchanged, and 𝐷(𝐴′)=𝐷(𝐴)=−𝐷(𝐴) for the interchanged matrix 𝐴′.

Not alternating. Let 𝐴 have first row (1,…,1) and all other rows 0. All columns of 𝐴 are equal to 𝐞1, so det𝐴=0, but 𝑔(𝐴)=1, and 𝐷(𝐴)=1≠0.

If 1+1≠0, an antisymmetric function is alternating (Proposition 5.1.11). So a normalized, multilinear, antisymmetric 𝐷 would be a determinant function, hence equal to det by uniqueness, and det is alternating. So over such a field the three conditions determine det, while over 𝔽2 they allow at least two functions, for every 𝑛≥2. This is why the definition asks for alternation (compare Example 5.1.12, the case 𝑛=2).

Problem 5.2.standard
  1. (a)State Theorem 5.4.7 and Theorem 5.4.10.
  2. (b)Prove det(𝐴𝐵)=det𝐴det𝐵 by recognizing the determinant by its axioms. Then deduce the implication “𝐴 invertible ⇒ det𝐴≠0” from it, without elementary matrices.
  3. (c)For which 𝑛≥1 is there a matrix 𝐴∈ℚ𝑛×𝑛 with 𝐴2=2𝐼𝑛? What changes over ℝ?

Solution.

Uses. Theorem 5.3.4 (Existence and uniqueness of the determinant), Definition 5.1.1 (Determinant function), Theorem 5.4.10 (Multiplicativity), Exercise 5.1.5, Corollary 5.4.27 (Several diagonal blocks), Theorem 2.4.34 (Block multiplication)

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

Hint 1. For (b), fix 𝐴 and regard 𝐷(𝐵)=det(𝐴𝐵) as a function of the columns of 𝐵. Column 𝑗 of 𝐴𝐵 is 𝐴𝐛𝑗.
Hint 2. For (c), take determinants: (det𝐴)2=2𝑛. When is 2𝑛 the square of a rational number? For even 𝑛, look for a 2×2 example and use blocks.
Sketch. (b) 𝐷(𝐵)=det(𝐴𝐛1,…,𝐴𝐛𝑛) is linear in each column (a linear map followed by det) and vanishes when two columns of 𝐵 agree, so 𝐷(𝐵)=𝐷(𝐼𝑛)det𝐵=det𝐴det𝐵. Then det𝐴det𝐴−1=det𝐼𝑛=1. (c) (det𝐴)2=2𝑛 with det𝐴∈ℚ; for odd 𝑛=2𝑘+1 this makes det𝐴/2𝑘 a rational square root of 2. For even 𝑛, use 𝑛/2 diagonal blocks (0210). Over ℝ, 2𝐼𝑛 works for every 𝑛.

(a) Theorem 5.4.7: 𝐴∈𝐹𝑛×𝑛 is invertible if and only if det𝐴≠0. Theorem 5.4.10: det(𝐴𝐵)=det𝐴det𝐵 for all 𝐴,𝐵∈𝐹𝑛×𝑛.

(b) Fix 𝐴, and let 𝐷(𝐵)=det(𝐴𝐵). Column 𝑗 of 𝐴𝐵 is 𝐴𝐛𝑗, so 𝐷(𝐵)=det(𝐴𝐛1,…,𝐴𝐛𝑛). In column 𝑗, 𝐷 is the linear map 𝐱↦𝐴𝐱 followed by det, which is linear in column 𝑗; so 𝐷 is multilinear. If two columns of 𝐵 are equal, the corresponding columns of 𝐴𝐵 are equal, and 𝐷(𝐵)=0; so 𝐷 is alternating. By Theorem 5.3.4, 𝐷(𝐵)=𝐷(𝐼𝑛)det𝐵=det(𝐴)det𝐵.

If 𝐴 is invertible, then 1=det𝐼𝑛=det(𝐴𝐴−1)=det𝐴det𝐴−1, so det𝐴≠0.

(c) Suppose 𝐴∈ℚ𝑛×𝑛 and 𝐴2=2𝐼𝑛. By (b) and Exercise 5.1.5, (det𝐴)2=det(2𝐼𝑛)=2𝑛, and det𝐴∈ℚ. If 𝑛=2𝑘+1 is odd, then (det𝐴/2𝑘)2=22𝑘+1/22𝑘=2, so 2 would be rational, which it is not. So 𝑛 must be even. Conversely, 𝑅=(0210) satisfies 𝑅2=2𝐼2, and for even 𝑛 the block-diagonal matrix with 𝑛/2 blocks 𝑅 satisfies 𝐴2=2𝐼𝑛, since block-diagonal matrices multiply block by block (Theorem 2.4.34). So the answer over ℚ is: exactly the even 𝑛.

Over ℝ, 𝐴=2𝐼𝑛 works for every 𝑛. The obstruction over ℚ is arithmetic, the irrationality of 2, and the determinant is what detects it.

Problem 5.3.standard
  1. (a)State Cramer’s rule.
  2. (b)Let 𝐵∈𝐹𝑛×𝑛 and 𝐲∈𝐹𝑛, with no assumption on det𝐵. Prove that every solution of 𝐵𝐱=𝐲 satisfies 𝑥𝑖det𝐵=det𝐵𝑖(𝐲) for 𝑖=1,…,𝑛, where 𝐵𝑖(𝐲) is 𝐵 with column 𝑖 replaced by 𝐲. Deduce Cramer’s rule.
  3. (c)Let 𝐵∈ℚ𝑛×𝑛 have integer entries and 𝑑=det𝐵≠0. Show that for every 𝐲 with integer entries, the solution of 𝐵𝐱=𝐲 has 𝑑𝐱 integral. Show also that if 𝑑≠±1, then some 𝐲 with integer entries has a solution that is not integral, and find one for 𝐵=(2113).

Solution.

Uses. Theorem 5.5.14 (Cramer’s rule), Proposition 2.4.8 (Four views of the product), Definition 5.1.1 (Determinant function), Theorem 5.4.7 (Invertibility and the determinant), Proposition 5.3.20 (Reduction modulo 𝑝), Corollary 5.5.12 (Integer inverses)

Techniques. Expand by multilinearity (Technique 5.1.7)

Hint 1. For (b), write 𝐲=∑𝑘𝑥𝑘𝐛𝑘 and expand det𝐵𝑖(𝐲) in column 𝑖.
Hint 2. For the second part of (c), if every integral 𝐲 had an integral solution, what would that say about the columns of 𝐵−1?
Sketch. (b) Linearity in column 𝑖 gives det𝐵𝑖(𝐲)=∑𝑘𝑥𝑘det𝐵𝑖(𝐛𝑘), and every term with 𝑘≠𝑖 has a repeated column, while 𝐵𝑖(𝐛𝑖)=𝐵. (c) det𝐵𝑖(𝐲) is an integer. If all 𝐵−1𝐞𝑗 were integral, 𝐵−1 would be, forcing 𝑑=±1. For the example, 𝐲=𝐞1 gives 𝐱=(3/5,−1/5).

(a) (Theorem 5.5.14) If 𝐵∈𝐹𝑛×𝑛 has det𝐵≠0 and 𝐲∈𝐹𝑛, then 𝐵𝐱=𝐲 has exactly one solution, and 𝑥𝑖=det𝐵𝑖(𝐲)/det𝐵 for each 𝑖.

(b) Let 𝐱 be a solution. Then 𝐲=𝐵𝐱=∑𝑘𝑥𝑘𝐛𝑘 (Proposition 2.4.8). By linearity in column 𝑖,

det𝐵𝑖(𝐲)=∑𝑘=1𝑛𝑥𝑘det𝐵𝑖(𝐛𝑘).

For 𝑘≠𝑖, the matrix 𝐵𝑖(𝐛𝑘) has 𝐛𝑘 in columns 𝑖 and 𝑘, so its determinant is 0. For 𝑘=𝑖, 𝐵𝑖(𝐛𝑖)=𝐵. Hence det𝐵𝑖(𝐲)=𝑥𝑖det𝐵.

If det𝐵≠0, then 𝐵 is invertible (Theorem 5.4.7), so 𝐱=𝐵−1𝐲 is the unique solution, and dividing by det𝐵 gives 𝑥𝑖=det𝐵𝑖(𝐲)/det𝐵.

(c) If 𝐲 is integral, then 𝐵𝑖(𝐲) has integer entries, so det𝐵𝑖(𝐲) is an integer (Proposition 5.3.20), and by (b), 𝑑𝑥𝑖=det𝐵𝑖(𝐲)∈ℤ.

Suppose that every integral 𝐲 gives an integral solution. Then each column 𝐵−1𝐞𝑗 of 𝐵−1, the solution for 𝐲=𝐞𝑗, is integral, so 𝐵−1 has integer entries, and 𝑑=±1 by Corollary 5.5.12. So if 𝑑≠±1, some 𝐞𝑗 has a non-integral solution.

For 𝐵=(2113), 𝑑=5. With 𝐲=𝐞1,

𝑥1=15det(1103)=35,𝑥2=15det(2110)=−15.

Check: 2⋅3/5−1/5=1 and 3/5+3⋅(−1/5)=0. The denominators are exactly 𝑑.

Synthesis problems

Problem 5.4.standard Prove or disprove each statement.

  1. (a)If 𝐴,𝐵∈ℝ𝑛×𝑛, with 𝑛≥2, have positive determinants, then so does 𝐴+𝐵.
  2. (b)If 𝐴∈𝐹𝑛×𝑛 satisfies 𝐴3=𝐴, then det𝐴∈{−1,0,1}.
  3. (c)If 𝐴∈𝐹𝑚×𝑛, then det(𝐴𝖳𝐴)=det(𝐴𝐴𝖳).
  4. (d)If every row of 𝐴∈𝐹𝑛×𝑛 sums to 0, then det𝐴=0.
  5. (e)If every row of 𝐴∈𝐹𝑛×𝑛 sums to 1, then det𝐴=1.

Solution.

Uses. Theorem 5.4.10 (Multiplicativity), Theorem 5.4.14 (The transpose), Proposition 1.1.17 (No zero divisors), Corollary 5.4.8 (Vanishing determinants), Proposition 5.3.15 (Triangular matrices)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. For (a), try diagonal matrices. For (c), the two products have different sizes when 𝑚≠𝑛.
Hint 2. For (d) and (e), what is 𝐴(1,…,1)?
Sketch. (a) False: 𝐼𝑛+diag(−1,−1,1,…,1)=diag(0,0,2,…,2). (b) True: 𝑑3=𝑑 gives 𝑑(𝑑−1)(𝑑+1)=0. (c) False: 𝐴=(10) gives det(𝐴𝖳𝐴)=0 and det(𝐴𝐴𝖳)=1; true when 𝑚=𝑛. (d) True: (1,…,1) is in the kernel. (e) False: (1010).

(a) False. Let 𝐴=𝐼𝑛 and 𝐵=diag(−1,−1,1,…,1). Both have determinant 1 (Proposition 5.3.15), but 𝐴+𝐵=diag(0,0,2,…,2) has determinant 0.

(b) True. Let 𝑑=det𝐴. By Theorem 5.4.10, 𝑑3=det(𝐴3)=det𝐴=𝑑, so 𝑑(𝑑−1)(𝑑+1)=𝑑3−𝑑=0. A field has no zero divisors (Proposition 1.1.17), so 𝑑 is 0, 1, or −1. (Over 𝔽2 the set {−1,0,1} is {0,1}.)

(c) False in general. Let 𝐴=(10)∈ℝ1×2. Then 𝐴𝖳𝐴=(1000) has determinant 0, while 𝐴𝐴𝖳=(1) has determinant 1. The statement is true when 𝑚=𝑛: then both sides equal det𝐴𝖳det𝐴=(det𝐴)2 by Theorem 5.4.10 and Theorem 5.4.14.

(d) True. The 𝑖-th entry of 𝐴(1,…,1) is the sum of row 𝑖, so 𝐴(1,…,1)=𝟎 with (1,…,1)≠𝟎, and det𝐴=0 by Corollary 5.4.8.

(e) False for every 𝑛≥2 (for 𝑛=1 it is true). (1010) has row sums 1 and determinant 0, and adding a diagonal block 𝐼𝑛−2 gives an example for each 𝑛≥2. The hypothesis says 𝐴(1,…,1)=(1,…,1), a statement about one vector, which says nothing about det𝐴.

Problem 5.5.standard Let 𝑝 be a prime.

  1. (a)Count the symmetric matrices (𝑎𝑏𝑏𝑑)∈𝔽𝑝2×2 with determinant 0.
  2. (b)Count the matrices 𝐴∈𝔽𝑝2×2 with tr𝐴=0 and det𝐴=0. Explain why the answers to (a) and (b) agree.
  3. (c)Show that 𝐴2−(tr𝐴)𝐴+(det𝐴)𝐼2=0 for every 𝐴∈𝐹2×2. Deduce that 𝐴2=0 if and only if tr𝐴=det𝐴=0, and count the 𝐴∈𝔽𝑝2×2 with 𝐴2=0.

Solution.

Uses. Definition 5.1.14 (The 2×2 determinant), Definition 2.4.26 (Trace), Theorem 5.4.10 (Multiplicativity), Proposition 1.1.17 (No zero divisors)

Hint 1. For (a), count the triples (𝑎,𝑏,𝑑) with 𝑎𝑑=𝑏2, splitting into the cases 𝑏=0 and 𝑏≠0.
Hint 2. In (b), 𝑑=−𝑎, and the condition becomes 𝑏(−𝑐)=𝑎2. For (c), multiply out 𝐴2; for the converse, take determinants of 𝐴2=0 first.
Sketch. (a) 𝑏=0: 𝑎𝑑=0 has 2𝑝−1 solutions. 𝑏≠0: 𝑎 is any of the 𝑝−1 nonzero elements and 𝑑=𝑏2𝑎−1. Total 2𝑝−1+(𝑝−1)2=𝑝2. (b) 𝑑=−𝑎 and 𝑏(−𝑐)=𝑎2 is the same equation 𝑥𝑦=𝑧2, so again 𝑝2. (c) Direct computation. If 𝐴2=0, then (det𝐴)2=0, so 𝐴2=(tr𝐴)𝐴, forcing tr𝐴=0. So there are 𝑝2 such 𝐴.

(a) By Definition 5.1.14 we count the triples (𝑎,𝑏,𝑑)∈𝔽𝑝3 with 𝑎𝑑−𝑏2=0. If 𝑏=0, we need 𝑎𝑑=0, that is, 𝑎=0 or 𝑑=0 (Proposition 1.1.17): there are 𝑝 triples with 𝑎=0 and 𝑝 with 𝑑=0, and one triple has both, so 2𝑝−1 in all. If 𝑏≠0 (𝑝−1 choices), then 𝑎𝑑=𝑏2≠0, so 𝑎≠0 (𝑝−1 choices), and then 𝑑=𝑏2𝑎−1 is determined. In all there are

2𝑝−1+(𝑝−1)2=𝑝2

such matrices.

(b) Write 𝐴=(𝑎𝑏𝑐𝑑). Then tr𝐴=0 means 𝑑=−𝑎, and then det𝐴=−𝑎2−𝑏𝑐, so the conditions say 𝑏(−𝑐)=𝑎2, with 𝑎,𝑏,𝑐 free otherwise. The map (𝑎,𝑏,𝑐)↦(𝑏,−𝑐,𝑎) is a bijection of 𝔽𝑝3 that turns these solutions into the solutions (𝑥,𝑦,𝑧) of 𝑥𝑦=𝑧2, and so does (𝑎,𝑏,𝑑)↦(𝑎,𝑑,𝑏) for the equation in (a). Both counts are the number of solutions of 𝑥𝑦=𝑧2 in 𝔽𝑝3, which is 𝑝2.

(c) With 𝐴=(𝑎𝑏𝑐𝑑),

𝐴2=(𝑎2+𝑏𝑐𝑎𝑏+𝑏𝑑𝑐𝑎+𝑑𝑐𝑐𝑏+𝑑2),(tr𝐴)𝐴=((𝑎+𝑑)𝑎(𝑎+𝑑)𝑏(𝑎+𝑑)𝑐(𝑎+𝑑)𝑑),

so 𝐴2−(tr𝐴)𝐴=(𝑏𝑐−𝑎𝑑00𝑏𝑐−𝑎𝑑)=−(det𝐴)𝐼2, as claimed.

If tr𝐴=det𝐴=0, the identity gives 𝐴2=0. Conversely, suppose 𝐴2=0. Then (det𝐴)2=det(𝐴2)=0 by Theorem 5.4.10, so det𝐴=0, and the identity becomes (tr𝐴)𝐴=𝐴2=0. Either tr𝐴=0, or 𝐴=0, and the zero matrix also has trace 0. So 𝐴2=0 exactly when tr𝐴=det𝐴=0, and by (b) there are 𝑝2 such matrices in 𝔽𝑝2×2, one of which is 0.

Problem 5.6.standard For points 𝐩1,…,𝐩𝑚∈ℝ2 with 𝑚≥3, put 𝐩𝑚+1=𝐩1 and

𝑆(𝐩1,…,𝐩𝑚)=12∑𝑘=1𝑚det(𝐩𝑘,𝐩𝑘+1),

where det(𝐮,𝐯) is the determinant of the matrix with columns 𝐮 and 𝐯.

  1. (a)Show that 𝑆 does not change when every 𝐩𝑘 is replaced by 𝐩𝑘+𝐜, for a fixed 𝐜∈ℝ2.
  2. (b)Show that 𝑆(𝐩,𝐪,𝐫)=12det(𝐪−𝐩,𝐫−𝐩). This is the signed area of the triangle 𝐩𝐪𝐫: its area, with a plus sign when 𝐩,𝐪,𝐫 run counterclockwise (Example 5.1.15).
  3. (c)Show that 𝑆(𝐩1,…,𝐩𝑚)=∑𝑘=1𝑚𝑆(𝐜,𝐩𝑘,𝐩𝑘+1) for every 𝐜∈ℝ2. Explain why 𝑆 is the area of a convex polygon whose vertices 𝐩1,…,𝐩𝑚 are listed counterclockwise. (Take for granted that the area of a region cut into triangles is the sum of their areas.)
  4. (d)Find the area of the pentagon with vertices (0,0),(4,0),(5,3),(2,5),(−1,3).

Solution.

Uses. Definition 5.1.14 (The 2×2 determinant), Theorem 5.1.13 (The 2×2 determinant), Proposition 5.1.10 (Alternating implies antisymmetric), Example 5.1.15 (det is signed area)

Techniques. Expand by multilinearity (Technique 5.1.7)

Hint 1. For (a), expand det(𝐩𝑘+𝐜,𝐩𝑘+1+𝐜) into four terms, and sum over 𝑘. The sums ∑𝑘𝐩𝑘 and ∑𝑘𝐩𝑘+1 are equal.
Hint 2. For (b), apply (a) with 𝐜=−𝐩. For (c), apply (b) to each triangle and then (a) with −𝐜.
Sketch. (a) The extra terms sum to det(𝐬,𝐜)+det(𝐜,𝐬) with 𝐬=∑𝑘𝐩𝑘, which is 0 by antisymmetry, and det(𝐜,𝐜)=0. (b) After translating by −𝐩, two of the three terms involve 𝟎. (c) ∑𝑘𝑆(𝐜,𝐩𝑘,𝐩𝑘+1)=12∑𝑘det(𝐩𝑘−𝐜,𝐩𝑘+1−𝐜)=𝑆 by (a); for an interior 𝐜 the triangles tile the polygon and are all counterclockwise. (d) 12(0+12+19+11+0)=21.

(a) By multilinearity, with det(𝐜,𝐜)=0,

det(𝐩𝑘+𝐜,𝐩𝑘+1+𝐜)=det(𝐩𝑘,𝐩𝑘+1)+det(𝐩𝑘,𝐜)+det(𝐜,𝐩𝑘+1).

Let 𝐬=∑𝑘=1𝑚𝐩𝑘. Since 𝐩𝑚+1=𝐩1, also ∑𝑘=1𝑚𝐩𝑘+1=𝐬. Summing over 𝑘 and using linearity in each column, the extra terms add up to

det(𝐬,𝐜)+det(𝐜,𝐬)=0

by antisymmetry (Proposition 5.1.10). So 𝑆 is unchanged.

(b) By (a) with 𝐜=−𝐩, and writing 𝐪′=𝐪−𝐩 and 𝐫′=𝐫−𝐩,

𝑆(𝐩,𝐪,𝐫)=𝑆(𝟎,𝐪′,𝐫′)=12(det(𝟎,𝐪′)+det(𝐪′,𝐫′)+det(𝐫′,𝟎))=12det(𝐪′,𝐫′),

since a matrix with a zero column has determinant 0. The triangle 𝐩𝐪𝐫 is half of the parallelogram spanned by 𝐪′ and 𝐫′, translated to 𝐩. By Example 5.1.15, det(𝐪′,𝐫′) is the signed area of that parallelogram, positive exactly when the turn from 𝐪′ to 𝐫′ is counterclockwise, that is, when 𝐩,𝐪,𝐫 run counterclockwise.

(c) By (b), 𝑆(𝐜,𝐩𝑘,𝐩𝑘+1)=12det(𝐩𝑘−𝐜,𝐩𝑘+1−𝐜). Summing over 𝑘 gives 𝑆(𝐩1−𝐜,…,𝐩𝑚−𝐜), which is 𝑆(𝐩1,…,𝐩𝑚) by (a).

Now let the polygon be convex with counterclockwise vertices, and let 𝐜 be a point inside it. The segments from 𝐜 to the vertices cut the polygon into the triangles 𝐜𝐩𝑘𝐩𝑘+1, and each of these runs counterclockwise, since the boundary of the polygon does. By (b), each 𝑆(𝐜,𝐩𝑘,𝐩𝑘+1) is the area of its triangle, and their sum is the area of the polygon.

(d) The terms det(𝐩𝑘,𝐩𝑘+1) are

det(0400)=0,det(4503)=12,det(5235)=19,det(2−153)=11,det(−1030)=0,

so 𝑆=12(0+12+19+11+0)=21. The pentagon is convex and its vertices run counterclockwise: the edge vectors (4,0),(1,3),(−3,2),(−3,−2),(1,−3) point in the directions of about 0°, 72°, 146°, 214°, and 288°, so the boundary turns left at every vertex and makes exactly one full turn in all. Hence the area is 21. (Left turns alone are not enough: the edges of a five-pointed star also turn left at every vertex, but they make two full turns.)

Problem 5.7.standard Let 𝐩0,…,𝐩𝑛∈𝐹𝑛, and let 𝑀∈𝐹(𝑛+1)×(𝑛+1) have column 𝑖+1 equal to (1,𝐩𝑖), the entry 1 followed by the entries of 𝐩𝑖.

  1. (a)Show that det𝑀=det(𝐩1−𝐩0,…,𝐩𝑛−𝐩0).
  2. (b)Deduce that det𝑀≠0 if and only if 𝐩1−𝐩0,…,𝐩𝑛−𝐩0 are linearly independent.
  3. (c)Suppose det𝑀≠0. Show that for each 𝐱∈𝐹𝑛 there are unique 𝜆0,…,𝜆𝑛∈𝐹 with 𝜆0+⋯+𝜆𝑛=1 and 𝜆0𝐩0+⋯+𝜆𝑛𝐩𝑛=𝐱, namely 𝜆𝑖=det𝑀𝑖/det𝑀, where 𝑀𝑖 is 𝑀 with column 𝑖+1 replaced by (1,𝐱).
  4. (d)Let 𝐹=ℝ and 𝑛=2. Using Problem 5.6 (b), express each 𝜆𝑖 as a ratio of signed areas of triangles. Deduce that 𝜆0,𝜆1,𝜆2>0 exactly when the triangles 𝐱𝐩1𝐩2, 𝐩0𝐱𝐩2, and 𝐩0𝐩1𝐱 have the same orientation as 𝐩0𝐩1𝐩2, and compute the 𝜆𝑖 for 𝐱=(1,2) and the triangle with vertices (0,0),(4,0),(0,4).

Solution.

Uses. Lemma 5.1.8 (Column replacement), Lemma 5.5.2 (A row or column with one nonzero entry), Corollary 5.4.8 (Vanishing determinants), Theorem 5.5.14 (Cramer’s rule), Proposition 2.4.8 (Four views of the product)

Hint 1. For (a), subtract column 1 from the other columns, and expand along the first row.
Hint 2. For (c), the two conditions on 𝜆 are one linear system 𝑀𝛌=(1,𝐱). For (d), apply (a) to 𝑀𝑖, which is the matrix of the same kind built from the points with 𝐩𝑖 replaced by 𝐱.
Sketch. (a) Column replacements turn column 𝑖+1 into (0,𝐩𝑖−𝐩0), after which row 1 is 𝐞1𝖳 and the minor is the matrix with columns 𝐩𝑖−𝐩0. (b) Corollary 5.4.8. (c) The conditions read 𝑀𝛌=(1,𝐱); apply Cramer’s rule. (d) By (a) and Problem 5.6 (b), det𝑀𝑖 is twice the signed area of the triangle with 𝐩𝑖 replaced by 𝐱, and det𝑀 is twice that of 𝐩0𝐩1𝐩2. For the example, det𝑀=16 and 𝜆=(1/4,1/4,1/2).

(a) For 𝑖=1,…,𝑛, subtract column 1 from column 𝑖+1. These replacements do not change the determinant (Lemma 5.1.8), and column 𝑖+1 becomes (0,𝐩𝑖−𝐩0). Now row 1 is (1,0,…,0), so by Lemma 5.5.2 the determinant is (−1)1+1⋅1 times the determinant of the matrix left after deleting row 1 and column 1, whose columns are 𝐩1−𝐩0,…,𝐩𝑛−𝐩0.

(b) By (a) and Corollary 5.4.8, det𝑀≠0 exactly when the columns 𝐩𝑖−𝐩0 are independent. For 𝑛=2 this says that 𝐩1−𝐩0 and 𝐩2−𝐩0 do not lie on one line through 𝟎, that is, the three points do not lie on one line.

(c) Let 𝛌=(𝜆0,…,𝜆𝑛). By Proposition 2.4.8, 𝑀𝛌=∑𝑖𝜆𝑖(1,𝐩𝑖), whose first entry is ∑𝑖𝜆𝑖 and whose other entries form ∑𝑖𝜆𝑖𝐩𝑖. So the two conditions say exactly 𝑀𝛌=(1,𝐱). Since det𝑀≠0, Cramer’s rule (Theorem 5.5.14) gives a unique solution, with 𝜆𝑖=det𝑀𝑖/det𝑀.

(d) 𝑀𝑖 is the matrix 𝑀 built from the points 𝐩0,…,𝐱,…,𝐩𝑛, with 𝐱 in place of 𝐩𝑖. By (a) and Problem 5.6 (b), det𝑀=2𝑆(𝐩0,𝐩1,𝐩2) and

det𝑀0=2𝑆(𝐱,𝐩1,𝐩2),det𝑀1=2𝑆(𝐩0,𝐱,𝐩2),det𝑀2=2𝑆(𝐩0,𝐩1,𝐱).

So 𝜆𝑖 is the signed area of the triangle with 𝐩𝑖 replaced by 𝐱, divided by the signed area of 𝐩0𝐩1𝐩2. It is positive exactly when the two signed areas have the same sign, that is, the two triangles have the same orientation.

For 𝐩0=(0,0), 𝐩1=(4,0), 𝐩2=(0,4), and 𝐱=(1,2):

det𝑀=det(4004)=16,det𝑀1=det(1024)=4,det𝑀2=det(4102)=8,

and det𝑀0=det(𝐩1−𝐱,𝐩2−𝐱)=det(3−1−22)=4. So 𝜆=(1/4,1/4,1/2), and indeed 14(0,0)+14(4,0)+12(0,4)=(1,2). All three are positive, so (1,2) lies inside the triangle in this sense. These 𝜆𝑖 are the barycentric coordinates of Section 4.7, and the sign test is the standard way to decide whether a point lies in a triangle.

Problem 5.8.standard Let 𝛼,𝛽∈𝐹, and let 𝑇∈L(𝐹𝑛×𝑛) be 𝑇(𝑋)=𝛼𝑋+𝛽𝑋𝖳. Write 𝑈𝑖𝑗 for the matrix units (Lemma 2.4.24).

  1. (a)Suppose 1+1≠0 in 𝐹. Show that the matrices 𝑈𝑖𝑖, 𝑈𝑖𝑗+𝑈𝑗𝑖, and 𝑈𝑖𝑗−𝑈𝑗𝑖 (for 𝑖<𝑗) form a basis of 𝐹𝑛×𝑛 in which the matrix of 𝑇 is diagonal, and deduce that

    det𝑇=(𝛼+𝛽)𝑛(𝑛+1)/2(𝛼−𝛽)𝑛(𝑛−1)/2.
  2. (b)Check (a) against Exercise 5.4.40.
  3. (c)Show that the formula holds for 𝑛=2 over every field, including 𝔽2, by using the basis 𝑈11,𝑈12,𝑈21,𝑈22.
  4. (d)Keep 1+1≠0. For which 𝛼,𝛽 is 𝑇 invertible? Describe ker𝑇 when 𝛼=𝛽≠0.

Solution.

Uses. Definition 5.4.18 (Determinant of an operator), Definition 1.6.1 (Basis), Proposition 5.3.15 (Triangular matrices), Proposition 5.4.20 (Properties of the determinant of an operator), Exercise 5.4.40

Hint 1. Symmetric matrices are fixed by the transpose and skew-symmetric ones are negated. What does 𝑇 do to each kind?
Hint 2. For the basis in (a), 𝑈𝑖𝑗=12((𝑈𝑖𝑗+𝑈𝑗𝑖)+(𝑈𝑖𝑗−𝑈𝑗𝑖)), and there are 𝑛+2⋅𝑛(𝑛−1)/2=𝑛2 matrices in the list.
Sketch. (a) 𝑇 multiplies 𝑈𝑖𝑖 and 𝑈𝑖𝑗+𝑈𝑗𝑖 by 𝛼+𝛽, and 𝑈𝑖𝑗−𝑈𝑗𝑖 by 𝛼−𝛽. There are 𝑛+𝑛(𝑛−1)/2=𝑛(𝑛+1)/2 basis vectors of the first kind. (b) 𝛼=0, 𝛽=1 gives (−1)𝑛(𝑛−1)/2. (c) The matrix is block diagonal with blocks 𝛼+𝛽, (𝛼𝛽𝛽𝛼), 𝛼+𝛽, so det𝑇=(𝛼+𝛽)2(𝛼2−𝛽2)=(𝛼+𝛽)3(𝛼−𝛽). (d) Invertible iff 𝛼+𝛽≠0 and, for 𝑛≥2, 𝛼−𝛽≠0; for 𝛼=𝛽≠0 the kernel is the space of skew-symmetric matrices.

(a) Let 𝑆𝑖𝑗=𝑈𝑖𝑗+𝑈𝑗𝑖 and 𝐾𝑖𝑗=𝑈𝑖𝑗−𝑈𝑗𝑖 for 𝑖<𝑗. The list 𝑈11,…,𝑈𝑛𝑛, 𝑆𝑖𝑗, 𝐾𝑖𝑗 has 𝑛+2⋅𝑛(𝑛−1)/2=𝑛2 entries.

It spans. Each 𝑈𝑖𝑖 is in the list, and for 𝑖<𝑗, 𝑈𝑖𝑗=(1+1)−1(𝑆𝑖𝑗+𝐾𝑖𝑗) and 𝑈𝑗𝑖=(1+1)−1(𝑆𝑖𝑗−𝐾𝑖𝑗). So the span contains every matrix unit, hence all of 𝐹𝑛×𝑛.

It is independent. Suppose ∑𝑖𝑎𝑖𝑈𝑖𝑖+∑𝑖<𝑗(𝑏𝑖𝑗𝑆𝑖𝑗+𝑐𝑖𝑗𝐾𝑖𝑗)=0. The (𝑖,𝑖) entry gives 𝑎𝑖=0. For 𝑖<𝑗, the (𝑖,𝑗) and (𝑗,𝑖) entries give 𝑏𝑖𝑗+𝑐𝑖𝑗=0 and 𝑏𝑖𝑗−𝑐𝑖𝑗=0, so (1+1)𝑏𝑖𝑗=0, hence 𝑏𝑖𝑗=0 and 𝑐𝑖𝑗=0.

So the list is a basis (Definition 1.6.1). Since 𝑈𝑖𝑖𝖳=𝑈𝑖𝑖, 𝑆𝑖𝑗𝖳=𝑆𝑖𝑗, and 𝐾𝑖𝑗𝖳=−𝐾𝑖𝑗,

𝑇(𝑈𝑖𝑖)=(𝛼+𝛽)𝑈𝑖𝑖,𝑇(𝑆𝑖𝑗)=(𝛼+𝛽)𝑆𝑖𝑗,𝑇(𝐾𝑖𝑗)=(𝛼−𝛽)𝐾𝑖𝑗.

So the matrix of 𝑇 in this basis is diagonal, with 𝛼+𝛽 appearing 𝑛+𝑛(𝑛−1)/2=𝑛(𝑛+1)/2 times and 𝛼−𝛽 appearing 𝑛(𝑛−1)/2 times. By Definition 5.4.18 and Proposition 5.3.15, det𝑇 is the product of these diagonal entries, as claimed.

(b) The transpose operator is the case 𝛼=0, 𝛽=1, and the formula gives 1⋅(−1)𝑛(𝑛−1)/2, which is the answer of Exercise 5.4.40.

(c) For 𝑛=2, 𝑇(𝑈11)=(𝛼+𝛽)𝑈11, 𝑇(𝑈22)=(𝛼+𝛽)𝑈22, 𝑇(𝑈12)=𝛼𝑈12+𝛽𝑈21, and 𝑇(𝑈21)=𝛽𝑈12+𝛼𝑈21. In the basis 𝑈11,𝑈12,𝑈21,𝑈22 the matrix of 𝑇 is

(𝛼+𝛽0000𝛼𝛽00𝛽𝛼0000𝛼+𝛽),

which is block diagonal, so det𝑇=(𝛼+𝛽)2(𝛼2−𝛽2)=(𝛼+𝛽)3(𝛼−𝛽) (Corollary 5.4.27). This is the formula of (a) for 𝑛=2, and the computation used nothing about 1+1. (Over 𝔽2 it reads (𝛼+𝛽)4.)

(d) By Proposition 5.4.20, 𝑇 is invertible exactly when det𝑇≠0, that is, when 𝛼+𝛽≠0 and, if 𝑛≥2, also 𝛼−𝛽≠0. If 𝛼=𝛽≠0, then in the basis of (a) the diagonal entries are 1+1 times 𝛼 for 𝑈𝑖𝑖 and 𝑆𝑖𝑗, which is nonzero, and 0 for 𝐾𝑖𝑗. So ker𝑇=span(𝐾𝑖𝑗|𝑖<𝑗), the space of skew-symmetric matrices, of dimension 𝑛(𝑛−1)/2. Directly: 𝛼(𝑋+𝑋𝖳)=0 exactly when 𝑋𝖳=−𝑋.

Problem 5.9.standard Let 𝑥1,…,𝑥𝑛∈𝐹, let 𝑠𝑘=𝑥1𝑘+⋯+𝑥𝑛𝑘 for 𝑘≥0 (so 𝑠0=1+⋯+1, with 𝑛 terms), and let 𝐻∈𝐹𝑛×𝑛 be the Hankel matrix with (𝑖,𝑗) entry 𝑠𝑖+𝑗−2:

𝐻=(𝑠0𝑠1⋯𝑠𝑛−1𝑠1𝑠2⋯𝑠𝑛⋮⋮⋱⋮𝑠𝑛−1𝑠𝑛⋯𝑠2𝑛−2).
  1. (a)Show that 𝐻=𝑉𝖳𝑉 for the Vandermonde matrix 𝑉=𝑉(𝑥1,…,𝑥𝑛), and deduce that det𝐻=∏1≤𝑖<𝑗≤𝑛(𝑥𝑗−𝑥𝑖)2.
  2. (b)Check (a) directly for 𝑛=2.
  3. (c)Let 𝐹=ℝ. Show that det𝐻≥0, with equality exactly when two of the 𝑥𝑖 coincide. Show by an example that det𝐻 can be negative when 𝐹=ℂ.
  4. (d)Real numbers 𝑥1,𝑥2,𝑥3 have 𝑠1=0, 𝑠2=6, 𝑠3=0, and 𝑠4=18. Are they distinct?

Solution.

Uses. Definition 3.4.22 (Vandermonde matrix), Theorem 5.5.21 (The Vandermonde determinant), Theorem 5.4.10 (Multiplicativity), Theorem 5.4.14 (The transpose), Definition 2.4.1 (Matrix product)

Techniques. Factor the matrix (Technique 5.6.1)

Hint 1. The (𝑙,𝑗) entry of 𝑉 is 𝑥𝑙𝑗−1. Compute the (𝑖,𝑗) entry of 𝑉𝖳𝑉 as a sum over 𝑙.
Hint 2. For (c), a real square is nonnegative. Over ℂ, try 𝑥=(𝑖,−𝑖). For (d), you do not need the 𝑥𝑖: compute det𝐻 from the power sums.
Sketch. (a) (𝑉𝖳𝑉)𝑖𝑗=∑𝑙𝑥𝑙𝑖−1𝑥𝑙𝑗−1=𝑠𝑖+𝑗−2, so det𝐻=(det𝑉)2. (b) 2(𝑥12+𝑥22)−(𝑥1+𝑥2)2=(𝑥1−𝑥2)2. (c) Squares of reals; over ℂ, 𝑥=(𝑖,−𝑖) gives 𝐻=(200−2). (d) det(3060606018)=108>0, so yes.

(a) The (𝑙,𝑗) entry of 𝑉 is 𝑥𝑙𝑗−1 (Definition 3.4.22), so the (𝑖,𝑙) entry of 𝑉𝖳 is 𝑥𝑙𝑖−1, and

(𝑉𝖳𝑉)𝑖𝑗=∑𝑙=1𝑛𝑥𝑙𝑖−1𝑥𝑙𝑗−1=∑𝑙=1𝑛𝑥𝑙𝑖+𝑗−2=𝑠𝑖+𝑗−2.

So 𝐻=𝑉𝖳𝑉, and by Theorem 5.4.10, Theorem 5.4.14, and Theorem 5.5.21,

det𝐻=det𝑉𝖳det𝑉=(det𝑉)2=∏1≤𝑖<𝑗≤𝑛(𝑥𝑗−𝑥𝑖)2.

(b) For 𝑛=2, 𝐻=(2𝑥1+𝑥2𝑥1+𝑥2𝑥12+𝑥22), and

det𝐻=2𝑥12+2𝑥22−(𝑥1+𝑥2)2=𝑥12−2𝑥1𝑥2+𝑥22=(𝑥2−𝑥1)2.

(c) Over ℝ, det𝐻=(det𝑉)2≥0, with equality exactly when det𝑉=0, that is, when some factor 𝑥𝑗−𝑥𝑖 is 0 (Proposition 1.1.17). Over ℂ, take 𝑛=2, 𝑥1=𝑖, and 𝑥2=−𝑖, where 𝑖 is the imaginary unit: then 𝑠0=2, 𝑠1=0, 𝑠2=𝑖2+(−𝑖)2=−2, and det𝐻=det(200−2)=−4, which is (𝑥2−𝑥1)2=(−2𝑖)2.

(d) Here 𝑠0=3, and

det𝐻=det(3060606018)=6(3⋅18−6⋅6)=108>0,

expanding along the middle row. By (c), the 𝑥𝑖 are distinct. (Indeed 𝑥=(−3,0,3) has these power sums, and (3)2(23)2(3)2=108.)

Problem 5.10.standard For 𝑎∈𝐹 and 𝑛≥1, let 𝐾𝑛∈𝐹𝑛×𝑛 have (𝑖,𝑗) entry 𝑎|𝑖−𝑗|, where 𝑎0=1. For example,

𝐾3=(1𝑎𝑎2𝑎1𝑎𝑎2𝑎1).
  1. (a)Show that det𝐾𝑛=(1−𝑎2)𝑛−1.
  2. (b)Compute adj𝐾3, and find 𝐾3−1 when 𝑎2≠1.
  3. (c)Let 𝑛≥2 and 𝑎2≠1. Guess 𝐾𝑛−1 from (b), and verify your guess.

Solution.

Uses. Corollary 5.4.15 (Rows), Proposition 5.3.15 (Triangular matrices), Definition 5.5.6 (Cofactors, cofactor matrix, adjugate), Theorem 5.5.9 (The adjugate and the inverse), Theorem 5.4.10 (Multiplicativity), Theorem 5.4.7 (Invertibility and the determinant)

Techniques. Expose a factor with row and column operations (Technique 5.5.22)

Hint 1. Subtract 𝑎 times row 𝑖−1 from row 𝑖, for 𝑖=𝑛,…,2. What happens to the entries left of the diagonal?
Hint 2. For (c), the inverse of 𝐾3 is tridiagonal. Guess a tridiagonal 𝑇 with −𝑎 next to the diagonal, and check 𝐾𝑛𝑇=(1−𝑎2)𝐼𝑛 column by column.
Sketch. (a) The row operations make the entries left of the diagonal 0 and multiply those on and right of it by 1−𝑎2 (except in row 1), leaving an upper triangular matrix with diagonal 1,1−𝑎2,…,1−𝑎2. (b) adj𝐾3=(1−𝑎2)(1−𝑎0−𝑎1+𝑎2−𝑎0−𝑎1). (c) 𝐾𝑛−1=(1−𝑎2)−1𝑇, where 𝑇 is tridiagonal with diagonal 1,1+𝑎2,…,1+𝑎2,1 and −𝑎 beside the diagonal.

(a) For 𝑖=𝑛,𝑛−1,…,2 in turn, subtract 𝑎 times row 𝑖−1 from row 𝑖; working from the bottom up, row 𝑖−1 is still the original row when it is used. These replacements do not change the determinant (Corollary 5.4.15). For 𝑖≥2 the new (𝑖,𝑗) entry is 𝑎|𝑖−𝑗|−𝑎⋅𝑎|𝑖−1−𝑗|. If 𝑗≤𝑖−1, this is 𝑎𝑖−𝑗−𝑎⋅𝑎𝑖−1−𝑗=0. If 𝑗≥𝑖, it is 𝑎𝑗−𝑖−𝑎⋅𝑎𝑗−𝑖+1=𝑎𝑗−𝑖(1−𝑎2). So the new matrix is upper triangular with diagonal entries 1,1−𝑎2,…,1−𝑎2, and det𝐾𝑛=(1−𝑎2)𝑛−1 by Proposition 5.3.15.

(b) The cofactors of 𝐾3 are

𝑐11=1−𝑎2,𝑐12=−(𝑎−𝑎3),𝑐13=𝑎2−𝑎2=0,𝑐22=1−𝑎4,𝑐23=−(𝑎−𝑎3),𝑐33=1−𝑎2,

and 𝑐𝑗𝑖=𝑐𝑖𝑗 since 𝐾3 is symmetric. Factoring out 1−𝑎2,

adj𝐾3=(1−𝑎2)(1−𝑎0−𝑎1+𝑎2−𝑎0−𝑎1).

By (a), det𝐾3=(1−𝑎2)2, so when 𝑎2≠1, Theorem 5.5.9 gives

𝐾3−1=11−𝑎2(1−𝑎0−𝑎1+𝑎2−𝑎0−𝑎1).

(c) Let 𝑇∈𝐹𝑛×𝑛 be tridiagonal with diagonal entries 1,1+𝑎2,…,1+𝑎2,1 (the first and last are 1) and every entry next to the diagonal equal to −𝑎. We check 𝐾𝑛𝑇=(1−𝑎2)𝐼𝑛 one column at a time.

Column 1 of 𝑇 is (1,−𝑎,0,…,0), so the (𝑖,1) entry of 𝐾𝑛𝑇 is 𝑎|𝑖−1|−𝑎⋅𝑎|𝑖−2|. For 𝑖=1 it is 1−𝑎2, and for 𝑖≥2 it is 𝑎𝑖−1−𝑎𝑖−1=0. Column 𝑛 is the mirror image of column 1, with the same result.

Column 𝑗 with 1<𝑗<𝑛 has entries −𝑎,1+𝑎2,−𝑎 in rows 𝑗−1,𝑗,𝑗+1. The (𝑖,𝑗) entry of 𝐾𝑛𝑇 is

−𝑎⋅𝑎|𝑖−𝑗+1|+(1+𝑎2)𝑎|𝑖−𝑗|−𝑎⋅𝑎|𝑖−𝑗−1|.

If 𝑖=𝑗, this is −𝑎2+1+𝑎2−𝑎2=1−𝑎2. If 𝑖<𝑗, put 𝑑=𝑗−𝑖≥1; the entry is −𝑎𝑑+𝑎𝑑+𝑎𝑑+2−𝑎𝑑+2=0. If 𝑖>𝑗, put 𝑑=𝑖−𝑗≥1; it is −𝑎𝑑+2+𝑎𝑑+𝑎𝑑+2−𝑎𝑑=0.

So 𝐾𝑛𝑇=(1−𝑎2)𝐼𝑛. Taking determinants, det𝐾𝑛det𝑇=(1−𝑎2)𝑛≠0, so 𝐾𝑛 is invertible (Theorem 5.4.7), and multiplying by 𝐾𝑛−1 gives 𝐾𝑛−1=(1−𝑎2)−1𝑇.

Problem 5.11.hard Call 𝑁∈𝐹𝑛×𝑛 nilpotent if 𝑁𝑘=0 for some 𝑘≥1.

  1. (a)Find the error in the following argument, and show that its claim is false.

    Claim. If 𝐴∈𝐹𝑛×𝑛 is invertible and 𝑁∈𝐹𝑛×𝑛 is nilpotent, then 𝐴+𝑁 is invertible.

    Proof. Write 𝐴+𝑁=𝐴(𝐼𝑛+𝐴−1𝑁). Since 𝑁 is nilpotent, so is 𝑀=𝐴−1𝑁, say 𝑀𝑘=0. Then

    (𝐼𝑛+𝑀)(𝐼𝑛−𝑀+𝑀2−⋯+(−1)𝑘−1𝑀𝑘−1)=𝐼𝑛+(−1)𝑘−1𝑀𝑘=𝐼𝑛,

    so 𝐼𝑛+𝑀 is invertible, and 𝐴+𝑁 is a product of invertible matrices.

  2. (b)Show that the claim is true when 𝐴𝑁=𝑁𝐴.
  3. (c)Let 𝑁∈ℂ𝑛×𝑛 be nilpotent. Show that det(𝐼𝑛+𝑁)=1. (Hint: 𝑡↦det(𝐼𝑛+𝑡𝑁) is a polynomial function of 𝑡 with no zeros.)
  4. (d)Deduce that if 𝐴∈ℂ𝑛×𝑛 is invertible, 𝑁 is nilpotent, and 𝐴𝑁=𝑁𝐴, then det(𝐴+𝑁)=det𝐴.

Solution.

Uses. Theorem 5.4.10 (Multiplicativity), Theorem 5.4.7 (Invertibility and the determinant), Proposition 5.3.19 (det(𝐴+𝑡𝐼𝑛) as a function of 𝑡), Theorem 7.1.32 (Fundamental Theorem of Algebra)

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

Hint 1. The product computation is fine. Test the sentence “so is 𝑀=𝐴−1𝑁” on 2×2 matrices, with 𝐴 a swap.
Hint 2. For (b), commuting lets you regroup (𝐴−1𝑁)𝑘. For (c), the polynomial det(𝐼𝑛+𝑡𝑁) never vanishes; over ℂ, what does that force?
Sketch. (a) 𝐴−1𝑁 need not be nilpotent: 𝐴=(0110) and 𝑁=(00−10) give 𝐴+𝑁=(0100), singular, and 𝐴−1𝑁=(−1000). (b) If 𝐴𝑁=𝑁𝐴, then (𝐴−1𝑁)𝑘=𝐴−𝑘𝑁𝑘=0. (c) 𝑔(𝑡)=det(𝐼𝑛+𝑡𝑁) is 𝑒0+𝑒1𝑡+⋯+𝑒𝑛𝑡𝑛 and has no zeros, since 𝑡𝑁 is nilpotent and commutes with 𝐼𝑛. A nonconstant complex polynomial has a root, so 𝑔 is constant, equal to 𝑔(0)=1. (d) det(𝐴+𝑁)=det𝐴det(𝐼𝑛+𝐴−1𝑁)=det𝐴.

(a) The error is the claim that 𝑀=𝐴−1𝑁 is nilpotent. (The displayed product is correct: it telescopes to 𝐼𝑛−(−𝑀)𝑘.) Let

𝐴=(0110),𝑁=(00−10).

Then 𝐴 is invertible (𝐴−1=𝐴), 𝑁2=0, and 𝐴+𝑁=(0100) has a zero row, so it is not invertible. Here 𝐴−1𝑁=(−1000), whose powers ((−1)𝑘000) are never 0.

(b) Suppose 𝐴𝑁=𝑁𝐴. Multiplying by 𝐴−1 on both sides gives 𝑁𝐴−1=𝐴−1𝑁. So 𝐴−1 and 𝑁 commute, and by induction on 𝑘, (𝐴−1𝑁)𝑘=𝐴−𝑘𝑁𝑘 (move each 𝐴−1 to the left past the factors 𝑁). If 𝑁𝑘=0, then (𝐴−1𝑁)𝑘=0, 𝑀=𝐴−1𝑁 is nilpotent, and the argument of (a) is valid.

(c) Let 𝑁𝑘=0 and 𝑔(𝑡)=det(𝐼𝑛+𝑡𝑁) for 𝑡∈ℂ. Since (𝑡𝑁)𝑘=𝑡𝑘𝑁𝑘=0 and 𝑡𝑁 commutes with 𝐼𝑛, (b) with 𝐴=𝐼𝑛 shows that 𝐼𝑛+𝑡𝑁 is invertible, so 𝑔(𝑡)≠0 for every 𝑡 (Theorem 5.4.7). Every entry of 𝐼𝑛+𝑡𝑁 has the form 𝛼+𝛽𝑡, so, as in the proof of Proposition 5.3.19, 𝑔(𝑡)=𝑒0+𝑒1𝑡+⋯+𝑒𝑛𝑡𝑛 for some 𝑒0,…,𝑒𝑛∈ℂ and all 𝑡, with 𝑒0=𝑔(0)=det𝐼𝑛=1. If 𝑒𝑚≠0 for some 𝑚≥1, the polynomial 𝑒0+𝑒1𝑥+⋯+𝑒𝑛𝑥𝑛∈ℂ[𝑥] has degree at least 1, so it has a root 𝑡0∈ℂ (Theorem 7.1.32), and 𝑔(𝑡0)=0, which is impossible. So 𝑒1=⋯=𝑒𝑛=0, and 𝑔(𝑡)=1 for every 𝑡. In particular det(𝐼𝑛+𝑁)=𝑔(1)=1.

(d) By (b), 𝐴−1𝑁 is nilpotent, so by (c) and Theorem 5.4.10,

det(𝐴+𝑁)=det(𝐴(𝐼𝑛+𝐴−1𝑁))=det𝐴det(𝐼𝑛+𝐴−1𝑁)=det𝐴.

A real matrix can be regarded as a complex one with the same determinant, since the Leibniz formula uses only sums and products of the entries, so (c) and (d) also hold over ℝ.

Problem 5.12.hard Let 𝑛≥2 and 𝑐0,…,𝑐𝑛−1∈ℂ, and let 𝐶∈ℂ𝑛×𝑛 be the circulant matrix whose rows are the successive cyclic shifts of (𝑐0,𝑐1,…,𝑐𝑛−1) to the right. With rows and columns indexed by 0,…,𝑛−1, its (𝑗,𝑘) entry is 𝑐(𝑘−𝑗)mod𝑛; for 𝑛=3,

𝐶=(𝑐0𝑐1𝑐2𝑐2𝑐0𝑐1𝑐1𝑐2𝑐0).

Let 𝑓(𝑧)=𝑐0+𝑐1𝑧+⋯+𝑐𝑛−1𝑧𝑛−1 and 𝜔=cos(2𝜋/𝑛)+𝑖sin(2𝜋/𝑛). You may use that 1,𝜔,…,𝜔𝑛−1 are distinct, that each of them satisfies 𝑧𝑛=1, and that 𝜔𝑛/2=−1 when 𝑛 is even (Section B.1).

  1. (a)For 0≤𝑚≤𝑛−1, let 𝐯𝑚=(1,𝜔𝑚,𝜔2𝑚,…,𝜔(𝑛−1)𝑚). Show that 𝐶𝐯𝑚=𝑓(𝜔𝑚)𝐯𝑚.
  2. (b)Deduce that det𝐶=𝑓(1)𝑓(𝜔)⋯𝑓(𝜔𝑛−1).
  3. (c)Deduce that det(𝑎𝑏𝑐𝑐𝑎𝑏𝑏𝑐𝑎)=(𝑎+𝑏+𝑐)(𝑎+𝜔𝑏+𝜔2𝑐)(𝑎+𝜔2𝑏+𝜔𝑐), where 𝜔=−12+(3/2)𝑖.
  4. (d)Let 𝐶 have first row (1,1,0,…,0). Show that 𝐶 is singular if and only if 𝑛 is even, and that det𝐶=2 when 𝑛 is odd.

Solution.

Uses. Theorem 5.5.21 (The Vandermonde determinant), Theorem 5.4.10 (Multiplicativity), Proposition 2.4.8 (Four views of the product), Proposition 5.3.15 (Triangular matrices), Lemma 5.5.23 (A polynomial with prescribed roots)

Techniques. Factor the matrix (Technique 5.6.1)

Hint 1. In (𝐶𝐯𝑚)𝑗=∑𝑘𝑐(𝑘−𝑗)mod𝑛𝜔𝑚𝑘, substitute 𝑙=(𝑘−𝑗)mod𝑛 and use 𝜔𝑛=1.
Hint 2. Put the 𝐯𝑚 side by side as the columns of a matrix 𝑊. Then 𝐶𝑊=𝑊𝐷 with 𝐷 diagonal, and 𝑊 is a Vandermonde matrix.
Hint 3. For (d), 𝑓(𝑧)=1+𝑧. For the value, evaluate 𝑡𝑛−1=∏𝑚(𝑡−𝜔𝑚) at 𝑡=−1.
Sketch. (a) (𝐶𝐯𝑚)𝑗=∑𝑙𝑐𝑙𝜔𝑚(𝑗+𝑙)=𝜔𝑚𝑗𝑓(𝜔𝑚). (b) 𝑊 with columns 𝐯𝑚 is 𝑉(1,𝜔,…,𝜔𝑛−1), invertible since the nodes are distinct, and 𝐶𝑊=𝑊diag(𝑓(𝜔𝑚)); cancel det𝑊. (c) 𝑛=3 and 𝜔4=𝜔. (d) 𝑓(𝜔𝑚)=1+𝜔𝑚=0 iff 𝜔𝑚=−1, possible iff 𝑛 is even. For odd 𝑛, 𝑡𝑛−1=∏𝑚(𝑡−𝜔𝑚) at 𝑡=−1 gives −2=−∏𝑚(1+𝜔𝑚).

(a) By definition, (𝐶𝐯𝑚)𝑗=∑𝑘=0𝑛−1𝑐(𝑘−𝑗)mod𝑛𝜔𝑚𝑘. As 𝑘 runs over 0,…,𝑛−1, so does 𝑙=(𝑘−𝑗)mod𝑛, and 𝑘=𝑗+𝑙 or 𝑘=𝑗+𝑙−𝑛. Since 𝜔𝑛=1, in both cases 𝜔𝑚𝑘=𝜔𝑚(𝑗+𝑙). So

(𝐶𝐯𝑚)𝑗=∑𝑙=0𝑛−1𝑐𝑙𝜔𝑚𝑗𝜔𝑚𝑙=𝜔𝑚𝑗𝑓(𝜔𝑚),

which is the 𝑗-th entry of 𝑓(𝜔𝑚)𝐯𝑚.

(b) Let 𝑊 be the matrix with columns 𝐯0,…,𝐯𝑛−1. Its (𝑘,𝑚) entry is 𝜔𝑘𝑚=(𝜔𝑘)𝑚, so 𝑊 is the Vandermonde matrix 𝑉(1,𝜔,…,𝜔𝑛−1), and det𝑊≠0 by Theorem 5.5.21, since the nodes are distinct. By (a) and Proposition 2.4.8, column 𝑚 of 𝐶𝑊 is 𝑓(𝜔𝑚)𝐯𝑚, which is column 𝑚 of 𝑊𝐷 for 𝐷=diag(𝑓(1),𝑓(𝜔),…,𝑓(𝜔𝑛−1)). So 𝐶𝑊=𝑊𝐷, and by Theorem 5.4.10 and Proposition 5.3.15,

det𝐶det𝑊=det𝑊det𝐷=det𝑊∏𝑚=0𝑛−1𝑓(𝜔𝑚).

Dividing by det𝑊≠0 gives the claim.

(c) For 𝑛=3 and (𝑐0,𝑐1,𝑐2)=(𝑎,𝑏,𝑐), the matrix is (𝑎𝑏𝑐𝑐𝑎𝑏𝑏𝑐𝑎) and 𝑓(𝑧)=𝑎+𝑏𝑧+𝑐𝑧2. So det=𝑓(1)𝑓(𝜔)𝑓(𝜔2) with 𝑓(𝜔2)=𝑎+𝑏𝜔2+𝑐𝜔4=𝑎+𝑏𝜔2+𝑐𝜔, since 𝜔3=1.

(d) Here 𝑓(𝑧)=1+𝑧, so by (b), det𝐶=0 exactly when 𝜔𝑚=−1 for some 𝑚. If 𝑛 is even, 𝜔𝑛/2=−1. If 𝑛 is odd, then (−1)𝑛=−1, while (𝜔𝑚)𝑛=1, so no 𝜔𝑚 equals −1. Hence 𝐶 is singular exactly when 𝑛 is even.

For odd 𝑛, the polynomial 𝑥𝑛−1 has degree 𝑛, leading coefficient 1, and the 𝑛 distinct roots 1,𝜔,…,𝜔𝑛−1, so by Lemma 5.5.23, 𝑡𝑛−1=∏𝑚=0𝑛−1(𝑡−𝜔𝑚) for every 𝑡∈ℂ. At 𝑡=−1,

−2=(−1)𝑛−1=∏𝑚(−1−𝜔𝑚)=(−1)𝑛∏𝑚(1+𝜔𝑚)=−det𝐶,

so det𝐶=2. For 𝑛=3 this is the matrix of Exercise 5.3.38 (a).

Problem 5.13.hard Let 𝑛≥1, let 𝑥1,…,𝑥𝑛,𝑦1,…,𝑦𝑛∈𝐹, and let 𝑀∈𝐹𝑛×𝑛 have entries 𝑚𝑖𝑗=(𝑥𝑖+𝑦𝑗)𝑛−1.

  1. (a)Show that

    det𝑀=∏𝑘=0𝑛−1(𝑛−1𝑘)⋅∏1≤𝑖<𝑗≤𝑛(𝑥𝑗−𝑥𝑖)(𝑦𝑖−𝑦𝑗),

    where the binomial coefficients are read as elements of 𝐹.

  2. (b)Check (a) directly for 𝑛=2.
  3. (c)For 𝑛=3, decide when 𝑀 is invertible, over ℚ and over 𝔽2.

Solution.

Uses. Theorem 5.4.10 (Multiplicativity), Theorem 5.5.21 (The Vandermonde determinant), Theorem 5.4.14 (The transpose), Proposition 5.3.15 (Triangular matrices), Proposition 5.1.10 (Alternating implies antisymmetric), Exercise 5.2.34

Techniques. Factor the matrix (Technique 5.6.1)

Hint 1. Expand (𝑥𝑖+𝑦𝑗)𝑛−1 by the binomial theorem and read the result as a product of three matrices.
Hint 2. 𝑀=𝑋𝐷𝑌, where 𝑋 has entries 𝑥𝑖𝑘, 𝐷 is diagonal with the binomial coefficients, and 𝑌 has entries 𝑦𝑗𝑛−1−𝑘. Up to the order of its rows, 𝑌 is 𝑉(𝑦1,…,𝑦𝑛)𝖳.
Sketch. By the binomial theorem, 𝑀=𝑋𝐷𝑌 with 𝑋=𝑉(𝑥1,…,𝑥𝑛), 𝐷=diag((𝑛−10),…,(𝑛−1𝑛−1)), and 𝑌 equal to 𝑉(𝑦1,…,𝑦𝑛)𝖳 with its rows reversed. Reversing 𝑛 rows takes ⌊𝑛/2⌋ interchanges, and (−1)⌊𝑛/2⌋=(−1)𝑛(𝑛−1)/2, which turns ∏𝑖<𝑗(𝑦𝑗−𝑦𝑖) into ∏𝑖<𝑗(𝑦𝑖−𝑦𝑗). (c) Over ℚ: invertible iff the 𝑥𝑖 are distinct and the 𝑦𝑗 are distinct. Over 𝔽2: never, since (21)=0.

(a) Index rows and columns of auxiliary matrices by 𝑘=0,…,𝑛−1 where needed. By the binomial theorem,

(𝑥𝑖+𝑦𝑗)𝑛−1=∑𝑘=0𝑛−1𝑥𝑖𝑘(𝑛−1𝑘)𝑦𝑗𝑛−1−𝑘.

So 𝑀=𝑋𝐷𝑌, where 𝑋 has (𝑖,𝑘) entry 𝑥𝑖𝑘, 𝐷=diag((𝑛−10),…,(𝑛−1𝑛−1)), and 𝑌 has (𝑘,𝑗) entry 𝑦𝑗𝑛−1−𝑘. Now 𝑋=𝑉(𝑥1,…,𝑥𝑛). The matrix 𝑉(𝑦1,…,𝑦𝑛)𝖳 has (𝑘,𝑗) entry 𝑦𝑗𝑘, so 𝑌 is 𝑉(𝑦1,…,𝑦𝑛)𝖳 with its rows in reverse order. Reversing the order of 𝑛 rows takes ⌊𝑛/2⌋ interchanges (the first row with the last, and so on), each of which negates the determinant (Proposition 5.1.10 with Theorem 5.4.14), and (−1)⌊𝑛/2⌋=(−1)𝑛(𝑛−1)/2 by Exercise 5.2.34 (c). So, by Theorem 5.5.21 and Theorem 5.4.14,

det𝑌=(−1)𝑛(𝑛−1)/2∏1≤𝑖<𝑗≤𝑛(𝑦𝑗−𝑦𝑖)=∏1≤𝑖<𝑗≤𝑛(𝑦𝑖−𝑦𝑗),

because the product has 𝑛(𝑛−1)/2 factors and each sign change flips one of them. By Theorem 5.4.10 and Proposition 5.3.15,

det𝑀=det𝑋det𝐷det𝑌=∏𝑖<𝑗(𝑥𝑗−𝑥𝑖)⋅∏𝑘=0𝑛−1(𝑛−1𝑘)⋅∏𝑖<𝑗(𝑦𝑖−𝑦𝑗).

(b) For 𝑛=2 the binomial coefficients are 1,1, and

det𝑀=(𝑥1+𝑦1)(𝑥2+𝑦2)−(𝑥1+𝑦2)(𝑥2+𝑦1)=𝑥1𝑦2+𝑥2𝑦1−𝑥1𝑦1−𝑥2𝑦2=(𝑥2−𝑥1)(𝑦1−𝑦2).

(c) For 𝑛=3 the coefficients are (20),(21),(22)=1,2,1. Over ℚ they are nonzero, so 𝑀 is invertible exactly when the 𝑥𝑖 are distinct and the 𝑦𝑗 are distinct (Proposition 1.1.17, Theorem 5.4.7). Over 𝔽2, (21)=2=0, so det𝑀=0 and 𝑀 is never invertible. This agrees with (𝑥+𝑦)2=𝑥2+𝑦2 over 𝔽2: there 𝑀 is the sum of the matrix with all columns (𝑥12,𝑥22,𝑥32) and the matrix with all rows (𝑦12,𝑦22,𝑦32), and both have rank at most 1.

Problem 5.14.hard Let 𝑇∈𝐹𝑛×𝑛 be tridiagonal, with diagonal entries 𝑎1,…,𝑎𝑛, entries 𝑏𝑘 in positions (𝑘,𝑘+1), and entries 𝑐𝑘 in positions (𝑘+1,𝑘), as in Proposition 5.5.18.

  1. (a)Show that the permutations 𝜎∈𝑆𝑛 with |𝜎(𝑗)−𝑗|≤1 for every 𝑗 are exactly the products of disjoint adjacent transpositions (𝑘𝑘+1) (the empty product included).
  2. (b)Show that there are 𝐹𝑛+1 such permutations, where 𝐹1=𝐹2=1 and 𝐹𝑚+1=𝐹𝑚+𝐹𝑚−1 are the Fibonacci numbers.
  3. (c)Call a set 𝑃 of pairwise disjoint pairs {𝑘,𝑘+1} a matching of [𝑛], and call 𝑖 unmatched if it lies in no pair of 𝑃. Show that

    det𝑇=∑𝑃∏{𝑘,𝑘+1}∈𝑃(−𝑏𝑘𝑐𝑘)∏𝑖unmatched𝑎𝑖,

    the sum over all matchings 𝑃 of [𝑛].

  4. (d)Derive the recurrence of Proposition 5.5.18 from (c). Explain the Fibonacci numbers in Example 5.5.19 (b) without computing.

Solution.

Uses. Theorem 5.3.3 (The Leibniz formula), Proposition 5.2.25 (Multiplicativity of the sign), Definition 5.2.10 (Transposition), Proposition 5.5.18 (Tridiagonal determinants)

Techniques. Read structure off the Leibniz expansion (Technique 5.3.12), Induction on matrix size (Technique 5.5.17)

Hint 1. For (a), induct on 𝑛 and look at 𝜎(𝑛), which is 𝑛 or 𝑛−1. If 𝜎(𝑛)=𝑛−1, which 𝑗 can have 𝜎(𝑗)=𝑛?
Hint 2. The same case split counts the permutations in (b). In (c), the term of 𝜎 is nonzero only if |𝜎(𝑗)−𝑗|≤1 for every 𝑗.
Sketch. (a) Induct on 𝑛. If 𝜎(𝑛)=𝑛, restrict to [𝑛−1]. If 𝜎(𝑛)=𝑛−1, then 𝜎−1(𝑛)∈{𝑛−1,𝑛} forces 𝜎(𝑛−1)=𝑛, and (𝑛−1𝑛)𝜎 fixes 𝑛−1 and 𝑛. (b) The two cases give 𝑁𝑛=𝑁𝑛−1+𝑁𝑛−2 with 𝑁0=𝑁1=1. (c) For the product 𝜎 of the transpositions of 𝑃, sgn(𝜎)=(−1)|𝑃|, and each pair contributes 𝑡𝑘+1,𝑘𝑡𝑘,𝑘+1=𝑐𝑘𝑏𝑘; all other terms of the Leibniz formula vanish. (d) Split by whether 𝑛 is matched. In the example, every term equals 1.

(a) A product of disjoint adjacent transpositions moves each point by at most 1. For the converse we induct on 𝑛; for 𝑛≤1 the only permutation is the identity, the empty product. Let 𝑛≥2 and let 𝜎 satisfy |𝜎(𝑗)−𝑗|≤1 for every 𝑗. Then 𝜎(𝑛)∈{𝑛−1,𝑛}.

If 𝜎(𝑛)=𝑛, then 𝜎 maps [𝑛−1] onto itself, and its restriction has the same property, so by induction it is a product of disjoint adjacent transpositions of [𝑛−1], and so is 𝜎.

If 𝜎(𝑛)=𝑛−1, let 𝑗=𝜎−1(𝑛). Then |𝑛−𝑗|≤1 and 𝑗≠𝑛, so 𝑗=𝑛−1, that is, 𝜎(𝑛−1)=𝑛. For 𝑗≤𝑛−2 we have 𝜎(𝑗)≤𝑗+1≤𝑛−1 and 𝜎(𝑗)≠𝑛−1, so 𝜎 maps [𝑛−2] onto itself. Its restriction to [𝑛−2] has the property, so by induction it is a product 𝜌 of disjoint adjacent transpositions of [𝑛−2], and 𝜎=𝜌(𝑛−1𝑛), where (𝑛−1𝑛) is disjoint from the factors of 𝜌.

(b) Let 𝑁𝑛 be the number of such permutations of [𝑛], with 𝑁0=𝑁1=1. The two cases of (a) give 𝑁𝑛=𝑁𝑛−1+𝑁𝑛−2 for 𝑛≥2, since in each case the restriction can be any of the permutations counted for [𝑛−1], respectively [𝑛−2]. So 𝑁𝑛=𝐹𝑛+1, by induction from 𝑁0=𝐹1 and 𝑁1=𝐹2.

(c) The term of 𝜎 in the Leibniz formula (Theorem 5.3.3) contains 𝑡𝜎(𝑗)𝑗, which is 0 unless |𝜎(𝑗)−𝑗|≤1. So only the permutations of (a) contribute. Such a 𝜎 is the product of the transpositions (𝑘𝑘+1) for the pairs of a matching 𝑃, and different matchings give different permutations, so the surviving terms correspond to the matchings. For the 𝜎 of 𝑃, sgn(𝜎)=(−1)|𝑃| by Proposition 5.2.25. Each unmatched 𝑖 contributes 𝑡𝑖𝑖=𝑎𝑖, and each pair {𝑘,𝑘+1}∈𝑃 contributes 𝑡𝜎(𝑘)𝑘𝑡𝜎(𝑘+1),𝑘+1=𝑡𝑘+1,𝑘𝑡𝑘,𝑘+1=𝑐𝑘𝑏𝑘. So the term of 𝜎 is ∏𝑃(−𝑏𝑘𝑐𝑘)∏unmatched𝑎𝑖, as claimed.

(d) Let 𝑑𝑚 be the sum in (c) for 𝑇𝑚, the upper left 𝑚×𝑚 corner. Split the matchings of [𝑚] according to whether 𝑚 is matched. If it is unmatched, the rest is any matching of [𝑚−1], and these terms add up to 𝑎𝑚𝑑𝑚−1. If it is matched, its pair is {𝑚−1,𝑚}, the rest is any matching of [𝑚−2], and these terms add up to −𝑏𝑚−1𝑐𝑚−1𝑑𝑚−2. So 𝑑𝑚=𝑎𝑚𝑑𝑚−1−𝑏𝑚−1𝑐𝑚−1𝑑𝑚−2, the recurrence of Proposition 5.5.18.

In Example 5.5.19 (b), 𝑎𝑘=1 and −𝑏𝑘𝑐𝑘=−𝑖⋅𝑖=1, so every term in (c) equals 1, and det𝑇 is the number of matchings of [𝑛], which is 𝐹𝑛+1 by (b). The cofactor recurrence computes the determinants; the matching formula explains what they count.

Problem 5.15.hard Let 𝐴∈ℚ𝑛×𝑛 have integer entries, with 𝑎𝑖𝑖 even for every 𝑖 and 𝑎𝑖𝑗+𝑎𝑗𝑖 even for all 𝑖,𝑗. (For example, 𝐴 could be symmetric with even diagonal, or skew-symmetric.)

  1. (a)Show that if 𝑛 is odd, then det𝐴 is even.
  2. (b)Show that the conclusion of (a) fails for every even 𝑛.
  3. (c)Show that the hypothesis on the diagonal cannot be dropped, and check (a) on 𝐽+𝐼𝑛, where every entry of 𝐽 is 1.

Solution.

Uses. Proposition 5.3.20 (Reduction modulo 𝑝), Exercise 5.6.13, Corollary 5.4.27 (Several diagonal blocks), Example 5.4.24 (A matrix with constant row sums)

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

Hint 1. Reduce modulo 2. What do the hypotheses say about the reduction 𝐴 over 𝔽2?
Hint 2. 𝐴 is alternating in the sense of Exercise 5.6.13. For (b), start with (0110).
Sketch. (a) Over 𝔽2, 𝑎𝑖𝑖=0 and 𝑎𝑗𝑖=𝑎𝑖𝑗=−𝑎𝑖𝑗, so 𝐴 is alternating of odd size and det𝐴=0; hence det𝐴 is even. (b) Block-diagonal matrices with blocks (0110) satisfy the hypotheses and have determinant ±1. (c) 𝐼𝑛 has odd determinant; 𝐽+𝐼𝑛 has determinant 𝑛+1.

(a) Let 𝐴∈𝔽2𝑛×𝑛 be the reduction of 𝐴 modulo 2. Since 𝑎𝑖𝑖 is even, 𝑎𝑖𝑖=0. Since 𝑎𝑖𝑗+𝑎𝑗𝑖 is even, 𝑎𝑗𝑖=−𝑎𝑖𝑗 in 𝔽2. So 𝐴 is alternating in the sense of Exercise 5.6.13, and since 𝑛 is odd, det𝐴=0 there. By Proposition 5.3.20, (det𝐴)mod2=det𝐴=0, so det𝐴 is even.

The argument must work in characteristic 2, which is why it uses the pairing of Exercise 5.6.13 and not the identity det𝐴=−det𝐴: over 𝔽2, −det𝐴=det𝐴 carries no information.

(b) Let 𝑛=2𝑘 and let 𝐴 be block diagonal with 𝑘 blocks 𝑅=(0110). Its diagonal entries are 0, and 𝑎𝑖𝑗+𝑎𝑗𝑖 is 0 or 2, so 𝐴 satisfies the hypotheses. By Corollary 5.4.27, det𝐴=(det𝑅)𝑘=(−1)𝑘, which is odd.

(c) For odd 𝑛, 𝐼𝑛 has 𝑎𝑖𝑗+𝑎𝑗𝑖=0 for 𝑖≠𝑗 but odd diagonal entries, and det𝐼𝑛=1 is odd. So the diagonal hypothesis is needed (it is not implied by the other one, which for 𝑖=𝑗 only says that 2𝑎𝑖𝑖 is even). The matrix 𝐽+𝐼𝑛 has diagonal entries 2 and 𝑎𝑖𝑗+𝑎𝑗𝑖=2, and by Example 5.4.24 with 𝑥=2, det(𝐽+𝐼𝑛)=(𝑛+1)⋅1𝑛−1=𝑛+1, which is even for odd 𝑛, as (a) predicts.

Problem 5.16.hard Let 𝐴∈ℝ𝑛×𝑛 be skew-symmetric, 𝐴𝖳=−𝐴.

  1. (a)Show that 𝐱𝖳𝐴𝐱=0 for every 𝐱∈ℝ𝑛, and deduce that 𝐼𝑛+𝑡𝐴 is invertible for every 𝑡∈ℝ.
  2. (b)Show that det(𝐼𝑛+𝐴)>0. (Consider 𝑡↦det(𝐼𝑛+𝑡𝐴) on [0,1].)
  3. (c)Compute det(𝐼𝑛+𝐴) for 𝑛=2 and 𝑛=3 in terms of the entries above the diagonal.
  4. (d)Show that the conclusion of (b) can fail if 𝐴 is only assumed to have tr𝐴=0.

Solution.

Uses. Proposition 2.4.23 (Transpose of a product), Corollary 5.4.8 (Vanishing determinants), Theorem 5.4.7 (Invertibility and the determinant), Proposition 5.3.19 (det(𝐴+𝑡𝐼𝑛) as a function of 𝑡), Proposition 5.3.15 (Triangular matrices)

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

Hint 1. A 1×1 matrix equals its own transpose. For invertibility, if (𝐼𝑛+𝑡𝐴)𝐱=𝟎, multiply on the left by 𝐱𝖳.
Hint 2. 𝑔(𝑡)=det(𝐼𝑛+𝑡𝐴) is a polynomial in 𝑡, so it is continuous, it is 1 at 𝑡=0, and by (a) it never vanishes.
Sketch. (a) 𝐱𝖳𝐴𝐱=(𝐱𝖳𝐴𝐱)𝖳=−𝐱𝖳𝐴𝐱, so it is 0; then 𝐱𝖳(𝐼𝑛+𝑡𝐴)𝐱=∑𝑥𝑖2 forces 𝐱=𝟎. (b) A continuous function on [0,1] with 𝑔(0)=1 and no zeros is positive at 1. (c) 1+𝑝2, and 1+𝑝2+𝑞2+𝑟2. (d) 𝐴=diag(−2,2).

(a) The 1×1 matrix 𝐱𝖳𝐴𝐱 equals its transpose, which by Proposition 2.4.23 is 𝐱𝖳𝐴𝖳𝐱=−𝐱𝖳𝐴𝐱. So 2𝐱𝖳𝐴𝐱=0, and 𝐱𝖳𝐴𝐱=0. Now suppose (𝐼𝑛+𝑡𝐴)𝐱=𝟎. Then

0=𝐱𝖳(𝐼𝑛+𝑡𝐴)𝐱=𝐱𝖳𝐱+𝑡𝐱𝖳𝐴𝐱=𝑥12+⋯+𝑥𝑛2,

so 𝐱=𝟎, and 𝐼𝑛+𝑡𝐴 is invertible by Corollary 5.4.8.

(b) Let 𝑔(𝑡)=det(𝐼𝑛+𝑡𝐴). Its entries are affine in 𝑡, so as in the proof of Proposition 5.3.19, 𝑔(𝑡)=𝑒0+𝑒1𝑡+⋯+𝑒𝑛𝑡𝑛 for real constants 𝑒𝑘. In particular 𝑔 is continuous, 𝑔(0)=det𝐼𝑛=1, and by (a) and Theorem 5.4.7, 𝑔(𝑡)≠0 for every 𝑡. If 𝑔(1)<0, the intermediate value theorem would give 𝑡∈(0,1) with 𝑔(𝑡)=0. So det(𝐼𝑛+𝐴)=𝑔(1)>0.

(c) For 𝑛=2, 𝐴=(0𝑝−𝑝0) and det(𝐼2+𝐴)=det(1𝑝−𝑝1)=1+𝑝2. For 𝑛=3, 𝐴=(0𝑝𝑞−𝑝0𝑟−𝑞−𝑟0), and expanding along the first row,

det(1𝑝𝑞−𝑝1𝑟−𝑞−𝑟1)=(1+𝑟2)−𝑝(−𝑝+𝑞𝑟)+𝑞(𝑝𝑟+𝑞)=1+𝑝2+𝑞2+𝑟2.

Both are at least 1. In fact det(𝐼𝑛+𝐴)≥1 for every real skew-symmetric 𝐴, but the proof needs the spectral theory of Chapter 8.

(d) 𝐴=diag(−2,2) has trace 0, and det(𝐼2+𝐴)=(−1)⋅3=−3<0 (Proposition 5.3.15). Here 𝐼2+𝑡𝐴 is singular at 𝑡=1/2, and the argument of (b) breaks at exactly that point.

Problem 5.17.hard Let 𝑊 be a subspace of 𝐹𝑛×𝑛 in which every nonzero matrix is invertible.

  1. (a)Show that dim𝑊≤𝑛. (Consider the vectors 𝑋𝐞1 for 𝑋 in a basis of 𝑊.)
  2. (b)Show that 𝑊={(𝑎−𝑏𝑏𝑎)|𝑎,𝑏∈ℝ} is a subspace of ℝ2×2 with this property and dim𝑊=2.
  3. (c)Let 𝐹=ℂ and 𝑛≥2. Show that dim𝑊≤1. (Take independent 𝐴,𝐵∈𝑊 and look at det(𝐴+𝑡𝐵).)
  4. (d)Let 𝐹=ℝ and let 𝑛 be odd. Show that dim𝑊≤1.

Solution.

Uses. Theorem 4.1.10 (Independent lists are short), Corollary 5.4.8 (Vanishing determinants), Exercise 5.5.48, Theorem 7.1.32 (Fundamental Theorem of Algebra), Theorem 5.4.7 (Invertibility and the determinant)

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

Hint 1. For (a), if dim𝑊>𝑛, a basis 𝑋1,…,𝑋𝑚 gives more than 𝑛 vectors 𝑋𝑘𝐞1 in 𝐹𝑛. A relation among them produces a nonzero singular matrix in 𝑊.
Hint 2. For (c), det𝐵≠0, and det(𝐴+𝑡𝐵) is a polynomial in 𝑡 of degree 𝑛 with leading coefficient det𝐵. Over ℂ it has a root. For (d), use that a real polynomial of odd degree has a real root.
Sketch. (a) If 𝑚=dim𝑊>𝑛, then ∑𝑘𝑐𝑘𝑋𝑘𝐞1=𝟎 nontrivially, and 𝑋=∑𝑘𝑐𝑘𝑋𝑘 is a nonzero matrix of 𝑊 with 𝑋𝐞1=𝟎. (b) det=𝑎2+𝑏2. (c) For independent 𝐴,𝐵∈𝑊, 𝐵≠0, so det𝐵≠0, and det(𝐴+𝑡𝐵) has degree 𝑛≥1 in 𝑡; a root 𝑡0∈ℂ gives the nonzero singular 𝐴+𝑡0𝐵∈𝑊. (d) The same with a real root of an odd-degree polynomial.

(a) Suppose 𝑚=dim𝑊>𝑛, and let 𝑋1,…,𝑋𝑚 be a basis of 𝑊. The 𝑚 vectors 𝑋1𝐞1,…,𝑋𝑚𝐞1 lie in 𝐹𝑛, so they are dependent (Theorem 4.1.10): ∑𝑘𝑐𝑘𝑋𝑘𝐞1=𝟎 with not all 𝑐𝑘=0. Let 𝑋=∑𝑘𝑐𝑘𝑋𝑘∈𝑊. Since the 𝑋𝑘 are independent, 𝑋≠0; but 𝑋𝐞1=𝟎, so 𝑋 is not invertible (Corollary 5.4.8). This contradicts the hypothesis, so dim𝑊≤𝑛.

(b) 𝑊=span(𝐼2,𝑅) with 𝑅=(0−110), so it is a subspace, and 𝐼2, 𝑅 are independent, so dim𝑊=2. For 𝑋=(𝑎−𝑏𝑏𝑎), det𝑋=𝑎2+𝑏2, which is positive unless 𝑎=𝑏=0. So every nonzero 𝑋∈𝑊 is invertible.

(c) Suppose dim𝑊≥2, and let 𝐴,𝐵∈𝑊 be independent. Then 𝐵≠0, so 𝐵 is invertible and det𝐵≠0. By Exercise 5.5.48 (a), there are 𝑒0,…,𝑒𝑛∈ℂ with det(𝐴+𝑡𝐵)=𝑒0+𝑒1𝑡+⋯+𝑒𝑛𝑡𝑛 for all 𝑡, and 𝑒𝑛=det𝐵≠0. So 𝑒0+𝑒1𝑥+⋯+𝑒𝑛𝑥𝑛 has degree 𝑛≥2, and it has a root 𝑡0∈ℂ (Theorem 7.1.32). Then 𝐴+𝑡0𝐵∈𝑊 is singular, and it is nonzero because 𝐴 and 𝐵 are independent. This contradicts the hypothesis, so dim𝑊≤1. The bound is attained by 𝑊=span(𝐼𝑛).

(d) For 𝑛=1 this is (a). For odd 𝑛≥3, argue as in (c): with 𝐴,𝐵 independent in 𝑊, 𝑔(𝑡)=det(𝐴+𝑡𝐵)=𝑒0+⋯+𝑒𝑛𝑡𝑛 with real 𝑒𝑘 and 𝑒𝑛=det𝐵≠0. Since 𝑛 is odd, 𝑔(𝑡)/𝑡𝑛→𝑒𝑛 as 𝑡→±∞ and 𝑡𝑛 changes sign, so 𝑔 takes both signs, and by the intermediate value theorem 𝑔(𝑡0)=0 for some real 𝑡0. Then 𝐴+𝑡0𝐵 is a nonzero singular matrix in 𝑊, a contradiction.

So the largest possible dim𝑊 depends on the field: 1 over ℂ, 1 over ℝ for odd 𝑛, but 2 over ℝ for 𝑛=2, by (b). (For 𝑛=4 over ℝ, a construction from the quaternions reaches dim𝑊=4.)

Problem 5.18.hard Let 𝑥,𝑎,𝑏∈𝐹 with 𝑎≠𝑏, and let 𝑇𝑛∈𝐹𝑛×𝑛 have every diagonal entry equal to 𝑥, every entry above the diagonal equal to 𝑎, and every entry below the diagonal equal to 𝑏. Show that

det𝑇𝑛=𝑏(𝑥−𝑎)𝑛−𝑎(𝑥−𝑏)𝑛𝑏−𝑎,

and check the formula for 𝑛=2. (Hint: let 𝐽 be the matrix with every entry 1, and show that 𝑡↦det(𝑇𝑛+𝑡𝐽) is affine in 𝑡.)

Solution.

Hint 1. Every column of 𝑇𝑛+𝑡𝐽 is a column of 𝑇𝑛 plus 𝑡(1,…,1). Subtract column 1 from the others.
Hint 2. An affine function 𝛼+𝛽𝑡 is determined by two of its values. At 𝑡=−𝑎 and at 𝑡=−𝑏 the matrix 𝑇𝑛+𝑡𝐽 is triangular.
Sketch. After subtracting column 1 from the others, only column 1 involves 𝑡, linearly, so 𝑓(𝑡)=det(𝑇𝑛+𝑡𝐽)=𝛼+𝛽𝑡. 𝑇𝑛−𝑎𝐽 is lower triangular with diagonal 𝑥−𝑎, and 𝑇𝑛−𝑏𝐽 is upper triangular with diagonal 𝑥−𝑏, so 𝑓(−𝑎)=(𝑥−𝑎)𝑛 and 𝑓(−𝑏)=(𝑥−𝑏)𝑛. Solve for 𝑓(0)=𝛼.

Let 𝟏=(1,…,1) and let 𝐭1,…,𝐭𝑛 be the columns of 𝑇𝑛, so the columns of 𝑇𝑛+𝑡𝐽 are 𝐭𝑗+𝑡𝟏. Subtracting column 1 from each other column does not change the determinant (Lemma 5.1.8), and leaves the columns 𝐭1+𝑡𝟏,𝐭2−𝐭1,…,𝐭𝑛−𝐭1, in which only the first involves 𝑡. By linearity in column 1,

𝑓(𝑡)=det(𝑇𝑛+𝑡𝐽)=det(𝐭1,𝐭2−𝐭1,…)+𝑡det(𝟏,𝐭2−𝐭1,…)=𝛼+𝛽𝑡

for constants 𝛼,𝛽∈𝐹. Note 𝑓(0)=det𝑇𝑛=𝛼.

The matrix 𝑇𝑛−𝑎𝐽 has diagonal entries 𝑥−𝑎, entries 0 above the diagonal, and 𝑏−𝑎 below it, so it is lower triangular and 𝑓(−𝑎)=(𝑥−𝑎)𝑛 (Proposition 5.3.15). Likewise 𝑇𝑛−𝑏𝐽 is upper triangular with diagonal entries 𝑥−𝑏, so 𝑓(−𝑏)=(𝑥−𝑏)𝑛. So

𝛼−𝑎𝛽=(𝑥−𝑎)𝑛,𝛼−𝑏𝛽=(𝑥−𝑏)𝑛.

Multiplying the first equation by 𝑏, the second by 𝑎, and subtracting, (𝑏−𝑎)𝛼=𝑏(𝑥−𝑎)𝑛−𝑎(𝑥−𝑏)𝑛. Since 𝑎≠𝑏,

det𝑇𝑛=𝛼=𝑏(𝑥−𝑎)𝑛−𝑎(𝑥−𝑏)𝑛𝑏−𝑎.

For 𝑛=2 the formula gives

𝑏(𝑥−𝑎)2−𝑎(𝑥−𝑏)2𝑏−𝑎=𝑏𝑥2+𝑎2𝑏−𝑎𝑥2−𝑎𝑏2𝑏−𝑎=(𝑏−𝑎)𝑥2−𝑎𝑏(𝑏−𝑎)𝑏−𝑎=𝑥2−𝑎𝑏,

which is det(𝑥𝑎𝑏𝑥). The proof never multiplied anything out: it located two values of 𝑡 at which the matrix becomes triangular and used that 𝑓 is determined by two values. When 𝑎=𝑏 the formula breaks down, and the answer is (𝑥−𝑎)𝑛−1(𝑥+(𝑛−1)𝑎) (compare Example 5.4.24).

Problem 5.19.challenge
  1. (a)Let 𝑥1,…,𝑥𝑛∈𝐹, and for 𝑘=0,…,𝑛−1 let 𝑝𝑘∈𝐹[𝑥] have degree 𝑘 and coefficient 1 of 𝑥𝑘. Show that the 𝑛×𝑛 matrix with (𝑖,𝑘+1) entry 𝑝𝑘(𝑥𝑖) has determinant ∏1≤𝑖<𝑗≤𝑛(𝑥𝑗−𝑥𝑖).
  2. (b)Let 𝑥1,…,𝑥𝑛 be integers. Show that ∏1≤𝑖<𝑗≤𝑛(𝑥𝑗−𝑥𝑖) is divisible by 0!⋅1!⋯(𝑛−1)!.
  3. (c)Deduce that ∏1≤𝑖<𝑗≤𝑛𝑥𝑗−𝑥𝑖𝑗−𝑖 is an integer for all integers 𝑥1,…,𝑥𝑛.

Solution.

Uses. Theorem 5.5.21 (The Vandermonde determinant), Theorem 5.4.10 (Multiplicativity), Proposition 5.3.15 (Triangular matrices), Definition 1.2.17 (Evaluation), Lemma 5.5.23 (A polynomial with prescribed roots), Proposition 5.3.20 (Reduction modulo 𝑝), Exercise 5.5.26

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

Hint 1. For (a), column 𝑘+1 is column 𝑘+1 of the Vandermonde matrix plus a combination of earlier columns. Write the matrix as 𝑉𝑈 with 𝑈 upper triangular.
Hint 2. For (b), take 𝑝𝑘(𝑡)=𝑡(𝑡−1)⋯(𝑡−𝑘+1), whose values at integers 𝑥≥0 are 𝑘!(𝑥𝑘). Translating all 𝑥𝑖 by the same integer does not change the product, so you may assume 𝑥𝑖≥0.
Sketch. (a) 𝑝𝑘=𝑥𝑘+∑𝑙<𝑘𝑢𝑙𝑘𝑥𝑙, so the matrix is 𝑉𝑈 with 𝑈 upper triangular with 1s on the diagonal; det=det𝑉. (b) Shift so that all 𝑥𝑖≥0 and use the falling factorials: the matrix has entries 𝑘!(𝑥𝑖𝑘), so det𝑉=(∏𝑘𝑘!)det((𝑥𝑖𝑘)), and the last determinant is an integer. (c) ∏𝑖<𝑗(𝑗−𝑖)=1!2!⋯(𝑛−1)!.

(a) Write 𝑝𝑘=∑𝑙=0𝑘𝑢𝑙𝑘𝑥𝑙 with 𝑢𝑘𝑘=1, and set 𝑢𝑙𝑘=0 for 𝑙>𝑘. Let 𝑈∈𝐹𝑛×𝑛 have (𝑙+1,𝑘+1) entry 𝑢𝑙𝑘; it is upper triangular with 1s on the diagonal, so det𝑈=1 (Proposition 5.3.15). Let 𝑉=𝑉(𝑥1,…,𝑥𝑛), with (𝑖,𝑙+1) entry 𝑥𝑖𝑙. By Definition 1.2.17,

𝑝𝑘(𝑥𝑖)=∑𝑙=0𝑛−1𝑥𝑖𝑙𝑢𝑙𝑘=(𝑉𝑈)𝑖,𝑘+1.

So the matrix in question is 𝑉𝑈, and its determinant is det𝑉det𝑈=det𝑉=∏𝑖<𝑗(𝑥𝑗−𝑥𝑖) by Theorem 5.4.10 and Theorem 5.5.21.

(b) Replacing every 𝑥𝑖 by 𝑥𝑖+𝑐, for an integer 𝑐, does not change any difference 𝑥𝑗−𝑥𝑖. So we may assume that every 𝑥𝑖≥0. For 𝑘≥0, multiplying out the product one factor at a time (as in the proof of Lemma 5.5.23) shows that there is a polynomial 𝑝𝑘∈ℚ[𝑥] of degree 𝑘, with coefficient 1 of 𝑥𝑘, such that

𝑝𝑘(𝑡)=𝑡(𝑡−1)⋯(𝑡−𝑘+1)for every𝑡,

with 𝑝0=1. For an integer 𝑡≥0, 𝑝𝑘(𝑡)=𝑘!(𝑡𝑘): if 𝑡≥𝑘 this is the formula for (𝑡𝑘), and if 𝑡<𝑘 both sides are 0. By (a),

∏𝑖<𝑗(𝑥𝑗−𝑥𝑖)=det(𝑝𝑘(𝑥𝑖))=det(𝑘!(𝑥𝑖𝑘))=(∏𝑘=0𝑛−1𝑘!)det((𝑥𝑖𝑘)),

pulling the factor 𝑘! out of column 𝑘+1. The matrix ((𝑥𝑖𝑘)) has integer entries, so its determinant is an integer (Proposition 5.3.20), and 0!⋅1!⋯(𝑛−1)! divides the product.

(c) By Exercise 5.5.26 (a), ∏1≤𝑖<𝑗≤𝑛(𝑗−𝑖)=det𝑉(1,…,𝑛)=1!⋅2!⋯(𝑛−1)!. So the quotient in (c) is ∏𝑖<𝑗(𝑥𝑗−𝑥𝑖) divided by 0!⋅1!⋯(𝑛−1)!, which is an integer by (b). For 𝑛=3 this says that among three integers some two have the same parity; for 𝑛=4, that the six differences of four integers have a product divisible by 12.

Problem 5.20.challenge Let 𝐺𝑛∈ℚ𝑛×𝑛 have entries 𝑔𝑖𝑗=gcd(𝑖,𝑗). For 𝑑≥1, let 𝜑(𝑑) be the number of 𝑘∈{1,…,𝑑} with gcd(𝑘,𝑑)=1. You may use that ∑𝑑∣𝑚𝜑(𝑑)=𝑚 for every integer 𝑚≥1.

  1. (a)Show that 𝐺𝑛=𝐿Φ𝐿𝖳, where Φ=diag(𝜑(1),…,𝜑(𝑛)) and 𝐿∈ℚ𝑛×𝑛 has (𝑖,𝑑) entry 1 if 𝑑∣𝑖 and 0 otherwise.
  2. (b)Deduce that det𝐺𝑛=𝜑(1)𝜑(2)⋯𝜑(𝑛), and evaluate det𝐺6.
  3. (c)Show that 𝐺𝑛 is invertible for every 𝑛, and that 𝐺𝑛−1 has integer entries only for 𝑛≤2.

Solution.

Uses. Theorem 5.4.10 (Multiplicativity), Theorem 5.4.14 (The transpose), Proposition 5.3.15 (Triangular matrices), Corollary 5.5.12 (Integer inverses), Theorem 5.4.7 (Invertibility and the determinant)

Techniques. Factor the matrix (Technique 5.6.1)

Hint 1. Apply the identity to 𝑚=gcd(𝑖,𝑗). The divisors of gcd(𝑖,𝑗) are exactly the common divisors of 𝑖 and 𝑗.
Hint 2. 𝐿 is lower triangular with 1s on the diagonal. For (c), when is ∏𝑘𝜑(𝑘)=1?
Sketch. (a) (𝐿Φ𝐿𝖳)𝑖𝑗=∑𝑑∣𝑖,𝑑∣𝑗𝜑(𝑑)=∑𝑑∣gcd(𝑖,𝑗)𝜑(𝑑)=gcd(𝑖,𝑗). (b) det𝐿=1, so det𝐺𝑛=detΦ; det𝐺6=1⋅1⋅2⋅2⋅4⋅2=32. (c) 𝜑(𝑑)≥1, so det𝐺𝑛≠0; the inverse is integral iff det𝐺𝑛=±1, iff 𝜑(𝑘)=1 for all 𝑘≤𝑛, iff 𝑛≤2.

(a) The (𝑖,𝑗) entry of 𝐿Φ𝐿𝖳 is

∑𝑑=1𝑛𝑙𝑖𝑑𝜑(𝑑)𝑙𝑗𝑑=∑𝑑≤𝑛,𝑑∣𝑖,𝑑∣𝑗𝜑(𝑑).

A common divisor of 𝑖 and 𝑗 is at most 𝑖≤𝑛, so the condition 𝑑≤𝑛 is automatic, and the common divisors of 𝑖 and 𝑗 are exactly the divisors of gcd(𝑖,𝑗). By the given identity with 𝑚=gcd(𝑖,𝑗), the sum is gcd(𝑖,𝑗)=𝑔𝑖𝑗.

(b) If 𝑑∣𝑖 then 𝑑≤𝑖, so 𝐿 is lower triangular, and 𝑙𝑖𝑖=1. So det𝐿=det𝐿𝖳=1 (Proposition 5.3.15, Theorem 5.4.14), and by Theorem 5.4.10,

det𝐺𝑛=det𝐿detΦdet𝐿𝖳=𝜑(1)𝜑(2)⋯𝜑(𝑛).

Since 𝜑(1),…,𝜑(6)=1,1,2,2,4,2, we get det𝐺6=32.

(c) Every 𝜑(𝑑)≥1, since 𝑘=1 is counted, so det𝐺𝑛≥1 and 𝐺𝑛 is invertible (Theorem 5.4.7). By Corollary 5.5.12, 𝐺𝑛−1 has integer entries exactly when det𝐺𝑛=±1, that is, when 𝜑(𝑘)=1 for every 𝑘≤𝑛. Since 𝜑(1)=𝜑(2)=1 and 𝜑(3)=2, this happens exactly for 𝑛≤2.

The factorization is the whole proof. Computing det𝐺𝑛 by elimination for each 𝑛 gives no hint of the pattern, while the identity 𝑚=∑𝑑∣𝑚𝜑(𝑑) says that each entry is a sum of products, which is what Technique 5.6.1 asks for. (This is H. J. S. Smith’s determinant, from 1875.)