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}.

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.

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.

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$.

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.

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!

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!

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.

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.

Solution. The row echelon form is:

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

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.

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