**Linear Algebra**

# Gaussian Elimination

*schedule*Jan 6, 2024

*toc*Table of Contents

*expand_more*

**mathematics behind data science**with 100+ top-tier guides

Start your free 7-days trial now!

# Algebraic approach to solve simultaneous equations

Consider the following system of linear equations:

One way of solving this is to algebraically manipulate the given equations such that we are left with an equation with one unknown variable. Once we solve for one variable, the other variable can easily be found through substitution. Let's demonstrate this.

We multiply the top equation by $2$ and the bottom equation by $3$ to get:

Even though we have modified the original set of linear equations, multiplying the rows like so does not change the solution of the system. This point will be important later as well.

Now, subtract the bottom equation from the top equation to eliminate the $y$ variable:

Substituting $x=1$ into the top equation in \eqref{eq:kJIkIimOl75yQKMMHL4} gives:

The solution to our linear system is therefore $x=1$ and $y=2$.

# Systematic approach to solve simultaneous equations (Gaussian elimination)

Let's now take another approach to solve our linear system called Gaussian elimination. We will cover the details of this algorithm later, but for now, we will simply go over its steps. We first express the linear system in the following matrix form:

If this does not make sense to you, please review this theoremlink.

Next, we rewrite \eqref{eq:EAGQ6wW6J7xoNf93euG} as an so-called augmented matrix, which is a matrix that combines the matrix on the left and the vector on the right-hand side:

As you can see, the augmented matrix leaves out the variables and captures the essence of our system of linear equations. Augmented matrices can therefore be translated back to the matrix form \eqref{eq:EAGQ6wW6J7xoNf93euG} or the original system of linear equations \eqref{eq:kJIkIimOl75yQKMMHL4}.

## Augmented, coefficient and constant matrix of a linear system

An augmented matrix is a matrix that represents a system of linear equations. It combines the coefficient matrix of the system with the constants from the equations, effectively "augmenting" the coefficient matrix with an extra column.

Mathematically, suppose we have the following system of linear equations:

Where $a_{ij}$ is a scaler and $x_{j}$ is a variable or unknown.

The augmented matrix of this system is:

The coefficient matrix of this system is:

The constant matrix of this system is:

### Finding the augmented matrix given a system of linear equations

Consider the following system of linear equations:

The augmented matrix of this system is:

Recall from earlier that we multiplied the top row by $3$ and the bottom row by $2$ when solving for the variables. We can also perform the same operations on the augmented matrix \eqref{eq:hOKoi1qwbFFSrjobLAk} to get:

This is equivalent to the simultaneous equation \eqref{eq:QvqY2GDyN0GsPJ24Hhz}. Such operations that do not alter the solutions of the system are called elementary row operations. Another example of an elementary row operation is interchanging the rows like so:

This clearly does not affect the solutions because the ordering of the linear equations does not matter.

## Elementary row operations

Elementary row operations are basic manipulations that can be performed on the rows of an augmented matrix. The main property of elementary row operations is that they don't change the solution set of a system of linear equations represented by the matrix.

There are three types of elementary row operations:

multiplying a row by a non-zero constant.

swapping one row with another row.

adding a multiple of a row to another to another row.

Intuition. Let's now demonstrate the three types of elementary row operations. We will use the following system of linear equations for this:

The first type of elementary row operation is multiplying a row by a non-zero constant. Let's multiply the first row by $2$ to get:

Notice how multiplying a row by some non-zero constant does not change the solution to the system.

Let's demonstrate the second type of elementary row operation of swapping one row with another. We swap the first row with the second row:

The ordering of the equations in the system clearly has no effect on the final solution.

Finally, we demonstrate the third type of elementary row operation and multiply the first row by $-3$ and then add it to the second row:

Again, we emphasize that such an operation does not alter the solutions to the system.

Now that you know the three types of elementary row operations, let's go back to our goal of systematically solving system. We will now start from the beginning and perform a series of elementary row operations on the augmented matrix such that we end up with a simplified form:

Note the following:

for the 1st step, we performed two elementary row operations of multiplying the top row by $2$ and the bottom row by $3$.

for the 2nd step, we performed an elementary row operation of subtracting the bottom row from the top row.

for the 3rd step, we performed two elementary row operations of multiplying the top row by $1/6$ and the bottom by $-1/6$.

Notice how we now have a zero term in middle. This means that we have managed to solve for $x$ because:

However, when simplifying an augmented matrix, we often don't stop here and we keep simplifying until the augmented matrix looks like the following:

The augmented matrix here is even simpler than \eqref{eq:cO6nps6cg0oOrhWvDSS} because it directly gives us the solution:

This form of the augmented matrix is called the reduced row echelon form, which we formally define below.

# Reduced row echelon form of a matrix

Let $\boldsymbol{A}$ be a matrix. The reduced row echelon form of $\boldsymbol{A}$, often denoted as $\mathrm{rref}(\boldsymbol{A})$, has the following properties:

unless the row has all $0$s, all the rows must begin with a leading value of $1$.

the leading $1$ in the $i+1$-th row must be on the right-hand side of the leading $1$ in the $i$-th row.

rows with all $0$s are grouped at the bottom.

every row with a leading $1$ has all other columns except the right-most column set to $0$.

If only the first three properties are met, then the form is called a row echelon form.

Some textbooks are more lenient with the structure of the row echelon form - they allow leading coefficients to be **any value** and not just $1$. We will stick with this lenient version of the row echelon form.

## Non-reduced row echelon form (1)

Consider the following augmented matrix:

Why is this not in reduced row echelon form?

Solution. The augmented matrix is in row echelon form because the leading value of nonzero rows is strictly to the right of the leading value of the previous row. However, this form is not in the reduced version because the first row does not begin with a leading $1$. Dividing the top row by $2$ will give us:

This is still not in the reduced row echelon form because the first row with a leading $1$ has a non-zero value for the second column. We can multiply the second row by two and then subtract the bottom row from the top row to get the reduced row echelon form:

Here, we have the value $2$ in the bottom-right entry but this is acceptable because the reduced row echelon form requires that every row with a leading $1$ has all other columns except the right-most column set to $0$.

## Non-reduced row echelon form (2)

Consider the following augmented matrix:

Why is this not in row echelon form?

Solution. This is not in row echelon form because the leading $1$ in the first row occurs on the right-hand side of the leading $1$ in the second row. We can swap the rows twice to get the reduced row echelon form:

Now, given any two successive rows, the leading $1$ of the latter row appears on the right-hand side of the leading $1$ of the row above it.

We will now introduce the Gaussian elimination algorithm, which is a systematic procedure to find the reduced row echelon form of a given augmented matrix.

# Gaussian elimination (1)

Consider the following system of linear equations in matrix form:

Find the reduced row echelon form and solve the system.

Solution. The augmented matrix is:

We now perform a set of elementary row operations to simplify this into the reduced row echelon form. We will denote the first, second and third rows as $\boldsymbol{r}_1$, $\boldsymbol{r}_2$ and $\boldsymbol{r}_3$ respectively. Note that these rows refer to the rows of the latest state of the augmented matrix.

The Gaussian elimination algorithm consists of two stages:

forward phase - make all the values below leading $1$s to be zero.

backward phase - make all the values apart from the leading $1$s and the last column zero.

Once we find the reduced row echelon form, we can then easily find the solutions.

Let's first carry out the forward phase. We swap $\boldsymbol{r}_1$ and $\boldsymbol{r}_2$ so that we get a leading $1$ for the first row:

Because the goal of the forward phase is to make all the values below the leading $1$s zero, we must convert the following red terms to zero:

We can achieve this by $3r_1-r_2$, that is, multiplying the first row by $3$ and then subtracting the second row:

Again, $3r_1-r_2$ is an elementary row operation and does not change the solution of our system! In essence, we are simplifying the system step-by-step until we end up with a form that allows us to directly find the solution!

Next, to make the red term become $0$, we perform $2\boldsymbol{r}_1-\boldsymbol{r}_3$ to get:

Notice how we have $0$s under the leading $1$ in the first row - in a sense, we have **eliminated** those numbers. We are now done with the first column, so let's focus on the following sub-matrix in green:

Typically, we divide the second row by $5$ to get a leading one, but strictly speaking, we do not need to be too concerned about getting leading $1$s just yet. What's more important is to get a $0$ below the value $5$, which we achieve by performing $3\boldsymbol{r}_2-5\boldsymbol{r}_3$ to get:

We can divide the second row by $5$ to get a leading $1$, which will conclude the forward phase since we will have $0$s below all leading $1$s. Again, we won't divide by $5$ because we would end up with fractions in the second row. Don't worry too much about getting the leading $1$s just yet because we can always divide by the first value in the row to convert them into leading $1$ at any time!

We now begin with the backward phase. In this phase, the objective is to convert the following red terms into zeros:

Remember, the forward phase guarantees that the last row has the most number of leading $0$s. Therefore, we can use this last row to convert the following red terms into zeros:

We perform $\boldsymbol{r}_2-2\boldsymbol{r}_3$ to get:

We perform $\boldsymbol{r}_1-2\boldsymbol{r}_3$ to get:

Great, what's left is to eliminate the $2$ on top of the $5$. Before we do so, let's first divide the second row by $5$ to get a leading one:

