2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ “Best” by what criteria? For instance, if you care about numerical stability, using the element with the greatest absolute value for the pivot can be best. $\endgroup$
    – amd
    Sep 29 '19 at 22:20
2
$\begingroup$

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}

  1. $R_2 = R_2/(-\tfrac32)$
  2. $R_1 = R_1 - \tfrac12 R_2$
  3. $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}

  1. $R_3 = R_3/\frac{17}3$
  2. $R_1 = R_1 + \tfrac23 R_3$
  3. $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}

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

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

  1. $R_3 = R_3/(-17)$
  2. $R_1 = R_1 - 5R_3$
  3. $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

$\endgroup$
1
  • $\begingroup$ Thank you, and yes R2 - R1 was what I was initially thinking, but yeh it can be difficult sometimes to know if you are doing unnecessary steps (especially by hand), so your comprehensive answer was very useful! $\endgroup$
    – DuncanK3
    Sep 29 '19 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.