2.3 Characterizations of invertible matrices

Big idea

Everything asked about a square matrix so far turns out to be one question in disguise. Does it have an inverse. Do its columns span the space. Are its columns independent. Does every system with this coefficient matrix have a solution. Does the homogeneous system have only the zero solution. For a square matrix all of these have the same answer, always.

The reason is pivot counting. An $n \times n$ matrix has $n$ rows and $n$ columns, so “a pivot in every row” and “a pivot in every column” are the same statement. The first controls existence of solutions, the second controls uniqueness. Force them to coincide and existence and uniqueness stop being separate concerns.

What you gain is leverage. Prove the easiest item on the list and you have proved them all. Disprove the easiest one and you have disproved them all. Most of the work in this section is learning which item is cheapest to check for the matrix in front of you, and remembering that the whole apparatus collapses the moment the matrix stops being square.

Decoder

For a square matrix, the conditions below are equivalent.

That phrasing means each statement implies every other. Any one of them holding forces all of them, and any one failing sinks all of them. The list is not a sequence of separate results to memorise in order; it is one property with a dozen names, and you pick whichever name is easiest to test.

Read the list as a partition of all square matrices into two heaps. The invertible heap has every good property at once. The singular heap has none of them. There is no matrix with independent columns that fails to span, or that spans without being one-to-one, as long as it is square.

Definitions and results

The characterization. Let $A$ be an $n \times n$ matrix. Each of the following holds for $A$ exactly when all the others do.

• $A$ is invertible.
• $A$ is row equivalent to $I_n$.
• $A$ has $n$ pivot positions.
• $A\mathbf{x} = \mathbf{0}$ has only the zero solution.
• The columns of $A$ are linearly independent.
• The transformation $\mathbf{x} \mapsto A\mathbf{x}$ is one-to-one.
• $A\mathbf{x} = \mathbf{b}$ has a solution for every $\mathbf{b}$ in $\mathbf{R}^n$.
• The columns of $A$ span $\mathbf{R}^n$.
• The transformation $\mathbf{x} \mapsto A\mathbf{x}$ is onto $\mathbf{R}^n$.
• Some $n \times n$ matrix $C$ satisfies $CA = I_n$.
• Some $n \times n$ matrix $D$ satisfies $AD = I_n$.
• $A^T$ is invertible.

Consequence for consistency. A square system is either uniquely solvable for every right-hand side or it fails to be uniquely solvable for any of them. If $A$ is singular, then for each $\mathbf{b}$ the system $A\mathbf{x} = \mathbf{b}$ has either no solution or infinitely many, depending on $\mathbf{b}$; exactly one solution never happens.

One-sided inverses are enough, for square matrices. If $A$ and $D$ are square and $AD = I$, then both are invertible and each is the inverse of the other. You never have to check the second product. This fails without squareness: a wide matrix can have a right inverse and no left inverse.

Invertible transformations. A linear transformation $T$ from $\mathbf{R}^n$ to $\mathbf{R}^n$ is invertible when some transformation $S$ satisfies $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 transformation has standard matrix $A^{-1}$. So the list above is a list about transformations too.

What is not on the list. Nothing here mentions the specific entries of $\mathbf{b}$, because the conditions are about $A$ alone. And nothing here applies to a non-square matrix. An $m \times n$ matrix with $m \neq n$ can have independent columns while failing to span, or span while failing to be one-to-one. Keeping those cases separate is the whole content of the earlier work on existence and uniqueness; this section is the special case where they merge.

How to use it in practice. Row reduce to echelon form and count pivots. That single computation answers every question on the list at once, and it costs less than computing an inverse. Reduce all the way only when you need $A^{-1}$ itself.

Worked examples

A singular matrix and everything that follows

Let

$$ A = \begin{bmatrix} 1 & -2 & 1 \\ 2 & -3 & 0 \\ 0 & 1 & -2 \end{bmatrix} $$

Subtract $2$ times row $1$ from row $2$ to get $(0, 1, -2)$, which is identical to row $3$. Subtracting row $2$ from row $3$ leaves a zero row:

$$ \begin{bmatrix} 1 & -2 & 1 \\ 0 & 1 & -2 \\ 0 & 0 & 0 \end{bmatrix} $$

Two pivots, not three. So $A$ is singular, and the rest follows without further work: the columns are dependent, the transformation is neither one-to-one nor onto, and some right-hand sides make the system inconsistent.

Make the dependence explicit. From the echelon form, $x_3$ is free, $x_2 = 2x_3$ and $x_1 = 2x_2 - x_3 = 3x_3$. Taking $x_3 = 1$ gives the solution $(3, 2, 1)$. Check it against the original rows: $3 - 4 + 1 = 0$, $6 - 6 + 0 = 0$, and $0 + 2 - 2 = 0$. A nonzero vector goes to zero, so the columns are dependent and the map is not one-to-one, exactly as the pivot count promised.

An invertible matrix, settled by counting

Let

$$ B = \begin{bmatrix} 2 & 1 & 0 \\ 1 & 3 & 1 \\ 0 & 1 & 2 \end{bmatrix} $$

Swap rows $1$ and $2$ to get a leading $1$, then subtract $2$ times the new row $1$ from row $2$:

$$ \begin{bmatrix} 1 & 3 & 1 \\ 0 & -5 & -2 \\ 0 & 1 & 2 \end{bmatrix} $$

Swap rows $2$ and $3$, then add $5$ times the new row $2$ to row $3$:

$$ \begin{bmatrix} 1 & 3 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & 8 \end{bmatrix} $$

Three pivots in a three-by-three matrix. $B$ is invertible, its columns are independent and span $\mathbf{R}^3$, $B\mathbf{x} = \mathbf{b}$ has exactly one solution for every $\mathbf{b}$, and $B^T$ is invertible too. None of those needed a separate computation.

Check the claim about uniqueness on the homogeneous system. Back-substitution in the last matrix gives $8x_3 = 0$, so $x_3 = 0$; then $x_2 + 2x_3 = 0$ gives $x_2 = 0$; then $x_1 + 3x_2 + x_3 = 0$ gives $x_1 = 0$. Only the zero solution.

Why squareness is not optional

Let

$$ A = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}, \qquad B = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{bmatrix} $$

Then $AB = I_2$: row $1$ of $A$ against the columns of $B$ gives $1$ and $0$, and row $2$ gives $0$ and $1$. A one-sided inverse exists. But

$$ BA = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} $$

which is not $I_3$. Neither matrix is invertible, since neither is square. The map for $A$ is onto and not one-to-one; the map for $B$ is one-to-one and not onto. Existence and uniqueness have come apart again, which is what the characterization rules out only when the two dimensions agree.

Practice

Decide invertibility by reduction, and produce the inverse when it exists.

Read independence of the columns straight off the pivot count.

Classify a system as inconsistent, uniquely solvable, or having infinitely many solutions.

Videos

Watch the passage on what happens to a system when the transformation squashes space into a lower dimension. The claim that solutions either fail to exist or come in an infinite family, with nothing in between, is the singular half of this section stated geometrically.

Quiz

Six items on invertibility, independence of columns, and classifying a system.