Linear Algebra › Section B · Matrix algebra › Topic B.3

The invertible matrix theorem

Pivots, independence, spanning, one-to-one maps and inverses looked like separate ideas. For a square matrix they are one idea seen from many sides: either every statement on a long list is true, or every one is false.

Many questions, one answer

Faced with a square matrix, you might ask: does \(A\mathbf{x} = \mathbf{b}\) always have a solution? Is the solution unique? Are the columns independent? Does \(A\) have an inverse? Each question seems to need its own calculation. The invertible matrix theorem says that for an \(n \times n\) matrix they all have the same answer. So one row reduction, which counts the pivots, settles every one of them at once. That is why this theorem is the hub of the course.

The theorem

Let \(A\) be an \(n \times n\) matrix. The following statements are equivalent: for a given \(A\), all are true or all are false. (a) \(A\) is invertible. (b) \(A\) is row equivalent to \(I_n\). (c) \(A\) has \(n\) pivot positions. (d) \(A\mathbf{x} = \mathbf{0}\) has only the trivial solution. (e) The columns of \(A\) are linearly independent. (f) The transformation \(\mathbf{x} \mapsto A\mathbf{x}\) is one-to-one. (g) \(A\mathbf{x} = \mathbf{b}\) has at least one solution for each \(\mathbf{b}\) in \(\mathbb{R}^n\). (h) The columns of \(A\) span \(\mathbb{R}^n\). (i) The transformation \(\mathbf{x} \mapsto A\mathbf{x}\) maps \(\mathbb{R}^n\) onto \(\mathbb{R}^n\). (j) There is an \(n \times n\) matrix \(C\) with \(CA = I\). (k) There is an \(n \times n\) matrix \(D\) with \(AD = I\). (l) \(A^T\) is invertible. Later topics, including "Dimension and rank" and "Properties of determinants", add more statements to the list.

Why square matters

The proof rests on pivots. An \(n \times n\) matrix has \(n\) rows and \(n\) columns, so \(n\) pivots means a pivot in every column and in every row at once. A pivot in every column leaves no free variables, which gives (d), (e) and (f), the uniqueness statements from "Span and linear independence" and "Introduction to linear transformations". A pivot in every row gives (g), (h) and (i), the existence statements. For a non-square matrix these two halves come apart: a \(3 \times 2\) matrix can have independent columns, yet two vectors can never span \(\mathbb{R}^3\).

One-sided inverses are enough

Statements (j) and (k) say something surprising. For square matrices you never need to check both products: if \(CA = I\), then \(A\) is invertible and \(C = A^{-1}\), and likewise if \(AD = I\). Here is why (j) leads back to (d). If \(CA = I\) and \(A\mathbf{x} = \mathbf{0}\), then \(\mathbf{x} = CA\mathbf{x} = C\mathbf{0} = \mathbf{0}\), so only the trivial solution exists. Statement (l) adds rows to the picture: because \(A^T\) is also invertible, the rows of an invertible matrix are independent and span \(\mathbb{R}^n\) too.

Using the theorem both ways

Because the statements stand or fall together, any one of them can prove all the others, and the failure of any one means all fail. If you know the columns of a \(5 \times 5\) matrix are independent, you immediately know every \(A\mathbf{x} = \mathbf{b}\) is solvable. If you spot two equal columns, or a column of zeros, the columns are dependent, so the matrix is singular and some \(A\mathbf{x} = \mathbf{b}\) has no solution. A triangular matrix is invertible exactly when none of its diagonal entries is zero, since those entries are then its pivots.

Worked example: a singular 3 × 3

Let \(A\) have rows (1, 2, 0), (0, 1, 1) and (2, 3, −1). 1. Row 3 minus 2 times row 1 gives (0, −1, −1). 2. Adding row 2 gives (0, 0, 0). 3. The echelon form has only 2 pivots, so (c) fails and \(A\) is singular. 4. Then (e) fails too: solving \(A\mathbf{x} = \mathbf{0}\) with \(x_3 = 1\) gives \(\mathbf{x} = (2, -1, 1)\), so \(2\mathbf{a}_1 - \mathbf{a}_2 + \mathbf{a}_3 = \mathbf{0}\); check:

2(1, 0, 2) - (2, 1, 3) + (0, 1, -1) = (0, 0, 0)

5. And (g) fails: for \(\mathbf{b} = (0, 0, 1)\), the same row operations turn the last row of \([A \ \mathbf{b}]\) into (0, 0, 0 | 1), so that system has no solution. One count of pivots told us all of this.

Worked example: reasoning without numbers

A \(4 \times 4\) matrix \(A\) has the property that the equation \(A\mathbf{x} = \mathbf{e}_1\) has two different solutions. Can \(A\mathbf{x} = \mathbf{b}\) be solved for every \(\mathbf{b}\)? 1. If \(\mathbf{u}\) and \(\mathbf{v}\) both solve it, then \(A(\mathbf{u} - \mathbf{v}) = \mathbf{0}\) with \(\mathbf{u} - \mathbf{v} \ne \mathbf{0}\). 2. So \(A\mathbf{x} = \mathbf{0}\) has a non-trivial solution, and (d) is false. 3. By the theorem, (g) is false as well. 4. Conclusion: no. Some \(\mathbf{b}\) in \(\mathbb{R}^4\) gives an inconsistent system, even though \(\mathbf{e}_1\) gives infinitely many solutions. Uniqueness failing has forced existence to fail.

Invertible linear transformations

A linear transformation \(T: \mathbb{R}^n \to \mathbb{R}^n\) is invertible if there is a map \(S\) with \(S(T(\mathbf{x})) = \mathbf{x}\) and \(T(S(\mathbf{x})) = \mathbf{x}\) for every \(\mathbf{x}\). If \(A\) is the standard matrix of \(T\), then \(T\) is invertible exactly when \(A\) is, and the inverse is \(S(\mathbf{x}) = A^{-1}\mathbf{x}\). A rotation of the plane by an angle is undone by rotating back by the same angle. Projecting the plane onto the \(x_1\)-axis cannot be undone: many points land on the same spot, so the map is not one-to-one and its matrix is singular.

Nearly singular matrices

On a computer, invertible is not the whole story. Take rows (1, 1) and (1, 1.0001). It is invertible, since \(ad - bc = 0.0001\), but barely. With \(\mathbf{b} = (2, 2)\) the solution is \((2, 0)\); change \(\mathbf{b}\) to \((2, 2.0001)\) and the solution jumps to \((1, 1)\). A matrix like this is called ill-conditioned: tiny errors in the data cause large errors in the answer. Software measures this with a condition number, which is large for nearly singular matrices.

Common mistakes to avoid

First, applying the theorem to a non-square matrix; every statement assumes \(n \times n\). Second, thinking you must check every statement; one is enough, in either direction. Third, concluding \(A\) is invertible because it has no zero entries: rows (1, 2) and (2, 4) are full of non-zero numbers but dependent. Fourth, treating an invertible but ill-conditioned matrix as safe for computation. Fifth, confusing "has a solution" (g) with "has a unique solution": for square matrices they happen together, but they are different statements.

Key takeaways

For an n × n matrix A, these stand or fall together: A is invertible; A is row equivalent to I; A has n pivots; Ax = 0 has only the trivial solution; the columns are independent; x ↦ Ax is one-to-one; Ax = b is solvable for every b; the columns span Rⁿ; x ↦ Ax is onto; A has a left or a right inverse; Aᵀ is invertible. The key is that n pivots in a square matrix fill every row and every column. A linear map of Rⁿ is invertible exactly when its standard matrix is, with inverse x ↦ A⁻¹x. Nearly singular matrices are ill-conditioned.

Flashcards

Flashcard

Invertible matrix theorem

For an n × n matrix, a long list of statements are all true or all false

Square matrices only.

Test your understanding

Question 1 of 5

A is a 6 × 6 matrix whose columns are linearly independent. Which conclusion follows?

Question 2 of 5

A is a 3 × 3 matrix and Ax = 0 has a non-trivial solution. Which statement must be true?

Question 3 of 5

A is a 4 × 4 matrix and C is a matrix with CA = I. What can you conclude?

Question 4 of 5

Which of these 3 × 3 matrices is certainly invertible?

Question 5 of 5

A is a 5 × 3 matrix with linearly independent columns. Why can't the invertible matrix theorem tell you that Ax = b is solvable for every b?

← Previous topicNext topic →