# Gaussian Elimination

Gaussian Elimination is a simple method for solving a system of simultaneous linear equations by expressing them in matrix form and then subtracting rows from each other sequentially in order to create all ones on the main diagonal and all zeros below the diagonal, thereby facilitating identification of solutions or range of solutions.

The three types of elementary row operations used are:

• swap rows
• multiple a row by a constant
• add or subtract rows from each other

## Example

Here, we work a simple example. Consider the two equations:

$3x-2y=7 \$

$x+\frac{y}{2} = -2 \$.

We represent this collection of equations in matrix form as:

$\begin{pmatrix}3 & -2 & 7\\1 & 1/2 & -2\end{pmatrix}$.

Now, the technique of Gaussian elimination allows us to add and subtract rows from each other, as well as multiples of rows. The idea is to achieve 1s in the main diagonal, and 0s elsewhere. This will become clear as we work the example.

Since the row $\begin{pmatrix}4 & 2 & -8 \end{pmatrix}$ is a multiple of the second row ( $4*\begin{pmatrix}1 & 1/2 & -2 \end{pmatrix}$), we can add this row to the first row:

$\begin{pmatrix}3 & -2 & 7\\1 & 1/2 & -2\end{pmatrix} \to \begin{pmatrix}3+4 & -2+2 & 7-8\\1 & 1/2 & -2\end{pmatrix}=\begin{pmatrix}7 & 0 & -1\\1 & 1/2 & -2\end{pmatrix}$

As you can see, we have already begun altering the matrix so that there will be 0s off of the main diagonal. In our next step, we will divide the top row by 7 and multiply the bottom row by 2 to put 1s in the main diagonal:

$\begin{pmatrix}7 & 0 & -1\\1 & 1/2 & -2\end{pmatrix} \to \begin{pmatrix}1 & 0 & -1/7\\2 & 1 & -4\end{pmatrix}$

Finally, we subtract twice the top row from the bottom to put a zero off the main diagonal in the bottom:

$\begin{pmatrix}1 & 0 & -1/7\\2 & 1 & -4\end{pmatrix} \to \begin{pmatrix}1 & 0 & -1/7\\0 & 1 & -4+2/7\end{pmatrix}=\begin{pmatrix}1 & 0 & -1/7\\0 & 1 & -26/7\end{pmatrix}$

This should yield a solution to the original equation: $x=-1/7, y=-26/7 \$. To check, we insert these values into the original equations:

$3\frac{-1}{7} - 2\frac{-26}{7} = \frac{-3+52}{7} = \frac{49}{7} = 7$

$\frac{-1}{7} + \frac{1}{2}{-26}{7} = \frac{-1-13}{7} = \frac{-14}{7} = -2$

as expected.