Gaussian Elimination Lesson

Up to this point, we have not discussed the concept of a matrix. A matrix is an ordered array of numbers. As an example: $$\left[ \begin{array}{ccc}7&3&1\\ 1&-2&4 \end{array}\right] $$ The entries in a matrix are referred to as "elements" of the matrix. When we refer to a row in a matrix, we are discussing the horizontal information. For example, in our above matrix, the top row has the numbers: 7, 3, and 1. Similarly, when we refer to a column in a matrix, we are discussing the vertical information. For example, in our above matrix, the leftmost column has the numbers: 7 and 1. A matrix is named according to the number of rows and columns it contains. The number of rows comes first, followed by the number of columns. In our above example, we have two rows and three columns. Therefore, we can say this is a "2 x 3" matrix. As another example, suppose we saw the following matrix: $$\left[ \begin{array}{ccc}-2&9&-6\\ 4&5&8\\ 11&-7&2\\ 17&6&-5 \end{array}\right] $$ For our above matrix, we can see that there are four rows and three columns. We can say this matrix is a "4 x 3" matrix. A square matrix has the same number of rows as columns:
2 x 2 Matrix:
A "2 x 2" matrix is a square matrix with two rows and two columns. $$\left[ \begin{array}{cc}8&1\\ -1&3 \end{array}\right] $$ 3 x 3 Matrix
A "3 x 3" matrix is a square matrix with three rows and three columns. $$\left[ \begin{array}{ccc}12&-5&4\\ 9&-7&13\\ -6&8&4 \end{array}\right] $$

Solving Linear Systems using Matrix Methods

Now that we have a basic understanding of a matrix, let's think about how to solve a linear system using matrix methods. Let's begin with a sample system. $$-17-7x-6y=0$$ $$-30-8y=2x$$ Let's start by writing the equations in standard form: $$-7x - 6y=17$$ $$2x + 8y=-30$$ Now we will create the augmented matrix. The augmented matrix has a vertical bar that separates the coefficients from the constants. Basically, we are taking all the numerical information from the two equations and placing it into a matrix: $$\left[ \begin{array}{cc|c}-7&-6&17\\ 2&8&-30 \end{array}\right] $$ Our first row contains the numerical information from the first equation: -7, -6, and 17. The second row contains the numerical information from the second equation: 2, 8, and -30. Notice how the vertical bar "|" separates the coefficients from the constants.
We can manipulate our matrix using "elementary row operations". These produce new matrices that lead to linear systems with the same solution(s) as the original system.

Elementary Row Operations

• We can interchange any two rows
• We can multiply any row by a non-zero number
• We can multiply a row by a real number and add this to the corresponding elements of any other row

Let's think about the row operations with a bit more detail. The first row operation tells us we can interchange any two rows. When solving equations, it doesn't matter which equation is on the top and which is on the bottom: $$-7x - 6y=17$$ $$2x + 8y=-30$$ is the same system as: $$2x + 8y=-30$$ $$-7x - 6y=17$$ Therefore, we can interchange the rows: $$\left[ \begin{array}{cc|c}-7&-6&17\\ 2&8&-30 \end{array}\right] $$ represents the same system as: $$\left[ \begin{array}{cc|c}2&8&-30\\ -7&-6&17 \end{array}\right] $$ The second row operation tells us we can multiply any row by a non-zero number. We already know that the multiplication property of equality lets us multiply both sides of an equation by the same non-zero number. Let's suppose we take our second (bottom) equation and multiply both sides by 1/2: $$2x + 8y=-30$$ $$x + 4y=-15$$ We can rewrite our system as: $$-7x - 6y=17$$ $$x + 4y=-15$$ Similarly, we can multiply row 2 of the augmented matrix by 1/2: $$\left[ \begin{array}{cc|c}-7&-6&17\\ 2&8&-30 \end{array}\right] $$ Which produces the following augmented matrix: $$\left[ \begin{array}{cc|c}-7&-6&17\\ 1&4&-15 \end{array}\right] $$ The third and final row operation corresponds to the way we eliminated a variable when using the elimination method. If we look at our system: $$-7x - 6y=17$$ $$x + 4y=-15$$ We see that we could eliminate the variable x by multiplying equation 2 (the bottom equation) by 7 and adding the result to equation 1 (the top equation). $$x + 4y=-15$$ Multiply by 7: $$7x + 28y=-105$$ Add to equation 1: $$-7x + -6y=17$$ $$\underline{7x+28y=-105}$$ $$0x + 22y=-88$$ $$22y=-88$$ $$y=-4$$ We can then substitute back into one of the original equations and find the value for x. Before we do this, let's see how this works with an augmented matrix: $$\left[ \begin{array}{cc|c}-7&-6&17\\ 1&4&-15 \end{array}\right] $$ We will first swap row 1 and 2, this is to stay consistent with row echelon form, which we will learn about momentarily. $$\left[ \begin{array}{cc|c}1&4&-15\\ -7&-6&17 \end{array}\right] $$ Multiply row 1 by 7 and add the result to row 2: $$\left[ \begin{array}{cc|c}1&4&-15\\ 0&22&-88 \end{array}\right] $$ If we look at the information from row 2, we can write this as: $$0x + 22y=-88$$ Which is exactly what we saw earlier when using elimination. In a moment, we will show how to complete the process using an augmented matrix. It is important to understand that we are fundamentally using the same techniques, just using the numerical information only. This makes things quicker and simpler. Let's now look at row echelon form.

