Gaussian Elimination for Solving Linear Systems

1. The Problem: From Equations to Matrices

A system of linear equations is simply a collection of equations with multiple variables. For example:

Solving this by substituting variables can be messy, especially as systems get larger. Gaussian elimination provides a methodical approach. The first step is to encode all the necessary information—the coefficients of the variables and the constant terms—into a single structure called an augmented matrix.

An augmented matrix is formed by taking the matrix of coefficients ($A$) and appending the vector of constants ($b$) as an extra column. We often draw a vertical line to separate them, representing the equals signs.

For the system above, the augmented matrix is:

To see this conversion explained clearly, please watch the first part of the following video.

2. The Goal: Row Echelon Form

The core idea of Gaussian elimination is to simplify the augmented matrix into a special form called Row Echelon Form (or more generally, an upper triangular form). A matrix is in row echelon form when all the non-zero elements are on or above the main diagonal, and all elements below the diagonal are zero.

For a 3x3 system, the goal is to transform the coefficient part of the matrix to look like this:

Here, • represents a non-zero number (called a pivot) and * can be any number.

Why is this form so useful? Because it represents a system of equations that is trivial to solve. The last row gives you the value of the last variable directly. You can then use that value in the second-to-last equation to find the next variable, and so on. This process is called back-substitution.

The following article explains this motivation and the concept of an upper triangular matrix very clearly.

This image provides a great visual summary of the entire process we're about to learn.

3. The Method: Elementary Row Operations

To transform a matrix into row echelon form without changing the solution to the system, we are allowed to perform three specific operations, called elementary row operations:

1. Swap: Exchange the position of any two rows.
2. Scale: Multiply all elements in a row by a non-zero constant.
3. Replace: Replace a row with the sum of itself and a multiple of another row.

The third operation is the workhorse of elimination, as it's how we strategically create zeros below the diagonal. For a formal definition of these operations, you can refer to the start of the Jupyter Guide to Linear Algebra.

4. A Complete Walkthrough

Now, let's put it all together. We will use the row operations to get our matrix into row echelon form and then use back-substitution to find the solution.

The following video provides a clear, step-by-step walkthrough of this entire process on the same example we started with.

5. Implementing Elimination in Python

Now for the practical part. While NumPy has a built-in function to solve linear systems directly (np.linalg.solve), implementing the row operations yourself is an excellent way to truly understand the algorithm. This is exactly the kind of foundational knowledge that is valuable for exams like GATE.

The resource below defines simple Python functions to perform each of the three elementary row operations on NumPy arrays and then uses them to solve a system.

6. When Elimination Breaks Down: Special Cases

Not every system of equations has a single, unique solution. Gaussian elimination neatly reveals two other possibilities.

1. No Solution (Inconsistent System): The elimination process results in a contradictory row, like 0x + 0y + 0z = c, where c is a non-zero number (e.g., 0 = 5). This is impossible, so the system has no solution.

2. Infinitely Many Solutions (Dependent System): The process results in an identity row, like 0x + 0y + 0z = 0. This is always true and provides no new information. It means you have fewer independent equations than variables. In this case, one or more variables can be chosen freely (they are called free variables), leading to an infinite number of solutions.

This video masterfully explains and demonstrates these three outcomes (unique, no solution, infinite solutions).

A final practical issue is what to do when a zero appears in a pivot position. You can't use a zero to eliminate other entries in its column. The solution is simple: use a row swap to move a non-zero number from a lower row into the pivot position and continue. The "Jupyter Guide to Linear Algebra" discusses this in "Example 3: Finding pivots" if you're interested in the details.

Conclusion

In this lesson, you have learned one of the most fundamental algorithms in linear algebra. It's a systematic procedure that guarantees you can find the solution to any system of linear equations, or determine if one doesn't exist.

Key Takeaways:

• A system of linear equations can be represented as an augmented matrix.
• The goal of Gaussian elimination is to use elementary row operations (Swap, Scale, Replace) to transform this matrix into row echelon form.
• A system in row echelon form is easily solved using back-substitution.
• The process will always lead to one of three outcomes:
  • A unique solution.
  • No solution, identified by a contradiction (e.g., 0 = 5).
  • Infinitely many solutions, identified by an identity (e.g., 0 = 0) and the presence of free variables.

In our next lesson, we will explore the concepts of the determinant and inverse of a matrix. You'll discover that the determinant is a single number that can tell you ahead of time whether a system will have a unique solution, which is a powerful shortcut