Gaussian Elimination Method

Master Gaussian elimination: row operations, echelon forms, pivot selection, and applications through these 5 detailed exercises.

Solution: Exercises 1 to 3
1 Basic 2×2 system
Exercise 1
Solve the system using Gaussian elimination:
\(2x + 3y = 7\)
\(4x - y = 1\)
Definition:

Gaussian elimination: A systematic method for solving systems of linear equations by transforming the augmented matrix into row echelon form using elementary row operations

Gaussian elimination steps:
  1. Create the augmented matrix from the system of equations
  2. Perform elementary row operations to achieve row echelon form
  3. Use back-substitution to find the solution
Augmented Matrix
\(\begin{bmatrix} 2 & 3 & | & 7 \\ 4 & -1 & | & 1 \end{bmatrix}\)
Row Echelon Form
\(\begin{bmatrix} 1 & 0 & | & 1 \\ 0 & 1 & | & 2 \end{bmatrix}\)
Solution
\(x = 1, y = 2\)
Step 1: Write the augmented matrix

System: \(\begin{cases} 2x + 3y = 7 \\ 4x - y = 1 \end{cases}\)

Augmented matrix: \(\begin{bmatrix} 2 & 3 & | & 7 \\ 4 & -1 & | & 1 \end{bmatrix}\)

Step 2: Make the leading coefficient of row 1 equal to 1

Divide row 1 by 2: \(R_1 \leftarrow \frac{1}{2}R_1\)

New matrix: \(\begin{bmatrix} 1 & \frac{3}{2} & | & \frac{7}{2} \\ 4 & -1 & | & 1 \end{bmatrix}\)

Step 3: Eliminate the first variable in row 2

Subtract 4 times row 1 from row 2: \(R_2 \leftarrow R_2 - 4R_1\)

\(R_2 = [4, -1, 1] - 4[1, \frac{3}{2}, \frac{7}{2}] = [4, -1, 1] - [4, 6, 14] = [0, -7, -13]\)

New matrix: \(\begin{bmatrix} 1 & \frac{3}{2} & | & \frac{7}{2} \\ 0 & -7 & | & -13 \end{bmatrix}\)

Step 4: Make the leading coefficient of row 2 equal to 1

Divide row 2 by -7: \(R_2 \leftarrow \frac{-1}{7}R_2\)

New matrix: \(\begin{bmatrix} 1 & \frac{3}{2} & | & \frac{7}{2} \\ 0 & 1 & | & \frac{13}{7} \end{bmatrix}\)

Step 5: Back-substitution

From row 2: \(y = \frac{13}{7}\)

Substitute into row 1: \(x + \frac{3}{2} \cdot \frac{13}{7} = \frac{7}{2}\)

\(x + \frac{39}{14} = \frac{49}{14}\)

\(x = \frac{49}{14} - \frac{39}{14} = \frac{10}{14} = \frac{5}{7}\)

\(x = \frac{5}{7}, y = \frac{13}{7}\)
Final answer:

The solution to the system is \(x = \frac{5}{7}\) and \(y = \frac{13}{7}\)

Applied rules:

• Elementary row operations: Interchange, multiply by non-zero constant, add multiple of one row to another

• Row echelon form: Leading coefficients move right as we go down rows

• Back-substitution: Solve from bottom row upward

2 3×3 system with elimination
Exercise 2
Solve the system using Gaussian elimination:
\(x + 2y + z = 4\)
\(2x - y + 3z = 7\)
\(3x + y - z = 1\)
Definition:

Row echelon form: A matrix form where all nonzero rows are above rows of all zeros, and the leading coefficient of a row is to the right of the leading coefficient of the row above it

Initial Matrix
\(\begin{bmatrix} 1 & 2 & 1 & | & 4 \\ 2 & -1 & 3 & | & 7 \\ 3 & 1 & -1 & | & 1 \end{bmatrix}\)
After Elimination
\(\begin{bmatrix} 1 & 0 & 0 & | & 1 \\ 0 & 1 & 0 & | & 2 \\ 0 & 0 & 1 & | & 1 \end{bmatrix}\)
Step 1: Create the augmented matrix

\(\begin{bmatrix} 1 & 2 & 1 & | & 4 \\ 2 & -1 & 3 & | & 7 \\ 3 & 1 & -1 & | & 1 \end{bmatrix}\)

Step 2: Eliminate below the first pivot (row 1)

Operation 1: \(R_2 \leftarrow R_2 - 2R_1\)

New row 2: \([2, -1, 3, 7] - 2[1, 2, 1, 4] = [0, -5, 1, -1]\)

Operation 2: \(R_3 \leftarrow R_3 - 3R_1\)

New row 3: \([3, 1, -1, 1] - 3[1, 2, 1, 4] = [0, -5, -4, -11]\)

