Page 43 - 35Linear Algebra

2.1 Gaussian Elimination 43

Algorithm For Obtaining RREF:

• Make the leftmost nonzero entry in the top row 1 by multiplication.

• Then use that 1 as a pivot to eliminate everything below it.

• Then go to the next row and make the leftmost nonzero entry 1.

• Use that 1 as a pivot to eliminate everything below and above it!
• Go to the next row and make the leftmost nonzero entry 1... etc

In the case that the first entry of the first row is zero, we may first interchange
the first row with another row whose first entry is non-vanishing and then
perform the above algorithm. If the entire first column vanishes, we may still
apply the algorithm on the remaining columns.
Here is a video (with special effects!) of a hand performing the algorithm
by hand. When it is done, you should try doing what it does.

Beginner Elimination

This algorithm and its variations is known as Gaussian elimination. The
endpoint of the algorithm is an augmented matrix of the form

1 ∗ 0 ∗ 0 · · · 0 ∗ b
 1 
0 0 1 ∗ 0 · · · 0 ∗
 b 2 
 
 0 0 0 0 1 · · · 0 ∗ b 3 
 
 . . . . . . . . . . . . . . . . . . 


 .
 

0 0 0 0 0 · · · 1 ∗ k
 b 
 
 0 0 0 0 0 · · · 0 0 b k+1 
 . . . . . . . . 
 . . . . . . . . . . . . . . . . 


0 0 0 0 0 · · · 0 0 b r
This is called Reduced Row Echelon Form (RREF). The asterisks denote
the possibility of arbitrary numbers (e.g., the second 1 in the top line of
example 13).
Learning to perform this algorithm by hand is the first step to learning
linear algebra; it will be the primary means of computation for this course.
You need to learn it well. So start practicing as soon as you can, and practice
often.

43