Gaussian Elimination

students, imagine trying to solve a system of equations the way a computer might: by turning a messy problem into a simpler one step by step. That is the big idea behind Gaussian elimination. It is one of the most important tools in Linear Algebra because it helps solve linear systems, understand whether solutions exist, and see how many solutions there are 🔍

What Gaussian Elimination Does

A linear system is a set of equations that all have to be true at the same time. For example,

$\begin{aligned}$

$ x + 2y &= 5 \\$

$ 3x - y &= 4$

$\end{aligned}$

Gaussian elimination is a procedure for rewriting such a system into an equivalent but easier one. The word equivalent means the new system has exactly the same solutions as the original system. That matters because the goal is not to change the answer, but to make the answer easier to find.

The method uses a matrix called the augmented matrix. For the system above, the augmented matrix is

$\begin{bmatrix}$

1 & 2 & | & 5 \\

3 & -1 & | & 4

$\end{bmatrix}$

The left side stores the coefficients of the variables, and the right side stores the constants. The vertical bar is just a visual divider between coefficients and constants.

Gaussian elimination works by using row operations. The three allowed 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 do not change the solution set, which is why they are safe to use ✅

Turning a System into Upper Triangular Form

The main goal of Gaussian elimination is to create an upper triangular matrix, also called row echelon form. In this form, the entries below each leading position are zeros, so the system becomes easier to solve by back substitution.

For example, start with

$\begin{aligned}$

$ x + 2y &= 5 \\$

$ 3x - y &= 4$

$\end{aligned}$

Write the augmented matrix:

$\begin{bmatrix}$

1 & 2 & | & 5 \\

3 & -1 & | & 4

$\end{bmatrix}$

Now eliminate the $3$ below the first pivot by replacing Row 2 with Row 2 minus $3$ times Row 1:

$R_2 \leftarrow R_2 - 3R_1$

This gives

$\begin{bmatrix}$

1 & 2 & | & 5 \\

0 & -7 & | & -11

$\end{bmatrix}$

The system is now easier because the second equation has only one variable:

$-7y = -11$

So,

$ y = \frac{11}{7}$

Then substitute into the first equation:

$ x + 2\left(\frac{11}{7}\right) = 5$

$ x = \frac{13}{7}$

This example shows the two major stages of Gaussian elimination: forward elimination and back substitution. Forward elimination creates zeros below the pivots, and back substitution finds the variable values from the bottom up.

Pivots, Leading Entries, and Row Echelon Form

A pivot is the first nonzero entry in a row after the matrix has been simplified. More specifically, it is the leading entry in a row that guides elimination. Pivots are important because they show which variables can be solved for directly.

A matrix is in row echelon form if:

all zero rows, if any, are at the bottom,
each leading entry is to the right of the leading entry in the row above,
all entries below each leading entry are zero.

Here is an example of a matrix in row echelon form:

$\begin{bmatrix}$

1 & 2 & -1 & | & 3 \\

0 & 4 & 5 & | & 1 \\

0 & 0 & 6 & | & 8

$\end{bmatrix}$

This matrix corresponds to a system that can be solved by back substitution. The pivots are the entries $1$, $4$, and $6$.

Gaussian elimination is not only about solving equations one by one. It also reveals structure. For instance, if a column has no pivot, then the corresponding variable may be a free variable, which can lead to infinitely many solutions.

What Can Happen After Elimination

After Gaussian elimination, one of three things can happen:

1. One unique solution

This happens when every variable has a pivot and no contradictions appear. For example, a system may reduce to something like

$\begin{aligned}$

x + y + z &= 4 \\

$ y - z &= 1 \\$

$ z &= 2$

$\end{aligned}$

Then you can solve $z$, then $y$, then $x$. The system has exactly one solution.

2. Infinitely many solutions

This happens when at least one variable is free and there is no contradiction. For example, a reduced system might contain

$ x + y = 3$