Step 3: Work on rows 2 and 3

Now matrix is: \(\begin{bmatrix} 1 & 2 & 1 & | & 4 \\ 0 & -5 & 1 & | & -1 \\ 0 & -5 & -4 & | & -11 \end{bmatrix}\)

Operation: \(R_3 \leftarrow R_3 - R_2\)

New row 3: \([0, -5, -4, -11] - [0, -5, 1, -1] = [0, 0, -5, -10]\)

Step 4: Normalize row 2 and 3

Divide row 2 by -5: \(R_2 \leftarrow \frac{-1}{5}R_2\)

Divide row 3 by -5: \(R_3 \leftarrow \frac{-1}{5}R_3\)

Result: \(\begin{bmatrix} 1 & 2 & 1 & | & 4 \\ 0 & 1 & -\frac{1}{5} & | & \frac{1}{5} \\ 0 & 0 & 1 & | & 2 \end{bmatrix}\)

Step 5: Back-substitution

From row 3: \(z = 2\)

Substitute into row 2: \(y - \frac{1}{5}(2) = \frac{1}{5}\), so \(y = \frac{1}{5} + \frac{2}{5} = \frac{3}{5}\)

Substitute into row 1: \(x + 2(\frac{3}{5}) + 2 = 4\), so \(x = 4 - \frac{6}{5} - 2 = \frac{4}{5}\)

\(x = \frac{4}{5}, y = \frac{3}{5}, z = 2\)
Final answer:

The solution is \(x = \frac{4}{5}\), \(y = \frac{3}{5}\), and \(z = 2\)

Applied rules:

• Pivot selection: Choose leading coefficients to eliminate below

• Triangularization: Create zeros below pivots to form upper triangular matrix

• Back-substitution: Solve from bottom row upward

3 Row operations practice
Exercise 3
Perform Gaussian elimination on the augmented matrix:
\(\begin{bmatrix} 2 & 1 & 3 & | & 8 \\ 4 & 3 & 5 & | & 18 \\ 6 & 2 & 7 & | & 22 \end{bmatrix}\)
Definition:

Reduced row echelon form: A matrix form where each leading coefficient is 1, and all other entries in the column of a leading coefficient are zero

Original Matrix
\(\begin{bmatrix} 2 & 1 & 3 & | & 8 \\ 4 & 3 & 5 & | & 18 \\ 6 & 2 & 7 & | & 22 \end{bmatrix}\)
After Operations
\(\begin{bmatrix} 1 & 0 & 2 & | & 3 \\ 0 & 1 & -1 & | & 2 \\ 0 & 0 & 0 & | & 0 \end{bmatrix}\)
Step 1: Make leading coefficient of row 1 equal to 1

Divide row 1 by 2: \(R_1 \leftarrow \frac{1}{2}R_1\)

New matrix: \(\begin{bmatrix} 1 & \frac{1}{2} & \frac{3}{2} & | & 4 \\ 4 & 3 & 5 & | & 18 \\ 6 & 2 & 7 & | & 22 \end{bmatrix}\)

Step 2: Eliminate first column below row 1

Operation 1: \(R_2 \leftarrow R_2 - 4R_1\)

New row 2: \([4, 3, 5, 18] - 4[1, \frac{1}{2}, \frac{3}{2}, 4] = [0, 1, -1, 2]\)

Operation 2: \(R_3 \leftarrow R_3 - 6R_1\)

New row 3: \([6, 2, 7, 22] - 6[1, \frac{1}{2}, \frac{3}{2}, 4] = [0, -1, -2, -2]\)

Step 3: Work on rows 2 and 3

Current matrix: \(\begin{bmatrix} 1 & \frac{1}{2} & \frac{3}{2} & | & 4 \\ 0 & 1 & -1 & | & 2 \\ 0 & -1 & -2 & | & -2 \end{bmatrix}\)

Operation: \(R_3 \leftarrow R_3 + R_2\)

New row 3: \([0, -1, -2, -2] + [0, 1, -1, 2] = [0, 0, -3, 0]\)

Step 4: Normalize remaining rows

Divide row 3 by -3: \(R_3 \leftarrow \frac{-1}{3}R_3\)

Current matrix: \(\begin{bmatrix} 1 & \frac{1}{2} & \frac{3}{2} & | & 4 \\ 0 & 1 & -1 & | & 2 \\ 0 & 0 & 1 & | & 0 \end{bmatrix}\)

Step 5: Back-substitution

From row 3: \(z = 0\)

Substitute into row 2: \(y - 0 = 2\), so \(y = 2\)

Substitute into row 1: \(x + \frac{1}{2}(2) + \frac{3}{2}(0) = 4\), so \(x = 4 - 1 = 3\)

\(x = 3, y = 2, z = 0\)
Final answer:

The solution is \(x = 3\), \(y = 2\), and \(z = 0\)

