04 Pre-Class Assignment: Gauss-Jordan Elimination#

Assignment Overview#

The Syntax for Systems of Linear Equations
Introduction to Gauss Jordan Elimination
Gauss Jordan Elimination and the Reduced Row Echelon Form
Gauss Jordan Practice

1. The Syntax for Systems of Linear Equations#

The following video explains the different syntax we use to describe linear systems.

from IPython.display import YouTubeVideo
YouTubeVideo("AQJeOg4ZoIk",width=640,height=360, cc_load_policy=True)

The following is a summary of the syntax shown in the video:

Linear Equation#

\[b = a_1x_1+a_2x_2+a_3x_3 + \ldots a_nx_n\]

System of linear equations (Equation form)#

\[\begin{split}\begin{align*} b_1 &= a_{11}x_1+a_{12}x_2+a_{13}x_3 + \ldots + a_{1n}x_n \\ b_2 &= a_{21}x_1+a_{22}x_2+a_{23}x_3 + \ldots + a_{2n}x_n\\ b_3 &= a_{31}x_1+a_{32}x_2+a_{33}x_3 + \ldots + a_{3n}x_n\\ & \hspace{0.08 in} \vdots \\ b_m &=a_{m1}x_1+a_{m2}x_2+a_{m3}x_3 + \ldots + a_{mn}x_n \end{align*} \end{split}\]

System of linear equations (Matrix form)#

\[\begin{split} \left[ \begin{matrix} b_1 \\ b_2 \\ b_3 \\ \vdots \\ b_m \end{matrix} \right] = \left[ \begin{matrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n} \\ a_{31} & a_{32} & a_{33} & \cdots & a_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & a_{m3} & \cdots & a_{mn} \end{matrix} \right] \left[ \begin{matrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_m \end{matrix} \right] \end{split}\]

\[b=Ax\]

System of linear equations (Augmented form)#

\[\begin{split} \left[ \begin{matrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n} \\ a_{31} & a_{32} & a_{33} & \cdots & a_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & a_{m3} & \cdots & a_{mn} \end{matrix} \, \middle\vert \, \begin{matrix} b_1 \\ b_2 \\ b_3 \\ \vdots \\ b_m \end{matrix} \right] \end{split}\]

2. Introduction to Gauss Jordan Elimination#

A system of linear equations can have:

no solutions
exactly one solution
infinitely many solutions

Solving a system of equations means being able to find all solutions and know that you have found them all. Gauss-Jordan elimination is a method to simplify a system of equations so that you can determine all of the solutions.

There are three elementary row operations that you can perform on a system of equations in augmented matrix form:

Interchange two rows of a matrix
Multiply the elements of a row by a nonzero constant
Add a multiple of the elements of one row to the corresponding elements of another

One can show that performing any of these elementary row operations on a system of equations won’t change the set of solutions. Hence, we can repeatedly perform these operations without changing the set of solutions until the system of equations is simple enough to know what the solutions are. This process of repeatedly performing elementary row operations to solve a system of equations is called Gauss-Jordan elimination. The following video uses Gauss-Jordan elimination to solve a system of $3$ equations with $3$ variables.

from IPython.display import YouTubeVideo
YouTubeVideo("iGmtmF_hm2g",width=640,height=360, cc_load_policy=True)

Consider the element $a_{21}$ in the following augmented matrix $\left[A | b \right]$.

\[\begin{split} \left[A | b \right] = \left[ \begin{matrix} 1 & 1 \\ 20 & 25 \end{matrix} \, \middle\vert \, \begin{matrix} 30 \\ 690 \end{matrix} \right] \end{split}\]

✅ QUESTION: : Describe an elementary row operation that could be used to make element $a_{21}$ zero?

Put your answer here.

✅ QUESTION: : What is the new augmented matrix given the above row operation?

Modify the contents of this cell and put your answer to the above question here.

\[\begin{split} \left[A | b \right] = \left[ \begin{matrix} 1 & 1 \\ 0 & ?? \end{matrix} \, \middle\vert \, \begin{matrix} 30 \\ ?? \end{matrix} \right] \end{split}\]

Hint, we are using a formating language called $\LaTeX$ to display the above matrix. You should just be able to replace the ?? with your new numbers. If you can’t figure out what is going on, try searching the web with “latex math and matrix.” If it still doesn’t make sense, format your answer in another way that will be clear to understand by the you and the instructor.

3. Gauss Jordan Elimination and the Reduced Row Echelon Form#

In the previous video, the system had the same number of variables and equations, and there was exactly one solution. So we were able to reduce the augmented matrix such that the left side was the identity matrix ($1$’s on the diagonal, $0$’s elsewhere), and the right side was the unique solution. However, not all systems of equations will be like that. How do we know when our augmented matrix is “simple enough” so we can stop simplifying things?

Row Echelon Form (REF)#

A matrix is in Row Echelon Form (REF) if it satisfies the following $3$ properties.

Any rows consisting entirely of zeros are grouped at the bottom of the matrix.
The first nonzero element of each other row is $1$. (This element is called a “leading 1” or a “pivot”)
The leading 1 of each row after the first is positioned to the right of the leading one in the previous row.

Reduced Row Echelon Form (RREF):#

A matrix is in Reduced Row Echelon Form (RREF) if it is in REF (satisfies 1-3 above) and

All other elements in a column that contains a leading 1 are zero.

Once we get the matrix into REF, Gauss-Jordan elimination is “all downhill from there”.

Once we get the matrix into RREF, it is simple enough for us to write down the simplified system in equation form and solve for all the solutions.

Example#

Suppose we performed elementary row operations on a linear system with $4$ equations and $5$ variables to the following augmented matrix in RREF $$ \left[ \begin{matrix} 1 & 2 & 0 & 3 & 0 \\ 0 & 0 & 1 & 2 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} \, \middle\vert \, \begin{matrix} 4 \\ 7 \\ 6 \\ 0 \end{matrix} \right] $$