with another equation that is just a multiple of the first. Then there are many pairs $\left(x,y\right)$ that work, such as $\left(0,3\right)$, $\left(1,2\right)$, and $\left(2,1\right)$. In this case, Gaussian elimination reveals that the equations are not independent.

3. No solution

This happens when the elimination process produces a contradiction like

$0 = 7$

That statement is never true, so the original system has no solution. This often means the equations describe parallel lines or inconsistent conditions in geometry.

For example, compare

$\begin{aligned}$

$ x + y &= 2 \\$

$ x + y &= 5$

$\end{aligned}$

These cannot both be true at the same time. Elimination would produce a contradiction.

A Larger Example with Three Variables

Consider the system

$\begin{aligned}$

x + y + z &= 6 \\

2x + 3y + z &= 11 \\

x + 2y + 3z &= 14

$\end{aligned}$

Its augmented matrix is

$\begin{bmatrix}$

1 & 1 & 1 & | & 6 \\

2 & 3 & 1 & | & 11 \\

1 & 2 & 3 & | & 14

$\end{bmatrix}$

Eliminate below the first pivot:

R_2 \leftarrow R_2 - 2R_1, \quad R_3 \leftarrow R_3 - R_1

This gives

$\begin{bmatrix}$

1 & 1 & 1 & | & 6 \\

0 & 1 & -1 & | & -1 \\

0 & 1 & 2 & | & 8

$\end{bmatrix}$

Now eliminate below the second pivot:

$R_3 \leftarrow R_3 - R_2$

so we get

$\begin{bmatrix}$

1 & 1 & 1 & | & 6 \\

0 & 1 & -1 & | & -1 \\

0 & 0 & 3 & | & 9

$\end{bmatrix}$

Now solve from the bottom:

3z = 9 \Rightarrow z = 3

Then

y - z = -1 \Rightarrow y - 3 = -1 \Rightarrow y = 2

Finally,

x + y + z = 6 \Rightarrow x + 2 + 3 = 6 \Rightarrow x = 1

So the solution is $\left(1,2,3\right)$. This example shows how Gaussian elimination can handle more than two equations and more than two unknowns.

Why Gaussian Elimination Matters in Linear Algebra

Gaussian elimination is a core part of Linear Algebra because it connects several important ideas:

solving linear systems,
matrix operations,
understanding pivots and free variables,
finding the rank of a matrix,
determining whether a system is consistent.

It is also a foundation for more advanced topics. Many later methods in mathematics, science, economics, and engineering rely on the same logic of simplifying a system step by step. Computers use closely related algorithms to solve large systems efficiently 💻

In the topic of Introduction to Linear Systems, Gaussian elimination is one of the main procedures students learn because it gives a reliable method for analyzing systems. It is not just a trick for arithmetic; it is a way to organize information and make hidden patterns visible.

Conclusion

Gaussian elimination is a systematic method for solving linear systems by using row operations to create an easier equivalent system. The method uses augmented matrices, pivots, row echelon form, and back substitution. It can lead to one solution, infinitely many solutions, or no solution, depending on the structure of the system. students, if you understand Gaussian elimination, you have learned one of the most important tools in Linear Algebra and a major idea within Introduction to Linear Systems 🎯

Study Notes

Gaussian elimination solves linear systems by turning them into simpler equivalent systems.
The three elementary row operations are swapping rows, multiplying a row by a nonzero number, and adding a multiple of one row to another row.
The augmented matrix combines the coefficients and constants of a system.
The goal of forward elimination is to create zeros below the pivots.
A pivot is the first nonzero entry in a row after simplification.
Row echelon form has leading entries stepping to the right as you move down the rows.
After elimination, use back substitution to find the variables.
A system can have one solution, infinitely many solutions, or no solution.
A contradiction like $0 = 7$ means the system has no solution.
A free variable appears when a column has no pivot, which can lead to infinitely many solutions.
Gaussian elimination is a central method in Linear Algebra and a key part of Introduction to Linear Systems.