The invertible matrix theorem

Day 1: the loop and the links

The loop from (a) to (d) to (c) to (b) and back to (a) makes those four equivalent, since from any one of them the loop leads to each of the others.

(a) gives (d). If A\mathbf{x} = \mathbf{0}, then \mathbf{x} = A^{-1}(A\mathbf{x}) = A^{-1}\mathbf{0} = \mathbf{0}.

(d) gives (c). A column of the reduced form without a pivot gives a free variable, and setting it to 1 gives a nonzero solution of A\mathbf{x} = \mathbf{0} (Solving a system by row reduction: one, none or infinitely many solutions). Under (d) there is none, so all n columns have pivots.

(c) gives (b). With n pivots in n columns, each column has one. Going down, the pivots move strictly right, so the pivot of row i sits in column i. In reduced form each pivot is 1 with zeros above and below: that is I_n.

(b) gives (a). This is Finding an inverse by row reducing A next to I: the row operations that turn A into I_n turn I_n into A^{-1}.

Every other condition is joined to one of these four by a link that runs both ways.

(d) with (e), (f) and (q). By Multiplying a matrix by a vector, A\mathbf{x} = x_1\mathbf{a}_1 + \dots + x_n\mathbf{a}_n for the columns \mathbf{a}_j, so a nonzero solution of A\mathbf{x} = \mathbf{0} is exactly a nontrivial dependence among the columns: (d) is (e). By Kernel a linear map is one-to-one exactly when its kernel is \{\mathbf{0}\}: (d) is (f). And A\mathbf{v} = 0\mathbf{v} says A\mathbf{v} = \mathbf{0}, so (d) is (q); eigenvalues are the subject of The characteristic equation and finding eigenvalues.

(e) with (n). By Basis and dimension, any n linearly independent vectors in \mathbb{R}^n span it, so (e) gives a basis; and a basis is independent.

(c) with (g), (h), (i). By Image, A\mathbf{x} = \mathbf{b} is solvable for every \mathbf{b} exactly when every row has a pivot. In an n \times n matrix that means n pivots, and n pivots means one in every row: (c) is (g). The set of all A\mathbf{x} is both \operatorname{im} A and the span of the columns (Span), so (g), (h), (i) say the same thing.

(c) with (m). The rank is the number of pivots (Rank); by Rank and nullity, rank n also says \dim \ker A = 0.

(a) with (j), (k). If A is invertible, C = D = A^{-1} works. Conversely, the result “one product is enough” of When a matrix or transformation can be undone says that for square matrices XY = I_n forces YX = I_n. With X = A, Y = D it turns (k) into (a); with X = C, Y = A it turns (j) into (a).

(a) with (l). By Result 6 of The transpose and symmetric matrices, if A is invertible so is A^{T}. Applied to A^{T}, whose transpose is A, it gives the converse.

(a) with (o). If A is invertible, A^{-1}\mathbf{b} is a solution, and any solution satisfies \mathbf{x} = A^{-1}(A\mathbf{x}) = A^{-1}\mathbf{b}. Conversely, (o) with \mathbf{b} = \mathbf{0} is (d).

(a) with (p). Theorem 3 of Properties of determinants: row operations, products, transposes: a square matrix is invertible exactly when its determinant is not 0.

The transpose conditions. A is invertible exactly when A^{T} is. Apply (e), (h) and (p) to A^{T}, whose columns are the rows of A, and use \det A^{T} = \det A (Theorem 5 of Properties of determinants: row operations, products, transposes).

Day 2: products and other shapes

Products. If A and B are invertible, B^{-1}A^{-1} undoes AB. Conversely, let P = AB be invertible. Then A\big(BP^{-1}\big) = PP^{-1} = I_n, so A satisfies (k), and \big(P^{-1}A\big)B = I_n, so B satisfies (j).

Other shapes. The links among (d), (e), (f) and among (g), (h), (i) never used squareness, and Rank and nullity gives the rank conditions; both together would make n = \operatorname{rank} A = m. A left inverse gives (d) as in Exercise 8; a right inverse D gives (g), since \mathbf{b} = A(D\mathbf{b}).

