An Inquiry-Based Introduction to Linear Algebra and Applications

Proof of the Invertible Matrix Theorem.

Statement (1) implies Statement (2)

This follows from work done in Activity 11.2.

Statement (2) implies Statement (3)

This was done in Activity 11.2.

Statement (3) implies Statement (4)

Suppose that every column of $A$ is a pivot column. The fact that $A$ is square means that every row of $A$ contains a pivot, and hence the columns of $A$ span ${\mathbb{R}}^n\text{.}$

Statement (4) implies Statement (5)

Since the columns of $A$ span ${\mathbb{R}}^n\text{,}$ it must be the case that every row of $A$ contains a pivot. This means that $A$ must be row equivalent to $I_n\text{.}$

Statement (5) implies Statement (6)

If $A$ is row equivalent to $I_n\text{,}$ there must be a pivot in every column, which means that the columns of $A$ are linearly independent.

Statement (6) implies Statement (7)

If the columns of $A$ are linearly independent, then there is a pivot in every column. Since $A$ is a square matrix, there is a pivot in every row as well. So the columns of $A$ span ${\mathbb{R}}^n\text{.}$ Since they are also linearly independent, the columns form a minimal spanning set, which is a basis of ${\mathbb{R}}^n\text{.}$

Statement (7) implies Statement (8)

If the columns form a basis of ${\mathbb{R}}^n\text{,}$ then the columns are linearly independent. This means that each column is a pivot column, which also implies $A\mathbf{x}=\mathbf{0}$ has a unique solution and that $T$ is one-to-one.

Statement (8) implies Statement (9)

If $T$ is one-to-one, then $A$ has a pivot in every column. Since $A$ is square, every row of $A$ contains a pivot. Therefore, the system $A\mathbf{x}=\mathbf{b}$ is consistent for every $\mathbf{b}\in {\mathbb{R}}^n$ and has a unique solution.

Statement (9) implies Statement (10)

If $A\mathbf{x}=\mathbf{b}$ has a unique solution for every $\mathbf{b}\text{,}$ then the transformation $T$ is onto since $T(\mathbf{x})=\mathbf{b}$ has a solution for every $\mathbf{b}\text{.}$

Statement (10) implies Statement (11)

Assume that $T$ defined by $T(\mathbf{x})=A\mathbf{x}$ is onto. For each $i\text{,}$ let ${\mathbf{e}}_i$ be the $i$th column of the $n\times n$ identity matrix $I_n\text{.}$ That is, ${\mathbf{e}}_i$ is the vector in ${\mathbb{R}}^n$ with 1 in the $i$th component and 0 everywhere else. Since $T$ is onto, for each $i$ there is a vector ${\mathbf{c}}_i$ such that $T({\mathbf{c}}_i)=A{\mathbf{c}}_i={\mathbf{e}}_i\text{.}$ Let $C=[{\mathbf{c}}_1{\mathbf{c}}_2\cdots {\mathbf{c}}_n]\text{.}$ Then

$$AC=A[{\mathbf{c}}_1{\mathbf{c}}_2\cdots {\mathbf{c}}_n]=[A{\mathbf{c}}_{1}A{\mathbf{c}}_2\cdots A{\mathbf{c}}_n]=[{\mathbf{e}}_1{\mathbf{e}}_2\cdots {\mathbf{e}}_n]=I_n\text{.}$$

Statement (11) implies Statement (12)

Assume $C$ is an $n\times n$ matrix so that $AC=I_n\text{.}$ First we show that the matrix equation $C\mathbf{x}=\mathbf{0}$ has only the trivial solution. Suppose $C\mathbf{x}=\mathbf{0}\text{.}$ Then multiplying both sides on the left by $A$ gives us

$$A(C\mathbf{x})=A\mathbf{0}\text{.}$$

Simplifying this equation using $AC=I_n\text{,}$ we find $\mathbf{x}=\mathbf{0}\text{.}$ Since $C\mathbf{x}=\mathbf{0}$ has only the trivial solution, every column of $C$ must be a pivot column. Since $C$ is an $n\times n$ matrix, it follows that every row of $C$ contains a pivot position. Thus, the matrix equation $C\mathbf{x}=\mathbf{b}$ is consistent and has a unique solution for every $\mathbf{b}$ in ${\mathbb{R}}^n\text{.}$ Let ${\mathbf{v}}_i$ be the vector in ${\mathbb{R}}^n$ satisfying $C{\mathbf{v}}_i={\mathbf{e}}_i$ for each $i$ between 1 and $n$ and let $M=[{\mathbf{v}}_1{\mathbf{v}}_2\cdots {\mathbf{v}}_n]\text{.}$ Then $CM=I_n\text{.}$ Now we show that $CA=I_n\text{.}$ Since

$$AC=I_n$$

we can multiply both sides on the left by $C$ to see that

$$C(AC)=C{I}_n\text{.}$$

Now we multiply both sides on the right by $M$ and obtain

$$(C(AC))M=CM\text{.}$$

Using the associative property of matrix multiplication and the fact that $CM=I_n$ shows that

$$\begin{array}{rl}(CA)(CM)& =CM\\ CA=I_n\text{.}\end{array}$$

Thus, if $A$ and $C$ are $n\times n$ matrices and $AC=I_n\text{,}$ then $CA=I_n\text{.}$ So we have proved our implication with $D=C$

Statement (12) implies Statement (13)

Assume that there is an $n\times n$ matrix $D$ so that $DA=I_n\text{.}$ Suppose $A\mathbf{x}=\mathbf{0}\text{.}$ Then multiplying both sides by $A$ on the left, we find that

$$\begin{array}{rl}D(A\mathbf{x})& =D\mathbf{0}\\ (DA)\mathbf{x}& =\mathbf{0}\\ \mathbf{x}& =\mathbf{0}\text{.}\end{array}$$

So the equation $A\mathbf{x}=\mathbf{0}$ has only the trivial solution and $0$ is not an eigenvalue for $A\text{.}$

Statement (13) implies Statement (14)

If 0 is not an eigenvalue of $A\text{,}$ then the equation $A\mathbf{x}=\mathbf{0}$ has only the trivial solution. Since statement 2 implies statement 11, there is an $n\times n$ matrix $C$ such that $AC=I_n\text{.}$ The proof that statement 11 implies statement 12 shows that $CA=I_n$ as well. So $A$ is invertible. By taking the transpose of both sides of the equation $A{A}^{-1}=A^{-1}A=I_n$ (remembering $(AB{)}^{\mathsf{T}}=B^{\mathsf{T}}{A}^{\mathsf{T}}$) we find

$$(A^{-1}{)}^{\mathsf{T}}{A}^{\mathsf{T}}=A^{\mathsf{T}}(A^{-1}{)}^{\mathsf{T}}=I_n^{\mathsf{T}}=I_n\text{.}$$

Therefore, $(A^{-1}{)}^{\mathsf{T}}$ is the inverse of $A^{\mathsf{T}}$ by definition of the inverse.

Statement (14) implies Statement (1)

Since statement (1) implies statement (14), we proved ‘If $A$ is invertible, then $A^{\mathsf{T}}$ is invertible.’' Using this implication with $A^{\mathsf{T}}$ replaced by $A\text{,}$ we find that ‘If $A^{\mathsf{T}}$ is invertible, then $(A^{\mathsf{T}}{)}^{\mathsf{T}}$ is invertible.’' But $(A^{\mathsf{T}}{)}^{\mathsf{T}}=A\text{,}$ which proves that statement (14) implies statement (1).