• Support PF! Buy your school textbooks, materials and every day products Here!

Linear algebra row reduction

  • Thread starter cdotter
  • Start date
  • #1
305
0
How exactly do you decide which operations to do in doing a matrix row reduction? Every example I see just randomly multiplies the rows or does row operations and magically they get the answer. HOW do you know to do certain operations? I understand the reduced row echelon form but it still doesn't help me.

[PLAIN]http://img232.imageshack.us/img232/4274/88315354.png [Broken]
 
Last edited by a moderator:

Answers and Replies

  • #2
33,507
5,192
The operations aren't at all random. The goal is to get a 1 entry in the upper left corner, and 0s below it, then a 1 in the middle entry, with 0's below it (and above it if you're going for reduced row-echelon form). Finally, get a 1 in the lower right entry (and 0s above for reduced row-echelon form).

Sometimes people will swap row if it looks like it might reduce the number of steps. In this case I might swap rows 1 and 2, and then replace row 1 by -1 times itself. That would give me
[tex]\left[ \begin{array}{c c c} 1 & -1 & 1 \\ 2 & 1 & 8\\-2 & 5 & 4 \end{array}\right] [/tex]

I would then use the 1 in the upper left to elimanate the entries directly below it, and so on, as described above.
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,833
955
Or, for a strict, "algorithmic" method:
work one column at at time.
1. Divide every term in the first row by 2.
2. Subtract the first row multiplied by whatever number is in each of the other rows from that row. That is
a) subtract -1 times the first row from the second row.
b) subtract -2 times the first row from the third row.

That will give you
[tex]\begin{bmatrix} 1 & \frac{1}{2} & 4 \\ 0 & \frac{3}{2} & 3 \\ 0 & 6 & 12\end{bmatrix}[/tex]

Then, for the second row do basically the same thing, dividing the second row by 3/2 to get "1" at that position. Notice that, because of those "0"s in the first column, nothing you do will change the first column!
 
  • #4
305
0
I can do the operations but I just end up going in circles never getting to [1, 0, 0] [0, 1, 0] [0, 0, 1]. How do you know what to do without doing a million steps?
 
  • #5
305
0
I think I solved it? {[1, 0, 3] [0, 1, 2] [0, 0, 0]}
 
  • #6
33,507
5,192
Yes, that's it.
 
  • #7
305
0
This is really frustrating me. The piece of **** book my idiot professor is using, A First Course in Linear Algebra by Robert Beezer, is not written for sophomores as it gives absolutely no problem solving techniques or useful examples. I think it assumes previous knowledge in linear algebra and discrete structures because I have no idea what it's talking about most of the time, but anyways...could someone recommend me a book at the sophomore level?
 
  • #8
HallsofIvy
Science Advisor
Homework Helper
41,833
955
Did you not understand what I (and Mark44) said? Start with the left column and work to the right. For each column, make the "pivot" number (the number on the main diagonal) by dividing that entire row by the number that is there to start with. Then get the number each row above below that "pivot" row (the one containing the pivot number) equal to 0 by subtracting the "pivot" row times that number from the row.

If the first column were
[tex]\begin{bmatrix}a \\ b \\ c[/tex]
the "pivot" row is the first row and the "pivot" number is a. Divide each number in the first row by a. Now you have
[tex]\begin{bmatrix}1 \\ b \\ c\end{bmatrix}[/tex]
and you want "0" in place of "b" and "c". Subtract the first row time b from the second row. Subtract the first row times c from the third row. Since you now have "1" in the first row, you will be subtracting b- b and c- c in the second and third rows and have "0" there:
[tex]\begin{bmatrix}1 \\ 0\\ 0\end{bmatrix}[/tex]

Suppose, after that, the second column is
[tex]\begin{bmatrix}d \\ e\\ f\end{bmatrix}[/tex].
Since this is the second column, the "pivot" row is the second row. The "pivot" number is e. Divide the entire second row by e so the second column is now
[tex]\begin{bmatrix}d \\ 1 \\ f\end{bmatrix}[/tex]

To get "0"s in place of f, subtract f times the second row from the third row. At this point you have
[math]\begin{bmatrix}1 & d & * \\ 0 & 1 & * \\ 0 & 0 & *\end{bmatrix}[/math]
where the "*"s in the third column indicate the numbers that we need to "fix" yet. Of course, they will NOT be the same numbers that were in the original matrix since they have been changed by the "dividing" and "subtracting" of the entire rows.

("Reduced row-echelon" has "0"s both above and below the "pivot". You would get the "0" above the "pivot" number by subtracting d times the second row from the first row.)

Suppose those number in the third (and, in this example, last) column are \
[tex]\begin{bmatrix}g \\ h \\ i\end{bmatrix}[/tex]
Since this is the third column the "pivot" row is the third row and the "pivot" number is i. Get a "1" there by dividing the entire third row by i. Now we have
[tex]begin{bmatrix}g \\ h \\ 1\end{bmatrix}[/tex]
For "row-echelon" that's all you have to do. For "reduced row-echelon" you would want to get "0" in the first and second rows of the third column by subtracting as above.
The example you gave in your post,
[tex]\begin{bmatrix} 2 & 1 & 8 \\ -1 & 1 & -1 \\ -2 & 5 & 4\end{bmatrix}[/tex]
would go like this:

Divide every number in the first column by 2 to get a "1" in the first column. Then subtract -1 times the new first row (add 1 times the new first row) from the second row and subtract -2 times the new first row (add 2 times the new first row) from the third row. That gives
[tex]\begin{bmatrix}1 & \frac{1}{2} & 4 \\ 0 & \frac{3}{2} & 3 \\ 0 & 6 & 12\end{bmatrix}[/tex]
That is exactly what I gave before.

Look at the second column. The "pivot" row is the second row and the "pivot" number is [math]3/2[/math]. Divide every number in the second rwo by [math]\frac{3}{2}[/math]. Then, since there is a "6" just below that "pivot" number, subtract 6 times the second row from the third. You should now have:
[tex]\begin{bmatrix}1 & \frac{1}{2} & 4 \\ 0 & 1 & 2 \\ 0 & 0 & 0\end{bmatrix}[/tex]

We would like to have a "1" in the third row, third column, but we can't. This matrix is not "invertible" (one way of finding an inverse for a matrix is to put it into "reduced row-echeolon" form, which would give you the identity matrix, while simultaneously performing the same row-operations on the identity matrix- if you can't do that, the matrix is not invertible). But what we have is the "row-echelon" form for this matrix.

Mark44 started by swapping two rows- that can make the calculations easier. Since we always divide a row by the "pivot" number, if that number happens to be 0, we will need to swap with a lower row. If there are NO non-zero numbers lower in the same column, that means the matrix is not invertible and you cannot proceed. What you have is the "row-reduced" matrix.
 

Related Threads on Linear algebra row reduction

  • Last Post
Replies
1
Views
1K
Replies
4
Views
4K
Replies
0
Views
4K
  • Last Post
Replies
1
Views
1K
Replies
4
Views
2K
Replies
2
Views
867
Replies
1
Views
957
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
8K
Top