In equation form, this becomes $$\begin{align*} x_1 + 2x_2 + 3x_4 &= 4 \\ x_3 + 2x_4 &= 7 \\ x_5 &= 6 \\ 0 &= 0 \end{align*}$$

The variables corresponding to a column with a leading $1$ are called pivot variables, and the variables corresponding to a column without a leading $1$ are called free variables. To obtain all solutions, you can allow the free variables to be any real numbers, and then solve for the pivot variables in terms of the free variables.

In our example, columns $1$, $3$, and $5$ have leading $1$’s. So, $x_1$, $x_3$, and $x_5$ are pivot variables and $x_2$ and $x_4$ are free variables.

If we solve the above equations for $x_1$, $x_3$, and $x_5$ in terms of $x_2$ and $x_4$, we get $$\begin{align*} x_1 &= -2x_2 - 3x_4 + 4 \\ x_3 &= -2x_4 + 7 \\ x_5 &= 6 \\ \end{align*}$$

So, the solutions to the system of equations are $$x = \begin{bmatrix}-2x_2-3x_4+4 \\ x_2 \\ -2x_4 + 7 \\ x_4 \\ 6\end{bmatrix} \quad \text{ for any real numbers } x_2 \text{ and } x_4.$$ Note that every vector in the above form is a solution to the system of equations, and every solution to the system of equations is of the above form.

4. Gauss Jordan Practice#

✅ DO THIS:: Solve the following system of linear equations using the Gauss-Jordan algorithm. Try to do this before watching the video!

\[\begin{split} \begin{array}{rrr} x_1 + x_3 &=& 3\\ 2x_2 - 2x_3 &=& -4\\ x_2 - 2x_3 &=& 5 \end{array} \end{split}\]

Put your answer here

In the following video, we solve the same set of linear equations. Watch the video after trying to do this on your own. It is provided here in case you get stuck.

from IPython.display import YouTubeVideo
YouTubeVideo("xT16yIVw_KE",width=640,height=360, cc_load_policy=True)

Written by Dr. Dirk Colbry, Michigan State University with some modifications by Dr. Santhosh Karnik, Michigan State University.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

###STARTFOOTER###

CMSE/MTH 314 Course Website

04 Pre-Class Assignment: Gauss-Jordan Elimination

Contents