# Homework Help: Gaussian elimination (pivoting)

1. Feb 23, 2017

### fonseh

1. The problem statement, all variables and given/known data
In my book , the author stated that when we do the pivoting , we need to make the element below the leading element = 0 . For example for 3x3 matrix , for the first column , we have to make a11 = max , and make sure that a21 and a31 less than a11 , for the second column , we have to make the a22 = max , make sure that the a32 less than a22 ...

But , according to my lecturer ( in second photo)( I have reduced it into row echelon formed in first matrix , for the 2nd matrix , my lecturer just swap the row) , he make the a11 max compared to the other element( a12 and a13) in the first row ...

For row 2 , he make the a22 max compared to a21 and a23 in the same row

For row 2 , he make the a33 max compared to other element (a31 and a32) ...

2. Relevant equations

3. The attempt at a solution

I dont think the lecturer is correct . Can someone explain about it ? I have read a lot of online resource , i cant find them similar to the way that the lecturer read

#### Attached Files:

File size:
40.8 KB
Views:
89
File size:
18.6 KB
Views:
104
File size:
31.7 KB
Views:
109
• ###### IMG_20170223_140126.jpg
File size:
31.6 KB
Views:
106
2. Feb 23, 2017

### BvU

Not clear to me what your question is. I see a piece of text in hhh.jpg and a worked out pivoting example in 140116.jpg and 140126
Is 134955.jpg what you call 'the second photo' ? It only shows a swap of row 1 and 2 of a different matrix.

What is it you think the lecturer does incorrectly ? placing the -3 in position 11 is according to the text.

3. Feb 23, 2017

### fonseh

140116.jpg and 140126 are the textbook question . So , it follows the rule that stated in hhh.jpg

4. Feb 23, 2017

### fonseh

134955,jpg is the question that the lecturer showed and solved .... I didnt posted the full solution for 134955,jpg because i am just having problem with the pivotisation ( I doubt the way that the lecturer switching row is correct ) . After the pivotisation , it's just the normal gaussian elimination , followed by backward substituition to solve the question...

5. Feb 23, 2017

### fonseh

6. Feb 23, 2017

### BvU

It's getting to be a bit labyrinthic ..

Why ? He picks the biggest $a_{i1}$ and moves that row to row 1

7. Feb 23, 2017

### fonseh

140116.jpg and 140126 shows that the author get the max a11 first , then he make the element below a11 = 0 , get max a22 , make the element below it = 0 ...

but , the lecturer gpot all the max a11 , a22 and a33 , then he only do the gauss elimination (make the element below a11 = 0 , make the element below a22 = 0 ... ) ....

Both method are correct ?

8. Feb 23, 2017

### BvU

Where do I see what he did ? ($\LaTeX$ please )

9. Feb 23, 2017

### Staff: Mentor

@fonseh, please start using LaTeX to represent your matrices instead of posting images of them. In post #1 of this thread you attached four images. That alone is enough for many helpers to refuse to provide help. What's worse is that your descriptions of what's in the images, such as "in second photo", are confusing, since it's not clear which one is the second photo.

In your other thread, @BvU also made this request. I am copying hs comment from that post, but have made a very minor change -- I like matrices to be inside brackets (i.e., bmatrix) rather than parentheses (pmatrix).
It's OK to post an image of the problem statement, but work on matrices should be posted using LaTeX, as in the example above. If you don't make an effort to comply with this I will close the thread.

10. Feb 23, 2017

### Ray Vickson

I agree with Mark44 about getting you to stop posting images if you want to continue using this forum. If you want, you can use a tabular form instead of matrices; in LaTeX you do that using an "array", allowing you to have vertical and horizontal separating lines and labelled rows if you want, like this:
$$\begin{array}{c|rrr|c} \text{row}&x_1 & x_2 & x_3 & \text{r.h.s.}\\ \hline 1 &5 & -5 & 1 & 2\\ 2 &-3 & 1 & 1 & 1 \\ 3 &3 & 2 & -7 & 1 \\ \hline 4 &-3 & 1 & 1 & 1\\ 5 &5 & -5 & 1 & 2\\ 6 &3 & 2 & -7 & 1 \\ \hline \vdots &\vdots & \vdots & \vdots & \vdots\\ \hline \end{array}$$
To see how this was done, right-click on the image and choose "show math as tex commands" from the displayed menu.

