## Row-reducing Algorithms

### January 4, 2008

* Row reduction* is the process of using row operations to transform a matrix into a row reduced echelon matrix. As the algorithm proceeds, you move in stairstep fashion through different positions in the matrix. In the description below, when I say that the * current position* is *(i, **j) *, I mean that your current location is in row *i* and column *j*. The * current position* refers to a *location*, not the element at that location. The * current row* means the row of the matrix containing the current position.

——————————————-

…

* Algorithm: Row Reducing a Matrix*

…

**Step 0.** Start with the current position at *(1,1).*

…

**Step 1.** If the element at the current position is nonzero, go to **Step 3**. If the element at the current position is 0, go to **Step 2**.

…

**Step 2. **To get to this step, the element at the current position must be 0. Look at the elements in the same column *below* the current position.

If some element in the same column *below* the current position is nonzero, then swap the current row with the row containing the nonzero element (without changing the current position). Then go to **Step 1**.

If no element in the same column *below* the current position is nonzero, then either there are no elements below the current position (i.e. you’re in the last row), or all the elements below the current position are 0. In that case, look at the column to the right of the current position.

If there is no column to the right of the current position, stop — * you’re done*. If there *is* a column to the right of the current position, then move the current position one column to the right (i.e. change the current position from* (i, j)* to *(i, j+1)* ) and go to **Step 1**.

…

**Step 3. **To get to this step, the element at the current position must be nonzero. (I’m calling it ** k** below.)

First, divide the current row by the (nonzero) element at the current position.

Next, add multiples of the current row to the other rows in the matrix (*above and below* the current position) so that the element in the current position is the only nonzero element in its column.

Finally, try to change the current position by moving down one row and moving to the right by one column (so the current position goes from *(i, j) *to *(i+1, j+1)* ).

If you are able to do this, go to **Step 1**. If you’re unable to do this (because the current position is in the last row or in the last column, or both), stop —* you’re done*!

—————–

Useful link for *Row-reducting Algorithm*:

http://marauder.millersville.edu/~bikenaga/linearalgebra/rowred/rowred.html