§ 16. The Rank of a Matrix and Matrix Inverses¶

Rank of a Matrix¶

Definition 16.1 : Rank of a Matrix

If \(A \in \mathrm{M}_{m \times n}(F)\), we define the rank of \(A\), denoted \(\operatorname{rank}(A)\), to be the rank of the linear transformation \(L_{A}: F^{n} \rightarrow F^{m}\).

Theorem 16.2 : Rank of invertible matrices are \(n\).

An \(n \times n\) matrix is invertible if and only if its rank is \(n\).

Proof

It follows from Fact 3 in Concept 11.2 and Corollary 11.8.

Theorem 16.3 : Rank of a matrix representation

Let \(T: V \rightarrow W\) be a linear transformation between finite-dimensional vector spaces, and let \(\beta\) and \(\gamma\) be ordered bases for \(V\) and \(W\), respectively. Then \(\operatorname{rank}(T)=\operatorname{rank}\left([T]_{\beta}^{\gamma}\right)\).

Proof

This is a restatement of Exercise 11.20.

Theorem 16.4 : Rank Is Invariant Under Multiplication by Invertible Matrices

Let \(A\) be an \(m \times n\) matrix. If \(P\) and \(Q\) are invertible \(m \times m\) and \(n \times n\) matrices, respectively, then

(a) \(\operatorname{rank}(A Q)=\operatorname{rank}(A)\),
(b) \(\operatorname{rank}(P A)=\operatorname{rank}(A)\), and therefore,
(c) \(\operatorname{rank}(P A Q)=\operatorname{rank}(A)\).

Proof

(a)
First observe that

\[ R\left(L_{A Q}\right)=R\left(L_{A} L_{Q}\right)=L_{A} L_{Q}\left(F^{n}\right)=L_{A}\left(L_{Q}\left(F^{n}\right)\right)=L_{A}\left(F^{n}\right)=R\left(L_{A}\right) \]

since \(L_{Q}\) is onto. Therefore

\[ \operatorname{rank}(A Q)=\operatorname{dim}\left(R\left(L_{A Q}\right)\right)=\operatorname{dim}\left(R\left(L_{A}\right)\right)=\operatorname{rank}(A). \]
(b)
Since \(P\) is invertible, the linear transformation \(L_{P}:F^{m}\to F^{m}\) is an isomorphism (with inverse \(L_{P^{-1}}\)). Hence, by Exercise 11.17(a), the image under \(L_{P}\) of any subspace of \(F^{m}\) is a subspace of \(F^{m}\), and by Exercise 11.17(b), \(L_{P}\) preserves dimension on subspaces.

Now observe that

\[ L_{PA}=L_{P}L_{A}, \]

so

\[ R(L_{PA})=R(L_{P}L_{A})=L_{P}\big(R(L_{A})\big). \]

Since \(R(L_{A})\) is a subspace of \(F^{m}\), Exercise 11.17(b) applied to the isomorphism \(L_{P}\) and the subspace \(R(L_{A})\) yields

\[ \operatorname{dim}\big(R(L_{A})\big)=\operatorname{dim}\Big(L_{P}\big(R(L_{A})\big)\Big)=\operatorname{dim}\big(R(L_{PA})\big). \]

Therefore,

\[ \operatorname{rank}(P A)=\operatorname{dim}\big(R(L_{PA})\big)=\operatorname{dim}\big(R(L_{A})\big)=\operatorname{rank}(A). \]
(c)
By part (a) applied to the matrix \(P A\),

\[ \operatorname{rank}(P A Q)=\operatorname{rank}(P A). \]

By part (b),

\[ \operatorname{rank}(P A)=\operatorname{rank}(A). \]

Hence

\[ \operatorname{rank}(P A Q)=\operatorname{rank}(A). \]

Corollary 16.5 : Elementary row and column operations preserve rank.

Elementary row and column operations on a matrix are rank-preserving.

Proof

If \(B\) is obtained from a matrix \(A\) by an elementary row operation, then there exists an elementary matrix \(E\) such that \(B=E A\). By Theorem 15.5, \(E\) is invertible, and hence \(\operatorname{rank}(B)=\operatorname{rank}(A)\) by Theorem 16.4. The proof that elementary column operations are rank-preserving is analogous.

Theorem 16.6 : Rank equals the maximum number of linearly independent columns.

The rank of any matrix equals the maximum number of its linearly independent columns; that is, the rank of a matrix is the dimension of the subspace generated by its columns.

Proof

For any \(A \in \mathrm{M}_{m \times n}(F)\),

\[ \operatorname{rank}(A)=\operatorname{rank}\left(L_{A}\right)=\operatorname{dim}\left(R\left(L_{A}\right)\right) . \]

Let \(\beta\) be the standard ordered basis for \(F^{n}\). Then \(\beta\) spans \(F^{n}\) and hence, by Theorem 2.2,

\[ R\left(L_{A}\right)=\operatorname{span}\left(L_{A}(\beta)\right)=\operatorname{span}\left(\left\{L_{A}\left(e_{1}\right), L_{A}\left(e_{2}\right), \ldots, L_{A}\left(e_{n}\right)\right\}\right) \]

But, for any \(j\), we have seen in Theorem 2.13(b) that \(L_{A}\left(e_{j}\right)=A e_{j}=a_{j}\), where \(a_{j}\) is the \(j\)th column of \(A\). Hence

\[ R\left(L_{A}\right)=\operatorname{span}\left(\left\{a_{1}, a_{2}, \ldots, a_{n}\right\}\right) \]

Thus

\[ \operatorname{rank}(A)=\operatorname{dim}\left(R\left(L_{A}\right)\right)=\operatorname{dim}\left(\operatorname{span}\left(\left\{a_{1}, a_{2}, \ldots, a_{n}\right\}\right)\right) \]

Using Elementary Operations to Compute Rank of a Matrix¶

Theorem 16.7 : Reduction to a simple form via elementary operations

Let \(A\) be an \(m \times n\) matrix of rank \(r\). Then \(r \leq m, r \leq n\), and, by means of a finite number of elementary row and column operations, \(A\) can be transformed into the matrix

\[ D=\left(\begin{array}{ll} I_{r} & O_{1} \\ O_{2} & O_{3} \end{array}\right) \]

where \(O_{1}, O_{2}\), and \(O_{3}\) are zero matrices. Thus \(D_{i i}=1\) for \(i \leq r\) and \(D_{i j}=0\) otherwise.

Proof

If \(A\) is the zero matrix, then every column of \(A\) is the zero vector, so the subspace generated by the columns of \(A\) is \(\{0\}\). Hence \(\operatorname{rank}(A)=0\) by Theorem 16.6. In this case, the conclusion follows with \(D=A\).

Now suppose that \(A \neq O\) and \(r=\operatorname{rank}(A)\); then \(r>0\). The proof is by mathematical induction on \(m\), the number of rows of \(A\).

Suppose that \(m=1\). By means of at most one type 1 column operation and at most one type 2 column operation, \(A\) can be transformed into a matrix with a 1 in the 1,1 position. By means of at most \(n-1\) type 3 column operations, this matrix can in turn be transformed into the matrix

\[ \left(\begin{array}{llll} 1 & 0 & \cdots & 0 \end{array}\right) . \]

Note that there is one linearly independent column in \(D\). So \(\operatorname{rank}(D)=\operatorname{rank}(A)=1\) by Corollary 16.5 and by Theorem 16.6. Thus the theorem is established for \(m=1\).

Next assume that the theorem holds for any matrix with at most \(m-1\) rows (for some \(m>1\)). We must prove that the theorem holds for any matrix with \(m\) rows.

Suppose that \(A\) is any \(m \times n\) matrix. If \(n=1\), we argue analogously as follows. Since \(A \neq O\), some entry \(A_{i1}\) is nonzero. By at most one type 1 row operation, move that nonzero entry to the 1,1 position. By at most one type 2 row operation, scale the first row so that the 1,1 entry becomes 1. By at most \(m-1\) type 3 row operations, eliminate all other entries in the first column. The resulting matrix has the form

\[ \left(\begin{array}{c} 1 \\ 0 \\ \vdots \\ 0 \end{array}\right), \]

which is exactly the desired form with \(r=1\).

We now suppose that \(n>1\). Since \(A \neq O, A_{i j} \neq 0\) for some \(i, j\). By means of at most one elementary row and at most one elementary column operation (each of type 1), we can move the nonzero entry to the 1,1 position (just as was done in Example 16.8). By means of at most one additional type 2 operation, we can assure a 1 in the 1,1 position. (Look at the second operation in Example 16.8.) By means of at most \(m-1\) type 3 row operations and at most \(n-1\) type 3 column operations, we can eliminate all nonzero entries in the first row and the first column with the exception of the 1 in the 1,1 position. (In Example 16.8, we used two row and three column operations to do this.)

Thus, with a finite number of elementary operations, \(A\) can be transformed into a matrix

\[ B=\left(\begin{array}{c|ccc} 1 & 0 & \cdots & 0 \\ \hline 0 & & & \\ \vdots & & B^{\prime} & \\ 0 & & & \end{array}\right) \]

where \(B^{\prime}\) is an \((m-1) \times(n-1)\) matrix. In Example 16.8, for instance,

\[ B^{\prime}=\left(\begin{array}{rrrr} 2 & 4 & 2 & 2 \\ -6 & -8 & -6 & 2 \\ -3 & -4 & -3 & 1 \end{array}\right) \]

We claim that \(\operatorname{rank}(B)=1+\operatorname{rank}\left(B^{\prime}\right)\). Indeed, write the columns of \(B\) as \(b_{1}, b_{2}, \ldots, b_{n}\). Then