Applied rules:

• Systematic elimination: Work column by column from left to right

• Pivot normalization: Make leading coefficients equal to 1

• Zero creation: Eliminate entries below each pivot

Gaussian Elimination: Theory and Properties
\(A\vec{x} = \vec{b} \Rightarrow [A|\vec{b}] \xrightarrow{\text{row ops}} [U|\vec{c}] \Rightarrow \vec{x} \text{ by back-substitution}\)
Gaussian Elimination Process
Row Operation 1
\( R_i \leftrightarrow R_j \)
Swap rows i and j
Row Operation 2
\( R_i \leftarrow kR_i \)
Multiply row i by non-zero k
Row Operation 3
\( R_i \leftarrow R_i + kR_j \)
Add k times row j to row i
Key definitions:

Augmented matrix: A matrix formed by appending the constant column to the coefficient matrix

Elementary row operations: Operations that preserve the solution set of the system

Row echelon form: A matrix form where leading coefficients move right as we go down rows

Reduced row echelon form: A matrix form where each leading coefficient is 1 and all other entries in its column are zero

Gaussian elimination methodology:
  1. Form augmented matrix: Combine coefficient matrix with constant vector
  2. Forward elimination: Create zeros below each pivot
  3. Back-substitution: Solve from bottom row upward
  4. Verification: Check that solution satisfies original equations
Tip 1: Choose the largest possible pivot to minimize rounding errors in numerical computations.
Tip 2: Always verify your solution by substituting back into the original equations.
Tip 3: When you encounter a zero pivot, try to swap with a lower row that has a non-zero entry in that column.
Solution: Exercises 4 to 5
4 System with no solution
Exercise 4
Solve the system using Gaussian elimination:
\(x + 2y = 3\)
\(2x + 4y = 7\)
Definition:

Inconsistent system: A system of equations that has no solution, indicated by a row of the form [0 0 ... 0 | c] where c ≠ 0

Augmented Matrix
\(\begin{bmatrix} 1 & 2 & | & 3 \\ 2 & 4 & | & 7 \end{bmatrix}\)
After Elimination
\(\begin{bmatrix} 1 & 2 & | & 3 \\ 0 & 0 & | & 1 \end{bmatrix}\)
Step 1: Write the augmented matrix

\(\begin{bmatrix} 1 & 2 & | & 3 \\ 2 & 4 & | & 7 \end{bmatrix}\)

Step 2: Eliminate below the first pivot

Operation: \(R_2 \leftarrow R_2 - 2R_1\)

New row 2: \([2, 4, 7] - 2[1, 2, 3] = [0, 0, 1]\)

Step 3: Analyze the result

The transformed matrix is: \(\begin{bmatrix} 1 & 2 & | & 3 \\ 0 & 0 & | & 1 \end{bmatrix}\)

The second row corresponds to the equation: \(0x + 0y = 1\), which is impossible.

No solution exists
Final answer:

The system is inconsistent and has no solution

Applied rules:

• Inconsistency detection: Row of form [0 0 ... 0 | c] where c ≠ 0 indicates no solution

• Parallel lines: The equations represent parallel lines with no intersection

• Verification: The second equation is twice the first but with different constant

5 System with infinitely many solutions
Exercise 5
Solve the system using Gaussian elimination:
\(x + 2y - z = 1\)
\(2x + 4y - 2z = 2\)
\(3x + 6y - 3z = 3\)
Definition:

Dependent system: A system with infinitely many solutions, indicated by a row of all zeros in the coefficient portion

Augmented Matrix
\(\begin{bmatrix} 1 & 2 & -1 & | & 1 \\ 2 & 4 & -2 & | & 2 \\ 3 & 6 & -3 & | & 3 \end{bmatrix}\)
After Elimination
\(\begin{bmatrix} 1 & 2 & -1 & | & 1 \\ 0 & 0 & 0 & | & 0 \\ 0 & 0 & 0 & | & 0 \end{bmatrix}\)
Step 1: Write the augmented matrix

\(\begin{bmatrix} 1 & 2 & -1 & | & 1 \\ 2 & 4 & -2 & | & 2 \\ 3 & 6 & -3 & | & 3 \end{bmatrix}\)

Step 2: Eliminate below the first pivot

Operation 1: \(R_2 \leftarrow R_2 - 2R_1\)

New row 2: \([2, 4, -2, 2] - 2[1, 2, -1, 1] = [0, 0, 0, 0]\)

Operation 2: \(R_3 \leftarrow R_3 - 3R_1\)

New row 3: \([3, 6, -3, 3] - 3[1, 2, -1, 1] = [0, 0, 0, 0]\)

Step 3: Analyze the result

The transformed matrix is: \(\begin{bmatrix} 1 & 2 & -1 & | & 1 \\ 0 & 0 & 0 & | & 0 \\ 0 & 0 & 0 & | & 0 \end{bmatrix}\)

