search
Search
Login
Map of Data Science
menu
menu
search toc
Thanks for the thanks!
close
Comments
Log in or sign up
Cancel
Post
account_circle
Profile
exit_to_app
Sign out
search
keyboard_voice
close
Searching Tips
Search for a recipe:
"Creating a table in MySQL"
Search for an API documentation: "@append"
Search for code: "!dataframe"
Apply a tag filter: "#python"
Useful Shortcuts
/ to open search panel
Esc to close search panel
to navigate between search results
d to clear all current filters
Enter to expand content preview
icon_star
Doc Search
icon_star
Code Search Beta
SORRY NOTHING FOUND!
mic
Start speaking...
Voice search is only supported in Safari and Chrome.
Navigate to

Gaussian Elimination

schedule Mar 5, 2023
Last updated
local_offer
Linear Algebra
Tags
map
Check out the interactive map of data science

Algebraic approach to solve simultaneous equations

Consider the following system of linear equations:

$$\begin{equation}\label{eq:kJIkIimOl75yQKMMHL4} \begin{cases} 3x+3y=9\\ 4x+2y=8\\ \end{cases} \end{equation}$$

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:

$$\begin{equation}\label{eq:QvqY2GDyN0GsPJ24Hhz} \begin{cases} 6x+6y&=18\\ 12x+6y&=24\\ \end{cases} \end{equation}$$

Even though we have modified the original set of linear equations, multiplying the rows like so does not change the solution of the system.

Now, subtract the bottom equation from the top equation:

$$\begin{align*} -6x&=-6\\ x&=1 \end{align*}$$

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

$$\begin{align*} 3(1)+3y&=9\\ y&=2 \end{align*}$$

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:

$$\begin{equation}\label{eq:EAGQ6wW6J7xoNf93euG} \begin{pmatrix} 3&3\\ 4&2 \end{pmatrix} \begin{pmatrix} x\\y \end{pmatrix}= \begin{pmatrix} 9\\8 \end{pmatrix} \end{equation}$$

Augmented matrices and elementary row operations

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

$$\begin{pmatrix} 3&3&9\\ 4&2&8 \end{pmatrix}$$

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:

$$\begin{pmatrix} 6&6&18\\ 12&6&24 \end{pmatrix} \;\;\;\;\;\Longleftrightarrow\;\;\;\;\; \begin{cases} 6x+6y=18\\ 12x+6y=24\\ \end{cases}$$

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:

$$\begin{pmatrix} 12&6&24\\ 6&6&18 \end{pmatrix} \;\;\;\;\;\Longleftrightarrow\;\;\;\;\; \begin{cases} 12x+6y=24\\ 6x+6y=18\\ \end{cases}$$

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

Let's now manipulate and simplify our augmented matrix:

$$\begin{pmatrix} 3&3&9\\ 4&2&8 \end{pmatrix}\underset{(1)}{\implies} \begin{pmatrix} 6&6&18\\ 12&6&24 \end{pmatrix}\underset{(2)}{\implies} \begin{pmatrix} 6&6&18\\ -6&0&-6 \end{pmatrix}\underset{(3)}{\implies} \begin{pmatrix} 1&1&3\\ 1&0&1 \end{pmatrix}$$

Note the following:

  • for the second step, we subtracted the bottom row from the top row. Again, this does not alter the solution set and is also considered to be an elementary row operation.

  • for the third step, we performed yet another elementary row operation of dividing the top row by $6$ and the bottom row by $-6$.

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

$$\begin{equation}\label{eq:cO6nps6cg0oOrhWvDSS} \begin{pmatrix} 1&1&3\\ 1&0&1 \end{pmatrix} \;\;\;\;\;\Longleftrightarrow\;\;\;\;\; \begin{cases} x+y=3\\ x\;\;\;\;\;\;=1\\ \end{cases} \end{equation}$$

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

$$\begin{pmatrix} 1&1&3\\ 1&0&1 \end{pmatrix} \underset{(4)}{\implies} \begin{pmatrix} 1&0&1\\ 1&1&3 \end{pmatrix} \underset{(5)}{\implies} \begin{pmatrix} 1&0&1\\ 0&1&2 \end{pmatrix}$$

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

$$\begin{equation}\label{eq:NPHg8xuR6DQbiCKs1bD} \begin{pmatrix} 1&0&1\\ 0&1&2 \end{pmatrix} \;\;\;\;\;\Longleftrightarrow\;\;\;\;\; \begin{cases} x=1\\ y=2 \end{cases} \end{equation}$$

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

Definition.

Reduced row echelon form of a matrix

