Gaussian Elimination

students, imagine trying to solve a puzzle where several clues are linked together 🔗. In Numerical Analysis, one of the most important tools for solving such linked problems is Gaussian elimination. It is a systematic method for solving systems of linear equations by turning a complicated system into an easier one. This lesson is part of Midterm 1 and Linear Systems I, and it connects directly to later ideas like LU factorization.

What you will learn

By the end of this lesson, students, you should be able to:

explain the main ideas and vocabulary of Gaussian elimination,
carry out Gaussian elimination on a system of equations,
understand why row operations do not change the solution set,
connect Gaussian elimination to the broader study of linear systems and LU factorization,
recognize how this method appears in Numerical Analysis and real applications.

Gaussian elimination is not just a classroom technique. It is used in science, engineering, computer graphics, economics, and data analysis whenever a model leads to a system of equations. 🧠

The big idea behind Gaussian elimination

A system of linear equations is a collection of equations involving the same variables. For example,

$\begin{aligned}$

2x + y - z &= 1,\\

-x + 3y + 2z &= 12,\\

3x + 2y + z &= 7.

$\end{aligned}$

The goal is to find values of $x$, $y$, and $z$ that satisfy all three equations at once. Gaussian elimination works by using elementary row operations to transform the system into an easier equivalent system, often one that is upper triangular. In an upper triangular system, the variables can be solved by back substitution.

The three elementary row operations are:

swap two rows,
multiply a row by a nonzero number,
add a multiple of one row to another row.

These operations are powerful because they do not change the solution set of the system. They only rewrite the same problem in a simpler form.

A system is usually written as an augmented matrix. For the system above, the augmented matrix is

$\left[\begin{array}{ccc|c}$

2 & 1 & -1 & 1\\

-1 & 3 & 2 & 12\\

3 & 2 & 1 & 7

$\end{array}\right].$

Working with matrices makes the process organized and efficient. Instead of rewriting equations over and over, students, you update the rows of the matrix directly. 📘

Step-by-step elimination

Gaussian elimination has two main phases: forward elimination and back substitution.

Forward elimination

The purpose of forward elimination is to create zeros below the main diagonal. The entries on the diagonal are called pivots when they are used to eliminate other entries.

Let us solve the system above. Start with

$\left[\begin{array}{ccc|c}$

2 & 1 & -1 & 1\\

-1 & 3 & 2 & 12\\

3 & 2 & 1 & 7

$\end{array}\right].$

First, it is often convenient to use the first row as the pivot row. To eliminate the $-1$ in row 2, column 1, add $\frac{1}{2}$ of row 1 to row 2. To eliminate the $3$ in row 3, column 1, subtract $\frac{3}{2}$ of row 1 from row 3.

This gives

$\left[\begin{array}{ccc|c}$

2 & 1 & -1 & 1\\

0 & $\frac{7}{2}$ & $\frac{3}{2}$ & $\frac{25}{2}$\\

0 & $\frac{1}{2}$ & $\frac{5}{2}$ & $\frac{11}{2}$

$\end{array}\right].$

Next, eliminate the $\frac{1}{2}$ below the second pivot. Use row 2 to eliminate the entry in row 3, column 2. The result is

$\left[\begin{array}{ccc|c}$

2 & 1 & -1 & 1\\

0 & $\frac{7}{2}$ & $\frac{3}{2}$ & $\frac{25}{2}$\\

0 & 0 & $\frac{16}{7}$ & $\frac{6}{7}$

$\end{array}\right].$

Now the system is upper triangular.

Back substitution

Back substitution means solving from the bottom row upward. The last row gives

$\frac{16}{7}z = \frac{6}{7},$

$z = \frac{3}{8}.$

Then the second row gives

$\frac{7}{2}y + \frac{3}{2}z = \frac{25}{2}.$

Substitute $z = \frac{3}{8}$:

$\frac{7}{2}y + \frac{9}{16} = \frac{25}{2}.$

Solving yields

$y = \frac{17}{8}.$

Finally, the first row gives

2x + y - z = 1.

Substitute the values of $y$ and $z$:

2x + $\frac{17}{8}$ - $\frac{3}{8}$ = 1,

$2x + \frac{14}{8} = 1,$

which gives

$2x + \frac{7}{4} = 1,$

and therefore

$x = -\frac{3}{8}.$

So the solution is

$(x,y,z) = \left(-\frac{3}{8}, \frac{17}{8}, \frac{3}{8}\right).$

This example shows the whole method: transform the system, then solve the simpler one. ✅

Why Gaussian elimination works

Gaussian elimination works because each elementary row operation creates a new equation that is a combination of the old equations, not a different problem. For example, if you replace one equation with that equation plus a multiple of another equation, any solution that worked before still works now, and any solution of the new system also satisfies the original system.

This idea is important in Numerical Analysis because we want methods that are reliable and systematic. The method turns a general system into one with a predictable structure. When the matrix is nonsingular, there is a unique solution. When there are fewer pivots than variables, the system may have infinitely many solutions or no solution at all.

A key concept is the pivot. A pivot is the first nonzero entry in a row after elimination. In many courses, the pivot is used to decide which variable to eliminate next. If a pivot is $0$, we may need to swap rows. This is called pivoting. Pivoting is important in practice because it can avoid division by zero and improve numerical stability.

In real computation, numbers are stored approximately, so small rounding errors can happen. Gaussian elimination is still a central method, but Numerical Analysis studies how the method behaves when arithmetic is not exact. That is one reason this topic appears in the course. 🔍

Common outcomes: unique solution, many solutions, or no solution

When you perform Gaussian elimination, one of three things usually happens:

1. Unique solution

If every variable has a pivot and there is no contradiction, the system has exactly one solution.

2. Infinitely many solutions

If there are fewer pivots than variables, some variables are free variables. These can take any value, which creates infinitely many solutions.

3. No solution

If elimination produces a row like

$\left[\begin{array}{ccc|c}$

0 & 0 & 0 & 5

$\end{array}\right],$

then the system says

$0 = 5,$

which is impossible. That means the system is inconsistent and has no solution.

Being able to recognize these outcomes is a major goal in Linear Systems I. students, this skill helps you interpret the structure of a system, not just compute an answer.

Connection to LU factorization

Gaussian elimination also prepares you for LU factorization. In LU factorization, a matrix $A$ is written as

$A = LU,$

where $L$ is a lower triangular matrix and $U$ is an upper triangular matrix.

Why is this useful? Because Gaussian elimination is essentially the process of turning $A$ into $U$ using row operations. The multipliers used during elimination can be stored in $L$. Then, once $A = LU$ is known, solving $Ax=b$ becomes two easier problems:

$Ly = b,$

followed by

$Ux = y.$

This is efficient when you need to solve multiple systems with the same coefficient matrix $A$ but different right-hand sides $b$. For example, in engineering simulations, the same structure may be reused many times. That is why Gaussian elimination is not just a one-time technique; it is the foundation for larger numerical methods. ⚙️

Practical tips for doing elimination correctly

To work accurately with Gaussian elimination, keep these habits in mind:

Write each row operation clearly.
Keep fractions organized instead of rounding too early.
Choose pivots carefully, especially if a pivot is $0$ or very small.
Check your final answer by substituting it back into the original equations.
Remember that every row operation must preserve equivalence of the system.

In exams and homework, students often make mistakes by changing one equation but forgetting to update the others, or by mixing up elimination and back substitution. students, a clean layout is one of the best tools for success. ✍️

Conclusion

Gaussian elimination is a core method in Numerical Analysis and a central topic in Linear Systems I. It transforms a system of linear equations into an equivalent simpler system using elementary row operations, then solves by back substitution. It also explains important ideas like pivots, row operations, consistency, and the structure of solutions. Even more importantly, it leads naturally to LU factorization, which is a major computational tool for solving many systems efficiently. Mastering Gaussian elimination gives you a strong foundation for the rest of Midterm 1 and for future topics in numerical linear algebra.

Study Notes

Gaussian elimination solves systems of linear equations by using elementary row operations.
The three row operations are row swapping, multiplying a row by a nonzero scalar, and adding a multiple of one row to another.
The system is usually written as an augmented matrix.
Forward elimination creates zeros below the pivots and produces an upper triangular matrix.
Back substitution solves the triangular system from bottom to top.
Row operations preserve the solution set of the system.
A pivot is the leading nonzero entry in a row after elimination.
If a pivot is $0$, row swapping or pivoting may be needed.
A row of the form $\left[\begin{array}{ccc|c}0 & 0 & 0 & 5\end{array}\right]$ means no solution.
Fewer pivots than variables usually means free variables and possibly infinitely many solutions.
Gaussian elimination is the computational basis for LU factorization, where $A = LU$.
In Numerical Analysis, the method is studied not only for correctness but also for efficiency and numerical stability.