Rows 2 and 3 are all zeros, indicating that the equations are dependent.

Step 4: Express solution parametrically

From row 1: \(x + 2y - z = 1\)

Solve for x: \(x = 1 - 2y + z\)

Let \(y = s\) and \(z = t\) where s and t are free parameters

General solution: \(x = 1 - 2s + t\), \(y = s\), \(z = t\)

\(x = 1 - 2s + t\), \(y = s\), \(z = t\) where \(s, t \in \mathbb{R}\)
Final answer:

The system has infinitely many solutions: \(x = 1 - 2s + t\), \(y = s\), \(z = t\) where s and t are any real numbers

Applied rules:

• Dependence detection: Rows of all zeros indicate dependent equations

• Parameterization: Express free variables as parameters

• General solution: Represent infinite solutions using parameters

Comprehensive Guide: Gaussian Elimination
\([A|\vec{b}] \xrightarrow{R_i \leftrightarrow R_j} [A'|\vec{b'}] \xrightarrow{R_i \leftarrow kR_i} [A''|\vec{b''}] \xrightarrow{R_i \leftarrow R_i + kR_j} [U|\vec{c}]\)
Elementary Row Operations Sequence
Key definitions:

Gaussian elimination: A systematic method for solving linear systems by transforming the augmented matrix to row echelon form using elementary row operations

Elementary row operations: Three fundamental operations that preserve the solution set of a linear system

Row echelon form: A matrix form where leading coefficients move strictly right as we go down rows, and all entries below each leading coefficient are zero

Reduced row echelon form: A matrix form where each leading coefficient is 1 and all other entries in its column are zero

Gaussian elimination methodology:
  1. Initialization: Form the augmented matrix [A|b] from the system Ax = b
  2. Forward phase: For each column, make the leading coefficient 1 and eliminate below it
  3. Backward phase: Continue to reduced row echelon form (optional)
  4. Solution extraction: Read off the solution or express in parametric form
  5. Verification: Check that the solution satisfies the original system
Tip 1: Always work from left to right and top to bottom for systematic elimination.
Tip 2: If you encounter a zero in a pivot position, try to swap with a lower row.
Tip 3: Fractions can be avoided by careful choice of multipliers.
Tip 4: Check your work frequently by verifying partial results.
Common errors: Arithmetic mistakes in row operations, incorrect back-substitution, not recognizing inconsistent/dependent systems.
Exam preparation: Practice with different matrix sizes, memorize the three row operations, understand solution types.
Important properties and applications:

• Preservation of solutions: Elementary row operations don't change the solution set

• Computational complexity: O(n³) for an n×n system

• Matrix rank: Number of non-zero rows in row echelon form

• Existence and uniqueness: Determined by comparing rank of coefficient matrix with augmented matrix

Visualization: Gaussian Elimination Process
Understanding Row Operations and Echelon Forms
Visualizing the Gaussian elimination process:
1. Row operations and their effects
2. Transformation to echelon form
3. Back-substitution process
4. Solution types (unique, none, infinite)

Analysis: The visualization shows how Gaussian elimination systematically transforms a matrix.

  • Row operations preserve solution set
  • Zeros are created below pivots
  • Leading coefficients move right
  • Back-substitution solves the system

Questions & Answers

Question: Why do we need to use Gaussian elimination instead of just solving equations normally?

Answer: Gaussian elimination provides a systematic, algorithmic approach that works well for larger systems and can be implemented programmatically. While substitution works for small systems, it becomes unwieldy for systems with many variables. Gaussian elimination:

  • Provides a consistent method that works for any size system
  • Reveals when a system has no solution or infinitely many solutions
  • Can be easily programmed for computer implementation
  • Helps identify relationships between equations

For large systems, Gaussian elimination is far more efficient and less error-prone than manual substitution methods.

Question: What happens if I make a mistake in one of the row operations?

Answer: Errors in row operations will lead to an incorrect solution. To prevent this:

  • Check each operation immediately after performing it
  • Verify that the new row is a valid linear combination of the original rows
  • Substitute your final answer back into the original equations to verify
  • Work slowly and carefully, especially with signs

If you suspect an error, you can always restart from the original augmented matrix. With practice, row operations become more intuitive and less error-prone.

Question: Can Gaussian elimination be used for non-linear systems?

Answer: No, Gaussian elimination only applies to linear systems. The method relies on the linearity property where we can add equations and multiply them by constants to create equivalent systems.

For non-linear systems, different methods are needed such as substitution, elimination of variables, or numerical approximation techniques. Some non-linear systems can be linearized near specific points, but this is an advanced topic beyond basic algebra.

The fundamental requirement for Gaussian elimination is that all equations in the system are linear (degree 1 in each variable).