Solving linear system using matrices a, ex from book-- I'm missing something!

• Jul 10th 2012, 03:02 PM
glock
Solving linear system using matrices a, ex from book-- I'm missing something!
Hello all!
Thanks in advance for looking at this for me.

I seem to missing a step somewhere as I am working through the example provided by this book.
Mathematics for 3D Game Programming and Computer Graphics - Eric Lengyel - Google Books

The link shows the exact problem and solution. I am having a hard time understanding how the matrix in figure 2.18 transitions into the matrix shown in figure 2.19. I have been stumped on this for literally hours working ahead and back again trying to get my work to match the examples. Hopefully, Im not just having a brain fart, but I was hoping someone would be able to provide a better explanation, specifically what we are doing the the first row of the matrix when the text saw we are effecting the second row.

Thanks
Glock
• Jul 10th 2012, 03:40 PM
HallsofIvy
Re: Solving linear system using matrices a, ex from book-- I'm missing something!
?? They tell you exactly how to go from 2.18 to 2.19: "Moving to the second row, we multiply by $\frac{4}{17}$ to obtain a leading entry of 1".
The matrix in 2.18 is $\begin{bmatrix}1 & -\frac{3}{4} & \frac{3}{2} & \frac{7}{4} \\ 0 & \frac{4}{17} & -\frac{15}{2} & -\frac{73}{4} \\ 0 & \frac{3}{4} & -\frac{5}{2} & -\frac{73}{4}\end{bmatrix}$.

Since the "reduced echelon" form that we are shooting for has "1"s on the diagonal, we need to change that " $\frac{17}{4}$" to "1". We can do that by multiplying by its reciprocal $\frac{4}{17}$, just as they said. Of course, we are doing "row operations" here so mutliplying that number by $\frac{4}{17}$ means multiplying every number in the second row by $\frac{4}{17}$: $0(\frac{4}{17})= 0$, $\frac{17}{4}(\frac{4}{17}= 1$, $-\frac{15}{2}(\frac{4}{17}= \frac{30}{17}$, and $\frac{73}{4}(\frac{4}{17})= \frac{73}{17}$ giving 2.19:
$\begin{bmatrix}1 & -\frac{3}{4} & \frac{3}{2} & \frac{7}{4} \\ 0 & 1 & -\frac{30}{17} & -\frac{73}{17} \\ 0 & \frac{3}{4} & -\frac{5}{2} & -\frac{73}{4}\end{bmatrix}$
• Jul 10th 2012, 03:55 PM
glock
Re: Solving linear system using matrices a, ex from book-- I'm missing something!
Thanks for the quick response!

The problem is that figure 2.19 shows a difference in the first row without any explanation, or that I can see manipulation. UNLESS I am missing something.

Look at the first row of the matrix shown on 2.19. How/why?

Thanks,
Glock
• Jul 10th 2012, 04:33 PM
Deveno
Re: Solving linear system using matrices a, ex from book-- I'm missing something!
ok, the idea is we want to solve n equations in n unknowns "simultaneously". so say n = 3, so we have 3 such equations:

ax + by + cz = d
ex + fy + gz = h
kx + my + nz = p

we can write this a bit more "compactly" as the matrix equation:

A(x,y,z) = (d,h,p), where A is the matrix:

[a b c]
[e f g]
[k m n].

the idea behind "row-reduction" is that doing "row operations" doesn't change "the answers we get for x,y,z". some people don't trust this, at first. let's use a simpler example:

3x + 2y + z = 13
2x + y + 2z = 13
x - y + z = 2

ok, i will say ahead of time that (x,y,z) = (1,3,4) works.

now normally, what we would try to do is: "eliminate one variable". so we might multiply equation 1 by 2, and equation 2 by 3, and then subtract the "new" equation 2, from the "new" equation 1:

(multplying both sides of an equation doesn't change anything).

6x + 4y + 2z = 26
-6x - 3y - 6z = -39
________________
0x + y - 4z = -13 <---this equation only has 2 variables, y and z.

matrix-wise, this amounts to multiplying the first row by 2, and the second row by 3, to get:

[ 6 ..4 ..2 | 26 ]
[-6 -3 -6 | -33]
[ 1 -1 ..1 | ...2]

now the next step (where we add our "new" equations) corresponds to adding row 1 to row 2. we don't change row 1, ONLY row 2. this gives us:

[6 4 .2 | ..26]
[0 1 -4 | -13]
[1 -1 1 | ...2] (the dots are just "spacers" here, not decimal points).

at this point, we can replace row 1, by 1/6 row 1:

[1 2/3 1/3 | 13/3]
[0 ..1. .-4 | ..-13]
[1 .-1 ...1 | .....2]

all we've done is replace our first two equations with 2 different equations. note that these still work for x = 1, y = 3, z = 4:

1(1) + (2/3)(3) + (1/3)(4) = 1 + 2 + 4/3 = 3/3 + 6/3 + 4/3 = 13/3

1(3) + (-4)(4) = 3 - 16 = -13

to eliminate the "x" in the third equation, we can just subtract row one from row three, and replace what was in row three, with this "new" equation:

[1 2/3 1/3 | 13/3]
[0 ..1. ..-4 | .-13]
[0 -5/3 2/3 |-7/3] <---notice how the "bottom right" is now 2 equations in two unknowns. so basically, we're going to "repeat the process":

we multiply the last row by -3/5, and get:

[1 2/3 .1/3 | 13/3]
[0 ..1. ..-4 | ..-13]
[0 ..1. -2/5 | .7/5]

and subtract row 2 from row 3 (we keep row 2, but we replace row 3):

[1 2/3 ..1/3 | 13/3]
[0 ..1. ...-4 | ..-13]
[0 ..0. 18/5 | 72/5] <--one equation, one unknown! we know z!

just to make it nice and neat, we replace row 3 by 5/18 times row 3:

[1 2/3 1/3 | 13/3]
[0 ..1. ..-4 | ..-13]
[0 ..0. ...1 | .....4] <---z is 4.

essentially, we're done, now. z = 4, and y - 4z = -13, we have that y - 16 = -13, so y = 3. and from:

x + (2/3)y + (1/3)z = 13/3, we get:

x + 2 + 4/3 = 13/3
x + 2 = 9/3 = 3
x = 1, as we knew going in. but we can "clean up the matrix" (putting it in a "standard form"), by putting in as many 0's as possible (0's in a matrix are good, they reduce calculation steps). so now we "work up", replacing row 2 by: 4 times row 3 + row 2:

[1 2/3 1/3 | 13/3]
[0 ..1 ...0 | .....3] <---this makes it obvious y = 3
[0 ..0 ...1 | .....4]

we can "clear out the 1/3" in the first row, by subtracting 1/3 row 3 from row 1, and replacing row 1 with this subtraction:

[1 2/3 0 | 3]
[0 ..1. 0 | 3]
[0 ..0. 1 | 4]

just one more thing to do: "clear out the 2/3" in the first row, by replacing row 1 with: row 1 - (2/3)*(row 2):

[1 0 0 | 1]
[0 1 0 | 3]
[0 0 1 | 4]

which translates to the 3 equations:

x = 1
y = 3
z = 4.