\(b_{1}=e_{1}\), the first standard basis vector in \(F^{m}\), and
for each \(j \ge 2\), the first entry of \(b_{j}\) is \(0\), and the remaining \((m-1)\) entries of \(b_{j}\) are exactly the corresponding column of \(B^{\prime}\).

Let \(C(B)\) denote the subspace generated by the columns of \(B\), and similarly for \(C(B')\). Then

\[ C(B)=\operatorname{span}\left(\{e_{1}\}\cup\{(0,u):u\in C(B')\}\right), \]

where \((0,u)\) denotes the vector in \(F^{m}\) with first coordinate \(0\) and remaining coordinates given by \(u\in F^{m-1}\). Moreover, \(\operatorname{span}(\{e_{1}\})\cap\{(0,u):u\in C(B')\}=\{0\}\) because a vector of the form \((0,u)\) has first coordinate \(0\), while \(e_{1}\) has first coordinate \(1\). Hence

\[ \dim C(B)=1+\dim C(B')=1+\operatorname{rank}(B') \]

by Theorem 16.6. Therefore \(\operatorname{rank}(B)=1+\operatorname{rank}(B')\).

Since \(\operatorname{rank}(A)=\operatorname{rank}(B)=r\), it follows that \(\operatorname{rank}\left(B^{\prime}\right)=r-1\). Therefore \(r-1 \leq m-1\) and \(r-1 \leq n-1\) by the induction hypothesis. Hence \(r \leq m\) and \(r \leq n\).

Also by the induction hypothesis, \(B^{\prime}\) can be transformed by a finite number of elementary row and column operations into the \((m-1) \times(n-1)\) matrix \(D^{\prime}\) such that

\[ D^{\prime}=\left(\begin{array}{cc} I_{r-1} & O_{4} \\ O_{5} & O_{6} \end{array}\right) \]

where \(O_{4}, O_{5}\), and \(O_{6}\) are zero matrices. That is, \(D^{\prime}\) consists of all zeros except for its first \(r-1\) diagonal entries, which are ones. Let

\[ D=\left(\begin{array}{c|ccc} 1 & 0 & \cdots & 0 \\ \hline 0 & & & \\ \vdots & & D^{\prime} & \\ 0 & & & \end{array}\right) \]

We see that the theorem now follows once we show that \(D\) can be obtained from \(B\) by means of a finite number of elementary row and column operations. To do this, note that any elementary row operation on \(B^{\prime}\) can be performed on \(B\) by applying the same operation to rows \(2,3,\ldots,m\) of \(B\), leaving row 1 unchanged. Similarly, any elementary column operation on \(B^{\prime}\) can be performed on \(B\) by applying the same operation to columns \(2,3,\ldots,n\) of \(B\), leaving column 1 unchanged. Therefore, since \(B^{\prime}\) can be transformed into \(D^{\prime}\) by finitely many elementary row and column operations, \(B\) can be transformed into \(D\) by finitely many elementary row and column operations.

Thus, since \(A\) can be transformed into \(B\) and \(B\) can be transformed into \(D\), each by a finite number of elementary operations, \(A\) can be transformed into \(D\) by a finite number of elementary operations.

Finally, since \(D^{\prime}\) contains ones as its first \(r-1\) diagonal entries, \(D\) contains ones as its first \(r\) diagonal entries and zeros elsewhere. This establishes the theorem.

Example 16.8 : Example of applying elementary operations to reach simple form

Consider the matrix

\[ A=\left(\begin{array}{rrrrr} 0 & 2 & 4 & 2 & 2 \\ 4 & 4 & 4 & 8 & 0 \\ 8 & 2 & 0 & 10 & 2 \\ 6 & 3 & 2 & 9 & 1 \end{array}\right) \]

By means of a succession of elementary row and column operations, we can transform \(A\) into a matrix \(D\) as in Theorem 16.7. We list many of the intermediate matrices, but on several occasions a matrix is transformed from the preceding one by means of several elementary operations. The number above each arrow indicates how many elementary operations are involved. Try to identify the nature of each elementary operation (row or column and type) in the following matrix transformations.

\[ \begin{gathered} \left(\begin{array}{rrrrr} 0 & 2 & 4 & 2 & 2 \\ 4 & 4 & 4 & 8 & 0 \\ 8 & 2 & 0 & 10 & 2 \\ 6 & 3 & 2 & 9 & 1 \end{array}\right) \xrightarrow{1}\left(\begin{array}{rrrrr} 4 & 4 & 4 & 8 & 0 \\ 0 & 2 & 4 & 2 & 2 \\ 8 & 2 & 0 & 10 & 2 \\ 6 & 3 & 2 & 9 & 1 \end{array}\right) \xrightarrow{1}\left(\begin{array}{rrrrr} 1 & 1 & 1 & 2 & 0 \\ 0 & 2 & 4 & 2 & 2 \\ 8 & 2 & 0 & 10 & 2 \\ 6 & 3 & 2 & 9 & 1 \end{array}\right) \xrightarrow{2} \\ \left(\begin{array}{rrrrrr} 1 & 1 & 1 & 2 & 0 \\ 0 & 2 & 4 & 2 & 2 \\ 0 & -6 & -8 & -6 & 2 \\ 0 & -3 & -4 & -3 & 1 \end{array}\right) \xrightarrow{3}\left(\begin{array}{rrrr} 1 & 0 & 0 & 0 & 0 \\ 0 & 2 & 4 & 2 & 2 \\ 0 & -6 & -8 & -6 & 2 \\ 0 & -3 & -4 & -3 & 1 \end{array}\right) \xrightarrow{1} \\ \left(\begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 1 & 1 \\ 0 & -6 & -8 & -6 & 2 \\ 0 & -3 & -4 & -3 & 1 \end{array}\right) \xrightarrow{2}\left(\begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 1 & 1 \\ 0 & 0 & 4 & 0 & 8 \\ 0 & 0 & 2 & 0 & 4 \end{array}\right) \xrightarrow{3}\left(\begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 4 & 0 & 8 \\ 0 & 0 & 2 & 0 & 4 \end{array}\right) \xrightarrow{1} \\ \left(\begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 2 \\ 0 & 0 & 2 & 0 & 4 \end{array}\right) \xrightarrow{1}\left(\begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right) \xrightarrow{1}\left(\begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right)=D \end{gathered} \]

By Corollary 16.5, \(\operatorname{rank}(A)=\operatorname{rank}(D)\). Clearly, however, \(\operatorname{rank}(D)=3\) and \(\operatorname{rank}(A)=3\).

Corollary 16.9 : Simple form via invertible matrices

Let \(A\) be an \(m \times n\) matrix of rank \(r\). Then there exist invertible matrices \(B\) and \(C\) of sizes \(m \times m\) and \(n \times n\), respectively, such that \(D=B A C\), where

\[ D=\left(\begin{array}{ll} I_{r} & O_{1} \\ O_{2} & O_{3} \end{array}\right) \]

is the \(m \times n\) matrix in which \(O_{1}, O_{2}\), and \(O_{3}\) are zero matrices.

Proof

By Theorem 16.7, \(A\) can be transformed by means of a finite number of elementary row and column operations into the matrix \(D\). We can appeal to Theorem 15.3 each time we perform an elementary operation. Thus there exist elementary \(m \times m\) matrices \(E_{1}, E_{2}, \ldots, E_{p}\) and elementary \(n \times n\) matrices \(G_{1}, G_{2}, \ldots, G_{q}\) such that

\[ D=E_{p} E_{p-1} \cdots E_{2} E_{1} A G_{1} G_{2} \cdots G_{q} \]

By Theorem 15.5, each \(E_{j}\) and \(G_{j}\) is invertible. Let \(B=E_{p} E_{p-1} \cdots E_{1}\) and \(C=G_{1} G_{2} \cdots G_{q}\). Then \(B\) and \(C\) are invertible by Exercise 11.4, and \(D=B A C\).

Corollary 16.10 : Row rank equals column rank.

Let \(A\) be an \(m \times n\) matrix. Then

(a) \(\operatorname{rank}\left(A^{t}\right)=\operatorname{rank}(A)\).
(b) The rank of any matrix equals the maximum number of its linearly independent rows; that is, the rank of a matrix is the dimension of the subspace generated by its rows.
(c) The rows and columns of any matrix generate subspaces of the same dimension, numerically equal to the rank of the matrix.

Proof

(a)
By Corollary 16.9, there exist invertible matrices \(B\) and \(C\) such that \(D=B A C\), where \(D\) satisfies the stated conditions of the corollary. Taking transposes, we have

\[ D^{t}=(B A C)^{t}=C^{t} A^{t} B^{t} \]

Since \(B\) and \(C\) are invertible, so are \(B^{t}\) and \(C^{t}\) by Exercise 11.5. Hence by Theorem 16.4,

\[ \operatorname{rank}\left(A^{t}\right)=\operatorname{rank}\left(C^{t} A^{t} B^{t}\right)=\operatorname{rank}\left(D^{t}\right) \]

Suppose that \(r=\operatorname{rank}(A)\). Then \(D^{t}\) is an \(n \times m\) matrix with the form of the matrix \(D\) in Corollary 16.9, and hence \(\operatorname{rank}\left(D^{t}\right)=r\) by Theorem 16.6. Thus

\[ \operatorname{rank}\left(A^{t}\right)=\operatorname{rank}\left(D^{t}\right)=r=\operatorname{rank}(A) \]

This establishes (a).
(b)
The row vectors of \(A\) are exactly the column vectors of \(A^{t}\). Hence the maximum number of linearly independent rows of \(A\) equals the maximum number of linearly independent columns of \(A^{t}\). By Theorem 16.6, this maximum equals \(\operatorname{rank}\left(A^{t}\right)\). By part (a), \(\operatorname{rank}\left(A^{t}\right)=\operatorname{rank}(A)\). Therefore the rank of \(A\) equals the maximum number of its linearly independent rows, and hence equals the dimension of the subspace generated by its rows.
(c)
By Theorem 16.6, the columns of \(A\) generate a subspace of dimension \(\operatorname{rank}(A)\). By part (b), the rows of \(A\) generate a subspace of dimension \(\operatorname{rank}(A)\). Hence the rows and columns of \(A\) generate subspaces of the same dimension, numerically equal to the rank of \(A\).

Corollary 16.11 : Invertible matrices are products of elementary matrices.

Every invertible matrix is a product of elementary matrices.

Proof

If \(A\) is an invertible \(n \times n\) matrix, then \(\operatorname{rank}(A)=n\). Hence the matrix \(D\) in Corollary 16.9 equals \(I_{n}\), and there exist invertible matrices \(B\) and \(C\) such that \(I_{n}=B A C\).

As in the proof of Corollary 16.9, note that \(B=E_{p} E_{p-1} \cdots E_{1}\) and \(C=G_{1} G_{2} \cdots G_{q}\), where the \(E_{i}\)'s and \(G_{i}\)'s are elementary matrices. Thus \(A=B^{-1} I_{n} C^{-1}=B^{-1} C^{-1}\), so that

\[ A=E_{1}^{-1} E_{2}^{-1} \cdots E_{p}^{-1} G_{q}^{-1} G_{q-1}^{-1} \cdots G_{1}^{-1} \]

The inverses of elementary matrices are elementary matrices, however, and hence \(A\) is the product of elementary matrices.

Theorem 16.12 : Rank inequalities for products

Theorem 16.12. Let \(T: V \rightarrow W\) and \(U: W \rightarrow Z\) be linear transformations on finite-dimensional vector spaces \(V, W\), and \(Z\), and let \(A\) and \(B\) be matrices such that the product \(A B\) is defined. Then

(a) \(\operatorname{rank}(U T) \leq \operatorname{rank}(U)\).
(b) \(\operatorname{rank}(UT) \leq \operatorname{rank}(T)\).
(c) \(\operatorname{rank}(A B) \leq \operatorname{rank}(A)\).
(d) \(\operatorname{rank}(A B) \leq \operatorname{rank}(B)\).

Proof

We prove these items in the order: (a), (c), (d), and (b).

(a)
Clearly, \(R(T) \subseteq W\). Hence

\[ R(U T)=U T(V)=U(T(V))=U(R(T)) \subseteq U(W)=R(U) \]

Thus

\[ \operatorname{rank}(U T)=\operatorname{dim}(R(U T)) \leq \operatorname{dim}(R(U))=\operatorname{rank}(U) \]
(c)
By (a),

\[ \operatorname{rank}(A B)=\operatorname{rank}\left(L_{A B}\right)=\operatorname{rank}\left(L_{A} L_{B}\right) \leq \operatorname{rank}\left(L_{A}\right)=\operatorname{rank}(A) \]
(d)
By (c) and Corollary 16.10,

\[ \operatorname{rank}(A B)=\operatorname{rank}\left((A B)^{t}\right)=\operatorname{rank}\left(B^{t} A^{t}\right) \leq \operatorname{rank}\left(B^{t}\right)=\operatorname{rank}(B) \]
(b)
Let \(\alpha, \beta\), and \(\gamma\) be ordered bases for \(V, W\), and \(Z\), respectively, and let \(A^{\prime}=[U]_{\beta}^{\gamma}\) and \(B^{\prime}=[T]_{\alpha}^{\beta}\). Then \(A^{\prime} B^{\prime}=[UT]_{\alpha}^{\gamma}\) by Theorem 2.11. Hence, by Theorem 16.3 and (d),

\[ \operatorname{rank}(UT)=\operatorname{rank}\left(A^{\prime} B^{\prime}\right) \leq \operatorname{rank}\left(B^{\prime}\right)=\operatorname{rank}(T) \]

Example 16.13 : Computing ranks in practice

It is important to be able to compute the rank of any matrix. We can use Corollary 16.5, Theorem 16.6, Theorem 16.7, and Corollary 16.10 to accomplish this goal.

The object is to perform elementary row and column operations on a matrix to "simplify" it (so that the transformed matrix has many zero entries) to the point where a simple observation enables us to determine how many linearly independent rows or columns the matrix has, and thus to determine its rank.

(a)
Let

\[ A=\left(\begin{array}{rrrr} 1 & 2 & 1 & 1 \\ 1 & 1 & -1 & 1 \end{array}\right) \]

Note that the first and second rows of \(A\) are linearly independent since one is not a multiple of the other. Thus \(\operatorname{rank}(A)=2\).
(b)
Let

\[ A=\left(\begin{array}{llll} 1 & 3 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 3 & 0 & 0 \end{array}\right) \]

In this case, there are several ways to proceed. Suppose that we begin with an elementary row operation to obtain a zero in the 2,1 position. Subtracting the first row from the second row, we obtain

\[ \left(\begin{array}{rrrr} 1 & 3 & 1 & 1 \\ 0 & -3 & 0 & 0 \\ 0 & 3 & 0 & 0 \end{array}\right) . \]

Now note that the third row is a multiple of the second row, and the first and second rows are linearly independent. Thus \(\operatorname{rank}(A)=2\).

As an alternative method, note that the first, third, and fourth columns of \(A\) are identical and that the first and second columns of \(A\) are linearly independent. Hence \(\operatorname{rank}(A)=2\).
(c)
Let

\[ A=\left(\begin{array}{rrrr} 1 & 2 & 3 & 1 \\ 2 & 1 & 1 & 1 \\ 1 & -1 & 1 & 0 \end{array}\right) \]

Using elementary row operations, we can transform \(A\) as follows:

\[ A \longrightarrow\left(\begin{array}{rrrr} 1 & 2 & 3 & 1 \\ 0 & -3 & -5 & -1 \\ 0 & -3 & -2 & -1 \end{array}\right) \longrightarrow\left(\begin{array}{rrrr} 1 & 2 & 3 & 1 \\ 0 & -3 & -5 & -1 \\ 0 & 0 & 3 & 0 \end{array}\right) . \]

It is clear that the last matrix has three linearly independent rows and hence has rank \(3\).

Computing the Inverse of a Matrix¶

Definition 16.14 : Augmented Matrix

Let \(A\) and \(B\) be \(m \times n\) and \(m \times p\) matrices, respectively. By the augmented matrix \((A \mid B)\), we mean the \(m \times(n+p)\) matrix \(\left(A \mid B\right)\), that is, the matrix whose first \(n\) columns are the columns of \(A\), and whose last \(p\) columns are the columns of \(B\).

Concept 16.15 : Method for computing inverse of a matrix by row reduction

Let \(A\) be an invertible \(n \times n\) matrix, and consider the \(n \times 2 n\) augmented matrix \(C=\left(A \mid I_{n}\right)\).

We claim that for any \(n \times n\) matrix \(M\) and any \(n \times n\) matrices \(A\) and \(B\),

\[ M(A\mid B)=(MA\mid MB). \]

Proof

Let \(A=\left[a_{1}\ \cdots\ a_{n}\right]\) and \(B=\left[b_{1}\ \cdots\ b_{n}\right]\), where \(a_{j}\) and \(b_{j}\) denote the \(j\)th columns of \(A\) and \(B\). Then, by definition of the augmented matrix,

\[ (A\mid B)=\left[a_{1}\ \cdots\ a_{n}\ b_{1}\ \cdots\ b_{n}\right]. \]

By Theorem 10.12, if \(X=\left[x_{1}\ \cdots\ x_{k}\right]\) is any matrix with columns \(x_{1},\ldots,x_{k}\), then

\[ MX=\left[Mx_{1}\ \cdots\ Mx_{k}\right]. \]

Applying this to \(X=(A\mid B)\) yields

\[ \begin{aligned} M(A\mid B) & =M\left[a_{1}\ \cdots\ a_{n}\ b_{1}\ \cdots\ b_{n}\right] \\ & =\left[Ma_{1}\ \cdots\ Ma_{n}\ Mb_{1}\ \cdots\ Mb_{n}\right]. \end{aligned} \]

The first \(n\) columns form \(MA=\left[Ma_{1}\ \cdots\ Ma_{n}\right]\), and the last \(n\) columns form \(MB=\left[Mb_{1}\ \cdots\ Mb_{n}\right]\). Therefore,

\[ M(A\mid B)=(MA\mid MB). \]

Applying the claim with \(B=I_{n}\) and \(M=A^{-1}\), we obtain

\[ A^{-1}C=A^{-1}(A\mid I_{n})=\left(A^{-1}A\mid A^{-1}I_{n}\right). \]

Since \(A^{-1}A=I_{n}\) and \(A^{-1}I_{n}=A^{-1}\), it follows that

\[ A^{-1}C=\left(I_{n}\mid A^{-1}\right). \]

By Corollary 16.11, \(A^{-1}\) is the product of elementary matrices, say \(A^{-1}=E_{p} E_{p-1} \cdots E_{1}\). Thus,

\[ E_{p} E_{p-1} \cdots E_{1}\left(A \mid I_{n}\right)=A^{-1} C=\left(I_{n} \mid A^{-1}\right) \]

Because multiplying a matrix on the left by an elementary matrix transforms the matrix by an elementary row operation (Theorem 15.3), we have the following result: If \(A\) is an invertible \(n \times n\) matrix, then it is possible to transform the matrix \(\left(A \mid I_{n}\right)\) into the matrix \(\left(I_{n} \mid A^{-1}\right)\) by means of a finite number of elementary row operations.

Conversely, suppose that \(A\) is invertible and that, for some \(n \times n\) matrix \(B\), the matrix \(\left(A \mid I_{n}\right)\) can be transformed into the matrix \(\left(I_{n} \mid B\right)\) by a finite number of elementary row operations. Let \(E_{1}, E_{2}, \ldots, E_{p}\) be the elementary matrices associated with these elementary row operations as in Theorem 15.3; then

\[ E_{p} E_{p-1} \cdots E_{1}\left(A \mid I_{n}\right)=\left(I_{n} \mid B\right) \]

Letting \(M=E_{p} E_{p-1} \cdots E_{1}\), we have from (2) that

\[ (M A \mid M)=M\left(A \mid I_{n}\right)=\left(I_{n} \mid B\right) \]

Hence \(M A=I_{n}\) and \(M=B\). It follows that \(M=A^{-1}\). So \(B=A^{-1}\). Thus we have the following result: If \(A\) is an invertible \(n \times n\) matrix, and the matrix \(\left(A \mid I_{n}\right)\) is transformed into a matrix of the form \(\left(I_{n} \mid B\right)\) by means of a finite number of elementary row operations, then \(B=A^{-1}\).

If, on the other hand, \(A\) is an \(n \times n\) matrix that is not invertible, then \(\operatorname{rank}(A)<n\). Hence any attempt to transform \(\left(A \mid I_{n}\right)\) into a matrix of the form \(\left(I_{n} \mid B\right)\) by means of elementary row operations must fail because otherwise \(A\) can be transformed into \(I_{n}\) using the same row operations. This is impossible, however, because elementary row operations preserve rank. In fact, \(A\) can be transformed into a matrix with a row containing only zero entries, yielding the following result: If \(A\) is an \(n \times n\) matrix that is not invertible, then any attempt to transform \(\left(A \mid I_{n}\right)\) into a matrix of the form \(\left(I_{n} \mid B\right)\) produces a row whose first \(n\) entries are zeros.

Example 16.16 : Example of computing inverse of a matrix

We determine whether the matrix

\[ A=\left(\begin{array}{lll} 0 & 2 & 4 \\ 2 & 4 & 2 \\ 3 & 3 & 1 \end{array}\right) \]

is invertible, and if it is, we compute its inverse. We attempt to use elementary row operations to transform

\[ (A \mid I)=\left(\begin{array}{lll|lll} 0 & 2 & 4 & 1 & 0 & 0 \\ 2 & 4 & 2 & 0 & 1 & 0 \\ 3 & 3 & 1 & 0 & 0 & 1 \end{array}\right) \]

into a matrix of the form \((I \mid B)\). One method for accomplishing this transformation is to change each column of \(A\) successively, beginning with the first column, into the corresponding column of \(I\). Since we need a nonzero entry in the 1,1 position, we begin by interchanging rows 1 and 2 . The result is

\[ \left(\begin{array}{lll|lll} 2 & 4 & 2 & 0 & 1 & 0 \\ 0 & 2 & 4 & 1 & 0 & 0 \\ 3 & 3 & 1 & 0 & 0 & 1 \end{array}\right) . \]

In order to place a 1 in the 1,1 position, we must multiply the first row by \(\frac{1}{2}\); this operation yields

\[ \left(\begin{array}{ccc|ccc} 1 & 2 & 1 & 0 & \frac{1}{2} & 0 \\ 0 & 2 & 4 & 1 & 0 & 0 \\ 3 & 3 & 1 & 0 & 0 & 1 \end{array}\right) . \]

We now complete work in the first column by adding -3 times row 1 to row 3 to obtain

\[ \left(\begin{array}{rrr|rrr} 1 & 2 & 1 & 0 & \frac{1}{2} & 0 \\ 0 & 2 & 4 & 1 & 0 & 0 \\ 0 & -3 & -2 & 0 & -\frac{3}{2} & 1 \end{array}\right) . \]

In order to change the second column of the preceding matrix into the second column of \(I\), we multiply row 2 by \(\frac{1}{2}\) to obtain a 1 in the 2,2 position. This operation produces

\[ \left(\begin{array}{rrr|rrr} 1 & 2 & 1 & 0 & \frac{1}{2} & 0 \\ 0 & 1 & 2 & \frac{1}{2} & 0 & 0 \\ 0 & -3 & -2 & 0 & -\frac{3}{2} & . \end{array}\right) . \]

We now complete our work on the second column by adding -2 times row 2 to row 1 and 3 times row 2 to row 3 . The result is

\[ \left(\begin{array}{rrr|rrr} 1 & 0 & -3 & -1 & \frac{1}{2} & 0 \\ 0 & 1 & 2 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 4 & \frac{3}{2} & -\frac{3}{2} & 1 \end{array}\right) \]

Only the third column remains to be changed. In order to place a 1 in the 3,3 position, we multiply row 3 by \(\frac{1}{4}\); this operation yields

\[ \left(\begin{array}{rrr|rrr} 1 & 0 & -3 & -1 & \frac{1}{2} & 0 \\ 0 & 1 & 2 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 1 & \frac{3}{8} & -\frac{3}{8} & \frac{1}{4} \end{array}\right) . \]

Adding appropriate multiples of row 3 to rows 1 and 2 completes the process and gives

\[ \left(\begin{array}{rrr|rrr} 1 & 0 & 0 & \frac{1}{8} & -\frac{5}{8} & \frac{3}{4} \\ 0 & 1 & 0 & -\frac{1}{4} & \frac{3}{4} & -\frac{1}{2} \\ 0 & 0 & 1 & \frac{3}{8} & -\frac{3}{8} & \frac{1}{4} \end{array}\right) . \]

Thus \(A\) is invertible, and

\[ A^{-1}=\left(\begin{array}{rrr} \frac{1}{8} & -\frac{5}{8} & \frac{3}{4} \\ -\frac{1}{4} & \frac{3}{4} & -\frac{1}{2} \\ \frac{3}{8} & -\frac{3}{8} & \frac{1}{4} \end{array}\right) . \]

Example 16.17 : Example of checking a noninvertible matrix

We determine whether the matrix

\[ A=\left(\begin{array}{rrr} 1 & 2 & 1 \\ 2 & 1 & -1 \\ 1 & 5 & 4 \end{array}\right) \]

is invertible, and if it is, we compute its inverse. Using a strategy similar to the one used in Example 16.16, we attempt to use elementary row operations to transform

\[ (A \mid I)=\left(\begin{array}{rrr|rrr} 1 & 2 & 1 & 1 & 0 & 0 \\ 2 & 1 & -1 & 0 & 1 & 0 \\ 1 & 5 & 4 & 0 & 0 & 1 \end{array}\right) \]

into a matrix of the form \((I \mid B)\). We first add -2 times row 1 to row 2 and -1 times row 1 to row 3 . We then add row 2 to row 3 . The result,

\[ \begin{aligned} \left(\begin{array}{rrr|rrr} 1 & 2 & 1 & 1 & 0 & 0 \\ 2 & 1 & -1 & 0 & 1 & 0 \\ 1 & 5 & 4 & 0 & 0 & 1 \end{array}\right) & \longrightarrow\left(\begin{array}{rrr|rrr} 1 & 2 & 1 & 1 & 0 & 0 \\ 0 & -3 & -3 & -2 & 1 & 0 \\ 0 & 3 & 3 & -1 & 0 & 1 \end{array}\right) \\ & \longrightarrow\left(\begin{array}{rrr|rrr} 1 & 2 & 1 & 1 & 0 & 0 \\ 0 & -3 & -3 & -2 & 1 & 0 \\ 0 & 0 & 0 & -3 & 1 & 1 \end{array}\right), \end{aligned} \]

is a matrix with a row whose first 3 entries are zeros. Therefore \(A\) is not invertible.

Exercise¶

Exercise 16.14

Let \(T, U: V \rightarrow W\) be linear transformations.

(a) Prove that \(R(T+U) \subseteq R(T)+R(U)\).
(b) Prove that if \(W\) is finite-dimensional, then \(\operatorname{rank}(T+U) \leq \operatorname{rank}(T)+\operatorname{rank}(U)\).
(c) Deduce from (b) that \(\operatorname{rank}(A+B) \leq \operatorname{rank}(A)+\operatorname{rank}(B)\) for any \(m \times n\) matrices \(A\) and \(B\).

Exercise 16.18

Let \(A\) be an \(m \times n\) matrix and \(B\) be an \(n \times p\) matrix. Prove that \(A B\) can be written as a sum of \(n\) matrices of rank at most one.

Exercise 16.19

Let \(A\) be an \(m \times n\) matrix with rank \(m\) and \(B\) be an \(n \times p\) matrix with rank \(n\). Determine the rank of \(A B\). Justify your answer.

Exercise 16.21

Let \(A\) be an \(m \times n\) matrix with rank \(m\). Prove that there exists an \(n \times m\) matrix \(B\) such that \(A B=I_{m}\).

Exercise 16.22

Let \(B\) be an \(n \times m\) matrix with rank \(m\). Prove that there exists an \(m \times n\) matrix \(A\) such that \(A B=I_{m}\).