Gaussian Elimination

The Gaussian elimination method is a linear algebra algorithm designed to solve systems of linear equations through successive transformations into equivalent matrices. The procedure is named after the German mathematician Carl Friedrich Gauss (1777–1855), who systematized its application to facilitate astronomical and geodetic computations, although similar principles were already used in ancient Chinese mathematical texts.

To apply the method, we represent the system of linear equations in matrix form by collecting its coefficients and constants into an augmented matrix. For example, given a system of three equations with three variables:

$$\begin{cases} a_{11}x + a_{12}y + a_{13}z = b_1 \\ a_{21}x + a_{22}y + a_{23}z = b_2 \\ a_{31}x + a_{32}y + a_{33}z = b_3 \end{cases}$$

We construct its corresponding augmented matrix by separating the coefficients of the variables from the constant terms using a vertical bar:

$$\left[\begin{array}{ccc|c} a_{11} & a_{12} & a_{13} & b_1 \\ a_{21} & a_{22} & a_{23} & b_2 \\ a_{31} & a_{32} & a_{33} & b_3 \end{array}\right]$$

The goal of the algorithm is to transform this matrix into row echelon form (REF). A matrix is considered to be in row echelon form when it satisfies the following three conditions:

1. Any rows consisting entirely of zeros, if present, are placed at the bottom of the matrix.
2. In each nonzero row, the first nonzero number (called the pivot or leading entry) is strictly to the right of the pivot of the row above it.
3. All entries below each pivot are zeros.

It is worth noting that, in classical Gaussian elimination, pivots are not required to be equal to 1. While some authors require normalizing each row by dividing it by its pivot, forcing this condition during manual calculations introduces fractions early on, unnecessarily complicating algebraic operations. Because the final step consists of back-substitution using simple equations, keeping nonzero integer pivots speeds up the process and drastically reduces arithmetic errors.

To reach row echelon form without changing the solution set of the system, we can apply three elementary row operations:

• Interchanging two rows: \(R_i \leftrightarrow R_j\). In words: swap row \(i\) with row \(j\).
• Multiplying a row by a nonzero scalar: \(R_i \to k \cdot R_i\) (where \(k \neq 0\)). In words: multiply row \(i\) by the nonzero constant \(k\).
• Adding a multiple of another row: \(R_i \to R_i + k \cdot R_j\). In words: add \(k\) times row \(j\) to row \(i\). The row written to the left of the arrow is always the one that changes.

The complete algorithm is divided into two main consecutive stages:

1. Forward elimination phase: involves applying elementary row operations from left to right to create zeros below each pivot until a row echelon form matrix is obtained.
2. Back-substitution phase: involves reconstructing the system of equations from the row echelon matrix and solving for the numerical value of each variable from bottom to top, substituting known values into the equations above.

Method Example

To understand how the algorithm works in practice, let us solve the following system of 3 equations with 3 variables:

$$\begin{cases} 2x + y - z = 3 \\ 4x + 3y + z = 11 \\ -2x + 2y + 2z = 4 \end{cases}$$

We write the corresponding augmented matrix by grouping the variable coefficients and constant terms:

$$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 3 \\ 4 & 3 & 1 & 11 \\ -2 & 2 & 2 & 4 \end{array}\right]$$

We begin the forward elimination phase by working on the first column. The first pivot is 2, located in the first row and first column. We must eliminate the entries below this pivot.

First, we eliminate the number 4 in the second row. To do this, subtract twice row 1 from row 2. In symbols: \(R_2 \to R_2 - 2R_1\).

$$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 3 \\ 0 & 1 & 3 & 5 \\ -2 & 2 & 2 & 4 \end{array}\right]$$

Next, we eliminate the number −2 in the third row. To do this, add row 1 to row 3. In symbols: \(R_3 \to R_3 + R_1\).

$$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 3 \\ 0 & 1 & 3 & 5 \\ 0 & 3 & 1 & 7 \end{array}\right]$$

We move to the second column. The second pivot is 1, located in the second row and second column.

We need to eliminate the entry below this pivot, which is the number 3 in the third row. To do this, subtract three times row 2 from row 3. In symbols: \(R_3 \to R_3 - 3R_2\).

$$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 3 \\ 0 & 1 & 3 & 5 \\ 0 & 0 & -8 & -8 \end{array}\right]$$

The matrix is now in row echelon form, since all entries below the pivots 2, 1, and −8 are zeros. Notice that it was not necessary to force the pivots to equal 1, avoiding intermediate fractions.

We now begin the back-substitution phase. To do this, we reconstruct the system of equations from the echelon matrix:

$$\begin{cases} 2x + y - z = 3 \\ y + 3z = 5 \\ -8z = -8 \end{cases}$$

Solve for z directly in the third equation:

$$-8z = -8 \implies z = \dfrac{-8}{-8} = 1$$

Substitute the obtained value of z into the second equation to solve for y:

