The Matrix: harnessing the power of Gaussian Elimination
In this article, I’ll be focusing on the rules for row equivalence within a matrix structure. I’ll be skipping over a lot of detail regarding the reduced form of a matrix, and variations that such a form implies for the possible solutions of a linear system.
Remember: if you want more detail about these operations, there’s a great article from Wikipedia on Gaussian Elimination. (If you’re wondering just how Gaussian this elimination is, I suggest you start here.) Because we’re already pretty familiar with our cinema tickets example from my previous article, we’ll stick with it! Furthermore, it happens to have exactly one solution that should be relatively easy to obtain. We’ll only be considering the operations for row equivalence. How do we decide which matrix cells to focus our operations on? You can find those rules in the “Reduced row-echelon form” of this page from Carlton University. I want to jump right to the fun part: using row-equivalent matrices to solve a linear system with three variables.
Personally, I think of these problems as little puzzles. To me, they’re almost like a sudoku puzzle: you start with a matrix of numbers and you use that form, along with a set of rules, to obtain missing values. OK, so what’s the reduced form that will magically provide us with answers for all our variables? To explore a matrix in reduced form, we’ll continue using the same system of linear equations that we obtained from our friendly neighbourhood cinema employee in my previous article.
REDUCED FORM
The reduced form of our system for cinema ticket prices will look like this:
| x | y | z | Variable Value |
|---|---|---|---|
| 1 | 0 | 0 | = Value for x! |
| 0 | 1 | 0 | = Value for y! |
| 0 | 0 | 1 | = Value for z! |
Note that the location of each ‘1‘ indicates the variable for which we’re obtaining a value.
Now we know the form we’re aiming for, how do we get there?
The RULES FOR ROW-EQUIVALENCE
Fortunately, there are only three rules to follow!
1) Any row can change positions.
For example if you happen to have a ‘1‘ in the first column of the third row, you can make it swap spots with the first row. In other words, you can move the first row values into the third row, and move the third row values into the first row position.
2) You can multiply any row by a nonzero number.
You’re probably already familiar with this rule because you’ve likely used it when working with equations before. It’s the same operation here: when you multiply one side of an equation by a number, you must multiply the other side by the same number. That means when you multiply each coefficient in a row by a number, you also multiply the value in the last column by the same number.
3) You can add any two rows together, and place the result in one of those rows.
This is where elimination comes into play. We explored this operation a little in my previous article when we only had two variables. We zeroed-out our y-terms to isolate x. Here we’ll be doing the same thing, but we’ll zero out all other coefficients in a row except for the ‘1‘ in the column for which we’re obtaining a value.
The Syntax for expressing Row Operations
We’re going to use some new syntax for expressing each row operation.
We’ll let an upper-case ‘R’, followed by a number, represent a particular row.
For example: Row 1 is represented by R1, Row 2 is represented by R2, and Row 3 is represented by R3.
We’ll use an arrow to express the placement of a given row after completing an operation. Generally, a double-sided arrow represents two rows swapping positions. If you want R1 and R3 to exchange positions, you can represent that operation like this:
R1 <-> R3
When a new row operation is completed and we’re placing the result in a particular location, we use an arrow pointing to the right to indicate where the result is stored. Adding two rows together can be expressed like this:
R1 + R2 -> R2
Lets try it out!
I think we’re ready to tackle our cinema ticket problem! Here’s the augmented coefficient matrix that we ended up with for our linear system of cinema ticket prices:
| x | y | z | |
|---|---|---|---|
| 2 | 3 | 5 | 117 |
| 4 | 2 | 4 | 112 |
| 5 | 2 | 3 | 111 |
We’re looking for the values of x, y, and z that match each equation we were given.
Here’s a couple more tips…
Start with the upper left corner spot, move through all the values in that column, then proceed to the column on the right.
Always obtain the ‘1‘ in a column first, because you’ll use that ‘1‘ to zero-out the other values in that column.
With that in mind, here’s our first row operation: we’ll reduce that ‘2‘ in the first row to a ‘1‘. To do that, we’ll divide the entire row by 2 (or divide each value in half).
(1/2)R1 -> R1
When that operation is completed, here’s the next state of our matrix:
| x | y | z | |
|---|---|---|---|
| 2/2 | 3/2 | 5/2 | 117/2 |
| 4 | 2 | 4 | 112 |
| 5 | 2 | 3 | 111 |
Now we’re going to zero-out the ‘4‘ in the first column of the second row with this operation: (-4)R1 + R2 -> R2
R1: (-4)1 (-4)1.5 (-4)2.5 (-4)58.5
R2: +4 +2 +4 +112
When we add up the numbers in each column (vertically) we get the following result:
0 -4 -6 -122
We’ll place these new values in R2.
| x | y | z | |
|---|---|---|---|
| 1 | 1.5 | 2.5 | 58.5 |
| 0 | -4 | -6 | -122 |
| 5 | 2 | 3 | 111 |
The next operation is zeroing-out the first value in R3: (-5)R1 + R3 -> R3
R1: (-5)1 (-5)1.5 (-5)2.5 (-5)58.5
R3: +5 +2 +3 +111
R3: 0 -5.5 -9.5 -181.5
We’ll place these new values in R3.
| x | y | z | |
|---|---|---|---|
| 1 | 1.5 | 2.5 | 58.5 |
| 0 | -4 | -6 | -122 |
| 0 | -5.5 | -9.5 | -181.5 |
We’re done with the first column! Lets move on to the next ONE!
That’s right, we’ll start with the spot where we want to place a ‘1‘: which is R2.
(- 1/4)R2 -> R2
The next state of our matrix is:
| x | y | z | |
|---|---|---|---|
| 1 | 1.5 | 2.5 | 58.5 |
| 0 | 1 | 1.5 | 30.5 |
| 0 | -5.5 | -9.5 | -181.5 |
The next two operations involve zeroing-out the other two values in our y-column:
(-1.5)R2 + R1 -> R1
(5.5)R2 + R3 -> R3
It doesn’t matter which operation you do first. Once you’ve completed both, you should end-up with a matrix that looks like this:
| x | y | z | |
|---|---|---|---|
| 1 | 0 | 0.25 | 12.75 |
| 0 | 1 | 1.5 | 30.5 |
| 0 | 0 | -1.25 | -13.75 |
What’s the next step? We’re done with the second column, and we’re moving on to the last ONE.
(- 1/1.25)R3 -> R3
When that’s completed, the result for R3 is: 0 0 1 = 11
Guess what?! That’s the long-lost z-value we’ve been searching for!!!
This is getting exciting!! We’re almost done!
| x | y | z | |
|---|---|---|---|
| 1 | 0 | 0.25 | 12.75 |
| 0 | 1 | 1.5 | 30.5 |
| 0 | 0 | 1 | 11 |
All that’s left to do is zero-out the other two values in our z-column. Again, the order in which you complete these two operations doesn’t matter.
(-0.25)R3 + R1 -> R1
(-1.5)R3 + R2 -> R2
The final state of your matrix should look like this:
| x | y | z | |
|---|---|---|---|
| 1 | 0 | 0 | 10 |
| 0 | 1 | 0 | 14 |
| 0 | 0 | 1 | 11 |
CONCLUSION
Behold the magic of the matrix! Do those numbers look familiar?
x represents the price of tickets for members: $10
y represents the price of tickets for non-members: $14
z represents the price of tickets for seniors: $11
My favourite thing about algebra is that you can always verify your results by plugging them into your original equations. If you’re feeling skeptical about the z-value you found, go ahead and substitute all our values into any one of the equations we started with. Everything should match up! If it doesn’t then you know you’ve made a mistake somewhere.
One last tip: it’s very easy to make a mistake when completing matrix operations. The math itself may not be difficult, but you might write numbers down in the wrong spot. This is why I recommend not skipping steps. It may seem quicker to avoid unnecessary steps and write fewer things down, however if you happen to make a mistake it’s more difficult to locate something you haven’t actually written. I knew the answers ahead of time when completing all the above matrix operations, and I STILL made a mistake. I had to go back over each operation and figure out what I got wrong.
We’ve only just scraped the surface of what you can do with a matrix structure, the possibilities are endless. There’s the Simplex Method, Markov Chains, and Game Theory… just to name a few of the topics you can explore using this structure. I know “The Matrix” is a kind of villain in that famous movie series but don’t hate the structure, hate the game. When used wisely, there’s an endless number of real world problems we can solve with a matrix.