Finally, we perform $\boldsymbol{r}_1-2\boldsymbol{r}_2$ to get:

What we have now is the reduced row-echelon form of the augmented matrix!

Once we find the augmented matrix, solving the system is a piece of cake 🍰. Converting the augmented matrix back into a system of linear equations:

Great, we're done!

# Gaussian elimination (2)

Consider the following system of linear equations:

Use Gaussian Elimination to solve the system.

Solution. The augmented matrix is:

Let's now perform a series of elementary row operations to obtain the reduced row echelon form:

The elementary row operation taken for each step is as follows:

$(1)$: $3\boldsymbol{r}_1-2\boldsymbol{r}_2$.

$(2)$: $\boldsymbol{r}_1-\boldsymbol{r}_2$.

(3): $\boldsymbol{r}_2-5\boldsymbol{r}_2$.

This concludes the forward phase. Next, let's simplify the last row by dividing by $7$ to get:

We now begin with the backward phase:

The elementary row operations taken are:

$(5)$: $\boldsymbol{r}_1+3\boldsymbol{r}_3$.

$(6)$: $\boldsymbol{r}_1-\boldsymbol{r}_2$.

$(7)$: $\boldsymbol{r}_1/2$ and $\boldsymbol{r}_2/10$.

Finally, we perform $\boldsymbol{r}_1-2\boldsymbol{r}_2$ to get our reduced row echelon form:

Converting this back into a linear system gives us the solution:

We're done!

# Using row echelon form to check for the existence of a solution

The row echelon form, instead of the reduced version, is sufficient to check for the existence of solutions. In other words, the row echelon form determines whether the system is consistentlink or inconsistentlink.

The reduced row echelon form is better for computing the actual solutions but if all we want to do is to check that a solution exists, then the row echelon form is sufficient.

## Consistent systems

Consider the following row echelon form of some augmented matrix:

Note that we colored the last column to emphasize that these values are not coefficients. We can already tell that a solution exists, that is, the system is consistent, because:

the last row gives us $z$.

substituting $z$ into the second row gives us $y$.

substituting $y$ and $z$ into the first equation gives us $x$.

Similarly, consider the following row echelon form:

The last row is all zeros, which means that we are left with $2$ equations and $3$ unknowns. Since one variable is free to vary, the system is consistent and has infinitely many solutions!

## Inconsistent systems

Consider the following row echelon form of some augmented matrix:

In this case, a solution does not exist because the last row leads to a contradiction of $0=3$. In other words, this system of linear equations is inconsistent, that is, this system cannot be solved.

## Showing that a system is consistent (1)

Consider the following system of linear equations:

Show that the system is consistent.

Solution. The augmented matrix of the system is:

Let's obtain the row echelon form:

Because we can solve for the unknowns, we conclude that the system is consistent with an unique solution.

## Showing that a system is consistent (2)

Consider the following simultaneous equations:

Show that the system is consistent.

Solution. The row echelon form is:

We get all zeros for the last row, which means that we are left with one equation with two unknowns. Therefore, the system is consistent with infinitely many solutions.

## Showing that a system is inconsistent

Consider the following system of linear equations:

Show that the system is inconsistent.

Solution. The row echelon form is:

Because we get a contradiction ($0=1$), we conclude that the system is inconsistent and has no solutions.

# Reduced row echelon form of homogeneous linear system

If $\boldsymbol{B}$ is the reduced row echelon form of some matrix $\boldsymbol{A}$, then solutions to the homogeneous linear system $\boldsymbol{Ax}=\boldsymbol{0}$ and $\boldsymbol{Bx}=\boldsymbol{0}$ are the same.

Proof. Suppose the augmented matrix of the homogenous linear system $\boldsymbol{Ax}=\boldsymbol{0}$ is:

Performing elementary row operations on this augmented matrix:

does not affect the rightmost column whose entries are all zeros; multiplying a row by a scalar, interchanging rows, or adding a multiple of one row to another will keep the rightmost column all zeroes. This means that we can simply focus on row-reducing the coefficient matrix instead of the augmented matrix.

does not change the solution of the system.

Since the reduced row echelon form $\boldsymbol{B}$ of $\boldsymbol{A}$ is obtained by performing a series of elementary row operations on $\boldsymbol{A}$, we know that $\boldsymbol{Ax}=\boldsymbol{0}$ and $\boldsymbol{Bx}=\boldsymbol{0}$ share the same solutions. This completes the proof.

# Row echelon form of an augmented matrix is not unique

A row echelon form of an augmented matrix is not unique.

Proof. Consider the following row echelon form of some augmented matrix:

Let's perform an elementary row operation of adding the bottom row to the top row:

We now have two different row echelon forms of our augmented matrix - both of which are equally valid. This completes the proof.

# Practice problems

Consider a system of linear equations with $4$ unknowns and $3$ equations. What is the shape of the coefficient matrix?

Each row of a coefficient matrix represents an equation whereas each column represents a variable (or unknown). Therefore, the shape of the coefficient matrix in this case is $3\times4$.

Find the augmented matrix and coefficient matrix of the following system of linear equations:

The augmented matrix of the system is:

The coefficient matrix of the system is:

Consider the following augmented matrix:

Convert this into a system of linear equations.

The system of linear equations is:

Consider the following matrix:

Find the row-echelon form as well as the reduced row-echelon form of $\boldsymbol{A}$.

Let's start by performing an elementary row operation $\boldsymbol{r}_1-1/2\;\boldsymbol{r}_2$ to get:

Therefore, the row-echelon form is:

If we require a strict version of the row-echelon form where the leading non-zero value must be one, then we can perform another elementary row operation of $1/5\;\boldsymbol{r}_2$ to get:

Note that the row-echelon form is not uniquelink so your answer may be different but still correct. For example, let's perform another elementary row operation $\boldsymbol{r}_1+2\boldsymbol{r}_2$ to get:

Notice how this is also a valid row-echelon form of $\boldsymbol{A}$.

Now, let's determine the reduced row-echelon form of $\boldsymbol{A}$. Let's refer to \eqref{eq:x47FAWEpJRzUCjS2mzH} and perform an elementary row operation of $\boldsymbol{r}_1-3\boldsymbol{r}_2$ to get:

Consider the following matrix:

Find the row-echelon form as well as the reduced row-echelon form of $\boldsymbol{A}$.

To obtain the row-echelon form, we must perform a series of elementary row operations:

Here, the we performed the following elementary row operations:

1. $\boldsymbol{r}_2-\boldsymbol{r}_3$.

2. interchange $\boldsymbol{r}_2$ and $\boldsymbol{r}_3$.

Let's continue:

The elementary row operations are:

3. $2\boldsymbol{r}_1$.

4. $\boldsymbol{r}_1-3\boldsymbol{r}_3$.

Finally, we perform $\boldsymbol{r}_2-3\boldsymbol{r}_3$ to get:

Therefore, the row-echelon form is:

If we go by the strict definition of row-echelon form where the leading non-zero value must be one, then:

Note that the row-echelon form is not unique, which means that the answer you came up with may be different but still correct. We encourage you to perform some elementary row operations on your answer to get the form above - if you can, then your answer is correct.

Let's now obtain the reduced row-echelon form.

Therefore, the reduced row-echelon form is:

Consider the following:

Solve for the system using Gaussian elimination. Use comma to separate the solutions (e.g. $3$,$4$ to indicate $x=3$, $y=4$).

The augmented matrix is:

We then perform a series of elementary row operations to obtain the reduced row echelon form. Let's first start with the forward-pass:

Here, the elementary row operations are as follows:

$3\boldsymbol{r}_1 -2\boldsymbol{r}_2$.

$(-1/7)\;\boldsymbol{r}_2$.

Technically, the first step is not an elementary row operation because we are multiplying not just one row but two rows at once and then taking their sum. This is only a shortcut and does not change the final solutions. We can break this down into two elementary row operations - first to multiply the 1st row by $3$, and then 2nd to multiply the second row by $-2$ and then adding it to the first row.

Next, we proceed with the backward-pass:

Here, the elementary row operations are as follows:

3. $-3\boldsymbol{r}_2+ \boldsymbol{r}_1$.

4. $(1/2)\;\boldsymbol{r}_1$.

Therefore, the solution to the system is:

Consider the following system of linear equations:

Solve for the system using Gaussian Elimination. Use comma to separate the values (e.g. $2$,$3$,$4$ for $x=2$, $y=3$ and $z=4$).

The augmented matrix is:

We then perform forward-passing via a series of elementary row operations:

We continue with forward-passing:

We're now done with forward-passing. We proceed with backward-passing:

Therefore, the solution is:

Consider the following system of linear equations:

By finding the row echelon form, identify the characteristic of the system.

The system is consistent with a unique solution.

The system is consistent with infinitely many solutions.

The system is inconsistent.

The augmented matrix is:

The row echelon form is:

The last row tells us that $0=1$, which means that the system is inconsistent.

Consider the following system of linear equations:

By finding the row echelon form, identify the characteristic of the system.

The system is consistent with a unique solution.

The system is consistent with infinitely many solutions.

The system is inconsistent.

The augmented matrix is:

The row echelon form is:

Because we can directly solve for the unknowns (e.g. $y=3$), the system is consistent with a unique solution.