Last edited: Feb 23, 2017
11. Feb 23, 2017

### fonseh

$$\begin{bmatrix} 2 & -5& 1 & 2 \\ 3 & 2 & -7 & 1 \\ -3 & 1 & 1 & 1 \end {bmatrix}$$

The author then make a11 , a22 and a33 max all at ONCE , , hence , become
$$\begin{bmatrix} -3 & 1 & 1 & 1\\ 2 & -5& 1 & 2 \\ 3 & 2 & -7 & 1 \end {bmatrix}$$

In the 2nd matrix , we can see that all the a11 , a22 and a33 is max

Is the author's working of making all the a11 , a22 and a33 = max correct ?

12. Feb 23, 2017

### Staff: Mentor

I don't think so. In the 2nd matrix, as far as I can see, it just happens that a11, a22, a33 have the largest values (absolute values).

There are only three row operations that you can apply to get a new matrix with the same solution set as the one you started with:
1) Swapping two rows (Ri <--> Rj)
2) Replacing a row by a nonzero multiple of itself (Ri <-- k*Ri)
3) Replacing a row by the sum of it and a nonzero multiple of another row (Ri <-- Ri + k * Rj)

For the two matrices above, it looks like there were two row operations performed:
Rows 1 and 2 were swapped, resulting in
$\begin{bmatrix} 3 & 2 & -7 & 1 \\ 2 & -5& 1 & 2 \\ -3 & 1 & 1 & 1\end{bmatrix}$
and in this new matrix, rows 1 and 3 were swapped, resulting in

$\begin{bmatrix} -3 & 1 & 1 & 1 \\ 2 & -5& 1 & 2 \\ 3 & 2 & -7 & 1\end{bmatrix}$

The most important thing is that whichever row you're going to pivot on, the leading entry in that column should not be zero. You then use that entry to eliminate all the entries in the columns below that entry, with the goal being a more-or-less diagonal matrix, with entries of zero below the diagonal.

Keep in mind that all this matrix business is just a shorthand way to solve a system of equations. The same row operations apply; namely a) you can interchange any two equations; b) you can replace an equation with a nonzero multiple of itself; c) you can replace any equation with the sum of it and a nonzero multiple of another equation.

In all cases here, you end up with a system of equations that looks different, but has exactly the same solution set.

13. Feb 23, 2017

### fonseh

Do you mean
instead of doing these steps ,
1) interchanging rows to get the the max a11 ,
2) make the element below the a11 (a21 and a31) equal to 0
3) Interchanging the rows to get max a22
4) make the element below a22 = 0

We can also interchanging the rows first , to get max a11 and a22 , followed by making the element below a11 and a22 = 0 ?

14. Feb 23, 2017

### Ray Vickson

That was just an accident of the data in this problem.

Generally, we start in column 1 and move the numerically largest value in that column to position (1,1), perhaps by swapping some row i and row 1. Then we do row operations to zero out the remaining elements in column 1.

At that point the rest of the matrix changes (because the row operations affect all the columns, not just column 1.) So, what WAS a largest element before the row operations may no longer be the largest in the new matrix. Therefore, we cannot predict what further row-interchanges will be needed; maybe $a_{22}$ was the largest element in column 2 before row operations, but then maybe the new value of $a_{42}$ is the largest after.

I am trying to get you to understand that you need to re-examine the matrix (below the current pivoting row) that you get after the row operations. Basically, forget about what was largest in the original matrix and look instead what is now largest in the new matrix. It may have moved to a new location.

15. Feb 23, 2017

### fonseh

Yes , i understand what you said ...But , is the way of swapping the row all at once firstly to get max a11 and a22 , then , followed by the zero out the element below a11 and a22 correct ?

16. Feb 23, 2017

### Ray Vickson

It is not incorrect, but it is a waste of time and nobody who writes linear algebra software (for example) would ever do it! The author should not have done that, unless it happened just by accident when he but the largest $|a_{i1}|$ into position (1,1) by swapping two rows. The fact that $a_{22}$ and $a_{33}$ are then also the largest is purely accidental and has no significance whatsoever. It is unimportant! Forget it!

You are trying to read way too much into things that have no importance, and it is getting in the way of your learning the subject.

17. Feb 23, 2017

### fonseh

