Gauss-Jordan Method

Definition 1.7 (elementary matrix). An elementary matrix is a matrix obtained from the identity matrix $I_n$ by applying exactly one elementary row operation.

Key fact. Applying a row operation to a matrix $A$ has exactly the same effect as pre-multiplying $A$ by the corresponding elementary matrix. For instance, applying $R_2\to R_2+\lambda R_3$ to a $3\times3$ matrix $A$ gives the same result as computing $\begin{pmatrix}1&0&0\\0&1&\lambda\\0&0&1\end{pmatrix}A$. Similarly, $R_i\leftrightarrow R_j$ corresponds to swapping rows $i,j$ of $I_n$, and $R_i\to\lambda R_i$ corresponds to scaling row $i$ of $I_n$ by $\lambda$.

Theorem 1.13. Every non-singular matrix can be transformed to the identity matrix by a sequence of elementary row operations.

Chaining $k$ such row operations that reduce a non-singular $A$ to $I_n$ therefore means $E_k\cdots E_2E_1A=I_n$ for the matching elementary matrices $E_1,\ldots,E_k$, so

The Gauss-Jordan algorithm.

Step 1. Augment $A$ with the identity matrix on the right: form $[A\,|\,I_n]$.

Step 2. Find elementary row operations $E_1,\ldots,E_k$ that reduce $A$ (the left block) all the way to $I_n$. Applying the same sequence to the whole augmented matrix carries the right block from $I_n$ to $E_k\cdots E_1I_n=A^{-1}$:

$[A\,|\,I_n]\ \xrightarrow{\ \text{row ops}\ }\ [I_n\,|\,A^{-1}].$ …