Math 1410, Spring 2020
Gaussian Elimination
February 4, 2020
| Sean Fitzpatrick |
|---|
| University of Lethbridge |
 |
Recap
Warm-up
What can you say about the set of solutions to each pair of equations below? (You might find it helpful to sketch the lines.)
- \begin{align*} x - 2y \amp = 5\\ -4x + 8y \amp =-10 \end{align*}
- \begin{align*} 4x + y \amp =6\\ 12x + 3y \amp =18 \end{align*}
- \begin{align*} 3x-y \amp =4\\ x+2y \amp =2 \end{align*}
Elementary row operations
The augmented matrix
If we're going to be solving lots of linear systems (and we are), then it gets tedious quickly to keep track of all the variables.
A “key idea”: write only the coefficients, and keep track of variables by position. We organize everything in a rectangular array, called a matrix.
Example:
System of equations:
Augmented matrix:
From matrix to system
It's important to be able to convert in both directions:
Example:
Write down the system (in variables \(x_1,x_2,x_3,x_4\)) corresponding to the augmented matrix
Elementary row operations
There are three elementary operations on the rows of a matrix, corresponding to the elementary operations on equations:
Swap any two rows: write \(R_i\leftrightarrow R_j\)
Multiply a row by a nonzero constant (rescale): write \(cR_j\to R_j\)
Add a multiple of one row to another: write \(R_i+cR_j \to R_i\)
Gaussian elimination
There is a standard algorithm for solving a system using row operations:
-
By swapping rows and/or rescaling, get a 1 in row 1, column 1.
(This is possible unless column 1 consists entirely of zeros.)
By adding multiples of row 1 to the other rows, create zeros in all other entries of column 1.
Move to row 2, column 2, and repeat (until you reach the last row or column).
Example
For the system below, write down the augmented matrix, and use Gaussian elimination to simplify.
Avoiding pitfalls
Be careful of minus signs!
Once first column looks like \(\bbm 1\\0\\0\\ \vdots \\0\ebm\text{,}\) stop using \(R_1\text{!}\)
To get next leading one, either divide, or use rows below.
Reduced row-echelon form
RREF
How do we know when to stop the algorithm?
Gaussian elimination works down and to the right, creating zeros and leading ones.
Once each row “starts” with a leading one (first nonzero entry), and leading ones in lower rows are to the right of leading ones in higher rows, (only zeros below each leading one) you're in row-echelon form.
Row-echelon form is not unique. From any REF you can probably solve by back-substitution.
Eliminating non-zero entries above each leading one leads to reduced row-echelon form. This is unique, and as simplified as possible.
Examples
Which matrices are in REF? RREF? If neither, what's the next step?
Gauss-Jordan Elimination
Forward steps: perform Gaussian elimination to reach row-echelon form.
You could solve by back substitution at this stage.
(If there's no solution, you should already be able to tell.)
Back substitution can be tricky if there are parameters involved.
Backward steps: starting with right-most leading one, create zeros above, working up and to the left.
Examples
Example 1
Solve the system:
Example 2
Solve the system: