Gaussian elimination

Gaussian elimination

Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. This method can also be used to compute the rank of a matrix, the determinant of a square matrix, and the inverse of an invertible matrix. To perform row reduction on a matrix, one uses a sequence of elementary row operations to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible.

Algorithm

  1. If necessary, swap the first row with another row such that the first entry of the first row is a nonzero number
  2. Scale the first row so that the first (should be a nonzero) entry is equal to 1
  3. Use elementary row operations to manipulate the matrix such that all the consecutive entries in the first column (other than the first entry) are equal to zero
  4. If necessary, swap the second row with another row such that the second entry of the second row is a nonzero number (and the first entry should also be a zero)
  5. Scale the second row so that the second entry is equal to 1
  6. Use elementary row operations to manipulate the matrix such that all the consecutive entries in the second column are equal to zero

Example

We shall demonstrate that

Assume we have matrix \[A\], where

\begin{align*} A= \begin{pmatrix} 1 & 2 & 1 \\ 0 & -1 & 2 \\ 2 & 3 & 1 \\ \end{pmatrix} \end{align*}

To find the inverse of \[A\], we form an augmented matrix \[(A|\mathbf{I}_{3})\].

\begin{align*} (A|\mathbf{I}_{3})= \begin{pmatrix} 1 & 2 & 1 & \bigm| & 1 & 0 & 0 \\ 0 & -1 & 2 & \bigm| & 0 & 1 & 0 \\ 2 & 3 & 1 & \bigm| & 0 & 0 & 1 \\ \end{pmatrix} \end{align*}

Then, \[L_{3}-2L_{1}\rightarrow L_{3}\]:

\begin{align*} = \begin{pmatrix} 1 & 2 & 1 & \bigm| & 1 & 0 & 0 \\ 0 & -1 & 2 & \bigm| & 0 & 1 & 0 \\ 0 & -1 & -1 & \bigm| & -2 & 0 & 1 \\ \end{pmatrix} \end{align*}

\[L_{3}-L_{2}\rightarrow L_{3}\]:

\begin{align*} = \begin{pmatrix} 1 & 2 & 1 & \bigm| & 1 & 0 & 0 \\ 0 & -1 & 2 & \bigm| & 0 & 1 & 0 \\ 0 & 0 & -3 & \bigm| & -2 & -1 & 1 \\ \end{pmatrix} \end{align*}

Now we have a matrix in row echelon form.
\[L_{1}+2L_{2}\rightarrow L_{1}\]

\begin{align*} = \begin{pmatrix} 1 & 0 & 5 & \bigm| & 1 & 2 & 0 \\ 0 & -1 & 2 & \bigm| & 0 & 1 & 0 \\ 0 & 0 & -3 & \bigm| & -2 & -1 & 1 \\ \end{pmatrix} \end{align*}

Follow it with \[5L_{3}+3L_{1}\rightarrow L_{1}\] and \[2L_{3}+3L_{2}\rightarrow L_{2}\]

\begin{align*} = \begin{pmatrix} 3 & 0 & 0 & \bigm| & -7 & 1 & 5 \\ 0 & -3 & 0 & \bigm| & -4 & 1 & 2 \\ 0 & 0 & -3 & \bigm| & -2 & -1 & 1 \\ \end{pmatrix} \end{align*}

Lastly, apply \[\frac{1}{3}L_{1}\rightarrow L_{1}\], \[-\frac{1}{3}L_{2}\rightarrow L_{2}\], \[-\frac{1}{3}L_{3}\rightarrow L_{3}\]

\begin{align*} (I|A^{-1})= \begin{pmatrix} 1 & 0 & 0 & \bigm| & -\frac{7}{3} & \frac{1}{3} & \frac{5}{3} \\ 0 & 1 & 0 & \bigm| & \frac{4}{3} & -\frac{1}{3} & -\frac{2}{3} \\ 0 & 0 & 1 & \bigm| & \frac{2}{3} & \frac{1}{3} & -\frac{1}{3} \\ \end{pmatrix} \end{align*}

Therefore

\begin{align*} A^{-1}=\frac{1}{3} \begin{pmatrix} -7 & 1 & 5 \\ 4 & -1 & -2 \\ 2 & 1 & -1 \\ \end{pmatrix} \end{align*}
index