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