This page is intended to be a part of the Numerical Analysis section of Math Online. Similar topics can also be found in the Linear Algebra section of the site.

The Gaussian Elimination Algorithm

Consider a general system of $n$ linear equations of $n$ unknowns:

(1)

\begin{align} \left\{\begin{matrix} a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n = b_1 \\a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n = b_2 \\ \: \vdots \quad \quad \quad \vdots \quad \quad \: \: \quad \vdots \quad \quad \: \: \vdots \: \: \: \\ a_{m1}x_1 + a_{m2}x_2 + ... + a_{mn}x_n = b_m \end{matrix}\right. \end{align}

Suppose that this system indeed has a solution (that is the coefficient matrix is nonsingular). Now take the coefficient matrix $A$ for this system and adjoin the column matrix $b = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix}$. We denote this new $n \times n + 1$ augmented matrix as $[ \: A \: | \: b \: ]$.

(2)

\begin{align} \quad [ \: A \: | \: b \: ] = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} & b_n \end{bmatrix} \end{align}

Our goal is to use elementary row operations to transform the augmented matrix above into the following form:

(3)

\begin{align} \quad \begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n} & b_1 \\ 0 & u_{22} & \cdots & u_{2n} & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & u_{nn} & b_n \end{bmatrix} \end{align}

In other words, we want to reduce the coefficient matrix $A$ so that it is an upper triangular matrix while applying the same elementary row operations to the matrix $b$. The matrix above is row equivalent to the augmented matrix of our system, and so the solutions to this matrix are the same as the solutions to the original system equations. The benefit with having the matrix above is that it is much simpler to solve. Note that the above augmented matrix is equivalent to the following system of equations:

(4)

\begin{align} \left\{\begin{matrix} u_{11}x_1 + u_{12}x_2 + ... + u_{1n}x_n = b_1 \\0x_1 + u_{22}x_2 + ... + u_{2n}x_n = b_2 \\ \: \vdots \quad \quad \quad \vdots \quad \: \: \quad \vdots \quad \quad \: \: \vdots \: \\ 0x_1 + 0x_2 + ... + u_{nn}x_n = b_m \end{matrix}\right. \end{align}

We immediately see that $x_n = b_n$. We can then take this and substitute this into the equation $x_{n-1} + a_{(n-1, n)}x_n = b_{n-1}$ and solve for $x_{n-1}$. Repeating this process and we obtain the entire solution to the original system by successive Back Substitution. This entire technique is known as Gaussian Elimination and is a nice method for solving systems of $n$ equations with $n$ variables.

Now let's take a closer look at the Gaussian Elimination Algorithm. For this algorithm, we will assume that we are not every dividing by zero (we'll look more into this later). Let $E(k)$ denote the $k^{\mathrm{th}}$ equation in our system of $n$ equations in $n$ variables for $k = 1, 2, ..., n$. Our system can be written in the following form:

(5)

\begin{align} \quad \begin{matrix} E(1): & & a_{11}^{(1)}x_1 & + & a_{12}^{(1)}x_2 & + & \cdots & + & a_{1n}^{(1)}x_n & = & b_1^{(1)} \\ E(2): & & a_{21}^{(1)}x_1 & + & a_{22}^{(1)}x_2 & + & \cdots & + & a_{2n}^{(1)}x_n & = & b_2^{(1)} \\ \vdots & & \vdots & & \vdots & & \ddots & & \vdots & & \vdots \\ E(n): & & a_{n1}^{(1)}x_1 & + & a_{n2}^{(1)}x_2 & + & \cdots & + & a_{nn}^{(1)}x_n & = & b_n^{(1)} \end{matrix} \end{align}

The first step that we want to do is to eliminate the variable $x_1$ from equations $E(2)$ through to $E(n)$. This will make it so that our system of equations have zeros underneath the entry $a_{11}^{(1)}x_{1}$. In doing so, we obtain the equivalent system below.

(6)

\begin{align} \quad \begin{matrix} E(1): & & a_{11}^{(1)}x_1 & + & a_{12}^{(1)}x_2 & + & \cdots & + & a_{1n}^{(1)}x_n & = & b_1^{(1)} \\ E(2): & & 0 & + & a_{22}^{(2)}x_2 & + & \cdots & + & a_{2n}^{(2)}x_n & = & b_2^{(2)} \\ \vdots & & \vdots & & \vdots & & \ddots & & \vdots & & \vdots \\ E(n): & & 0 & + & a_{n2}^{(2)}x_2 & + & \cdots & + & a_{nn}^{(2)}x_n & = & b_n^{(2)} \end{matrix} \end{align}

Let $m_{21} = \frac{a_{21}^{(1)}}{a_{11}^{(1)}}$, $m_{31} = \frac{a_{31}^{(1)}}{a_{11}^{(1)}}$, …, $m_{n1} = \frac{a_{n1}^{(1)}}{a_{11}^{(1)}}$. Then the coefficients $a_{ij}^{(2)}$ and $b_i^{(2)}$ in the matrix above can be obtained with the following formulas:

(7)

\begin{align} \quad a_{ij}^{(2)} = a_{ij} - m_{i1}a_{1j} \quad i, j = 2, 3, ..., n \\ \quad b_1^{(2)} = b_i - m_{i1}b_1 \quad i = 2, 3, ..., n \end{align}

At the $k^{\mathrm{th}}$ step, we will have the following (partially reduced) matrix to work with:

(8)

\begin{align} \quad \begin{matrix} E(1): & & a_{11}^{(1)}x_1 & + & a_{12}^{(1)}x_2 & + & \cdots & + & \cdots & + & a_{1n}^{(1)}x_n & = & b_1^{(1)}\\ E(2): & & 0 & + & a_{22}^{(2)}x_2 & + & \cdots & + & \cdots & + & a_{2n}^{(2)}x_n & = & b_2^{(2)} \\ \vdots & & \vdots & & \vdots & & & & & & \vdots & & \vdots \\ E(k): & & 0 & + & 0 & + & a_{kk}^{(k)}x_k & + & \cdots & + & a_{kn}^{(k)}x_n & = & b_k^{(k)} \\ \vdots & & \vdots & & \vdots & & & & & & \vdots & & \vdots \\ E(n): & & 0 & + & 0 & + & a_{nk}^{(k)}x_k & + & \cdots & + & a_{nn}^{(k)}x_n & = & b_n^{(k)} \end{matrix} \end{align}

At this step we will want to eliminate the variable $x_k$ from the equations $E(k+1)$ through to $E(n)$. This will make it so that all entries under $a_{kk}^{(k)}x_k$ are zero.

Let $m_{ik} = \frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}$ for $i = k+1, k+2, ..., n$. For equations $E(k+1)$, $E(k+2)$, …, $E(n)$ we will subtract $m_{ik}$ times $E(k)$ from $E(i)$ for each $i = k+1, k+2, ..., n$. The coefficients below equation $E(k)$ will be:

(9)

\begin{align} \quad a_{ij}^{(k+1)} = a_{ij}^{(k)} - m_{ik}a_{kj}^{(k)} \quad \quad i, j = k+1, k+2, ..., n \\ \quad b_i^{(k+1)} = b_i^{(k)} - m_{ik}b_k^{(k)} \quad \quad i = k+1, k+2, ... , n \end{align}

At the $(n - 1)^{\mathrm{th}}$ step will will have transformed our system into an "upper triangular" equivalent form:

(10)

\begin{align} \quad u_{11}x_1 + u_{12}x_2 + \cdots + u_{1n} x_n = g_2 \\ u_{22}x_2 + \cdots + u_{2n} x_n = g_2 \\ \vdots \\ u_{nn}x_n = g_n \end{align}

The coefficients of this row equivalent system we will denote as $u_{ij} = a_{ij}^{(i)}$ and $g_i = b_i^{(i)}$ for $i = 1, 2, ..., n$. We then proceed to solve this system of equations by back substitution. We have that for $i = n-1, n-2, ..., 1$:

(11)

\begin{align} \quad x_n = \frac{g_n}{u_{nn}} \quad , \quad x_{n-1} = \frac{g_{n-1} - u_{(n-1, n)}x_n}{u_{(n-1, n-1)}} \quad \cdots \quad x_{i} = \frac{g_i - \sum_{j=i+1}^{n} u_{ij}x_j}{u_{ii}} \end{align}