First step on Gaussian Elimination

Question

How do you know what the best first step to take is in Gaussian Elimination. Consider the matrix
\begin{pmatrix} 2&1&-3&-2 \\ 3&0&-2&5 \\ 2&2&1&4 \end{pmatrix} I know ideally that the $2$ in the first row needs to become a $0$ or a $1$, but it seems that there could be different ways to do this, so how do you know what's correct?

Answer 1

As long as step moves the matrix closer to RREF, it is correct.

• dividing the first row by 2 is correct because now there is a 1 in the correct pivot position
• subtracting the first row from the second is correct because that creates a 1 that we can later use as a pivot
• subtracting the first row from the third is correct because that creates a 0 and we need two 0s in the first column
• subtracting the third row from the first is correct for the same reason

If you were to implement this on a computer, the computer needs to know what the first step is, not what are all the possible first steps. A naïve algorithm is the following:

1. Find the first entry of the matrix that can become the next pivot.
2. Swap rows if necessary
3. Divide that row by its first entry to create a 1
4. Subtract that row from the rows above and below it to create 0s
5. Repeat

So a computer following this algorithm will do the following steps

1. $R_1 = R_1/2$
2. $R_2 = R_2 - 3R_1$
3. $R_3 = R_3 - 2R_1$

\begin{pmatrix} 1 & \frac{1}{2} & -\frac{3}{2} & -1 \\ 0 & -\frac{3}{2} & \frac{5}{2} & 8 \\ 0 & 1 & 4 & 6 \\ \end{pmatrix}

4. $R_2 = R_2/(-\tfrac32)$
5. $R_1 = R_1 - \tfrac12 R_2$
6. $R_3 = R_3 - R_2$

\begin{pmatrix} 1 & 0 & -\frac{2}{3} & \frac{5}{3} \\ 0 & 1 & -\frac{5}{3} & -\frac{16}{3} \\ 0 & 0 & \frac{17}{3} & \frac{34}{3} \\ \end{pmatrix}

7. $R_3 = R_3/\frac{17}3$
8. $R_1 = R_1 + \tfrac23 R_3$
9. $R_2 = R_2 + \tfrac53 R_3$

\begin{pmatrix} 1 & 0 & 0 & 3 \\ 0 & 1 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ \end{pmatrix}

If the matrix has $m$ rows and $n$ columns, we can expect this algorithm to take $\min\{m,n\}^2$ steps and each step will require $n$ operations. For an $n \times n$ matrix, this is $n^3$ operations.

On the other hand, these operations involve a lot of fractions which becomes a problem if you are storing the matrix as floating point numbers. (Floating point numbers are stored in base-2 scientific notation with a certain number of significant digits; they are not exact representations. As a result, applying many operations to the floating point numbers can cause large rounding errors.)

We can, in fact, row reduce this matrix and have only integer entries at every stage:

1. $R_2 = R_2 - R_1$
2. $R_1 = R_1 - 2R_2$
3. $R_3 = R_3 - 2R_2$
4. $R_1 \leftrightarrow R_2$

\begin{pmatrix} 1 & -1 & 1 & 7 \\ 0 & 3 & -5 & -16 \\ 0 & 4 & -1 & -10 \\ \end{pmatrix}

5. $R_3 = R_3 - R_2$
6. $R_1 = R_1 + R_3$
7. $R_2 = R_2 - 3R_3$
8. $R_2 \leftrightarrow R_3$

\begin{pmatrix} 1 & 0 & 5 & 13 \\ 0 & 1 & 4 & 6 \\ 0 & 0 & -17 & -34 \\ \end{pmatrix}

9. $R_3 = R_3/(-17)$
10. $R_1 = R_1 - 5R_3$
11. $R_2 = R_2 - 4R_3$

\begin{pmatrix} 1 & 0 & 0 & 3 \\ 0 & 1 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ \end{pmatrix}

Here the goal is to use clever row subtraction to create a 1, rather than row division. Both methods work. Which one you choose is up to you.

I encourage you to use this interactive tool to assist you with learning row operations and row reduction:

http://textbooks.math.gatech.edu/ila/demos/rrinter.html?mat=2,1,-3,-2:3,0,-2,5:2,2,1,4&ops=r0:-1:1,r1:-2:0,r1:-2:2,s0:1,r1:-1:2,r2:1:0,r2:-3:1,s1:2,m2:-1.17,r2:-5:0,r2:-4:1