Gaussian Elimination
MAT1503 - Linear Algebra I · SYSTEMS OF LINEAR EQUATIONS AND MATRICES
Gaussian Elimination
Gaussian elimination is a method used to solve systems of linear equations. It transforms a system's augmented matrix into a simpler form, making it easier to find solutions. This method is essential in linear algebra because it provides a systematic way to handle equations with multiple variables.
Key idea: After studying this topic, you should be able to:
- Understand the concepts of row-echelon form (REF) and reduced row-echelon form (RREF).
- Perform elementary row operations on matrices.
- Apply Gaussian elimination to solve systems of linear equations.
- Identify the nature of the solutions based on the echelon form of the matrix.
Understanding Row-Echelon Form (REF) and Reduced Row-Echelon Form (RREF)
To solve a system of linear equations, we first convert it into an augmented matrix. The goal is to transform this matrix into REF or RREF.
Row-Echelon Form (REF)
A matrix is in row-echelon form if:
- All non-zero rows are above any rows of all zeros.
- The leading entry (pivot) of each non-zero row is 1.
- The leading entry of each non-zero row is to the right of the leading entry of the previous row.
Reduced Row-Echelon Form (RREF)
A matrix is in reduced row-echelon form if:
- It is in row-echelon form.
- Each leading 1 is the only non-zero entry in its column.
Elementary Row Operations
We can perform three types of operations to manipulate the rows of a matrix:
- Scaling: Multiply all entries in a row by a non-zero constant.
- Interchange: Swap two rows.
- Row Addition: Add a multiple of one row to another row.
Applying Gaussian Elimination
Let us solve the following system of equations:
x + y + z = 6
2x - y + z = 3
x + 2y - z = 2We first write the augmented matrix:
[[1, 1, 1 | 6],
[2, -1, 1 | 3],
[1, 2, -1 | 2]]Next, we will perform row operations to reach RREF.
Step 1: Make leading 1s
We can start by making the leading entry of the first row a pivot:
R1 ↔ R1
R2 - 2R1 → R2
R3 - R1 → R3This gives us:
[[1, 1, 1 | 6],
[0, -3, -1 | -9],
[0, 1, -2 | -4]]Step 2: Continue elimination
Next, we can simplify the second row:
R2 ÷ -3 → R2
R3 + R2 → R3This results in:
[[1, 1, 1 | 6],
[0, 1, 1/3 | 3],
[0, 0, -5/3 | -1]]Step 3: Back substitution
Now we can convert the last row to make the leading entry a 1:
R3 ÷ -5/3 → R3We obtain:
[[1, 1, 1 | 6],
[0, 1, 1/3 | 3],
[0, 0, 1 | 3/5]]Continuing this process will lead us to:
[[1, 0, 0 | 1],
[0, 1, 0 | 2],
[0, 0, 1 | 3]]The solution is:
(x, y, z) = (1, 2, 3)Identifying Solution Types
After row-reducing a matrix, you can determine the nature of the solutions:
- If you find a row like [0, 0, 0 | b] (where b ≠ 0), the system has no solution (inconsistent).
- If the number of non-zero rows equals the number of variables, there is exactly one solution (unique).
- If there are fewer non-zero rows than variables, there are infinitely many solutions (free variables).
Watch out: Be careful with row operations. If you use a row that has been modified incorrectly, it can lead to incorrect solutions.
Summary
- Gaussian elimination transforms an augmented matrix into REF or RREF.
- Elementary row operations include scaling, interchanging, and row addition.
- Identifying the types of solutions depends on the final echelon form of the matrix.
Check your understanding
- What is the row-echelon form of the matrix [[1, 2, 3 | 4], [2, 4, 6 | 8], [3, 6, 9 | 12]]?
- How do you determine if a system of equations has no solution?
- Perform Gaussian elimination on the system: x + y = 2, 2x + 3y = 5. What is the solution?
- What does it mean if a matrix has a row of zeros in RREF?
Common mistakes explained
Determinants and Row Operations
The determinant of a matrix is a special number that can tell us various properties of the matrix, such as whether it is invertible. When performing row operations on a matrix, the determinant changes in specific ways:
- Multiplying a row by a scalar multiplies the determinant by that scalar.
- Swapping two rows changes the sign of the determinant.
- Adding a multiple of one row to another row does not change the determinant.
In this case, we start with a matrix A with determinant |A| = 5. The new matrix D is formed by the following operations:
R1 → 3R1This operation multiplies the first row by 3, so the determinant of D becomes:
|D| = 3 × |A| = 3 × 5 = 15.
R3 → -2R3This operation multiplies the third row by -2. Therefore, we multiply the determinant by -2:
|D| = -2 × 15 = -30.
The common misconceptions include thinking that multiplying a row by a scalar only affects the row itself, or forgetting that the determinant changes sign when a row is multiplied by a negative scalar. Thus, options like 30, -10, and 10 do not account for the correct application of both row operations.
Gaussian Elimination and Unique Solutions
In linear algebra, a system of equations is consistent if it has at least one solution. A unique solution occurs when the augmented matrix has full rank, meaning it has as many pivots as variables and no contradictory rows.
To determine if a matrix has a unique solution, follow these steps:
- Convert the augmented matrix to row echelon form using Gaussian elimination.
- Count the number of pivots (leading 1s) in the matrix.
- Ensure there are no rows of the form [0, 0, ..., 0 | c] where c is a non-zero constant, as this indicates inconsistency.
For example, consider the augmented matrix:
[[1, 2, 1 | 4], [0, 1, -1 | 2], [0, 0, 1 | 3]]This matrix has three pivots and no contradictory rows, indicating a unique solution.
The wrong options are misleading because:
- A row of zeros equal to a nonzero constant shows inconsistency, meaning no solutions exist.
- Identical rows do not contribute additional information and can indicate dependency, potentially leading to infinite solutions.
- A free variable indicates that the system has infinitely many solutions, not a unique one.
Pivot Entries and Unique Solutions
In a system of linear equations, a unique solution exists when there are no free variables. This occurs when every column of the coefficient matrix (except the last column for the augmented part) has a pivot entry. A pivot entry is a non-zero value in the row echelon form of the matrix.
In this case, the pivot entry is given as α² - α - 2. To find when the system fails to have a unique solution, we need to set this expression equal to zero:
α² - α - 2 = 0 This quadratic equation can be factored as:
(α - 2)(α + 1) = 0 Setting each factor to zero gives:
- α - 2 = 0 → α = 2
- α + 1 = 0 → α = -1
The system fails to have a unique solution when α = 2 or α = -1. However, we are looking for the specific case where the pivot entry becomes zero, which is α = 2. This is the value that leads to a lack of a unique solution.
The wrong options arise from misunderstanding the quadratic equation. For α = 1 and α = 0, the pivot entry does not equal zero:
- For α = 1: 1² - 1 - 2 = -2 (not zero)
- For α = 0: 0² - 0 - 2 = -2 (not zero)
Thus, neither of these values leads to a failure in having a unique solution.
Test yourself
5 quick questions on this lesson. Pick an answer to see if you're right.
1. An augmented matrix has a pivot entry α²-α-2. For what value of α does the system fail to have a unique solution?
2. Which augmented matrix below is consistent with a unique solution?
3. Solve the system: x+y+z=1, 2x-y+3z=0, x+2y-z=5. What is (x, y, z)?
4. Row-reducing an augmented matrix leaves one free variable t. The solution is x=10+t, y=3+t, z=t. Which option matches this parametric solution?
5. Solve the system: x+y+z=6, 2x-y+z=3, x+2y-z=2. What is (x, y, z)?