Let $\boldsymbol{A}$ be a matrix. The reduced row echelon 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.

WARNING

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.

Example.

Non-reduced row echelon form (1)

Consider the following augmented matrix:

$$\begin{pmatrix} 2&4&10\\ 0&1&2 \end{pmatrix}$$

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:

$$\begin{pmatrix} 1&2&5\\ 0&1&2 \end{pmatrix}$$

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:

$$\begin{pmatrix} 1&0&1\\ 0&1&2 \end{pmatrix}$$
Example.

Non-reduced row echelon form (2)

Consider the following augmented matrix:

$$\begin{pmatrix} 0&0&1&3\\ 1&0&0&2\\ 0&1&0&8 \end{pmatrix}$$

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:

$$\begin{pmatrix} 1&0&0&2\\ 0&1&0&8\\ 0&0&1&3 \end{pmatrix}$$

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.

Example.

Gaussian Elimination (1)

Consider the following system of linear equations in matrix form:

$$\begin{pmatrix} 3&1&4\\ 1&2&2\\ 2&1&3 \end{pmatrix} \begin{pmatrix} x\\y\\z\\ \end{pmatrix}= \begin{pmatrix} 2\\5\\2 \end{pmatrix}$$

Find the reduced row echelon form and solve the system.

Solution. The augmented matrix is:

$$\begin{pmatrix} 3&1&4&2\\ 1&2&2&5\\ 2&1&3&2 \end{pmatrix}$$

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 form of the augmented matrix.

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

$$\begin{pmatrix} 1&2&2&5\\ 3&1&4&2\\ 2&1&3&2 \end{pmatrix}$$

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:

$$\begin{pmatrix} 1&2&2&5\\ \color{red}3&1&4&2\\ \color{red}2&1&3&2 \end{pmatrix}$$

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

$$\begin{pmatrix} 1&2&2&5\\ 0&5&2&13\\ \color{red}2&1&3&2 \end{pmatrix}$$

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:

$$\begin{pmatrix} 1&2&2&5\\ 0&5&2&13\\ 0&3&1&8 \end{pmatrix}$$

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

$$\begin{pmatrix} 1&2&2&5\\ 0&\color{green}5&\color{green}2&\color{green}13\\ 0&\color{green}3&\color{green}1&\color{green}8 \end{pmatrix}$$

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:

$$\begin{pmatrix} 1&2&2&5\\ 0&5&2&13\\ 0&0&1&-1 \end{pmatrix}$$

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:

$$\begin{pmatrix} 1&\color{red}2&\color{red}2&5\\ 0&5&\color{red}2&13\\ 0&0&1&-1 \end{pmatrix}$$

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:

$$\begin{pmatrix} 1&2&\color{red}2&5\\ 0&5&\color{red}2&13\\ 0&0&1&-1 \end{pmatrix}$$

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

$$\begin{pmatrix} 1&2&2&5\\ 0&5&0&15\\ 0&0&1&-1 \end{pmatrix}$$

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

$$\begin{pmatrix} 1&2&0&7\\ 0&5&0&15\\ 0&0&1&-1 \end{pmatrix}$$

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:

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

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

$$\begin{pmatrix} 1&0&0&1\\ 0&1&0&3\\ 0&0&1&-1 \end{pmatrix}$$

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:

$$\begin{pmatrix} 1&0&0&1\\ 0&1&0&3\\ 0&0&1&-1 \end{pmatrix} \;\;\;\;\;\Longleftrightarrow\;\;\;\;\; \begin{cases} x=1\\ y=3\\ z=-1\\ \end{cases}$$

Great, we're done!

Example.

Gaussian elimination (2)

Consider the following system of linear equations:

$$\begin{cases} 2x_1+4x_2+x_3=1\\ 3x_1+1x_2+3x_3=8\\ 2x_1+2x_2+3x_3=5\\ \end{cases}$$

Use Gaussian Elimination to solve the system.

Solution. The augmented matrix is:

$$\begin{pmatrix} 2&4&1&1\\ 3&1&3&8\\ 2&2&3&5\\ \end{pmatrix}$$

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

$$\begin{pmatrix} 2&4&1&1\\ 3&1&3&8\\ 2&2&3&5\\ \end{pmatrix} \underset{(1)}{\implies} \begin{pmatrix} 2&4&1&1\\ 0&10&-3&-13\\ 2&2&3&5\\ \end{pmatrix} \underset{(2)}{\implies} \begin{pmatrix} 2&4&1&1\\ 0&10&-3&-13\\ 0&2&-2&-4\\ \end{pmatrix} \underset{(3)}{\implies} \begin{pmatrix} 2&4&1&1\\ 0&10&-3&-13\\ 0&0&7&7\\ \end{pmatrix} $$

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:

$$\begin{pmatrix} 2&4&1&1\\ 0&10&-3&-13\\ 0&0&7&7\\ \end{pmatrix}\underset{(4)}{\implies} \begin{pmatrix} 2&4&1&1\\ 0&10&-3&-13\\ 0&0&1&1\\ \end{pmatrix}$$

We now begin with the backward phase:

$$\begin{pmatrix} 2&4&1&1\\ 0&10&-3&-13\\ 0&0&1&1\\ \end{pmatrix} \underset{(5)}{\implies} \begin{pmatrix} 2&4&1&1\\ 0&10&0&-10\\ 0&0&1&1\\ \end{pmatrix} \underset{(6)}{\implies} \begin{pmatrix} 2&4&0&0\\ 0&10&0&-10\\ 0&0&1&1\\ \end{pmatrix} \underset{(7)}{\implies} \begin{pmatrix} 1&2&0&0\\ 0&1&0&-1\\ 0&0&1&1\\ \end{pmatrix}$$

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:

$$\begin{pmatrix} 1&0&0&2\\ 0&1&0&-1\\ 0&0&1&1\\ \end{pmatrix}$$

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

$$x=2,\;\;\;\;\; y=-1,\;\;\;\;\; z=1$$

We're done!

Theorem.

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.

Example.

Consistent systems

Consider the following row echelon form of some augmented matrix:

$$\begin{pmatrix} 3&8&4&\color{purple}5\\ 0&2&3&\color{purple}2\\ 0&0&5&\color{purple}3\\ \end{pmatrix}$$

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:

  1. the last row gives us $z$.

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

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

Similarly, consider the following row echelon form:

$$\begin{pmatrix} 3&8&4&\color{purple}5\\ 0&2&3&\color{purple}2\\ 0&0&0&\color{purple}0\\ \end{pmatrix}$$

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!

Example.

Inconsistent systems

Consider the following row echelon form of some augmented matrix:

$$\begin{pmatrix} 3&8&4&\color{purple}5\\ 0&2&3&\color{purple}2\\ 0&0&0&\color{purple}3\\ \end{pmatrix}$$

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.

Example.

Showing that a system is consistent (1)

Consider the following system of linear equations:

$$\begin{cases} 2x+3y&=1\\ 4x+y&=3\\ \end{cases}$$

Show that the system is consistent.

Solution. The augmented matrix of the system is:

$$\begin{pmatrix} 2&3&\color{purple}1\\ 4&1&\color{purple}3\\ \end{pmatrix}$$

Let's obtain the row echelon form:

$$\begin{pmatrix} 2&3&\color{purple}1\\ 4&1&\color{purple}3\\ \end{pmatrix}\sim \begin{pmatrix} 2&3&\color{purple}1\\ 0&5&\color{purple}-1\\ \end{pmatrix}$$

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

Example.

Showing that a system is consistent (2)

Consider the following simultaneous equations:

$$\begin{cases} 2x+3y&=1\\ 4x+6y&=2\\ \end{cases}$$

Show that the system is consistent.

Solution. The row echelon form is:

$$\begin{pmatrix} 2&3&\color{purple}1\\ 4&6&\color{purple}2\\ \end{pmatrix}\sim \begin{pmatrix} 2&3&\color{purple}1\\ 0&0&\color{purple}0\\ \end{pmatrix}$$

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.

Example.

Showing that a system is inconsistent

Consider the following system of linear equations:

$$\begin{cases} 2x+3y&=9\\ 2x+3y&=8\\ \end{cases}$$

Show that the system is inconsistent.

Solution. The row echelon form is:

$$\begin{pmatrix} 2&3&\color{purple}9\\ 2&3&\color{purple}8\\ \end{pmatrix}\sim \begin{pmatrix} 2&3&\color{purple}9\\ 0&0&\color{purple}1\\ \end{pmatrix}$$

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

Theorem.

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:

$$\begin{pmatrix} *&*&*&*&\color{blue}0\\ *&*&*&*&\color{blue}0\\ *&*&*&*&\color{blue}0\\ *&*&*&*&\color{blue}0\\ \end{pmatrix}$$

Performing elementary row operations on this augmented matrix:

  • does not affect the rightmost column whose entries are all zeros. For instance, multiplying a row by a scalar will keep the 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.

robocat
Published by Isshin Inada
Edited by 0 others
Did you find this page useful?
thumb_up
thumb_down
Comment
Citation
Ask a question or leave a feedback...