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.

 

$$\bordermatrix{& & & & \cr & \cdot & \cdot & \cdot & \cdot \cr \rightarrow & \cdot & {\bf 0} & \cdot & \cdot \cr & \cdot & * & \cdot & \cdot \cr \rightarrow & \cdot & \hbox{(nonzero element)} & \cdot & \cdot \cr}$$

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.

 

$$\bordermatrix{& & & & \cr & \cdot & * & \cdot & \cdot \cr 1/k \rightarrow & \cdot & {\bf k} & \cdot & \cdot \cr & \cdot & * & \cdot & \cdot \cr & \cdot & * & \cdot & \cdot \cr} \to \left[\matrix{\cdot & * & \cdot & \cdot \cr \cdot & {\bf 1} & \cdot & \cdot \cr \cdot & * & \cdot & \cdot \cr \cdot & * & \cdot & \cdot \cr}\right]$$

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

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: