Problems for Chapter 5
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
- (a)State the theorem on the existence and uniqueness of determinant functions, including its description of all multilinear alternating functions on .
- (b)Prove that the function of (5.3.1) is alternating, by an argument that works over every field.
- (c)Let and , and define
for . Show that is normalized, multilinear, and antisymmetric (Definition 5.1.9), but not alternating. Explain why no such exists over a field in which .
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 ), Definition 5.1.1 (Determinant function)
Techniques. Cancel terms in pairs (Technique 5.3.5)
(a) Statement (Theorem 5.3.4). Let . The function
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
and since columns and are equal,
The map is its own inverse and changes the sign, so it maps the even permutations bijectively onto the odd ones. Therefore
No step divides by : over the two terms of a pair are equal and cancel because .
(c) Write
Normalized. , and contains the factor (as ). So .
Multilinear. contains exactly one entry of each column, namely from column . With the other columns fixed, is a constant times , a linear function of column . So is multilinear, and so is .
Antisymmetric. Interchanging two columns negates (Proposition 5.1.10) and permutes the factors of , so it leaves unchanged. In , , so both and are unchanged, and
Not alternating. Let have first row and all other rows . All columns of are equal to , so , but , and .
If , an antisymmetric function is alternating (Proposition 5.1.11). So a normalized, multilinear, antisymmetric would be a determinant function, hence equal to by uniqueness, and is alternating. So over such a field the three conditions determine , while over they allow at least two functions, for every . This is why the definition asks for alternation (compare Example 5.1.12, the case ).
- (a)State Theorem 5.4.7 and Theorem 5.4.10.
- (b)Prove
by recognizing the determinant by its axioms. Then deduce the implication “ invertible ” from it, without elementary matrices. - (c)For which is there a matrix with ? What changes over ?
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)
(a) Theorem 5.4.7: is invertible if and only if . Theorem 5.4.10:
(b) Fix , and let . Column of is , so
If is invertible, then
(c) Suppose and . By (b) and Exercise 5.1.5,
Over , works for every . The obstruction over is arithmetic, the irrationality of , and the determinant is what detects it.
- (a)State Cramer’s rule.
- (b)Let and , with no assumption on . Prove that every solution of satisfies
for , where is with column replaced by . Deduce Cramer’s rule. - (c)Let have integer entries and . Show that for every with integer entries, the solution of has integral. Show also that if , then some with integer entries has a solution that is not integral, and find one for .
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)
(a) (Theorem 5.5.14) If has and , then has exactly one solution, and
(b) Let be a solution. Then
For , the matrix has in columns and , so its determinant is . For , . Hence
If , then is invertible (Theorem 5.4.7), so is the unique solution, and dividing by gives
(c) If is integral, then has integer entries, so is an integer (Proposition 5.3.20), and by (b),
Suppose that every integral gives an integral solution. Then each column of , the solution for , is integral, so has integer entries, and by Corollary 5.5.12. So if , some has a non-integral solution.
For , . With ,
Check: and . The denominators are exactly .
Synthesis problems
Problem 5.4. Prove or disprove each statement.
- (a)If , with , have positive determinants, then so does .
- (b)If satisfies , then .
- (c)If , then
. - (d)If every row of sums to , then .
- (e)If every row of sums to , then .
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)
(a) False. Let and
(b) True. Let . By Theorem 5.4.10,
(c) False in general. Let . Then has determinant , while has determinant . The statement is true when : then both sides equal
(d) True. The -th entry of is the sum of row , so with , and by Corollary 5.4.8.
(e) False for every (for it is true). has row sums and determinant , and adding a diagonal block gives an example for each . The hypothesis says , a statement about one vector, which says nothing about .
Problem 5.5. Let be a prime.
- (a)Count the symmetric matrices
with determinant . - (b)Count the matrices with and . Explain why the answers to (a) and (b) agree.
- (c)Show that
for every . Deduce that if and only if , and count the with .
Uses. Definition 5.1.14 (The determinant), Definition 2.4.26 (Trace), Theorem 5.4.10 (Multiplicativity), Proposition 1.1.17 (No zero divisors)
(a) By Definition 5.1.14 we count the triples with . If , we need , that is, or (Proposition 1.1.17): there are triples with and with , and one triple has both, so in all. If ( choices), then , so ( choices), and then is determined. In all there are
such matrices.
(b) Write . Then means , and then , so the conditions say , with free otherwise. The map
(c) With ,
so
If , the identity gives . Conversely, suppose . Then
Problem 5.6. For points with , put and
where is the determinant of the matrix with columns and .
- (a)Show that does not change when every is replaced by , for a fixed .
- (b)Show that
. This is the signed area of the triangle : its area, with a plus sign when run counterclockwise (Example 5.1.15). - (c)Show that
for every . Explain why is the area of a convex polygon whose vertices are listed counterclockwise. (Take for granted that the area of a region cut into triangles is the sum of their areas.) - (d)Find the area of the pentagon with vertices
.
Uses. Definition 5.1.14 (The determinant), Theorem 5.1.13 (The determinant), Proposition 5.1.10 (Alternating implies antisymmetric), Example 5.1.15 ( is signed area)
Techniques. Expand by multilinearity (Technique 5.1.7)
(a) By multilinearity, with ,
Let . Since , also . Summing over and using linearity in each column, the extra terms add up to
by antisymmetry (Proposition 5.1.10). So is unchanged.
(b) By (a) with , and writing and ,
since a matrix with a zero column has determinant . The triangle is half of the parallelogram spanned by and , translated to . By Example 5.1.15, is the signed area of that parallelogram, positive exactly when the turn from to is counterclockwise, that is, when run counterclockwise.
(c) By (b),
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 , and each of these runs counterclockwise, since the boundary of the polygon does. By (b), each is the area of its triangle, and their sum is the area of the polygon.
(d) The terms are
so
Problem 5.7. Let , and let
- (a)Show that
. - (b)Deduce that if and only if
are linearly independent. - (c)Suppose . Show that for each there are unique with and
, namely , where is with column replaced by . - (d)Let and . Using Problem 5.6 (b), express each as a ratio of signed areas of triangles. Deduce that exactly when the triangles , , and have the same orientation as , and compute the for and the triangle with vertices .
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)
(a) For , subtract column from column . These replacements do not change the determinant (Lemma 5.1.8), and column becomes . Now row is , so by Lemma 5.5.2 the determinant is times the determinant of the matrix left after deleting row and column , whose columns are
(b) By (a) and Corollary 5.4.8, exactly when the columns are independent. For this says that and do not lie on one line through , that is, the three points do not lie on one line.
(c) Let . By Proposition 2.4.8,
(d) is the matrix built from the points , with in place of . By (a) and Problem 5.6 (b),
So is the signed area of the triangle with replaced by , divided by the signed area of . It is positive exactly when the two signed areas have the same sign, that is, the two triangles have the same orientation.
For , , , and :
and
Problem 5.8. Let , and let be
(a)Suppose in . Show that the matrices , , and (for ) form a basis of in which the matrix of is diagonal, and deduce that
- (b)Check (a) against Exercise 5.4.40.
- (c)Show that the formula holds for over every field, including , by using the basis
. - (d)Keep . For which is invertible? Describe when .
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
(a) Let
It spans. Each is in the list, and for ,
It is independent. Suppose
So the list is a basis (Definition 1.6.1). Since , , and ,
So the matrix of in this basis is diagonal, with appearing
(b) The transpose operator is the case , , and the formula gives , which is the answer of Exercise 5.4.40.
(c) For ,
which is block diagonal, so
(d) By Proposition 5.4.20, is invertible exactly when , that is, when and, if , also . If , then in the basis of (a) the diagonal entries are times for and , which is nonzero, and for . So
Problem 5.9. Let , let
- (a)Show that for the Vandermonde matrix , and deduce that
. - (b)Check (a) directly for .
- (c)Let . Show that , with equality exactly when two of the coincide. Show by an example that can be negative when .
- (d)Real numbers have , , , and . Are they distinct?
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)
(a) The entry of is (Definition 3.4.22), so the entry of is , and
So , and by Theorem 5.4.10, Theorem 5.4.14, and Theorem 5.5.21,
(b) For ,
(c) Over , , with equality exactly when , that is, when some factor is (Proposition 1.1.17). Over , take , , and , where is the imaginary unit: then , , , and
(d) Here , and
expanding along the middle row. By (c), the are distinct. (Indeed has these power sums, and .)
Problem 5.10. For and , let have entry , where . For example,
- (a)Show that
. - (b)Compute , and find when .
- (c)Let and . Guess from (b), and verify your guess.
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)
(a) For in turn, subtract times row from row ; working from the bottom up, row is still the original row when it is used. These replacements do not change the determinant (Corollary 5.4.15). For the new entry is
(b) The cofactors of are
and since is symmetric. Factoring out ,
By (a), , so when , Theorem 5.5.9 gives
(c) Let be tridiagonal with diagonal entries (the first and last are ) and every entry next to the diagonal equal to . We check
Column of is , so the entry of is
Column with has entries in rows . The entry of is
If , this is
So
Problem 5.11. Call nilpotent if for some .
(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
. Since is nilpotent, so is , say . Then so is invertible, and is a product of invertible matrices.
- (b)Show that the claim is true when .
- (c)Let be nilpotent. Show that . (Hint: is a polynomial function of with no zeros.)
- (d)Deduce that if is invertible, is nilpotent, and , then .
Uses. Theorem 5.4.10 (Multiplicativity), Theorem 5.4.7 (Invertibility and the determinant), Proposition 5.3.19 ( as a function of ), Theorem 7.1.32 (Fundamental Theorem of Algebra)
Techniques. is a polynomial in the entries (Technique 5.3.18)
(a) The error is the claim that is nilpotent. (The displayed product is correct: it telescopes to .) Let
Then is invertible (), , and has a zero row, so it is not invertible. Here , whose powers are never .
(b) Suppose . Multiplying by on both sides gives . So and commute, and by induction on ,
(c) Let and
(d) By (b), is nilpotent, so by (c) and Theorem 5.4.10,
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. Let and , and let be the circulant matrix whose rows are the successive cyclic shifts of to the right. With rows and columns indexed by , its entry is ; for ,
Let
- (a)For , let
. Show that . - (b)Deduce that
. - (c)Deduce that
, where . - (d)Let have first row . Show that is singular if and only if is even, and that when is odd.
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)
(a) By definition,
which is the -th entry of .
(b) Let be the matrix with columns . Its entry is , so is the Vandermonde matrix , and 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
Dividing by gives the claim.
(c) For and
(d) Here , so by (b), exactly when for some . If is even, . If is odd, then , while , so no equals . Hence is singular exactly when is even.
For odd , the polynomial has degree , leading coefficient , and the distinct roots , so by Lemma 5.5.23,
so . For this is the matrix of Exercise 5.3.38 (a).
Problem 5.13. Let , let
(a)Show that
where the binomial coefficients are read as elements of .
- (b)Check (a) directly for .
- (c)For , decide when is invertible, over and over .
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)
(a) Index rows and columns of auxiliary matrices by where needed. By the binomial theorem,
So , where has entry ,
because the product has factors and each sign change flips one of them. By Theorem 5.4.10 and Proposition 5.3.15,
(b) For the binomial coefficients are , and
(c) For the coefficients are
Problem 5.14. Let be tridiagonal, with diagonal entries , entries in positions , and entries in positions , as in Proposition 5.5.18.
- (a)Show that the permutations with for every are exactly the products of disjoint adjacent transpositions (the empty product included).
- (b)Show that there are such permutations, where and
are the Fibonacci numbers. (c)Call a set of pairwise disjoint pairs a matching of , and call unmatched if it lies in no pair of . Show that
the sum over all matchings of .
- (d)Derive the recurrence of Proposition 5.5.18 from (c). Explain the Fibonacci numbers in Example 5.5.19 (b) without computing.
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)
(a) A product of disjoint adjacent transpositions moves each point by at most . For the converse we induct on ; for the only permutation is the identity, the empty product. Let and let satisfy for every . Then .
If , then maps onto itself, and its restriction has the same property, so by induction it is a product of disjoint adjacent transpositions of , and so is .
If , let . Then and , so , that is, . For we have and , so maps onto itself. Its restriction to has the property, so by induction it is a product of disjoint adjacent transpositions of , and , where is disjoint from the factors of .
(b) Let be the number of such permutations of , with . The two cases of (a) give
(c) The term of in the Leibniz formula (Theorem 5.3.3) contains , which is unless . So only the permutations of (a) contribute. Such a is the product of the transpositions for the pairs of a matching , and different matchings give different permutations, so the surviving terms correspond to the matchings. For the of , by Proposition 5.2.25. Each unmatched contributes , and each pair contributes
(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 , and these terms add up to . If it is matched, its pair is , the rest is any matching of , and these terms add up to . So
In Example 5.5.19 (b), and
Problem 5.15. Let have integer entries, with even for every and even for all . (For example, could be symmetric with even diagonal, or skew-symmetric.)
- (a)Show that if is odd, then is even.
- (b)Show that the conclusion of (a) fails for every even .
- (c)Show that the hypothesis on the diagonal cannot be dropped, and check (a) on , where every entry of is .
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)
(a) Let be the reduction of modulo . Since is even, . Since is even, in . So is alternating in the sense of Exercise 5.6.13, and since is odd, there. By Proposition 5.3.20,
The argument must work in characteristic , which is why it uses the pairing of Exercise 5.6.13 and not the identity : over , carries no information.
(b) Let and let be block diagonal with blocks . Its diagonal entries are , and is or , so satisfies the hypotheses. By Corollary 5.4.27,
(c) For odd , has for but odd diagonal entries, and is odd. So the diagonal hypothesis is needed (it is not implied by the other one, which for only says that is even). The matrix has diagonal entries and , and by Example 5.4.24 with ,
Problem 5.16. Let be skew-symmetric, .
- (a)Show that for every , and deduce that is invertible for every .
- (b)Show that . (Consider on .)
- (c)Compute for and in terms of the entries above the diagonal.
- (d)Show that the conclusion of (b) can fail if is only assumed to have .
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 ( as a function of ), Proposition 5.3.15 (Triangular matrices)
Techniques. is a polynomial in the entries (Technique 5.3.18)
(a) The matrix equals its transpose, which by Proposition 2.4.23 is
so , and is invertible by Corollary 5.4.8.
(b) Let
(c) For , and
Both are at least . In fact for every real skew-symmetric , but the proof needs the spectral theory of Chapter 8.
(d) has trace , and
Problem 5.17. Let be a subspace of in which every nonzero matrix is invertible.
- (a)Show that . (Consider the vectors for in a basis of .)
- (b)Show that
is a subspace of with this property and . - (c)Let and . Show that . (Take independent and look at .)
- (d)Let and let be odd. Show that .
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. is a polynomial in the entries (Technique 5.3.18)
(a) Suppose , and let be a basis of . The vectors lie in , so they are dependent (Theorem 4.1.10): with not all . Let . Since the are independent, ; but , so is not invertible (Corollary 5.4.8). This contradicts the hypothesis, so .
(b) with , so it is a subspace, and , are independent, so . For , , which is positive unless . So every nonzero is invertible.
(c) Suppose , and let be independent. Then , so is invertible and . By Exercise 5.5.48 (a), there are with
(d) For this is (a). For odd , argue as in (c): with independent in ,
So the largest possible depends on the field: over , over for odd , but over for , by (b). (For over , a construction from the quaternions reaches .)
Problem 5.18. 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
and check the formula for . (Hint: let be the matrix with every entry , and show that is affine in .)
Uses. Lemma 5.1.8 (Column replacement), Definition 5.1.1 (Determinant function), Proposition 5.3.15 (Triangular matrices)
Techniques. Polynomial identity arguments (Technique 5.5.24), is a polynomial in the entries (Technique 5.3.18)
Let and let be the columns of , so the columns of are . Subtracting column from each other column does not change the determinant (Lemma 5.1.8), and leaves the columns
for constants . Note .
The matrix has diagonal entries , entries 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,
For the formula gives
which is . 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 (compare Example 5.4.24).
- (a)Let , and for let have degree and coefficient of . Show that the matrix with entry has determinant .
- (b)Let be integers. Show that is divisible by .
- (c)Deduce that is an integer for all integers .
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)
(a) Write
So the matrix in question is , and its determinant is
(b) Replacing every by , for an integer , does not change any difference . So we may assume that every . For , 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 of , such that
with . For an integer ,
pulling the factor out of column . The matrix has integer entries, so its determinant is an integer (Proposition 5.3.20), and divides the product.
(c) By Exercise 5.5.26 (a),
Problem 5.20. Let have entries . For , let be the number of with . You may use that for every integer .
- (a)Show that , where
and has entry if and otherwise. - (b)Deduce that
, and evaluate . - (c)Show that is invertible for every , and that has integer entries only for .
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)
(a) The entry of is
A common divisor of and is at most , so the condition is automatic, and the common divisors of and are exactly the divisors of . By the given identity with , the sum is .
(b) If then , so is lower triangular, and . So (Proposition 5.3.15, Theorem 5.4.14), and by Theorem 5.4.10,
Since
(c) Every , since is counted, so and is invertible (Theorem 5.4.7). By Corollary 5.5.12, has integer entries exactly when , that is, when for every . Since and , this happens exactly for .
The factorization is the whole proof. Computing 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.)