Gaussian Elimination - Introduction

Gaussian elimination is a systematic process (algorithm) to solve any linear system. On top of being systematic, it is relatively simple and allows for finding the solution to a linear system quite quickly compared to traditional methods commonly learned in high school.

Before we get into the actual steps, it’s important that we lay the correct foundation.

Upper Triangular Matrices

A triangular matrix is a square matrix where everything on one side of the main diagonal are zero entries. The main diagonal of a matrix is the diagonal going from the top left to the bottom right of the matrix.

An upper triangular matrix specifically is a triangular matrix where the non-zero entries are found above - and on - the diagonal, and the zero entries are found below the diagonal.

Here is an example of a $3 \times 3$ upper triangular matrices:

As you can see, in the bottom left (below the diagonal) we only find $0$s. All other entries can be non-zero (they don’t have to, they could also be $0$).

Here is a $4 \times 4$ upper triangular matrix:

Lower Triangular Matrices

It is less vital for Gaussian elimination, but for the sake of completion I would like to mention that there is also the concept of lower triangular matrices, which is the same idea, but the zero entries are now above the main diagonal.

For example:

The Zero Matrix

By definition, the zero matrix is an upper triangular matrix and a lower triangular matrix at the same time, since the requirement for an upper triangular matrix is to have all zeros below the main diagonal and for a lower triangular matrix the requirement is to have all zeros above the main diagonal. The zero matrix has zeros everywhere, so it is both at the same time.

The Idea of Gaussian Elimination

The goal of Gaussian elimination is to reduce any given linear system to an upper triangular system (which is just a linear system with an upper triangular matrix).

This is convenient because the next step (which we will see is called back substitution) is very fast once we have an upper triangular system.

Here is a quick overview:

Take the linear system

Through Gaussian elimination, this can be reduced to the system

which is equivalent to the system we started with (i.e. it has the same solution).

And then the process of back substitution involves substituting the known variables back into the equations from bottom to top. Right now we know that $y = 1$, and there is only one equation left. We substitute for $y = 1$ in the first equation to get

The system is now solved. The solution is

This is not supposed to be a comprehensive guide, just an introduction to what’s ahead.