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:

  1. Scaling: Multiply all entries in a row by a non-zero constant.
  2. Interchange: Swap two rows.
  3. 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 = 2

We 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 → R3

This 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 → R3

This 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 → R3

We 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

  1. What is the row-echelon form of the matrix [[1, 2, 3 | 4], [2, 4, 6 | 8], [3, 6, 9 | 12]]?
  2. How do you determine if a system of equations has no solution?
  3. Perform Gaussian elimination on the system: x + y = 2, 2x + 3y = 5. What is the solution?
  4. 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 → 3R1

This operation multiplies the first row by 3, so the determinant of D becomes:

|D| = 3 × |A| = 3 × 5 = 15.

R3 → -2R3

This 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:

  1. Convert the augmented matrix to row echelon form using Gaussian elimination.
  2. Count the number of pivots (leading 1s) in the matrix.
  3. 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. 1. An augmented matrix has a pivot entry α²-α-2. For what value of α does the system fail to have a unique solution?

  2. 2. Which augmented matrix below is consistent with a unique solution?

  3. 3. Solve the system: x+y+z=1, 2x-y+3z=0, x+2y-z=5. What is (x, y, z)?

  4. 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. 5. Solve the system: x+y+z=6, 2x-y+z=3, x+2y-z=2. What is (x, y, z)?