Row Echelon Form

The goal of Gaussian Elimination is to place the augmented matrix in "row echelon" form. This gives us "1's" down the diagonal and "0's" below. $$\left[ \begin{array}{cc|c}1&a&b\\ 0&1&c \end{array}\right] $$ Once our matrix is in row echelon form, we can easily use substitution to find the solution. Let's return to our example and go step by step: $$-7x - 6y=17$$ $$x + 4y=-15$$ Augmented Matrix: $$\left[ \begin{array}{cc|c}-7&-6&17\\ 1&4&-15 \end{array}\right] $$ It is best to work column by column. In the first column, at the top, we have a "-7". We want this to be a 1. The easiest thing to do here is to swap row 1 and 2. $$\left[ \begin{array}{cc|c}1&4&-15\\ -7&-6&17 \end{array}\right] $$ Now we want the bottom of the first column to be a 0. We can multiply the top row by 7 and add the result to the bottom row: $$\left[ \begin{array}{cc|c}1&4&-15\\ 0&22&-88 \end{array}\right] $$ At this point, we know we could get a solution for y. We will not stop here, we will continue and make the bottom entry in the second column into a 1. In order to do this, we will multiply row 2 by 1/22: $$\left[ \begin{array}{cc|c}1&4&-15\\ 0&1&-4 \end{array}\right] $$ At this point, we have achieved row echelon form. We can go back to our equations using this information and achieve our answer using substitution. If we take the numerical information and place it back into the system: $$1x + 4y=-15$$ $$0x + 1y=-4$$ From the second equation, we see that y is -4. We can plug in a -4 for y in the first equation and solve for x: $$1x + 4(-4)=-15$$ $$x - 16=-15$$ $$x=1$$ Our solution is the ordered pair (1, -4). This may seem like it took longer, but as we learn more about solving systems with matrices, we will find this is the faster and preferred method. Especially in the case of systems with many equations. Let's check our answer:
-7x - 6y = 17
-7(1) - 6(-4) = 17
-7 + 24 = 17
17 = 17 ✔
x + 4y = -15
(1) + 4(-4) = -15
1 + (-16) = -15
-15 = -15 ✔

Reduced-Row Echelon Form

Although we can find our solution using substitution when the augmented matrix is in row echelon form, we can keep working on the matrix until it is reduced-row echelon form. This format gives us "1's" down the diagonal and "0's" above and below. $$\left[ \begin{array}{cc|c}1&0&a\\ 0&1&b \end{array}\right] $$ When the matrix is in reduced-row echelon form, we can obtain the solution directly from the matrix, no substitution is needed. Let's go back to our last spot on our example, where we were using the matrix. $$\left[ \begin{array}{cc|c}1&4&-15\\ 0&1&-4 \end{array}\right] $$ At this point, we know that y is -4. Since in row 2, 0 is the coefficient for x, and 1 is the coefficient for y. We know this translates into: $$0x + 1y=-4$$ $$y=-4$$ To obtain reduced-row echelon form, we need to change the 4 at the top of column 2 into a 0. We can do this by multiplying row 2 by -4, and adding the result to row 1: $$\left[ \begin{array}{cc|c}1&0&1\\ 0&1&-4 \end{array}\right] $$ Now we know from our matrix that x is 1. In the top row, the information translates into: $$1x + 0y=1$$ $$x=1$$