1. Rows 2 - 2\cdot 1 and 3 - 1 give (0, 1, 1) and (0, 1, 2), then row 3 - 2 gives (0, 0, 1). Three pivots, so yes, and the determinant is 1, the product of the pivots.
2. \ker B = \operatorname{span}\{(1, -2, 1)\}: both lower rows reduce to multiples of (0, 1, 2), so x_2 = -2t, x_1 = -2x_2 - 3x_3 = t. Row 1 plus row 2 equals row 3. None of (a) to (q) holds.
3. \det K_0 = 1(0 - 1) - 1(1 - 0) = -2, so invertible. Adding the three equations gives x_1 + x_2 + x_3 = \tfrac32, and each pair sums to 1, so \mathbf{x} = (\tfrac12, \tfrac12, \tfrac12).
4. \det = 1(2 - 1) + c(0 - c) = 1 - c^2: invertible for every c except c = 1 and c = -1. At c = 1, \mathbf{a}_1 + \mathbf{a}_2 - \mathbf{a}_3 = \mathbf{0}, since (1, 0, 1) + (0, 1, 1) = (1, 1, 2).
5. First: each row sums to 0, so 0 is an eigenvalue with eigenvector (1, 1, 1). Second: \det = 3(6 - 1) - 1(3 - 0) = 12 \neq 0, so 0 is not an eigenvalue.
6. (h) holds, so every condition does. (1) true; (2) true, as A^{T} is invertible by (l); (3) false; (4) true, by the transpose conditions.
7. Nullity 5 - 4 = 1 by Rank and nullity. Condition (m) fails, so all fail: some \mathbf{b} is unreachable, and \det A = 0.
8. \mathbf{x} = I_n\mathbf{x} = (CA)\mathbf{x} = C(A\mathbf{x}) = C\mathbf{0} = \mathbf{0}, by associativity of the product.
9. If columns i and j are equal, \mathbf{a}_i - \mathbf{a}_j = \mathbf{0} is a nontrivial relation, so (e) fails. Also \det A = 0 by Theorem 6 of Properties of determinants: row operations, products, transposes, so (p) fails.
10. If A\mathbf{u} = A\mathbf{v} = \mathbf{b} with \mathbf{u} \neq \mathbf{v}, then \mathbf{u} - \mathbf{v} is a nonzero kernel vector, so (d) fails, and by the theorem (g) fails.
11. By the triangular theorem of Determinants by cofactor expansion, its determinant is the product of its diagonal entries. That is nonzero exactly when no diagonal entry is 0; then use (p).
12. \det = 1 - a(0 - a^2) = 1 + a^3, which factors as (1 + a)(1 - a + a^2), and 1 - a + a^2 has no real root, so invertible for every real a except a = -1. There each row sums to 0, so the kernel is \operatorname{span}\{(1, 1, 1)\}; the rows add to \mathbf{0}, so every output has b_1 + b_2 + b_3 = 0, and (1, 0, 0) has no solution.
13. The first and third equations give x_1 = x_3 = -x_2, and the second becomes (k - 2)x_2 = 1, so \displaystyle \mathbf{x} = \frac{1}{k - 2}(-1, 1, -1). At k = 2 it reads 0 = 1: no solution, matching b_1 - b_2 + b_3 = -1 \neq 0.
14. The determinant is 1(t - 1) - 1(1 - t) + t(1 - t^2), which simplifies to -(t - 1)^2(t + 2): a basis for every t except t = 1 and t = -2.
15. R_4 is singular: (1, -1, 1, -1) is in its kernel. Each column also has alternating sum 0, so every reading has b_1 - b_2 + b_3 - b_4 = 0, and (1, 0, 0, 0) never occurs. R_3 is invertible: \det R_3 = 1(1 - 0) - 0 + 1(1 - 0) = 2.
16. By the product rule, \det A \det B = 6, so neither is 0: A and B are invertible, and so is BA, with \det(BA) = 6.
17. The top rows \begin{bmatrix} 1 & 2 \\ 1 & 3 \end{bmatrix} have inverse \begin{bmatrix} 3 & -2 \\ -1 & 1 \end{bmatrix}, so C = \begin{bmatrix} 3 & -2 & 0 \\ -1 & 1 & 0 \end{bmatrix} has CH = I_2. H(x, y) = (x + 2y,\ x + 3y,\ y), so outputs satisfy b_3 = b_2 - b_1, and (0, 0, 1) never occurs.
18. D = \begin{bmatrix} 1 & -1 \\ 0 & 1 \\ 0 & 0 \end{bmatrix} has WD = I_2 (its columns solve W\mathbf{d} = \mathbf{e}_1 and W\mathbf{d} = \mathbf{e}_2). Kernel vector (1, -2, 1). If CW = I_3, then (1, -2, 1) = CW(1, -2, 1) = \mathbf{0}, which is false.
19. \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{bmatrix} has independent columns but is not square, so it has no inverse; (0, 0, 1) is not an output.
20. A(4I_n - A) = 4A - A^2 = 3I_n, so A \cdot \tfrac13(4I_n - A) = I_n. That is (k), so A^{-1} = \tfrac13(4I_n - A).
21. If A were invertible, so would be A^3 = A(AA) by the products result; the zero matrix fails (d). And (I_n - A)(I_n + A + A^2) = I_n - A^3 = I_n, which is (k).
22. Independent columns need a pivot in each of the n columns and spanning needs one in each of the m rows, so the pivot count would equal both n and m.
23. Let \mathbf{x}_0 be the solution. If A\mathbf{k} = \mathbf{0}, then A(\mathbf{x}_0 + \mathbf{k}) = \mathbf{b}, so \mathbf{x}_0 + \mathbf{k} = \mathbf{x}_0 and \mathbf{k} = \mathbf{0}. That is (d), so A is invertible.