3 Matrices 3.11 Solving RREF systems 3.13 Finding inverses

3.12 Invertibility and RREF

We are going to prove the following theorem:

Theorem 3.12.1.

A square matrix $A$ is invertible if and only if there is a sequence of row operations taking $A$ to the identity matrix.

We need a lemma to make the proof work.

Lemma 3.12.2.

Let $X$ be an $n\times n$ matrix in RREF. Either $X=I_{n}$ or $X$ has a column with no leading entry.

Proof.

Suppose every column has a leading entry, so there are $n$ leading entries. There’s at most one leading entry per row and there are $n$ rows, so every row must have a leading entry.

The leading entries go from left to right as we move down the rows of the matrix, so the leading entries in row 1, 2, …, $n$ must be in columns 1, 2, … $n$ otherwise there would be no room to fit them in.

Because $X$ is in RREF, columns with leading entries have zeroes in all other positions. So the first column is $\begin{pmatrix}1\\ 0\\ \vdots\\ 0\end{pmatrix}$ , the second column is $\begin{pmatrix}0\\ 1\\ 0\\ \vdots\\ 0\end{pmatrix}$ , and so on. These are the columns of the identity matrix, so $X=I_{n}$ . ∎

Now we can prove the theorem.

Proof.

Suppose there is a sequence of row operations taking $A$ to $I$ , say $r_{1},\ldots,r_{k}$ . Let $E_{i}=r_{i}(I)$ , the elementary matrix associated to $r_{i}$ . Then

E_{k}E_{k-1}\cdots E_{1}A=I_{n}

since we know from Theorem 3.8.1 that doing $r_{i}$ is the same as left-multiplication by $E_{i}$ . Every elementary matrix is invertible by Corollary 3.8.2. The matrix $E=E_{k}\cdots E_{1}$ is invertible as it is a product of invertible matrices (Theorem 3.5.3). $EA=I$ , so $A=E^{-1}$ which is invertible (with inverse $E$ ).

Conversely suppose there is no sequence of row operations taking $A$ to $I$ . We can do a sequence of row operations to any matrix and end up with a RREF matrix, so when we do this to $A$ , the RREF matrix $X$ we get cannot be $I$ .

Our lemma tells us that in this case $X$ has a column with no leading entry, so there are $n-1$ or fewer leading entries, so there’s a row with no leading entry, that is, a zero row. So $X$ isn’t invertible by Theorem 3.5.2.

As before, there’s an invertible matrix $E$ such that $EA=X$ . By Corollary 3.5.4, $A$ isn’t invertible. ∎

3.12.1 Invertibility and solving equations

Theorem 3.12.3.

A square matrix $A$ is invertible if and only if the only solution to $A\mathbf{x}=\mathbf{0}$ is $\mathbf{0}$ .

Proof.

If $A$ is invertible and $A\mathbf{v}=\mathbf{0}$ then $\mathbf{v}=A^{-1}\mathbf{0}=\mathbf{0}$ .

If $A$ is not invertible, we can do a sequence of row operations to $A$ ending with a RREF matrix $R$ which cannot be the identity because of Theorem 3.12.1.

By Lemma 3.12.2, $R$ has a column with no leading entry, so there is at least one fundamental solution to $R\mathbf{x}=\mathbf{0}$ . The fundamental solutions are not zero, and the solutions of $A\mathbf{x}=\mathbf{0}$ are the same as the solutions of $R\mathbf{x}=\mathbf{0}$ by Theorem 3.9.1, so we are done. ∎