2.1: Gaussian Elimination

Last updated
Save as PDF

Page ID: 96144

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

View Gaussian Elimination on YouTube

The standard algorithm to solve a system of linear equations is called Gaussian elimination. It is easiest to illustrate this algorithm by example.

Consider the linear system of equations given by

\[\begin{align}-3x_1+2x_2-x_3&=-1, \\[4pt] 6x_1-6x_2+7x_3&=-7\label{eq:1} \\[4pt] 3x_1-4x_2+4x_3&=-6,\end{align} \]

which can be rewritten in matrix form as

\[\left(\begin{array}{rrr}-3&2&-1\\6&-6&7\\3&-4&4\end{array}\right)\left(\begin{array}{c}x_1\\x_2\\x_3\end{array}\right)=\left(\begin{array}{r}-1\\-7\\-6\end{array}\right).\nonumber \]

To perform Gaussian elimination, we form what is called an augmented matrix by combining the matrix \(\text{A}\) with the column vector \(\text{b}\):

\[\left(\begin{array}{rrrr}-3&2&-1&-1\\6&-6&7&-7\\3&-4&4&-6\end{array}\right).\nonumber \]

Row reduction is then performed on this matrix. Allowed operations are

multiply any row by a constant,
add a multiple of one row to another row,
interchange the order of any rows.

It is easy to confirm that these operations do not change the solution of the original equations. The goal here is to convert the matrix \(\text{A}\) into a matrix with all zeros below the diagonal. This is called an upper-triangular matrix, from which one can quickly solve for the unknowns \(\text{x}\).

We start with the first row of the matrix and work our way down as follows. The key element is called the pivot, which is the diagonal element that we use to zero all the elements below it. The pivot in the first row is the diagonal entry \(−3\). To zero the \(6\) in the second row below the pivot, we multiply the first row by \(2\) and add it to the second row. To zero the \(3\) in the third row below the pivot, we add the first row to the third row:

\[\left(\begin{array}{rrrr}-3&2&-1&-1\\6&-6&7&-7\\3&-4&4&-6\end{array}\right)\to\left(\begin{array}{rrrr}-3&2&-1&-1\\0&-2&5&-9\\0&-2&3&-7\end{array}\right).\nonumber \]

We then go to the second row. The new pivot is the number \(−2\) in the diagonal of the second row. To zero the \(−2\) below the pivot, we multiply the second row by \(−1\) and add it to the third row:

\[\left(\begin{array}{rrrr}-3&2&-1&-1\\0&-2&5&-9\\0&-2&3&-7\end{array}\right)\to\left(\begin{array}{rrrr}-3&2&-1&-1\\0&-2&5&-9\\0&0&-2&2\end{array}\right).\nonumber \]

The original matrix \(\text{A}\) is now upper triangular, and the transformed equations can be determined from the augmented matrix as

\[\begin{aligned}-3x_1+2x_2-x_3&=-1,\\ -2x_2+5x_3&=-9,\\ -2x_3&=2.\end{aligned} \nonumber \]

These equations can be solved by back substitution, starting from the last equation and working backwards. We have

\[\begin{aligned}x_3&=-\frac{1}{2}(2)=-1 \\ x_2&=-\frac{1}{2}(-9-5x_3)=2, \\ x_1&=-\frac{1}{3}(-1-2x_2+x_3)=2.\end{aligned} \nonumber \]

Therefore,

\[\left(\begin{array}{c}x_1\\x_2\\x_3\end{array}\right)=\left(\begin{array}{r}2\\2\\-1\end{array}\right).\nonumber \]