Row Reduction (1)
From a General Matrix to the Reduced Echelon Form

• (Row i) replaced by (Row i)+c(Row j), where i≠j and c≠0.
• (Row i) replaced by c(Row i), where c≠0.
• Interchange two rows, or rearrange the order of several rows.

In a nutshell, the row reduction process is mainly about three things:

• To Choose Pivots: To find the candidates for pivots, search the columns one by one from left to right. Pivots should be nonzero entries. You are only allowed to choose at most one pivot from a single column. Likewise, no multiple pivots should appear in a single row.
• To Put Pivots in Positions: Put the first pivot in Row 1, the second pivot in Row 2, the third pivot in Row 3, ..., by using row swappings if necessary.
• To Exploit Pivots to Kill: Use a pivot to eliminate all nonzero entries in the same column.

• Start with the leftmost nonzero column of the matrix. We have nothing to do with the zero columns on the left of the working column; they are done.

• Pick a nonzero entry in the working column as a pivot

• Swap Row 1 and Row 3 to bring the pivot to the top of the working column

• Row 1 replaced by (1/2)Row 1, to make the pivot equal to 1

• Eliminating the entries below the pivot in the working column:
  Row 4 replaced by Row 4 - 6 Row 1
  Row 5 replaced by Row 5 - 4 Row 1

• The blue columns are done. Now we look at the next nonzero (yellow) column and try to pick a pivot there. The restrictions to choose the next pivot is that it needs to be a nonzero entry and should not be in the same row(s) of the previous pivot(s).
  In this particular example, we are allowed to choose either the second, third, fourth, or fifth entry in the working (yellow) column.

• We choose the second entry in the working (yellow) column as the next pivot.

• Row 2 replaced by (-1/3)Row 2, to make the pivot =1.

• Eliminate the other entries in the (Yellow) working column by using the pivot:
  Row 1 replaced by Row 1 + (1/2)Row 2
  Row 3 replaced by Row 3 - Row 2
  Row 4 replaced by Row 4 + 8Row 2
  Row 5 replaced by Row 5 + 5Row 2
  

• The blue columns are done. The next nonzero column is Column 5. Let's try to pick the next pivot from Column 5. The restrictions to choose the next pivot is that it needs to be a nonzero entry and should not be in the same rows of the previous pivots.
  In this particular example, there are no candidates for the next pivot from Column 5.
  Next we move to Column 6 (the yellow column). Let's try to pick a pivot there. The pivot candidates satisfying the restrictions are the fifth and sixth entries. We choose the fifth entry.

• The blue columns are done.
  Move the row of the new pivot just below the previous pivot, by swapping Row 3 and Row 5.

• Row 3 replaced by (-1/2)Row 3, to make the pivot equal to 1.

• Eliminate the other entries in the (Yellow) working column by using the pivot:
  Row 1 replaced by Row 1 -2Row 3
  Row 2 replaced by Row 2 -Row 3
  Row 6 replaced by Row 6 -4Row 2
  

• The next two columns have no candidates for the next pivot.
  We move to the next column containing pivot candidates, the yellow column.
  There is only one candidate for the next pivot.

• Row 4 replaced by (1/3)Row 4, to make the pivot equal to 1.

• Eliminate the other entries in the (Yellow) working column by using the pivot:
  Row 1 replaced by Row 1 +(11/2)Row 4
  Row 2 replaced by Row 2 +(5/2)Row 4
  Row 3 replaced by Row 3 -(5/2)Row 4
  

• The next pivot is in the last column.

• Row 5 replaced by (1/2)Row 5, to make the new pivot equal to 1.

• Eliminate the other entries in the (Yellow) working column by using the pivot:
  Row 1 replaced by Row 1 -18Row 5
  Row 2 replaced by Row 2 -9Row 5
  Row 3 replaced by Row 3 +8Row 5
  Row 4 replaced by Row 4 -2Row 5
  

• The resulting matrix is in the reduced echelon form now. The five pink entries are the pivots.

Remark: The reduced echelon form is unique. The reduced echelon form is independent of the row operations you choose.

1 0 2 3 2 8 1 1 3

R2-3R1   R3-R1

→

1 0 2 0 2 2 0 1 1

R3-(1/2)R2

→

1 0 2 0 2 2 0 0 0

(1/2)R2

→

1 0 2 0 1 1 0 0 0

(Reduced Echelon Form)

1 0 2 3 2 8 1 1 3

Swap R1 & R3

→

1 1 3 3 2 8 1 0 2

R2-3R1   R3-R1

→

1 1 3 0 -1 -1 0 -1 -1

R1+R2   R3-R2

→

1 0 2 0 -1 -1 0 0 0

-R2

→

1 0 2 0 1 1 0 0 0

(Reduced Echelon Form)