Gaussian Elimination vs Gauss-Jordan

Let's clarify a point of confusion. You will hear a few different names floating around for solving systems with matrices. We will hear the terms "Gaussian Elimination" and "Gauss-Jordan". What's the difference between the two?
Gaussian Elimination places the matrix in row echelon form and requires us to go back and substitute to get the final answer. Gauss-Jordan places the matrix in reduced-row echelon form and does not require substitution. It's just a matter of personal preference, but it is usually faster to use Gauss-Jordan and obtain the solution directly from the augmented matrix.

Gauss-Jordan Two-Variable System

• Obtain a 1 as the first element in the first column
• Use the first row to transform the remaining element in the first column into a 0
• Obtain a 1 as the second element in the second column
• Use the second row to transform the remaining element in the second column into a 0

In other words, we transform an augmented matrix into reduced-row echelon form, working left to right, focusing on one column at a time. Let's look at a few examples.
Example 1: Solve each system using the Gauss-Jordan method $$-7x+2y=-4$$ $$-14x-3y=6$$ Let's begin by setting up the augmented matrix: $$\left[ \begin{array}{cc|c}-7&2&-4\\ -14&-3&6 \end{array}\right] $$ First, we want to obtain a 1 as the first element in the first column. We can multiply row 1 by -1/7: $$\left[ \begin{array}{cc|c}1&-2/7&4/7\\ -14&-3&6 \end{array}\right] $$ Next, we want to obtain a 0 as the second element in the first column. We can multiply row 1 by 14 and add the result to row 2: $$\left[ \begin{array}{cc|c}1&-2/7&4/7\\ 0&-7&14 \end{array}\right] $$ Now that column 1 is complete, we move on to column 2. Let's begin with the second element in column 2. We want this to be a 1. We can multiply row 2 by -1/7: $$\left[ \begin{array}{cc|c}1&-2/7&4/7\\ 0&1&-2 \end{array}\right] $$ For our final step, we want the first element in column 2 to be a 0. We can multiply row 2 by 2/7 and add the result to row 1: $$\left[ \begin{array}{cc|c}1&0&0\\ 0&1&-2 \end{array}\right] $$ We can translate this back into: $$1x + 0y=0$$ $$0x + 1y=-2$$ $$x=0$$ $$y=-2$$ Our solution is the ordered pair (0,-2) Let's check using substitution:
-7x + 2y = -4
-7(0) + 2(-2) = -4
0 - 4 = -4
-4 = -4 ✔
-14x - 3y = 6
-14(0) - 3(-2) = 6
0 + 6 = 6
6 = 6 ✔

Inconsistent Systems and Dependent Equations

When we run into special case scenarios, such as inconsistent systems (systems with no solution) or dependent equations (systems with an infinite number of solutions), we will see all coefficients entries in a row as a 0. The constant in the row will be a 0 for dependent equations or a non-zero number for an inconsistent system. Let's look at an example.
Example 2: Solve each system using the Gauss-Jordan method $$-18x-24y=11$$ $$-3x-4y=2$$ Let's begin by setting up the augmented matrix: $$\left[ \begin{array}{cc|c}-18&-24&11\\ -3&-4&2 \end{array}\right] $$ First, we want to obtain a 1 as the first element in the first column. We can multiply row 1 by -1/18: $$\left[ \begin{array}{cc|c}1&4/3&-11/18\\ -3&-4&2 \end{array}\right] $$ Next, we want to obtain a 0 as the second element in the first column. We can multiply row 1 by 3 and add the result to row 2: $$\left[ \begin{array}{cc|c}1&4/3&-11/18\\ 0&0&1/6 \end{array}\right] $$ We can stop once we see a 0 as the entry for each coefficient. Row 2 translates into: $$0x + 0y=\frac{1}{6}$$ $$0=\frac{1}{6}$$ Since we have a false statement, this tells us there is no solution.

---

Skills Check: