Gaussian Elimination

Gaussian Elimination, also called Gauss-Jordan 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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3x-2y=7 \ }

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{pmatrix}4 & 2 & -8 \end{pmatrix}} is a multiple of the second row ( Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.

Sources

• Gaussian Elimination from Mathworld