So , just follow these steps will be enough ?
1) interchanging rows to get the the max a11 ,
2) make the element below the a11 (a21 and a31) equal to 0
3) Interchanging the rows to get max a22
4) make the element below a22 = 0

18. Feb 24, 2017

### Staff: Mentor

I agree completely.
You do the above at each pivot row, moving across the matrix column by column.

Here's a simple system as an example.
x + y + z = 6
2x -z = -1
x + z = 4

As an augmented matrix this system is
$\begin{bmatrix} 1 & 1 & 1 & | & 6\\ 2 & 0 & -1 & | & -1 \\ 1 & 0 & 1 & | & 4 \end{bmatrix}$

Replace R2 by -2* R1 + R2:
$\begin{bmatrix} 1 & 1 & 1 & | & 6\\ 0 & -2 & -3 & | & -13 \\ 1 & 0 & 1 & | & 4 \end{bmatrix}$
Now replace R3 by -1 * R1 + R3:
$\begin{bmatrix} 1 & 1 & 1 & | & 6\\ 0 & -2 & -3 & | & -13 \\ 0 & -1 & 0 & | & -2 \end{bmatrix}$

The pivot was the a1,1 entry. I used it to eliminate the entries below it in the 2nd and 3rd rows.
To save some time I could swap rows 2 and 3 for a reason I'll explain later.

Swap R2 and R3:
$\begin{bmatrix} 1 & 1 & 1 & | & 6\\ 0 & -1 & 0 & | & -2\\ 0 & -2 & -3 & | & -13 \end{bmatrix}$

Replace R2 by -1 times itself
$\begin{bmatrix} 1 & 1 & 1 & | & 6\\ 0 & 1 & 0 & | & 2\\ 0 & -2 & -3 & | & -13 \end{bmatrix}$
The second row tells me that y = 2, and this is why I swapped R2 and R3.

Replace R3 by 2 * R2 + R3:
$\begin{bmatrix} 1 & 1 & 1 & | & 6\\ 0 & 1 & 0 & | & 2\\ 0 & 0 & -3 & | & -9 \end{bmatrix}$

Finally, replace R3 by -1/3 * R3:
$\begin{bmatrix} 1 & 1 & 1 & | & 6\\ 0 & 1 & 0 & | & 2\\ 0 & 0 & 1 & | & 3 \end{bmatrix}$

Notice that I used only the three row operations I mentioned in my earlier post, nothing more.

This matrix is now in reduced echelon form, with each row having a leading entry of 1, and every row with a leading 1 has 0 entries below it. The second row tells me that y = 2. The third row tells me that z = 3. By substituting these values into the equation represented by the first row (x + y + z = 6), I can determine that x = 1.

The solution to the system of equations is x = 1, y = 2, z = 3, which you can check by substituting into the original system of equations.

Last edited: Feb 24, 2017
19. Feb 24, 2017

### fonseh

why 3 operation in the earlier post you are referring to ?

20. Feb 24, 2017

### Staff: Mentor

Because those are the only operations that result in a new system with the same solution set.

21. Feb 24, 2017

### fonseh

Sorry , i mean which 3 operation in the earlier post you are referring to ?

22. Feb 24, 2017

### fonseh

I dont understand why you swapped row 2 and row 3 , at here , a22 is already max , why we need to swap row 2 and row 3 ? Swapping row 3 would make the a22 become not maximum ... To pivot 'a22' , we need to make it max , right ? Then , we can only make the element below a22 = 0

#### Attached Files:

• ###### 590.PNG
File size:
25 KB
Views:
60
23. Feb 24, 2017

### fonseh

Or i misunderstood something ?

24. Feb 24, 2017

### BvU

No you didn't misunderstand. Mark tells you: 'to save time'. Do it both ways and you already have found the explanation Mark gives a few lines later.

Note that swapping rows is for numerical analysis purposes only (one wants to avoid subtracting big numbers from big numbers) and it's no big deal NOT to swap an $|a_{22}| = 2$ of for one with absolute value $1$.

25. Feb 24, 2017

### fonseh

sorry , i didnt quite understand the example that Mark gave in post #18.....

Can you explain based on the example i gave in post #11 ?

Do you mean that it is actually unnecessary to interchange all the row at ONCE to get max a11 , a22 and a33 ?

We can also change the row to get the max a11 first , then zero out a21 and a31 , after that , change the row to get max a22 ... and so on ?