Math Core

You now have many ways to describe a square matrix: its pivots, its columns, the solutions of $A\mathbf{x} = \mathbf{0}$ and $A\mathbf{x} = \mathbf{b}$ , and whether it has an inverse. For a square matrix these descriptions are not independent facts. They all rise or fall together, and the theorem that says so is one of the most useful tools in the course.

The theorem

The Invertible Matrix Theorem

Let $A$ be an $n \times n$ matrix. The following statements are equivalent: for a given $A$ , they are either all true or all false.

$A$ is invertible.
$A$ is row equivalent to $I_n$ .
$A$ has $n$ pivot positions.
The equation $A\mathbf{x} = \mathbf{0}$ has only the trivial solution.
The columns of $A$ are linearly independent.
The equation $A\mathbf{x} = \mathbf{b}$ has at most one solution for each $\mathbf{b}$ in $\mathbb{R}^n$ .
The equation $A\mathbf{x} = \mathbf{b}$ has at least one solution for each $\mathbf{b}$ in $\mathbb{R}^n$ .
The columns of $A$ span $\mathbb{R}^n$ .
There is an $n \times n$ matrix $C$ with $CA = I$ .
There is an $n \times n$ matrix $D$ with $AD = I$ .
$A^T$ is invertible.

In the next two lessons you will meet linear transformations. Statement 6 will then read " $\mathbf{x} \mapsto A\mathbf{x}$ is one-to-one" and statement 7 will read " $\mathbf{x} \mapsto A\mathbf{x}$ maps $\mathbb{R}^n$ onto $\mathbb{R}^n$ ." In the next unit, " $\det A \ne 0$ " joins the list too.

Why it is true

Everything hinges on counting pivots in an $n \times n$ matrix.

Statements 2, 3 and 1. A square matrix with $n$ pivots has a pivot in every row and every column, so its reduced echelon form is $I_n$ . Conversely, $I_n$ has $n$ pivots. The previous lesson showed that $A$ is invertible exactly when it row reduces to $I_n$ .

The "independence" side (3, 4, 5, 6). From the last unit: $A\mathbf{x} = \mathbf{0}$ has only the trivial solution exactly when there are no free variables, that is, when every column has a pivot. That is statement 3 for a square matrix. Statement 5 is statement 4 restated, since a nontrivial solution of $A\mathbf{x} = \mathbf{0}$ is precisely a dependence relation among the columns. Statement 6 is also equivalent: if $A\mathbf{x} = \mathbf{b}$ had two solutions, their difference would be a nontrivial solution of $A\mathbf{x} = \mathbf{0}$ .

The "spanning" side (3, 7, 8). Also from the last unit: $A\mathbf{x} = \mathbf{b}$ is consistent for every $\mathbf{b}$ exactly when $A$ has a pivot in every row, and that is the same as saying the columns span $\mathbb{R}^n$ . With $n$ rows, a pivot in every row means $n$ pivots.

This is the heart of the theorem. For a rectangular matrix, "a pivot in every column" and "a pivot in every row" are different conditions. For a square matrix they are both the statement "there are $n$ pivots," so they coincide.

Statements 9, 10 and 11. If $CA = I$ , then $A\mathbf{x} = \mathbf{0}$ implies $\mathbf{x} = CA\mathbf{x} = C\mathbf{0} = \mathbf{0}$ , which is statement 4. If $AD = I$ , then for any $\mathbf{b}$ , $\mathbf{x} = D\mathbf{b}$ solves $A\mathbf{x} = \mathbf{b}$ , which is statement 7. Invertibility gives both $C$ and $D$ (take $A^{-1}$ ). Finally, $A^T$ is invertible when $A$ is (with inverse $(A^{-1})^T$ ), and applying that fact to $A^T$ gives the converse.

A bonus from statements 9 and 10: for square matrices, a one-sided inverse is automatically a two-sided inverse. If $CA = I$ , then $A$ is invertible and $C = A^{-1}$ .

Common mistake

The Invertible Matrix Theorem applies only to square matrices. A $3 \times 2$ matrix can have linearly independent columns, but its columns can never span $\mathbb{R}^3$ , and it has no inverse. Before you use the theorem, check that the matrix is $n \times n$ .

Using the theorem

The practical power of the theorem is that you can prove any one statement, by whatever method is easiest, and get all the others for free. The same goes for disproving one.

Worked example: Deciding invertibility

Is $A = \begin{bmatrix} 1 & 3 & 0 \\ -2 & -5 & 1 \\ 0 & 4 & 7 \end{bmatrix}$ invertible?

You don't need $A^{-1}$ ; you only need the number of pivots. Add $2$ times row 1 to row 2, then subtract $4$ times the new row 2 from row 3:

\begin{bmatrix} 1 & 3 & 0 \\ -2 & -5 & 1 \\ 0 & 4 & 7 \end{bmatrix} \sim \begin{bmatrix} 1 & 3 & 0 \\ 0 & 1 & 1 \\ 0 & 4 & 7 \end{bmatrix} \sim \begin{bmatrix} 1 & 3 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 3 \end{bmatrix}.

There are $3$ pivots, so $A$ is invertible. Without further work you also know the columns of $A$ are independent and span $\mathbb{R}^3$ , and $A\mathbf{x} = \mathbf{b}$ has exactly one solution for every $\mathbf{b}$ .

Worked example: Spotting a dependence

Is $B = \begin{bmatrix} 1 & 2 & 3 \\ 4 & -1 & 3 \\ 0 & 5 & 5 \end{bmatrix}$ invertible?

Look at the columns before reducing anything. Column 3 is column 1 plus column 2: $1 + 2 = 3$ , $4 - 1 = 3$ and $0 + 5 = 5$ . So the columns are linearly dependent, statement 5 fails, and $B$ is not invertible.

The theorem then tells you more: some $\mathbf{b}$ in $\mathbb{R}^3$ makes $B\mathbf{x} = \mathbf{b}$ inconsistent, and $B\mathbf{x} = \mathbf{0}$ has a nontrivial solution. Indeed, $\mathbf{x} = (1, 1, -1)$ works.

Worked example: Reasoning without numbers

$A$ is a $4 \times 4$ matrix, and the equation $A\mathbf{x} = \mathbf{b}$ has a solution for every $\mathbf{b}$ in $\mathbb{R}^4$ . Can $A\mathbf{x} = \mathbf{c}$ have two different solutions for some $\mathbf{c}$ ?

No. $A$ is square and statement 7 holds, so $A$ is invertible, and then statement 6 holds as well. Every equation $A\mathbf{x} = \mathbf{c}$ has exactly one solution, $\mathbf{x} = A^{-1}\mathbf{c}$ .

The contrapositive view

It often helps to read the theorem in the negative. For an $n \times n$ matrix $A$ , the following are all equivalent to " $A$ is singular": $A$ has fewer than $n$ pivots; $A\mathbf{x} = \mathbf{0}$ has a nontrivial solution; the columns are dependent; the columns fail to span $\mathbb{R}^n$ ; some equation $A\mathbf{x} = \mathbf{b}$ has no solution. A singular square matrix fails in both directions at once: it loses uniqueness and existence.

Tip

Quick singularity checks for a square matrix: a zero row or zero column, two equal (or proportional) rows or columns, or one column that is an obvious combination of others. Any of these means the matrix is not invertible. A triangular matrix is invertible exactly when all of its diagonal entries are nonzero, because those entries are its pivots.

Practice

Practice 1

Is $\begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix}$ invertible?

Practice 2

Is $\begin{bmatrix} 2 & 4 & -2 \\ 1 & 3 & 0 \\ 3 & 7 & -2 \end{bmatrix}$ invertible?

Practice 3

$A$ is a $4 \times 4$ matrix, and $A\mathbf{x} = \mathbf{0}$ has a nontrivial solution. Which statement must be true?

Practice 4

$A$ is a $5 \times 5$ matrix whose columns span $\mathbb{R}^5$ . How many solutions does $A\mathbf{x} = \mathbf{b}$ have when $\mathbf{b} = (1, 0, 2, 0, 3)$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 5

For what value of $h$ is $\begin{bmatrix} 1 & 2 & 1 \\ 2 & 5 & h \\ 1 & 3 & 4 \end{bmatrix}$ not invertible?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 6

$A$ is a $3 \times 3$ matrix, and for one particular vector $\mathbf{b}$ the equation $A\mathbf{x} = \mathbf{b}$ has infinitely many solutions. What can you say about $A\mathbf{x} = \mathbf{c}$ for a different vector $\mathbf{c}$ ?

Practice 7

For an $n \times n$ matrix $A$ , which statement is not equivalent to " $A$ is invertible"?