Skip to content

Instantly share code, notes, and snippets.

@oelmekki
Last active July 30, 2016 16:13
Show Gist options
  • Save oelmekki/56820e3ecb1ee1d9f66bbf510bffbac5 to your computer and use it in GitHub Desktop.
Save oelmekki/56820e3ecb1ee1d9f66bbf510bffbac5 to your computer and use it in GitHub Desktop.
Reduced row echelon with rows expansion

Reduced row echelon with rows expansion

Learning about matrices on KhanAcademy, I came to a great video from Sal Khan explaining how to use matrices to solve equations. Thanks!

What occured to me while watching the demonstration was that it seems inefficient to reuse the same rows to drop results, because we lose potentially valuable previous rows, which could help us in further steps. My initial thought was : "we could probably make this more easy/efficient by create new rows for the results", so I decided to play with that idea.

Initial demonstration

Here is the equation system Sal started from:

     1   1   1   |   3
A =  1   2   3   |   0
     1   3   4   |   -2

And here is his initial demonstration (btw, sorry if I misuse terminology, I'm not from a math background):

a2 - a1 -> a2
a3 - a1 -> a3
a1 - a2 -> a1
a3 - 2(a2) -> a3
a3 * -1 -> a3
a1 + a3 -> a1
a2 - 2(a3) -> a2

It's the standard way of solving this, if I got this right, and it takes 7 steps to solve the system.

Same demonstration, with rows expansion

I first wanted to rewrite the exact same solution but with rows expansion, to act as a reference.

Let's define two rules:

  • rows are immutable, you can't override a previously existing row with an instruction's result
  • the result of an instruction is stored in a new row, appended at the end of the matrix

Ok, let's go. I'll rewrite Sal demonstration using those rules. I'll show the state of the matrix at each step to make the behavior clear. As we'll add a lot of rows, I'll add a -> visual helper before each manipulated row in the current instruction to make them easier to spot.

    a2 - a1 -> a4
 -> 1   1   1   |   3
 -> 1   2   3   |   0
    1   3   4   |   -2
    0   1   2   |   -3
    a3 - a1 -> a5
 -> 1   1   1   |   3
    1   2   3   |   0
 -> 1   3   4   |   -2
    0   1   2   |   -3
    0   2   3   |   -5
    a1 - a4 -> a6
 -> 1   1   1   |   3
    1   2   3   |   0
    1   3   4   |   -2
 -> 0   1   2   |   -3
    0   2   3   |   -5
    1   0   -1  |   6
    a5 - 2(a4) -> a7
    1   1   1   |   3
    1   2   3   |   0
    1   3   4   |   -2
 -> 0   1   2   |   -3
 -> 0   2   3   |   -5
    1   0   -1  |   6
    0   0   -1  |   1
    a7 * -1 -> a8
    1   1   1   |   3
    1   2   3   |   0
    1   3   4   |   -2
    0   1   2   |   -3
    0   2   3   |   -5
    1   0   -1  |   6
 -> 0   0   -1  |   1
    0   0   1   |   -1
    a6 + a8 -> a9
    1   1   1   |   3
    1   2   3   |   0
    1   3   4   |   -2
    0   1   2   |   -3
    0   2   3   |   -5
 -> 1   0   -1  |   6
    0   0   -1  |   1
 -> 0   0   1   |   -1
    1   0   0   |   5
    a4 - 2(a8) -> a10
    1   1   1   |   3
    1   2   3   |   0
    1   3   4   |   -2
 -> 0   1   2   |   -3
    0   2   3   |   -5
    1   0   -1  |   6
    0   0   -1  |   1
 -> 0   0   1   |   -1
    1   0   0   |   5
    0   1   0   |   -1

So, we'll end up with that matrix:

0   0   1   |   -1
1   0   0   |   5
0   1   0   |   -1

... which solves equation systems the exact same way than initial demonstration, in 7 steps. Good.

Here are the steps:

a2 - a1 -> a4
a3 - a1 -> a5
a1 - a4 -> a6
a5 - 2(a4) -> a7
a7 * -1 -> a8
a6 + a8 -> a9
a4 - 2(a8) -> a10

Solving it faster with rows expansion

Using rows expansion, I could solve it in 5 steps. I wouldn't be suprised people more used to maths than me could do it in less.

Ok, let's look at initial matrix, as a reminder:

     1   1   1   |   3
A =  1   2   3   |   0
     1   3   4   |   -2

I will use the same notation as previously.

    a3 - a2 -> a4
    1   1   1   |   3
 -> 1   2   3   |   0
 -> 1   3   4   |   -2
    0   1   1   |   -2
    a1 - a4 -> a5
 -> 1   1   1   |   3
    1   2   3   |   0
    1   3   4   |   -2
 -> 0   1   1   |   -2
    1   0   0   |   5
    a2 - a1 -> a6
 -> 1   1   1   |   3
 -> 1   2   3   |   0
    1   3   4   |   -2
    0   1   1   |   -2
    1   0   0   |   5
    0   1   2   |   -3
    a6 - a4 -> a7
    1   1   1   |   3
    1   2   3   |   0
    1   3   4   |   -2
 -> 0   1   1   |   -2
    1   0   0   |   5
 -> 0   1   2   |   -3
    0   0   1   |   -1
    a6 - 2(a7) -> a8
    1   1   1   |   3
    1   2   3   |   0
    1   3   4   |   -2
    0   1   1   |   -2
    1   0   0   |   5
 -> 0   1   2   |   -3
 -> 0   0   1   |   -1
    0   1   0   |   -1

And we solved it.

The solved matrix:

1   0   0   |   5
0   0   1   |   -1
0   1   0   |   -1

Here is the solution:

a3 - a2 -> a4
a1 - a4 -> a5
a2 - a1 -> a6
a6 - a4 -> a7
a6 - 2(a7) -> a8

5 steps, yay! Note that we could do that because we used a1 two times (at step 2 and step 3) and we reused the intermediate result a4 two times too, instead of overriding at first use.

I couldn't find a way to use this shorter path without rows expansion. This is why I think this makes things more efficient: we don't lose precious ammo.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment