Matrix Inverses

Section 3.10 Matrix Inverses

For \(2\times2\) nonsingular matrices, Theorem 2.10.23 gave a formula for the inverse. In Theorem 2.10.34 we obtained a condition equivalent to “\(\A\) is invertible,” namely “\(\A^T\) is invertible.”

In this section we collect a sizeable number of conditions equivalent to “\(\A\) is invertible” and offer a practical method for finding the inverse when it exists or showing that it does not exist, whichever the case may be.

A nonsquare matrix does not have inverses (though as noted in Exercise 7.3.18 and Exercise 7.3.19 it may have a left- or right-inverse) and not all square matrices have inverses.

Theorem 3.10.1. Invertibility and \(\A\x=\b\).

\(\A\in\R^{n\times n}\) is invertible if and only if for every \(\b\in\R^n,\,\A\x=\b\) has a solution.

Proof.

\(\left(\Rightarrow\right):\) Suppose \(\A\in\R^{n\times n}\) is invertible, fix \(\b\in\R^n\) and consider the equation \(\A\x=\b.\) Then by Theorem 2.10.25 \(\,\x=\A^{-1}\b\) is a (actually, the) solution of \(\A\x=\b.\)

\(\left(\Leftarrow\right):\) Suppose that for every \(\b\in\R^n,\,\A\x=\b\) has a solution. For each of \(\boldsymbol{\wh{e_1\!}},\,\boldsymbol{\wh{e_2\!}},\,\ldots,\,\boldsymbol{\wh{e_n\!}}\) fix vectors \(\x_1,\,\x_2,\,\ldots,\,\x_n\in\R^n\) for which

\begin{align*} \A\x_1\amp=\boldsymbol{\wh{e_1\!}}\\ \A\x_2\amp=\boldsymbol{\wh{e_2\!}}\\ \amp\quad\vdots\\ \A\x_n\amp=\boldsymbol{\wh{e_n\!}} \end{align*}

Then

\begin{equation*} \A\left(\begin{array}{cccc}\x_1\amp\x_2\amp\cdots\amp\x_n\end{array}\right)=\left(\begin{array}{cccc}\boldsymbol{\wh{e_1\!}}\amp\boldsymbol{\wh{e_2\!}}\amp\cdots\amp\boldsymbol{\wh{e_n\!}}\end{array}\right)=\I \end{equation*}

so by Definition 2.10.21 we must have \(\A^{-1}=\left(\begin{array}{cccc}\x_1\amp\x_2\amp\cdots\amp\x_n\end{array}\right).\)

The reader will have noticed our overlap in terminology where we have applied the terms nonsingular/invertible and singular/non-invertible to both matrices and systems, which are different objects.

We justify this collision of terminology in Corollary 3.10.2 below where we relate, in a natural way, the notions of nonsingular and singular as they apply to systems to the notions of nonsingular/invertible and singular/non-invertible as they apply to matrices.

Corollary 3.10.2. The singularity of \(\A\) and the singularity of \(\A\x=\b\).

Let \(\A\in\R^{n\times n}\) and \(\b\in\R^n.\)The system \(\A\x=\b\) is nonsingular if and only if the matrix \(\A\) is invertible (nonsingular).

Proof.

\((\Rightarrow)\) Suppose the system \(\A\x=\b\) is nonsingular. By Theorem 3.1.4 and Definition 3.1.14, \(\A\x=\b\) has a unique solution. Then by Theorem 3.10.1, \(\A\) is nonsingular.

\((\Leftarrow)\) Suppose the matrix \(\A\) is nonsingular. By Theorem 2.10.25, \(\A\x=\b\) has a unique solution so by Definition 3.1.14 the system \(\A\x=\b\) is nonsingular.

The next several theorems and definitions serve to build the theoretical support for our method of calculating inverses or determining that the inverse does not exist, expressed in Remark 3.10.9.

Theorem 3.10.3. Invertibility and \(\A\x=\vec{0}\).

\(\A\in\R^{n\times n}\) is nonsingular if and only if the unique solution to \(\A\x=\vec{0}\) is \(\x=\vec{0}.\)

Proof.

\(\left(\Rightarrow\right):\) Suppose \(\A\in\R^{n\times n}\) is invertible and consider the equation \(\A\x=\vec{0}.\) Then by Theorem 2.10.25 \(\,\x=\A^{-1}\vec{0}=\vec{0}\) is a (the) solution of \(\A\x=\vec{0}.\)

This solution is unique as follows. If \(\y\) satisfies \(\A\y=\vec{0},\) then \(\A\x=\A\y.\) Since \(\A\) is invertible, we may multiply both sides by \(\A^{-1}\) to obtain \(\x=\y,\) so \(\x\) is the only solution to \(\A\x=\vec{0}.\)

\(\left(\Leftarrow\right):\) Fix \(\b\in\R^m,\) suppose that the unique solution to \(\A\x=\vec{0}\) is \(\x=\vec{0}\) and let \(\left(\A|\b\right)\) eliminate to \(\left(\U|\c\right).\) Theorem 3.1.21 Then \(\U\x=\vec{0}\) is nonsingular by Theorem 3.1.29, and has \(n\) pivots by Theorem 3.1.21. Since \(\U\x=\vec{0}\) has \(n\) pivots, \(\U\x=\c\) has \(n\) pivots as well, so \(\U\x=\c\) is nonsingular by Theorem 3.1.21. Finally, by Theorem 3.1.29 \(\A\x=\b\) is nonsingular and hence has a solution, so by Theorem 3.10.1 \(\A\) is invertible.

Theorem 3.10.4. Invertibility and the zero row vector.

\(\A\in\R^{n\times n}\) is invertible if and only if the zero vector \((0,0,\ldots,0)\) is not a nontrivial linear combination of the rows of \(\A.\)

Proof.

\(\left(\Rightarrow\right):\) Assume that \(\A\) is invertible so by Theorem 2.10.34 \(\A^T\) is invertible. By Theorem 3.10.3 \(\A^T\x=\vec{0}\) can only have the solution \(\x=\vec{0}.\) Transposing both sides of \(\A^T\x=\vec{0}\) yields \(\vec{0}^T=\x^T\A,\) whose only solution is \(\x^T=\vec{0}^T.\) This is precisely the statement that the zero vector \((0,0,\ldots,0)\) is not a nontrivial linear combination of the rows of \(\A.\)

\(\left(\Leftarrow\right):\) Assume that \(\A\) is not invertible so by Theorem 2.10.34 \(\A^T\) is not invertible. By Theorem 3.10.3 \(\A^T\x=\vec{0}\) must have a nontrivial solution \(\x\ne\vec{0}.\) Transposing both sides of \(\A^T\x=\vec{0}\) yields \(\vec{0}^T=\x^T\A,\) which has nontrivial solution \(\x^T\ne\vec{0}^T.\) This is precisely the statement that the zero vector \((0,0,\ldots,0)\) is a nontrivial linear combination of the rows of \(\A.\)

Definition 3.10.5. Row-equivalence.

A matrix \(\A\) is row-equivalent to a matrix \(\B\) if there exists a finite sequence of elemetary matrices \(\E_1,\,\E_2,\,...,\E_k\) for which \(\E_k\cdots\E_2\E_1\A=\B.\)

Theorem 3.10.6. Row-equivalence is an equivalence relation.

Let \(\A,\B,\C\in\R^{n\times n}.\) Then 1) \(\A\) is row-equivalent to itself, 2) if \(\A\) is row-equivalent to \(\B,\) then \(\B\) is row-equivalent to \(\A,\) and 3) if \(\A\) is row-equivalent to \(\B\) and \(\B\) is row-equivalent to \(\C,\) then \(\A\) is row-equivalent to \(\C.\)

Proof.

Let \(\A,\B,\C\in\R^{n\times n}.\) Since \(\I\) is an elementary matrix and \(\I\A=\A,\) \(\A\) is row-equivalent to itself.

Suppose \(\A\) is row-equivalent to \(\B,\) and by Definition 3.10.5 fix \(\E_1,\,\E_2,\,...,\E_k\) for which \(\E_k\cdots\E_2\E_1\A=\B.\) By Corollary 2.10.28 we have \(\A=\E_1^{-1}\E_2^{-1}\cdots\E_k^{-1}\B,\) and by Theorem 3.7.7 each of the \(\E_i^{-1}\) are elementary matrices. So by Definition 3.10.5 \(\B\) is row-equivalent to \(\A.\)

Now suppose \(\A\) is row-equivalent to \(\B\) and \(\B\) is row-equivalent to \(\C,\) and fix \(\E_1,\,\E_2,\,...,\E_k\) for which \(\E_k\cdots\E_2\E_1\A=\B\) and \(\E'_1,\,\E'_2,\,...,\E'_k\) for which \(\E'_k\cdots\E'_2\E'_1\B=\C.\) Then

\begin{equation*} \C=\E'_k\cdots\E'_2\E'_1\B=\E'_k\cdots\E'_2\E'_1\E_k\cdots\E_2\E_1\A \end{equation*}

so by Definition 3.10.5 \(\A\) is row-equivalent to \(\C.\)

Theorem 3.10.7. When it exists, \(\A^{-1}\) is a product of elementary matrices.

Let \(\A\in\R^{n\times n}\) be invertible. Then there exist elementary matrices \(\E_1,\,\E_2,\,..., \E_k\) for which we have \(\E_k\cdots\E_2\E_1\A=\I.\) That is,

\begin{equation*} \A^{-1}=\E_k\cdots\E_2\E_1\,. \end{equation*}

Proof.

Let \(\A\in\R^{n\times n}.\) By Theorem 3.7.15 let \(\E_1,\,\E_2,\,\ldots,\E_k\) be elementary matrices for which \(\E_k\cdots\E_2\E_1\A=\I.\) Then by Theorem 2.10.20, \(\A\E_k\cdots\E_2\E_1=\I.\) Now by Definition 2.10.21 we have \(\A^{-1}=\E_k\cdots\E_2\E_1.\)

Theorem 3.10.8. Invertibility and row-equivalence of \(\A\) to \(\I\).

\(\A\in\R^{n\times n}\) is invertible if and only if \(\A\) is row-equivalent to \(\I.\)

Proof.

\(\left(\Rightarrow\right):\) Assume that \(\A\) is invertible and by Theorem 3.7.15 let \(\E_1,\,\E_2,\,\ldots,\E_k\) be elementary matrices for which \(\E_k\cdots\E_2\E_1\A=\I.\) Since the \(\E_i\) represent elementary row operations, by Definition 3.10.5, \(\,\A\) is row-equivalent to \(\I.\)

\(\left(\Leftarrow\right):\) Assume that \(\A\) is row-equivalent to \(\I,\) and by Definition 3.10.5 fix a sequence of elemetary matrices \(\E_1,\,\E_2,\,...,\E_k\) for which \(\E_k\cdots\E_2\E_1\A=\I.\) By Definition 2.10.21, \(\A^{-1}=\E_k\cdots\E_2\E_1.\)

Remark 3.10.9. Computing the inverse or showing that it does not exist - \(\boldsymbol{3\times3}\) or larger matrices.

Theorem 3.10.8, Theorem 3.10.7 and Theorem 3.10.4 give us a nice way 1) to compute the inverse for a nonsingular \(\A\) or 2) to determine that \(\A\) is singular.

If we keep track of the row operations, in the correct order, which transform \(\A\) into the identity, we may use those row operations in order to produce \(\A^{-1}\) by augmenting \(\A\) by the entire identity matrix and performing Gauss-Jordan elimination on \(\left(\A|\I\right).\)

If \(\A\) is nonsingular, the process is:

\begin{align*} \left(\A|\I\right)\amp\longrightarrow\left(\E_1\A\,|\,\E_1\right)\\ \amp\longrightarrow\left(\E_2\E_1\A\,|\,\E_2\E_1\right)\\ \amp\longrightarrow\left(\E_3\E_2\E_1\A\,|\,\E_3\E_2\E_1\right)\\ \amp\qquad\qquad\qquad\vdots\\ \amp\longrightarrow\left(\E_k\cdots\E_2\E_1\A\,|\,\E_k\cdots\E_2\E_1\right)\\ \amp\,\,\,\,=\,\,\,\left(\I\,|\,\A^{-1}\right) \end{align*}

which exhibits \(\A^{-1}\) to the right of the vertical separator.

If after any sequence of \(p\) row operations the augmented system \(\left(\E_p\cdots\E_2\E_1\A\,|\,\E_p\cdots\E_2\E_1\right)\) exhibits a zero row on the left of the vertical separator, then the zero (row-) vector is a linear combination of the rows of \(\A,\) and by Theorem 3.10.4 we conclude that \(\A\) has no inverse.

Example 3.10.10. Computing \(\boldsymbol{\A^{-1}}\).

Determine whether \(\A=\left(\begin{array}{rrr}1\amp -3\amp 11\\2\amp -5\amp 19\\4\amp -11\amp 41 \end{array} \right)\) is invertible; if so find the inverse; if not explain why.

Solution:

\begin{equation*} \begin{array}{llc} \left(\begin{array}{rrr|rrr}1\amp -3\amp 11\amp 1\amp 0\amp 0\\2\amp -5\amp 19\amp 0\amp 1\amp 0\\0\amp -2\amp 7\amp 0\amp 0\amp 1 \end{array}\right) \!\!\!\!\!\amp\xrightarrow{-2R_1+R_2\rightarrow R_2}\amp\!\!\!\!\!\!\!\! \left(\begin{array}{rrr|rrr}1\amp -3\amp 11\amp 1\amp 0\amp 0\\0\amp 1\amp -3\amp -2\amp 1\amp 0\\0\amp -2\amp 7\amp 0\amp 0\amp 1 \end{array}\right)\\ \amp \xrightarrow{2R_2+R_3\rightarrow R_3}\amp\!\!\!\!\!\!\!\! \left(\begin{array}{rrr|rrr}1\amp -3\amp 11\amp 1\amp 0\amp 0\\0\amp 1\amp -3\amp -2\amp 1\amp 0\\0\amp 0\amp 1\amp -4\amp 2\amp 1 \end{array}\right)\\ \amp \underset{-11R_3+R_1\rightarrow R_1}{\xrightarrow{3R_3+R_2\rightarrow R_2}}\amp\!\!\!\! \left(\begin{array}{rrr|rrr}1\!\amp\!-3\!\amp\!0\!\amp\!45\!\amp\!-22\!\amp\!-11\\0\!\amp\!1\!\amp\!0\!\amp\!-14\!\amp\!7\!\amp\!3\\0\!\amp\!0\!\amp\!1\!\amp\!-4\!\amp\!2\!\amp\!1\end{array}\right)\\ \amp \xrightarrow{3R_2+R_1\rightarrow R_1}\amp\!\!\!\! \left(\begin{array}{rrr|rrr}1\amp 0\amp 0\amp 3\amp -1\amp -2\\0\amp 1\amp 0\amp -14\amp 7\amp 3\\0\amp 0\amp 1\amp -4\amp 2\amp 1 \end{array}\right).\end{array} \end{equation*}

Thus by Theorem 3.10.7, \(\left(\begin{array}{rrr}1\amp -3\amp 11\\2\amp -5\amp 19\\0\amp -2\amp 7 \end{array} \right)^{-1}\,\,=\,\,\left(\begin{array}{rrr}3\amp -1\amp -2\\-14\amp 7\amp 3\\-4\amp 2\amp 1 \end{array} \right).\)

Remark 3.10.11. Orthogonality and \(\boldsymbol{\A^{-1}}\).

In Example 3.10.10, since

\begin{equation*} \left(\begin{array}{rrr}1\amp -3\amp 11\\2\amp -5\amp 19\\0\amp -2\amp 7 \end{array} \right)\left(\begin{array}{rrr}3\amp -1\amp -2\\-14\amp 7\amp 3\\-4\amp 2\amp 1 \end{array} \right)=\left(\begin{array}{rrr}1\amp 0\amp 0\\0\amp 1\amp 0\\0\amp 0\amp 1\end{array}\right) \end{equation*}

and

\begin{equation*} \left(\begin{array}{rrr}3\amp -1\amp -2\\-14\amp 7\amp 3\\-4\amp 2\amp 1 \end{array} \right)\left(\begin{array}{rrr}1\amp -3\amp 11\\2\amp -5\amp 19\\0\amp -2\amp 7 \end{array} \right)=\left(\begin{array}{rrr}1\amp 0\amp 0\\0\amp 1\amp 0\\0\amp 0\amp 1\end{array}\right) \end{equation*}

we observe an example of the following general principle: the columns and rows of \(\A^{-1}\) are orthogonal to different rows and columns, respectively, of \(\A.\) That is, for \(i\ne j,\) we have

\begin{equation*} \A_{i*}\perp \A^{-1}_{*j}\,\,\text{ and }\,\,\A^{-1}_{i*}\perp \A_{*j}. \end{equation*}

Example 3.10.12. Showing that \(\boldsymbol{\A^{-1}}\) does not exist.

Determine whether \(\A=\left(\begin{array}{rrr}1\amp -3\amp 11\\2\amp -5\amp 19\\4\amp -11\amp 41 \end{array} \right)\) is invertible; if so find the inverse; if not explain why.

Solution: We have

\begin{equation*} \begin{array}{llc} \left(\begin{array}{rrr|rrr}1\amp \!-3\amp 11\amp 1\amp 0\amp 0\\2\amp \!-5\amp 19\amp 0\amp 1\amp 0\\4\amp \!-11\amp 41\amp 0\amp 0\amp 1\end{array}\right) \!\!\!\!\!\amp\xrightarrow{-2R_1+R_2\rightarrow R_2}\amp\!\!\!\!\! \left(\begin{array}{rrr|rrr}1\amp \!-3\amp 11\amp 1\amp 0\amp 0\\0\amp \!1\amp -3\amp -2\amp 1\amp 0\\4\amp \!-11\amp 41\amp 0\amp 0\amp 1\end{array}\right)\\ \amp \xrightarrow{-4R_1+R_3\rightarrow R_3}\amp\!\!\!\!\! \left(\begin{array}{rrr|rrr}1\amp-3\amp 11\amp 1\amp 0\amp 0\\0\amp 1\amp -3\amp -2\amp 1\amp 0\\0\amp 1\amp -3\amp -4\amp 0\amp 1\end{array}\right)\\ \amp \xrightarrow{-R_2+R_3\rightarrow R_3}\amp\!\!\!\! \left(\begin{array}{rrr|rrr}1\amp -3\amp 0\amp 1\amp 0\amp 0\\0\amp 1\amp 0\amp -2\amp 1\amp 0\\0\amp 0\amp 0\amp -2\amp -1\amp 1\end{array}\right)\end{array} \end{equation*}

which shows that \(\vec{0}\) is a nontrivial linear combination of the rows of \(\A\) so by Theorem 3.10.4 \(\A\) is not invertible.

Theorem 3.10.13. Invertibility and uniqueness of solutions to \(\A\x=\b\).

\(\A\in\R^{n\times n}\) is invertible if and only if given any \(\b,\) if \(\A\x=\b\) has a solution, that solution is unique.

Proof.

\(\left(\Rightarrow\right):\) Assume that \(\A\) is invertible. Then by Theorem 2.10.25 the unique solution to \(\A\x=\b\) is \(\x=\A^{-1}\b.\)

\(\left(\Leftarrow\right):\) Assume that \(\A\) is not invertible. Then by Theorem 3.10.3 \(\A\x=\vec{0}\) does not have a unique solution, so the statement “given any \(\b,\) if \(\A\x=\b\) has a solution that solution is unique” is false.

Theorem 3.10.14. Invertibility and the zero column vector.

\(\A\in\R^{n\times n}\) is invertible if and only if the zero vector \((0,0,\ldots,0)^T\) is not a nontrivial linear combination of the columns of \(\A.\)

Proof.

\(\left(\Rightarrow\right):\) Assume that \(\A\) is invertible so by Theorem 3.10.3 the unique solution to \(\A\x=\vec{0}\) is \(\x=\vec{0}.\) This is precisely the statement that the zero vector \((0,0,\ldots,0)^T\) is not a nontrivial linear combination of the columns of \(\A.\)

\(\left(\Leftarrow\right):\) Assume that \(\A\) is not invertible so by Theorem 3.10.3 there is a nontrivial solution \(\x\ne\vec{0}\) to \(\A\x=\vec{0}\) is \(\x=\vec{0}.\) This is precisely the statement that the zero vector \((0,0,\ldots,0)^T\) can be expressed as a nontrivial linear combination of the columns of \(\A.\)

Theorem 3.10.15. Invertibility and linear combinations of the rows of \(\A\).

\(\A\in\R^{n\times n}\) is invertible if and only if no row of \(\A\) is a nontrivial linear combination of the other rows of \(\A.\)

Proof.

\(\left(\Rightarrow\right):\) We prove the contrapositive. Assume that \(\A_{i\ast}\) is a linear combination of the other rows of \(\A\) with

\begin{equation*} \A_{i\ast}=\sum_{k=1,k\ne i}^n c_k\A_{k\ast}. \end{equation*}

Then

\begin{equation*} \E_{(-c_1)i1},\,\E_{(-c_2)i2},\,\ldots,\,\E_{(-c_{i-1})i(i-1)},\,\E_{(-c_{i+1})i(i+1)},\,\ldots,\,\E_{(-c_n)in} \end{equation*}

are elementary matrices for which

\begin{equation*} \left(\E_{(-c_n)in}\cdots\E_{(-c_{i+1})i(i+1)}\E_{(-c_{i-1})i(i-1)}\cdots\E_{(-c_2)i2}\E_{(-c_1)i1}\right)\A_{i\ast}=\vec{0}. \end{equation*}

Now by Theorem 3.10.4 \(\,\A\) is not invertible.

\(\left(\Leftarrow\right):\) We again prove the contrapositive. Assume that \(\A\) is not invertible, and by Theorem 3.10.4 fix a nontrivial linear combination \(\sum_{i=1}^nc_i\A_{i\ast}\) which equals \(\vec{0}.\) Fix \(i'\) between \(1\) and \(n\) inclusive for which \(c_{i'}\ne0.\) Then

\begin{equation*} \A_{i'\ast}=-\frac{1}{c_{i'}}\sum_{i=1,i\ne i'}^nc_i\A_{i\ast} \end{equation*}

which exhibits the row \(\A_{i'\ast}\) as a linear combination of the other rows of \(\A.\)

Corollary 3.10.16. Invertibility and the columns of \(\A\).

\(\A\in\R^{n\times n}\) is invertible if and only if no column of \(\A\) is a nontrivial linear combination of the other columns of \(\A.\)

Proof.

By Theorem 2.10.34 we have that \(\A\in\R^{n\times n}\) is invertible if and only if \(\A^T\) is invertible, which by Theorem 3.10.15 holds if and only if no row of \(\A^T\) is a nontrivial linear combination of the other rows of \(\A^T,\) exactly the statement that no column of \(\A\) is a nontrivial linear combination of the other columns of \(\A.\)

Theorem 3.10.17. Invertibility and the row-echelon forms of \(\A\).

\(\A\in\R^{n\times n}\) is invertible if and only if every row-echelon form \(\U\) of \(\A\) is invertible.

Proof.

\(\left(\Rightarrow\right):\) Let \(\A\in\R^{n\times n}\) be invertible, let \(\U\in\R^{n\times n}\) be a row-echelon form of \(\A,\) and fix elementary matrices \(\E_1,\,\E_2,\,\ldots,\E_k\) for which \(\E_k\cdots\E_2\E_1\A=\U;\) note that by Theorem 3.7.7 each \(\E_i\) is invertible. Then the expression on the LHS of this equation \(\E_k\cdots\E_2\E_1\A\) is invertible by Corollary 2.10.28 so the expression \(\U\) on the RHS must be invertible as well.

\(\left(\Leftarrow\right):\) Let \(\A\in\R^{n\times n}\) and let \(\U\in\R^{n\times n}\) be a row-echelon form of \(\A,\) suppose \(\U\) is invertible, and fix elementary matrices \(\E_1,\,\E_2,\,\ldots,\E_k\) for which \(\E_k\cdots\E_2\E_1\A=\U.\) Since each \(\E_i\) is invertible, we have \(\A=\E_1^{-1}\E_2^{-1}\cdots\E_k^{-1}\U.\) Now Corollary 2.10.28 applied to \(\E_1^{-1}\E_2^{-1}\cdots\E_k^{-1}\U\) yields that this expression is invertible, so the expression \(\A\) on the LHS must be invertible as well.

Theorem 3.10.18. Invertibility of \(\U\) and pivots.

An upper-triangular \(\U\in\R^{n\times n}\) is invertible if and only if \(\U\) exhibits a full set of pivots.

Proof.

\(\left(\Rightarrow\right):\) Assume that \(\U\) is invertible so that by Corollary 3.10.2 the system \(\U\x=\vec{0}\) is nonsingular as well. By Theorem 3.1.21 \(\,\U\) has \(n\) pivots.

\(\left(\Leftarrow\right):\) Assume that \(\U\) has \(n\) pivots, so that the system \(\U\x=\vec{0}\) has \(n\) pivots. Now by Corollary 3.10.2 \(\U\) is invertible.

Theorem 3.10.19. Invertibility and \(\A\) and of \(\U\).

\(\A\in\R^{n\times n}\) is invertible if and only if every row-echelon form \(\U\) of \(\A\) has a full set of pivots.

Proof.

\(\left(\Rightarrow\right):\) Assume that \(\A\) is invertible and let \(\U\in\R^{n\times n}\) be a row-echelon form of \(\A.\) By Theorem 3.10.17, \(\U\) is invertible and by Theorem 3.10.18 \(\,\U\) has a full set of pivots.

\(\left(\Leftarrow\right):\) Let \(\A\in\R^{n\times n},\) let \(\U\in\R^{n\times n}\) be a row-echelon form of \(\A\) and suppose \(\U\) has a full set of pivots. Then \(\U\) is invertible by Theorem 3.10.18 and hence \(\A\) is invertible by Theorem 3.10.17.

Corollary 3.10.20. Invertibility and the rows of the row-echelon forms of \(\A\).

\(\A\in\R^{n\times n}\) is invertible if and only if every row-echelon form \(\U\) of \(\A\) has no zero rows.

Proof.

Let \(\A\in\R^{n\times n}\) and let \(\U\) be a row-echelon form of \(\A.\) Since any \(\U\in\R^{n\times n}\) has no zero rows if and only if \(\U\) has a full set of pivots, the Theorem holds by Theorem 3.10.19.

Corollary 3.10.21. Invertibility and the RREF \(\J\).

\(\A\in\R^{n\times n}\) is invertible if and only if the reduced row-echelon form \(\J\) of \(\A\) equals \(\I.\)

Proof.

Let \(\A\in\R^{n\times n}\) and by Theorem 3.7.15 let \(\J\) be the unique RREF of \(\A.\) By Theorem 3.7.15, \(\,\A\) is invertible if and only if \(\J=\I.\)

Theorem 3.10.22. The inverse of a permutation matrix.

Let \(\P\) be an \(n\times n\) permutation matrix. Then \(\P^{-1}=\P^T.\)

Proof.

Supppose \(\P\) is an \(n\times n\) permutation matrix. Then

\begin{equation*} \left(\P\P^T\right)_{ij}=\sum_{k=1}^nP_{ik}P_{kj}^T=\sum_{k=1}^nP_{ik}P_{jk} \end{equation*}

which by Theorem 3.7.12 equals \(1\) if \(i=j\) and \(0\) otherwise. This shows that \(\P\P^T=\I\) so by Definition 2.10.21 we have that \(\P^{-1}=\P^T.\)

Remark 3.10.23. Counterintuitive behavior of matrices.

When \(\boldsymbol{\A^{-1}}\) does not exist, zero divisors do exist. Note that \(\A=\left(\begin{array}{rr} 2\amp 3\\4\amp 6 \end{array} \right)\) is not invertible by Item 13 since any associated \(\U\) will exhibit a zero row. We have \(\left(\begin{array}{rr} 2\amp 3\\4\amp 6 \end{array} \right)\left(\begin{array}{rr}-3\amp 9\\2\amp -6 \end{array}\right)=\begin{pmatrix}0\amp 0\\0\amp 0 \end{pmatrix},\) which implies that there are nonzero factors of the zero matrix, a situation which has no analogue in the set of real numbers!

We will see how to generate zero divisors - non-\(\boldsymbol{0_{n\times n}}\) factors of \(\boldsymbol{0_{n\times n}}\) in Section 6.4.

There are a lot more “square roots” of \(\I\) than there are of \(\boldsymbol{1}:\) Of course \(\left(\pm\I\right)^2=\I\) so \(\I\) is its own inverse, but there are other matrices which are their own inverses (for example any row swap matrix \(\E_{(ij)}\)). Here are some other examples in \(\R^{2 \times 2}\text{:}\)

\(\left(\begin{array}{rr}1\amp 0\\0\amp -1 \end{array} \right),\,\left(\begin{array}{rr}-1\amp 0\\0\amp 1 \end{array} \right),\, \left(\begin{array}{rr}-1\amp 0\\0\amp -1 \end{array} \right),\,\left(\begin{array}{rr}0\amp 1\\1\amp 0 \end{array} \right),\, \left(\begin{array}{rr} 0\amp -1\\-1\amp 0 \end{array} \right)\) have exactly two zeros
\(\left(\begin{array}{rr}2\amp -3\\1\amp -2 \end{array} \right)\) and many others have no zeros
An example of such a matrix which has exactly one zero is \(\left(\begin{array}{rr}1\amp 1\\0\amp -1 \end{array} \right)\)
No such matrices in \(\R^{2 \times 2}\) have exactly three zeros.

Remark 3.10.24. For \(\A\x=\b\) to have a solution, any relation between the rows of \(\A\) must be present in the rows of \(\b\).

When \(\A\) is singular, by Theorem 3.10.25 Part 9 at least one row of \(\A\) is a linear combination of the other rows of \(\A.\) In this case, the only \(\b\)’s for which \(\A\x=\b\) has a solution are those whose corresponding components satisfy the same linear combination relations as the zero-rows of the row-echelon form of \(\A:\) If \(\A\) satisfies for example \(R_2=R_1-3R_3,\) then the only \(\b\)’s for which \(\A\x=\b\) has a solution are those \(\b\)’s for which \(b_2=b_1-3b_3.\)

Finding \(\A^{-1}\) to solve \(\A\x=\b\) is wasteful. It is much easier to simply augment and eliminate, then back-substitute. It is, as it ought to be, less work to find a particular set of coefficients for a linear combination of the columns of \(\A,\) than to produce an object which will generate such coefficients for every \(\,\b.\)

Theorem 3.10.1 - Theorem 3.10.14 and Theorem 3.10.8 - Corollary 3.10.21 are just some of the many conditions equivalent to the invertibility of \(\A\in\R^{n\times n}.\) We record the above equivalent properties and the corollaries with \(\A^T\) in place of \(\A\) in Theorem 3.10.25. More equivalent conditions will follow as we progress through the course material; we list the complete set of conditions equivalent to invertibility of \(\A\in\R^{n\times n}\) - “The Big Theorem” - in Section A.5 of Appendix A.

Theorem 3.10.25. Matrix Inverse Equivalence - The Big Theorem Part 1.

Let \(\A\in\R^{n\times n}.\) The following statements are equivalent (TFAE):

\(\A\) is invertible.
\(\A^T\) is invertible. (Theorem 2.10.34)
\(\A\x=\b\) has a solution for every \(\b\in\R^n.\) (Theorem 3.10.1)
For a given \(\b\in\R^n,\) if \(\A\x=\b\) has a solution, that solution is unique. (Theorem 3.10.13)
\(\A\x=\vec{0}\) has the unique solution \(\x=\vec{0}.\) (Theorem 3.10.3)
The zero vector \((0,0,\ldots,0)\) is not a nontrivial linear combination of the rows of \(\A.\) (Theorem 3.10.4)
The zero vector \((0,0,\ldots,0)^T\) is not a nontrivial linear combination of the columns of \(\A.\) (Theorem 3.10.14)
\(\A\) is row-equivalent to \(\I.\) (Theorem 3.10.8)
No row of \(\A\) is a linear combination of the other rows of \(\A.\) (Theorem 3.10.15)
No column of \(\A\) is a linear combination of the other columns of \(\A.\) (Corollary 3.10.16)
Every row-echelon form \(\U\) of \(\A\) is invertible. (Theorem 3.10.17)
Every row-echelon form \(\U\) of \(\A\) shows a full set of pivots. (Theorem 3.10.19)
Every row-echelon form \(\U\) of \(\A\) has no zero rows. (Corollary 3.10.20)
The reduced row-echelon form \(\J\) of \(\A\) is the identity. (Corollary 3.10.21)

Further, since \(\A\) invertible \(\Longleftrightarrow\,\A^T\) invertible, substituting \(\A^T\) for \(\A\) in each of Item 3, Item 4, Item 5, Item 8, Item 13, Item 12 and Item 14 yields additional propositions equivalent to “\(\A\) is invertible.”

An aside about multiple equivalences: Theorem 3.10.25 exhibits a huge number of equivalences. (How many?) How would we go about proving that each of the parts of Theorem 3.10.25 are equivalent to all other parts? It’s certainly a big task, for which we may minimize our efforts if we proceed logically. Proving that each of the propositions in Theorem 3.10.25 is equivalent to each of the other propositions in Theorem 3.10.25 is the least efficient way to do this. (Based on how many equivalences there are, about how long do you think this would take?)

Fortunately there are a huge number of far more efficient approaches which we will call schemes. As long as any scheme exhibits an implication from Proposition \(i\) to Proposition \(j\) and an implication from Proposition \(j\) to Proposition \(i\) for every \(i,j\) the scheme is valid.

To show that all of the results in Theorem 3.10.25 are equivalent, we could use any of the three schemes below:

Prove Item 1\(\Longleftrightarrow\)Item 2\(\Longleftrightarrow\)Item 3\(\Longleftrightarrow\cdots\Longleftrightarrow\)Item 14, or
prove Item 1\(\Longrightarrow\)Item 2\(\Longrightarrow\)Item 3\(\Longrightarrow\cdots\Longrightarrow\)Item 14\(\Longrightarrow\)Item 1, or
prove Item 1\(\Longleftrightarrow\)Item 2, Item 1\(\Longleftrightarrow\)Item 3, Item 1\(\Longleftrightarrow\)Item 4,\(\,\ldots\,\text{,}\)Item 1\(\Longleftrightarrow\)Item 14.

These three are not the only choices; we could use any of a huge number of other efficient schemes. That’s the nice thing about all these equivalences; any of them may stand in for the original statement “\(\A\) is invertible.”

If we are trying to prove Theorem 3.10.25 all at once and each of the successive implications are not too hard to prove, then the second scheme above (or its reversed version) is the most efficient approach.

If instead of proving Theorem 3.10.25 all at once we want to prove it one equivalence at a time, as is the case above where we present the equivalences one theorem at a time, the third approach is the best.

Prev Top Next