gaussian elimination - struggling to understand why it's allowed or how it works

[giladgressel]

Hey, so starting in lecture 2, Strang jumps straight into gaussian elimination. I've seen this before, but it's still a little perplexing to me. I understand how to solve algebraic equations, and make y=mx + b form. I understand how to isolate variables if i have 2 equations with 2 unknowns and use substitution to solve for a single variable.

but gaussian elimination is something a little different. This concept of, multiply by the factor you want to get rid of and subtract, just seems so random.
Is this something that will get explained more? or should I look into on my own some?

[joshuacook]

Are you struggling because he seems to ignore the right hand side of the equation?

[giladgressel]

no, i'm not actually worried about the right hand side
I'm struggling to get why we are allowed to multiply the top equation and subtract it from the next.
like what math principle is that following from.
in regular algebra stuff, I get how "what you must do to one side of an equation, you must do the other"
in this case, i'm intuiting that it has to do with finding a solution for both equations, but don't really get why.

[giladgressel]

i guess this is what I want/need to read
http://math.stackexchange.com/questions/648013/proof-of-gaussian-elimination-why-does-it-work

You are probably familiar with the fact that when working with a system of equations you can add multiples of the equations together without affecting the solution. The truth of this statement is related to Euclid's common notions which are in fact axioms. This is why adding and subtracting the rows of a matrix do not affect the solution.

Furthermore you can exchange the rows of the matrix and the constant vector without affecting the solution because they yield the same equations for x,y,x,y, and zz.

So I'll look into this Euclid fellow and his common notions. which are in fact axioms heh.

[parambharat]

the math principle is basic substitution.
say you have 3 equations in x,y and z
x + y + z = 10 -- (1)
x + 2y + 2z = 30 -- (2)
x + 2y + 3z = 90 -- (3)

One way to solve it is:
express (1) as
x = 10 - y - z
substitute value of x in (2)
(10-y-z) + 2y + 2z = 30
10+y+z = 30 or y = 30-10-z = y = 20-z
substituting value of x and y from (1) and (2) in 3
(10-y-z) +2y + 3z = 90
10-y-z+ 2y+3z = 90
y+2z = 80
(20-z)+2z = 80 -- >z = 60
z = 60, y = -40, x = -10

There is another way.. Can you think of it ?

[ntaylorwss]

I'm going to take a stab at this. Let's say we have these 2 equations:

x+2y+3z = 11
4x+6y+5z = 31

So our first goal is to subtract 4x from equation 2. "Whatever we do to the left, we do to the right", so we'll need to subtract 4x from both sides. On the left is easy enough, but how do we subtract 4x from the right in a meaningful way? Well, if we look at equation 1, it's giving us a value for 4x:

# original equation
x+2y+3z = 11
# multiply both sides by 4
4x+8y+12z = 44
# isolate x
4x = 44 - 8y - 12z

So we can subtract 4x from the left because that's easy, and we can equivalently subtract (44-8y-12z) from the right:

4x + 6y + 5z = 31
# this becomes...
0x + 6y + 5z = 31 - (44 - 8y - 12z)
# simplify
6y + 5z = 31 - 44 + 8y + 12z
# now group the constants, the y's, and the z's (moving over the y's and z's from right to left)
(6y-8y) + (5z-12z) = (31-44)
# simplify again
-2y -7z = -13

And this is our new equation 2.

So all of this is to say: our goal was to subtract 4x from both sides, but in order to do that while making progress on the other variables (and the right side of the equation), we had to express x in terms of y and z. Once we did that, we could subtract 4x from the left and [new representation] from the right, and arrive at a simpler equation with one less variable.

[giladgressel]

hey! that makes total sense!! thank you!
the key line for me was

On the left is easy enough, but how do we subtract 4x from the right in a meaningful way?