$$y + 3(1) = 5 \implies y + 3 = 5 \implies y = 5 - 3 = 2$$

Finally, substitute the values of y and z into the first equation to solve for x:

$$2x + 2 - 1 = 3 \implies 2x + 1 = 3 \implies 2x = 2 \implies x = 1$$

The system has a unique solution: \(x = 1\), \(y = 2\), \(z = 1\). Therefore, it is classified as a consistent independent system (unique solution).

To verify that the solution is correct, substitute these values into the original three equations of the system:

$$\begin{cases} 2(1) + (2) - (1) = 2 + 2 - 1 = 3 \\ 4(1) + 3(2) + (1) = 4 + 6 + 1 = 11 \\ -2(1) + 2(2) + 2(1) = -2 + 4 + 2 = 4 \end{cases}$$

Since all three equations hold true simultaneously, we confirm that the computed values are correct.

Types of Solutions in 3×3 Systems

One major advantage of Gaussian elimination is that it allows classifying the linear system as soon as the matrix reaches row echelon form, without needing to complete back-substitution.

In a system of three equations with three variables, the nature of the solution set can be deduced directly by analyzing the third row of the augmented echelon matrix:

System Classification	Structure of Row 3	Algebraic Interpretation	Geometric Interpretation (in R3)
Consistent Independent System	[0 0 c | d] with c ≠ 0	Unique solution. The equation c · z = d allows solving for z directly: z = d / c.	The three planes intersect at a single point in space.
Consistent Dependent System	[0 0 0 | 0]	Infinitely many solutions. The row cancels out completely (0 = 0), indicating a redundant equation and at least one free variable.	The planes intersect along a common line or are coincident planes.
Inconsistent System	[0 0 0 | d] with d ≠ 0	No solution. A mathematical contradiction occurs (0 = d), which is impossible for any real values of the variables.	The planes share no common point of intersection (e.g., parallel planes or forming a triangular prism).

In systems where the number of variables exceeds the number of equations (such as 2×3 or 2×4 systems), the system can be consistent with infinitely many solutions even without a row of zeros. The general criterion states that a consistent system has infinitely many solutions whenever the number of pivots is less than the number of variables. The difference between these quantities defines the degrees of freedom, which represent the parameters needed to describe the solution set.

Difference between Gaussian Elimination and Gauss-Jordan Elimination

Although both methods rely on elementary row operations on the augmented matrix, they differ in where the matrix operations stop and in the final form the matrix takes.

Gaussian elimination stops row operations once the matrix reaches row echelon form (upper triangular in the coefficient submatrix, if square). From that stage forward, solving for the variables shifts to basic algebra using back-substitution.

In contrast, Gauss-Jordan elimination continues the matrix reduction process: in addition to clearing entries below each pivot, it scales each pivot to 1 and clears entries above them as well, transforming the coefficient submatrix into the identity matrix (reduced row echelon form or RREF).

The operational differences between both approaches are summarized in the comparison table below:

Feature	Gaussian Elimination	Gauss-Jordan Elimination
Final Matrix Form	Row echelon form (REF)	Reduced row echelon form (RREF)
Pivot Condition	Pivots can be any nonzero number.	All leading pivots must be scaled to 1.
Row Operations Required	Fewer operations. Forward elimination only (clearing entries below the diagonal).	More operations. Both forward and backward elimination (clearing entries above and below).
Final Solving Phase	Requires back-substitution by solving simple equations step by step.	No substitution required: variable values are read directly from the augmented column.
Efficiency for Manual Calculation	Higher. Allows working predominantly with integers, avoiding early fractions.	Lower. Forcing leading ones typically introduces fractions from the earliest steps.

Gaussian Elimination Worked Examples

Below are several step-by-step examples designed to illustrate the most frequent scenarios seen on exams and the most efficient strategies for performing row reduction without introducing unnecessary fractions.

3×3 Systems of Linear Equations

Example 1

Solve the following system of linear equations using the Gaussian elimination method:

$$\begin{cases} 2x - y + z = 1 \\ x + 2y - z = 4 \\ 3x + y + 2z = 7 \end{cases}$$

Solution

Write the augmented matrix of the system:

$$\left[\begin{array}{ccc|c} 2 & -1 & 1 & 1 \\ 1 & 2 & -1 & 4 \\ 3 & 1 & 2 & 7 \end{array}\right]$$

To begin clearing entries in the first column, we could choose 2 in the first row as the pivot. However, eliminating the 1 in the second row would require subtracting \(\frac{1}{2}\) of row 1, which introduces fractions early on and complicates subsequent calculations. Instead, it is much more practical to swap the first row with the second row to place a 1 as the leading entry. In symbols: \(R_1 \leftrightarrow R_2\).

$$\left[\begin{array}{ccc|c} 1 & 2 & -1 & 4 \\ 2 & -1 & 1 & 1 \\ 3 & 1 & 2 & 7 \end{array}\right]$$

With a pivot of 1 in the first row, eliminate the 2 in the second row. To do this, subtract twice row 1 from row 2. That is: \(R_2 \to R_2 - 2R_1\).

$$\left[\begin{array}{ccc|c} 1 & 2 & -1 & 4 \\ 0 & -5 & 3 & -7 \\ 3 & 1 & 2 & 7 \end{array}\right]$$

Next, eliminate the number 3 in the third row. Subtract three times row 1 from row 3. In symbols: \(R_3 \to R_3 - 3R_1\).

$$\left[\begin{array}{ccc|c} 1 & 2 & -1 & 4 \\ 0 & -5 & 3 & -7 \\ 0 & -5 & 5 & -5 \end{array}\right]$$

Before eliminating entries in the second column, notice that all numbers in the third row are multiples of −5. While we could continue operating directly between row 3 and row 2 with larger numbers, simplifying the row now keeps numbers manageable. Therefore, divide row 3 by −5, which is equivalent to multiplying it by \(-\frac{1}{5}\). In symbols: \(R_3 \to -\frac{1}{5}R_3\).

$$\left[\begin{array}{ccc|c} 1 & 2 & -1 & 4 \\ 0 & -5 & 3 & -7 \\ 0 & 1 & -1 & 1 \end{array}\right]$$

Again, to avoid working with the pivot −5 and generating fractions when clearing the 1 below it, swap row 2 with row 3. In symbols: \(R_2 \leftrightarrow R_3\).

$$\left[\begin{array}{ccc|c} 1 & 2 & -1 & 4 \\ 0 & 1 & -1 & 1 \\ 0 & -5 & 3 & -7 \end{array}\right]$$

The second pivot is now 1. Eliminate the number −5 below it. Add 5 times row 2 to row 3. In symbols: \(R_3 \to R_3 + 5R_2\).

$$\left[\begin{array}{ccc|c} 1 & 2 & -1 & 4 \\ 0 & 1 & -1 & 1 \\ 0 & 0 & -2 & -2 \end{array}\right]$$

The matrix is now in row echelon form. Reconstruct the system to perform back-substitution:

$$\begin{cases} x + 2y - z = 4 \\ y - z = 1 \\ -2z = -2 \end{cases}$$

Solve for z in the third equation:

$$-2z = -2 \implies z = \dfrac{-2}{-2} = 1$$

Substitute \(z = 1\) into the second equation to solve for y:

$$y - (1) = 1 \implies y = 2$$

Substitute \(y = 2\) and \(z = 1\) into the first equation to find x:

$$x + 2(2) - (1) = 4 \implies x + 4 - 1 = 4 \implies x = 1$$

The system has the unique solution \(x = 1\), \(y = 2\), \(z = 1\). It is classified as a consistent independent system. Verification is confirmed by substituting these values back into the original equations.

Example 2

Solve the following system of linear equations using the Gaussian elimination method:

$$\begin{cases} 2x + 3y + z = 1 \\ 3x + 2y + 4z = 9 \\ 4x - y + 3z = 11 \end{cases}$$

Solution

Write the corresponding augmented matrix:

$$\left[\begin{array}{ccc|c} 2 & 3 & 1 & 1 \\ 3 & 2 & 4 & 9 \\ 4 & -1 & 3 & 11 \end{array}\right]$$

The first pivot is 2. In this case, we do not have a 1 in the first column to swap rows. Standard textbook approaches suggest dividing row 1 by 2 or subtracting \(\frac{3}{2}\) of row 1 from row 2, but this fills the matrix with fractions. To avoid this, cross-multiply coefficients: multiply row 2 by 2 and subtract row 1 multiplied by 3. In symbols: \(R_2 \to 2R_2 - 3R_1\).

$$\left[\begin{array}{ccc|c} 2 & 3 & 1 & 1 \\ 0 & -5 & 5 & 15 \\ 4 & -1 & 3 & 11 \end{array}\right]$$

Now eliminate the number 4 in the third row. Since 4 is an exact multiple of 2, subtract twice row 1 from row 3. That is: \(R_3 \to R_3 - 2R_1\).

$$\left[\begin{array}{ccc|c} 2 & 3 & 1 & 1 \\ 0 & -5 & 5 & 15 \\ 0 & -7 & 1 & 9 \end{array}\right]$$

Notice that all coefficients in the second row are divisible by −5. Instead of carrying larger numbers through row combinations, divide row 2 by −5, which is equivalent to multiplying it by \(-\frac{1}{5}\). In symbols: \(R_2 \to -\frac{1}{5}R_2\).

$$\left[\begin{array}{ccc|c} 2 & 3 & 1 & 1 \\ 0 & 1 & -1 & -3 \\ 0 & -7 & 1 & 9 \end{array}\right]$$

The second pivot is now 1. Eliminate the number −7 below it. Add 7 times row 2 to row 3. In symbols: \(R_3 \to R_3 + 7R_2\).

$$\left[\begin{array}{ccc|c} 2 & 3 & 1 & 1 \\ 0 & 1 & -1 & -3 \\ 0 & 0 & -6 & -12 \end{array}\right]$$

With the matrix in row echelon form, proceed to back-substitution by reconstructing the equations:

$$\begin{cases} 2x + 3y + z = 1 \\ y - z = -3 \\ -6z = -12 \end{cases}$$

Solve for z in the third equation:

$$-6z = -12 \implies z = \dfrac{-12}{-6} = 2$$

Substitute \(z = 2\) into the second equation to solve for y:

$$y - (2) = -3 \implies y = -3 + 2 = -1$$

Substitute \(y = -1\) and \(z = 2\) into the first equation to solve for x:

$$2x + 3(-1) + (2) = 1 \implies 2x - 3 + 2 = 1 \implies 2x - 1 = 1 \implies 2x = 2 \implies x = 1$$

The unique solution is \(x = 1\), \(y = -1\), \(z = 2\). The system is a consistent independent system.

Example 3

Solve the following system of linear equations using Gaussian elimination and express its solution set if consistent:

$$\begin{cases} x + 2y - z = 3 \\ 2x + 5y + z = 7 \\ 3x + 7y = 10 \end{cases}$$

Solution

Write the augmented matrix, inserting a zero for the missing variable in the third equation:

$$\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 2 & 5 & 1 & 7 \\ 3 & 7 & 0 & 10 \end{array}\right]$$

The first pivot is 1. Eliminate the 2 in the second row by subtracting twice row 1 from row 2. In symbols: \(R_2 \to R_2 - 2R_1\).

$$\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 1 \\ 3 & 7 & 0 & 10 \end{array}\right]$$

Eliminate the number 3 in the third row by subtracting three times row 1 from row 3. That is: \(R_3 \to R_3 - 3R_1\).

$$\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 1 \\ 0 & 1 & 3 & 1 \end{array}\right]$$

The second pivot is 1. To eliminate the 1 in the third row, subtract row 2 directly from row 3. In symbols: \(R_3 \to R_3 - R_2\).

$$\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 1 \\ 0 & 0 & 0 & 0 \end{array}\right]$$

The last row consists entirely of zeros, translating algebraically to the identity \(0 = 0\). This indicates that one equation was a linear combination of the others and provides no additional constraints.

The system has 3 variables but only 2 nonzero rows. Consequently, it has \(3 - 2 = 1\) degree of freedom. It is classified as a consistent dependent system and has infinitely many solutions.

To write the solution set in parametric form, assign a free parameter to the variable z: \(z = t\), where \(t \in \mathbb{R}\). From the second row, solve for y:

$$y + 3z = 1 \implies y = 1 - 3t$$

Substitute these expressions into the first equation to solve for x:

$$x + 2(1 - 3t) - t = 3 \implies x + 2 - 6t - t = 3 \implies x + 2 - 7t = 3 \implies x = 1 + 7t$$

The set of infinitely many solutions is given by:

$$\begin{cases} x = 1 + 7t \\ y = 1 - 3t \\ z = t \end{cases} \quad \text{where } t \in \mathbb{R}$$

Example 4

Determine the solution of the following system of linear equations using Gaussian reduction:

$$\begin{cases} x - y + 2z = 4 \\ 2x + y - z = 1 \\ 3x + z = 8 \end{cases}$$

Solution

Write the augmented matrix, placing a zero for the variable missing in the third equation:

$$\left[\begin{array}{ccc|c} 1 & -1 & 2 & 4 \\ 2 & 1 & -1 & 1 \\ 3 & 0 & 1 & 8 \end{array}\right]$$

The first pivot is 1. Eliminate the 2 in the second row by subtracting twice the first row from it. In symbols: \(R_2 \to R_2 - 2R_1\).

$$\left[\begin{array}{ccc|c} 1 & -1 & 2 & 4 \\ 0 & 3 & -5 & -7 \\ 3 & 0 & 1 & 8 \end{array}\right]$$

Eliminate the number 3 in the third row by subtracting three times the first row. In symbols: \(R_3 \to R_3 - 3R_1\).

$$\left[\begin{array}{ccc|c} 1 & -1 & 2 & 4 \\ 0 & 3 & -5 & -7 \\ 0 & 3 & -5 & -4 \end{array}\right]$$

The second pivot is 3. To clear the 3 in the third row, subtract row 2 from row 3. That is: \(R_3 \to R_3 - R_2\).

$$\left[\begin{array}{ccc|c} 1 & -1 & 2 & 4 \\ 0 & 3 & -5 & -7 \\ 0 & 0 & 0 & 3 \end{array}\right]$$

Analyzing the third row of the echelon matrix reveals that the coefficients of the variables are all zero while the constant term is 3. This translates to the equation:

$$0x + 0y + 0z = 3 \implies 0 = 3$$

Because this equality represents a mathematical contradiction that cannot hold for any real values of the variables, the system has no solution. It is classified as an inconsistent system.

Example 5

Solve the following linear system by Gaussian elimination:

$$\begin{cases} x + 2y = 5 \\ 2x + 3y - z = 6 \\ y + 2z = 6 \end{cases}$$

Solution

When setting up the augmented matrix, account for the missing variables in the first and third equations to keep coefficients aligned properly by column:

$$\left[\begin{array}{ccc|c} 1 & 2 & 0 & 5 \\ 2 & 3 & -1 & 6 \\ 0 & 1 & 2 & 6 \end{array}\right]$$

The first pivot is 1. The third row already contains a zero in the first column, so we only need to eliminate the 2 in the second row. Subtract twice row 1 from row 2. In symbols: \(R_2 \to R_2 - 2R_1\).

$$\left[\begin{array}{ccc|c} 1 & 2 & 0 & 5 \\ 0 & -1 & -1 & -4 \\ 0 & 1 & 2 & 6 \end{array}\right]$$

While we could operate directly with the pivot −1 in the second row, changing the sign of row 2 first simplifies arithmetic. Multiply row 2 by −1. That is: \(R_2 \to -R_2\).

$$\left[\begin{array}{ccc|c} 1 & 2 & 0 & 5 \\ 0 & 1 & 1 & 4 \\ 0 & 1 & 2 & 6 \end{array}\right]$$

With a pivot of 1 in the second row, eliminate the 1 in the third row by subtracting row 2 from it. In symbols: \(R_3 \to R_3 - R_2\).

$$\left[\begin{array}{ccc|c} 1 & 2 & 0 & 5 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 1 & 2 \end{array}\right]$$

With the matrix in row echelon form, set up the equations for back-substitution:

$$\begin{cases} x + 2y = 5 \\ y + z = 4 \\ z = 2 \end{cases}$$

The value of z is obtained directly: \(z = 2\). Substitute this value into the second equation to compute y:

$$y + (2) = 4 \implies y = 2$$

Substitute the value of y into the first equation to solve for x:

$$x + 2(2) = 5 \implies x + 4 = 5 \implies x = 1$$

The system has the unique solution \(x = 1\), \(y = 2\), \(z = 2\). It is a consistent independent system.

Example 6

Solve the following system of equations with fractional coefficients using the Gaussian elimination method:

$$\begin{cases} \dfrac{x}{2} + \dfrac{y}{3} - z = 1 \\[2ex] x - \dfrac{y}{3} + z = 2 \\[2ex] x + y - 2z = 3 \end{cases}$$

Solution

If we entered fractions directly into the augmented matrix, adding and subtracting rows would require constant common denominator computations. To simplify the problem from the start, clear fractions by multiplying each equation by the least common multiple of its denominators:

• First equation: multiply by 6 \(\implies 3x + 2y - 6z = 6\).
• Second equation: multiply by 3 \(\implies 3x - y + 3z = 6\).
• Third equation: already has integer coefficients \(\implies x + y - 2z = 3\).

The equivalent integer system is:

$$\begin{cases} 3x + 2y - 6z = 6 \\ 3x - y + 3z = 6 \\ x + y - 2z = 3 \end{cases}$$

Write the augmented matrix:

$$\left[\begin{array}{ccc|c} 3 & 2 & -6 & 6 \\ 3 & -1 & 3 & 6 \\ 1 & 1 & -2 & 3 \end{array}\right]$$

Instead of starting with the pivot 3, swap row 1 with row 3 to place the coefficient 1 in the top-left position. In symbols: \(R_1 \leftrightarrow R_3\).

$$\left[\begin{array}{ccc|c} 1 & 1 & -2 & 3 \\ 3 & -1 & 3 & 6 \\ 3 & 2 & -6 & 6 \end{array}\right]$$

With a pivot of 1, eliminate the 3 in the second row by subtracting three times row 1. That is: \(R_2 \to R_2 - 3R_1\).

$$\left[\begin{array}{ccc|c} 1 & 1 & -2 & 3 \\ 0 & -4 & 9 & -3 \\ 3 & 2 & -6 & 6 \end{array}\right]$$

Eliminate the number 3 in the third row by also subtracting three times row 1. That is: \(R_3 \to R_3 - 3R_1\).

$$\left[\begin{array}{ccc|c} 1 & 1 & -2 & 3 \\ 0 & -4 & 9 & -3 \\ 0 & -1 & 0 & -3 \end{array}\right]$$

In the second column, using the pivot −4 would introduce fractions when clearing the −1 below it. To prevent this, swap row 2 with row 3. In symbols: \(R_2 \leftrightarrow R_3\).

$$\left[\begin{array}{ccc|c} 1 & 1 & -2 & 3 \\ 0 & -1 & 0 & -3 \\ 0 & -4 & 9 & -3 \end{array}\right]$$

Multiply row 2 by −1 to work with a positive pivot: \(R_2 \to -R_2\).

$$\left[\begin{array}{ccc|c} 1 & 1 & -2 & 3 \\ 0 & 1 & 0 & 3 \\ 0 & -4 & 9 & -3 \end{array}\right]$$

Eliminate the −4 in the third row by adding 4 times row 2. In symbols: \(R_3 \to R_3 + 4R_2\).

$$\left[\begin{array}{ccc|c} 1 & 1 & -2 & 3 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 9 & 9 \end{array}\right]$$

The matrix is now in row echelon form. Reconstruct the system of equations for back-substitution:

$$\begin{cases} x + y - 2z = 3 \\ y = 3 \\ 9z = 9 \end{cases}$$

Solve for z in the third equation:

$$9z = 9 \implies z = 1$$

The second equation gives y directly: \(y = 3\). Substitute both values into the first equation to solve for x:

$$x + (3) - 2(1) = 3 \implies x + 3 - 2 = 3 \implies x + 1 = 3 \implies x = 2$$

The unique solution is \(x = 2\), \(y = 3\), \(z = 1\). It is classified as a consistent independent system.

Higher-Order and Rectangular Systems

While Gaussian elimination is commonly practiced on systems of three equations and three variables, its greatest strength is that the algorithmic procedure is identical for any dimension.

In systems of 2 equations with 2 variables (2×2 systems), the algorithm reduces to clearing a single entry in the second row, matching standard elimination. Therefore, Gaussian elimination is most valuable when solving higher-order systems (such as 4×4) or rectangular systems where the number of equations does not match the number of variables.

Example 7

Solve the following system of 4 equations with 4 variables using the Gaussian elimination algorithm:

$$\begin{cases} x + y - z + w = 3 \\ 2x - y + 2z - w = 1 \\ x + 2y + z - w = 5 \\ 2x + y + z + w = 6 \end{cases}$$

Solution

Build the corresponding augmented matrix:

$$\left[\begin{array}{cccc|c} 1 & 1 & -1 & 1 & 3 \\ 2 & -1 & 2 & -1 & 1 \\ 1 & 2 & 1 & -1 & 5 \\ 2 & 1 & 1 & 1 & 6 \end{array}\right]$$

The first pivot is 1, located in row 1. Clear the entries in the first column:

Subtract twice row 1 from row 2 (\(R_2 \to R_2 - 2R_1\)):

$$\left[\begin{array}{cccc|c} 1 & 1 & -1 & 1 & 3 \\ 0 & -3 & 4 & -3 & -5 \\ 1 & 2 & 1 & -1 & 5 \\ 2 & 1 & 1 & 1 & 6 \end{array}\right]$$

Subtract row 1 from row 3 (\(R_3 \to R_3 - R_1\)):

$$\left[\begin{array}{cccc|c} 1 & 1 & -1 & 1 & 3 \\ 0 & -3 & 4 & -3 & -5 \\ 0 & 1 & 2 & -2 & 2 \\ 2 & 1 & 1 & 1 & 6 \end{array}\right]$$

Subtract twice row 1 from row 4 (\(R_4 \to R_4 - 2R_1\)):

$$\left[\begin{array}{cccc|c} 1 & 1 & -1 & 1 & 3 \\ 0 & -3 & 4 & -3 & -5 \\ 0 & 1 & 2 & -2 & 2 \\ 0 & -1 & 3 & -1 & 0 \end{array}\right]$$

Move to the second column. Rather than operating with pivot −3, swap row 2 with row 3 to place the coefficient 1 in the pivot position. In symbols: \(R_2 \leftrightarrow R_3\).

$$\left[\begin{array}{cccc|c} 1 & 1 & -1 & 1 & 3 \\ 0 & 1 & 2 & -2 & 2 \\ 0 & -3 & 4 & -3 & -5 \\ 0 & -1 & 3 & -1 & 0 \end{array}\right]$$

With pivot 1 in the second row, eliminate the −3 in the third row by adding three times row 2 (\(R_3 \to R_3 + 3R_2\)):

$$\left[\begin{array}{cccc|c} 1 & 1 & -1 & 1 & 3 \\ 0 & 1 & 2 & -2 & 2 \\ 0 & 0 & 10 & -9 & 1 \\ 0 & -1 & 3 & -1 & 0 \end{array}\right]$$

Eliminate the −1 in the fourth row by adding row 2 directly (\(R_4 \to R_4 + R_2\)):

$$\left[\begin{array}{cccc|c} 1 & 1 & -1 & 1 & 3 \\ 0 & 1 & 2 & -2 & 2 \\ 0 & 0 & 10 & -9 & 1 \\ 0 & 0 & 5 & -3 & 2 \end{array}\right]$$

Move to the third column. To clear the 5 in the fourth row without fractions, multiply row 4 by 2 and subtract row 3. That is: \(R_4 \to 2R_4 - R_3\).

$$\left[\begin{array}{cccc|c} 1 & 1 & -1 & 1 & 3 \\ 0 & 1 & 2 & -2 & 2 \\ 0 & 0 & 10 & -9 & 1 \\ 0 & 0 & 0 & 3 & 3 \end{array}\right]$$

The matrix is now in row echelon form. Reconstruct the system to carry out back-substitution:

$$\begin{cases} x + y - z + w = 3 \\ y + 2z - 2w = 2 \\ 10z - 9w = 1 \\ 3w = 3 \end{cases}$$

Solve for w in the fourth equation:

$$3w = 3 \implies w = 1$$

Substitute \(w = 1\) into the third equation to solve for z:

$$10z - 9(1) = 1 \implies 10z = 10 \implies z = 1$$

Substitute \(z = 1\) and \(w = 1\) into the second equation to solve for y:

$$y + 2(1) - 2(1) = 2 \implies y = 2$$

Finally, substitute all three values into the first equation to solve for x:

$$x + (2) - (1) + (1) = 3 \implies x + 2 = 3 \implies x = 1$$

The system has the unique solution \(x = 1\), \(y = 2\), \(z = 1\), \(w = 1\). It is classified as a consistent independent system.

Example 8

Solve the following underdetermined system of 2 equations with 3 variables using Gaussian reduction:

$$\begin{cases} x + 2y - 3z = 4 \\ 2x + 5y - 4z = 11 \end{cases}$$

Solution

Write the corresponding rectangular augmented matrix:

$$\left[\begin{array}{ccc|c} 1 & 2 & -3 & 4 \\ 2 & 5 & -4 & 11 \end{array}\right]$$

The first pivot is 1. Eliminate the 2 in the second row by subtracting twice row 1. In symbols: \(R_2 \to R_2 - 2R_1\).

$$\left[\begin{array}{ccc|c} 1 & 2 & -3 & 4 \\ 0 & 1 & 2 & 3 \end{array}\right]$$

The matrix is already in row echelon form. With 3 variables but only 2 nonzero rows, the system has \(3 - 2 = 1\) degree of freedom. It is a consistent dependent system with infinitely many solutions.

Assign the parameter \(t \in \mathbb{R}\) to the free variable z. Solve for y in the second row:

$$y + 2z = 3 \implies y = 3 - 2t$$

Substitute the expressions for y and z into the first equation to solve for x:

$$x + 2(3 - 2t) - 3t = 4 $$

$$ x + 6 - 4t - 3t = 4 $$

$$ x + 6 - 7t = 4 $$

$$ x = -2 + 7t$$

The solution set in parametric form is:

$$\begin{cases} x = -2 + 7t \\ y = 3 - 2t \\ z = t \end{cases} \quad \text{where } t \in \mathbb{R}$$

Example 9

Determine the consistency and solve the following overdetermined system of 4 equations with 3 variables:

$$\begin{cases} x - y + z = 2 \\ 2x + y - 3z = -1 \\ x + 2y - 4z = -3 \\ 3x + 3y - 5z = 4 \end{cases}$$

Solution

Construct the 4×4 augmented matrix:

$$\left[\begin{array}{ccc|c} 1 & -1 & 1 & 2 \\ 2 & 1 & -3 & -1 \\ 1 & 2 & -4 & -3 \\ 3 & 3 & -5 & 4 \end{array}\right]$$

With a pivot of 1 in the first row, clear entries in the first column through the following operations in succession:

Subtract twice row 1 from row 2 (\(R_2 \to R_2 - 2R_1\)):

$$\left[\begin{array}{ccc|c} 1 & -1 & 1 & 2 \\ 0 & 3 & -5 & -5 \\ 1 & 2 & -4 & -3 \\ 3 & 3 & -5 & 4 \end{array}\right]$$

Subtract row 1 from row 3 (\(R_3 \to R_3 - R_1\)):

$$\left[\begin{array}{ccc|c} 1 & -1 & 1 & 2 \\ 0 & 3 & -5 & -5 \\ 0 & 3 & -5 & -5 \\ 3 & 3 & -5 & 4 \end{array}\right]$$

Subtract three times row 1 from row 4 (\(R_4 \to R_4 - 3R_1\)):

$$\left[\begin{array}{ccc|c} 1 & -1 & 1 & 2 \\ 0 & 3 & -5 & -5 \\ 0 & 3 & -5 & -5 \\ 0 & 6 & -8 & -2 \end{array}\right]$$

Move to the second column with pivot 3 in the second row. Eliminate the 3 in the third row by subtracting row 2. In symbols: \(R_3 \to R_3 - R_2\).

$$\left[\begin{array}{ccc|c} 1 & -1 & 1 & 2 \\ 0 & 3 & -5 & -5 \\ 0 & 0 & 0 & 0 \\ 0 & 6 & -8 & -2 \end{array}\right]$$

Swap row 3 with row 4 to place the zero row at the bottom, following the definition of row echelon form. That is: \(R_3 \leftrightarrow R_4\).

$$\left[\begin{array}{ccc|c} 1 & -1 & 1 & 2 \\ 0 & 3 & -5 & -5 \\ 0 & 6 & -8 & -2 \\ 0 & 0 & 0 & 0 \end{array}\right]$$

Now eliminate the 6 in the third row by subtracting twice the second row. That is: \(R_3 \to R_3 - 2R_2\).

$$\left[\begin{array}{ccc|c} 1 & -1 & 1 & 2 \\ 0 & 3 & -5 & -5 \\ 0 & 0 & 2 & 8 \\ 0 & 0 & 0 & 0 \end{array}\right]$$

The row echelon matrix contains no contradictions and features a zero row at the bottom, indicating that one of the four constraints was redundant. Reconstruct the nonzero system:

$$\begin{cases} x - y + z = 2 \\ 3y - 5z = -5 \\ 2z = 8 \end{cases}$$

Solve for z in the third equation:

$$2z = 8 \implies z = 4$$

Substitute \(z = 4\) into the second equation to solve for y:

$$3y - 5(4) = -5 \implies 3y - 20 = -5 \implies 3y = 15 \implies y = 5$$

Substitute \(y = 5\) and \(z = 4\) into the first equation to solve for x:

$$x - (5) + (4) = 2 \implies x - 1 = 2 \implies x = 3$$

Despite having more equations than variables, the constraints are consistent. The system has the unique solution \(x = 3\), \(y = 5\), \(z = 4\), classifying it as a consistent independent system.

Example 10

Analyze and solve the following system of 2 equations with 4 variables using Gaussian elimination:

$$\begin{cases} x + y - 2z + 3w = 1 \\ 2x + 2y - 3z + 8w = 5 \end{cases}$$

Solution

Write the augmented matrix of the system:

$$\left[\begin{array}{cccc|c} 1 & 1 & -2 & 3 & 1 \\ 2 & 2 & -3 & 8 & 5 \end{array}\right]$$

The first pivot is 1. Clear the entry 2 in the second row by subtracting twice row 1. In symbols: \(R_2 \to R_2 - 2R_1\).

$$\left[\begin{array}{cccc|c} 1 & 1 & -2 & 3 & 1 \\ 0 & 0 & 1 & 2 & 3 \end{array}\right]$$

The matrix is fully in row echelon form. Notice that the second pivot did not fall in the column for variable \(y\), but rather in the column for \(z\). The system has 4 variables and 2 nonzero rows, yielding \(4 - 2 = 2\) degrees of freedom. It is classified as a consistent dependent system with infinitely many solutions parameterized by two independent parameters.

The free variables correspond to the columns that do not contain a pivot: y and w. We assign them real parameters: \(y = s\) and \(w = t\), where \(s, t \in \mathbb{R}\).

From the second row, solve for z:

$$z + 2w = 3 \implies z = 3 - 2t$$

Substitute \(y = s\), \(z = 3 - 2t\), and \(w = t\) into the first equation to solve for x:

$$x + s - 2(3 - 2t) + 3t = 1 \implies x + s - 6 + 4t + 3t = 1 \implies x + s - 6 + 7t = 1$$

$$x = 7 - s - 7t$$

The set of infinitely many solutions expressed in parametric form is:

$$\begin{cases} x = 7 - s - 7t \\ y = s \\ z = 3 - 2t \\ w = t \end{cases} \quad \text{where } s, t \in \mathbb{R}$$

Applications of the Gaussian Method

Beyond solving systems of linear equations, row reduction via elementary row operations is a foundational tool across matrix algebra.

Computing the Rank of a Matrix

The rank of a matrix represents the maximum number of linearly independent rows (or columns) it contains. To find it, we apply elementary row operations until the matrix is in row echelon form.

Once in row echelon form, the rank is strictly equal to the number of nonzero rows (rows containing at least one nonzero entry). Rows consisting entirely of zeros correspond to linear combinations of the other rows and do not contribute to the rank.

Computing Determinants

Calculating the determinant of a square matrix of size 3×3 or larger using Laplace cofactor expansion often requires extensive computations with minors. Gaussian elimination simplifies this process by reducing the original matrix to an upper triangular matrix, whose determinant is simply the product of its main diagonal entries.

However, when applying Gaussian reduction to determinant computation, we must track how elementary row operations affect the final value:

• Adding a multiple of one row to another (\(R_i \to R_i + kR_j\)): does not change the determinant. This is the ideal operation for generating zeros.
• Interchanging two rows (\(R_i \leftrightarrow R_j\)): multiplies the determinant by −1. If rows are swapped, the final product must be multiplied by −1 for each swap performed.
• Multiplying a row by a scalar (\(R_i \to kR_i\)): multiplies the determinant by that scalar factor \(k\). For this reason, rows should not be scaled arbitrarily without factoring the scalar out to compensate by dividing by \(k\) at the end.