Row reduction

January 4, 2008

What is row reduction?

Row reduction (or Gauss-Jordan elimination) is the process of using row operations to reduce a matrix to row reduced echelon form. This procedure is used to solve systems of linear equations, invert matrices, compute determinants, and do many other things.

——————————-

A matrix is in row reduced echelon form if the following conditions are satisfied:

  1. The first nonzero element in each row (if any) is a “1” (a leading coefficient).
  2. Each leading coefficient is the only nonzero element in its column.
  3. All the all-zero rows (if any) are at the bottom of the matrix.
  4. The leading coefficients form a “stairstep pattern” from northwest to southeast:

 

$$\left[\matrix{ 0 & 1 & 6 & 0 & 0 & 2 & \ldots \cr 0 & 0 & 0 & 1 & 0 & -1 & \ldots \cr 0 & 0 & 0 & 0 & 1 & 4 & \ldots \cr 0 & 0 & 0 & 0 & 0 & 0 & \ldots \cr \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \cr}\right]$$

In this matrix, the leading coefficients are in positions $(1,2)$ , $(2,4)$ , $(3,5)$ , … .

Here some more matrices in row-reduced echelon form. Notice the “stairstep pattern” made by the leading coefficients. The *’s indicate that the numbers in those positions can be anything.

——————————-

 

Example

$$\left[\matrix{1 & 0 & 0 \cr 0 & 1 & 0 \cr 0 & 0 & 1 \cr}\right]$$

is in row reduced echelon form. This matrix is called the $3 \times 3$ identity matrix.

$$\left[\matrix{1 & 0 & 0 \cr 0 & 7 & 0 \cr 0 & 0 & 1 \cr}\right]$$

is not in row reduced echelon form. The first nonzero element in row 2 is a “7”, rather than a “1”.

$$\left[\matrix{1 & 0 & -3 \cr 0 & 1 & 5 \cr 0 & 0 & 1 \cr}\right]$$

is in not row reduced echelon form. The leading coefficient in row 3 is not the only nonzero element in its column.

$$\left[\matrix{0 & 0 & 0 & 0 \cr 0 & 1 & 0 & -1 \cr 0 & 0 & 1 & 9 \cr}\right]$$

is not in row reduced echelon form. There is an all-zero row lying above a nonzero row.

$$\left[\matrix{1 & 37 & 2 & -1 \cr 0 & 1 & -3 & 0 \cr 0 & 0 & 0 & 0 \cr}\right]$$

is not in row reduced echelon form. The leading coefficient in row 2 is not the only nonzero element in its column.

———————–

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: