The case where \(\Mtrx{A}\) is invertible

Consider first the situation where \(\Mtrx{A}\) is invertible. We want to show that the RREF of \(\Mtrx{A}\) is the identity matrix.

Each of the row operations which accomplish this reduction can be performed by multiplying \(\Mtrx{A}\) on the left with a row rescaling matrix \(D_u(s)\), an elementary matrix \(E_{ij}(t)\), or a row interchanging matrix \(R_{ij}\). If \(k\) such moves are required, we have

\(\Mtrx{R}_k\cdot \dots \cdot \Mtrx{R}_1\cdot \Mtrx{A}\ =\ \Mtrx{T}\)

where \(\Mtrx{T}\) is in RREF. If \(\Mtrx{T}\) is not the identity matrix, we will show that \(\Mtrx{A}\) could not have been invertible. – Indeed, if the RREF \(\Mtrx{T}\) of \(\Mtrx{A}\) is not \(\IdMtrx{n}\), then the last row of \(\Mtrx{T}\) will consist of \(0\)’s only. We can rewrite the above identity as:

\[\Mtrx{R}_k\cdot \dots \cdot \Mtrx{R}_1\ =\ \Mtrx{T} \Mtrx{A}^{-1}\]

The matrix on the left is invertible. So \(\Mtrx{T}\Mtrx{A}^{-1}\) is invertible. But the bottom row of \(\Mtrx{T}\Mtrx{A}^{-1}\) consists of \(0\)’s only, hence cannot be invertible . This contradiction resulted from the assumption that \(\Mtrx{T}\neq \IdMtrx{n}\). Therefore this assumption is false, and we conclude that \(\Mtrx{T} = \IdMtrx{n}\).

The case where the RREF of \(\Mtrx{A}\) is the identity matrix

Let us now consider the situation where the RREF of \(\Mtrx{A}\) is the identity matrix. We need to show that \(\Mtrx{A}\) is invertible, and we need to verify the proposed method of computing \(\Mtrx{A}^{-1}\). From the above, we know now that

\(\Mtrx{R}_k\cdot \dots \cdot \Mtrx{R}_1\cdot \Mtrx{A}\ =\ \Mtrx{T}\)

Each of the row transformation matrices \(\Mtrx{R}_k,\dots ,\Mtrx{R}_1\) is invertible. So we get

\[A = \Mtrx{R}_{1}^{-1}\cdot \dots \cdot \Mtrx{R}_{k}^{-1}\cdot \IdMtrx{n} = \Mtrx{R}_{1}^{-1}\cdot \dots \cdot \Mtrx{R}_{k}^{-1}\]

But then we see that \(\Mtrx{A}\) is a product of invertible matrices, hence is itself invertible, and

\(\Mtrx{A}^{-1}\)	\(=\)	\(\left( \Mtrx{R}_{1}^{-1} \cdot \dots \cdot \Mtrx{R}_{k}^{-1} \right)^{-1}\)
\(\)	\(=\)	\(\Mtrx{R}_k\cdot \dots \cdot \Mtrx{R}_1\)
\(\)	\(= \)	\(\Mtrx{R}_k\cdot \dots \cdot \Mtrx{R}_1\cdot \IdMtrx{n}\)

This last identity says exactly that the inverse of \(\Mtrx{A}\) can be found by applying to \(\IdMtrx{n}\) the exact same sequence of row operations which transforms \(\Mtrx{A}\) to \(\IdMtrx{n}\). – This completes the proof.