Systems of Linear Equations: Gaussian Elimination and Gauss-Jordan Reduction

Gaussian elimination solves a system of linear equations by applying row operations to its augmented matrix until it is in echelon form and then back-substituting; Gauss–Jordan reduction continues to the reduced row echelon form, from which the solution can be read off directly. In brief: the system x + y + z = 6, 2x − y + z = 3, x + 2y − z = 2 reduces to a triangular form with z = 3, then y = 2 and x = 1. A zero row with a nonzero right-hand side, such as [0, 0 | 1], means that the system has no solution.

This guide explains the augmented matrix, the elimination algorithm, how to recognize a unique solution, infinitely many solutions or none, how free variables are used to write the general solution, and how Gauss–Jordan reduction computes an inverse, with worked examples and a table.

What is the augmented matrix?

A system of m equations in n unknowns, Ax = b, is described by its coefficient matrix A and the augmented matrix [A | b], with the right-hand sides as an extra column. Elementary row operations on [A | b] correspond to adding multiples of equations, swapping equations and scaling equations, and they do not change the set of solutions.

How does Gaussian elimination work?

The forward phase creates zeros below each pivot, from left to right, giving an echelon form. The backward phase solves from the last equation upwards. In numerical practice, one picks the entry of largest magnitude in the column as the pivot (partial pivoting) to limit rounding errors.

Example 1: a unique solution

x + y + z = 6, 2x − y + z = 3, x + 2y − z = 2. The augmented matrix is [[1, 1, 1 | 6], [2, −1, 1 | 3], [1, 2, −1 | 2]].

• R₂ → R₂ − 2R₁: (0, −3, −1 | −9). R₃ → R₃ − R₁: (0, 1, −2 | −4).
• Swap R₂ ↔ R₃. Then R₃ → R₃ + 3R₂: (0, 0, −7 | −21).

Back-substitution: z = 3; y − 2z = −4 gives y = 2; x = 6 − y − z = 1. Check in the second equation: 2 − 2 + 3 = 3 ✓.

Example 2: a 2 × 2 system

2x + 4y = 10, 3x + 5y = 13. R₁ → R₁/2: (1, 2 | 5). R₂ → R₂ − 3R₁: (0, −1 | −2). So y = 2 and x = 5 − 4 = 1.

How do you recognize the three outcomes?

After the forward phase:

• A row [0, …, 0 | c] with c ≠ 0 means the system is inconsistent (no solution).
• Otherwise, if every unknown has a pivot, there is exactly one solution.
• Otherwise, the unknowns without pivots are free variables; there are infinitely many solutions, depending on n − (number of pivots) parameters.

The count of pivots is the rank.

Example 3: infinitely many solutions

x + 2y + z = 4, 2x + 4y = 2, x + 2y + 3z = 10. As computed in the previous article, the reduced form is [[1, 2, 0 | 1], [0, 0, 1 | 3], [0, 0, 0 | 0]]. The pivots are in the columns of x and z; y is free. Setting y = s: x = 1 − 2s, z = 3. The solution set is the line (1 − 2s, s, 3). Check in the second equation: 2(1 − 2s) + 4s = 2 ✓.

Example 4: no solution

x + y = 1, 2x + 2y = 3. R₂ → R₂ − 2R₁ gives (0, 0 | 1), i.e. 0 = 1. The system is inconsistent. Geometrically, the lines are parallel and distinct.

Example 5: a homogeneous system

x + y + z = 0, x − y + 2z = 0. R₂ → R₂ − R₁: (0, −2, 1 | 0). So y = z/2, x = −y − z = −3z/2. Taking z = 2t: (−3t, t, 2t). A homogeneous system always has the trivial solution, and here also infinitely many others, since there are more unknowns than equations.

How does Gauss–Jordan reduction differ?

Gauss–Jordan elimination continues the forward phase by clearing the entries above the pivots and scaling each pivot to 1, producing the reduced row echelon form. The solution can be read directly with no back-substitution. It needs somewhat more arithmetic (about n³/2 multiplications versus n³/3 for Gaussian elimination on an n × n system), so for a single system Gaussian elimination is cheaper, while for inverses Gauss–Jordan is convenient.

Example 6: Example 1 continued to RREF

From [[1, 1, 1 | 6], [0, 1, −2 | −4], [0, 0, −7 | −21]]: R₃ → −R₃/7: (0, 0, 1 | 3). R₂ → R₂ + 2R₃: (0, 1, 0 | 2). R₁ → R₁ − R₂ − R₃: (1, 0, 0 | 1). The last column is the solution (1, 2, 3).

How do you compute an inverse with it?

Reduce the block matrix [A | I]. If A is invertible, the result is [I | A⁻¹]; if the left block cannot be reduced to I, A is singular. The method works because the row operations are multiplication by A⁻¹ on the left.

Example 7: a 2 × 2 inverse

A = [[2, 1], [5, 3]]. [[2, 1 | 1, 0], [5, 3 | 0, 1]]. R₁ → R₁/2: (1, 1/2 | 1/2, 0). R₂ → R₂ − 5R₁: (0, 1/2 | −5/2, 1). R₂ → 2R₂: (0, 1 | −5, 2). R₁ → R₁ − (1/2)R₂: (1, 0 | 3, −1). So A⁻¹ = [[3, −1], [−5, 2]]. Check: [[2, 1], [5, 3]] · [[3, −1], [−5, 2]] = [[6 − 5, −2 + 2], [15 − 15, −5 + 6]] = I ✓.

Table of outcomes

Where does elimination come from?

The method is described in the Chinese Nine Chapters on the Mathematical Art, in the chapter on rectangular arrays (around the first century AD), and was known in Europe in the seventeenth century through Newton’s algebra notes. It carries Gauss’s name because he used it systematically in 1809 for the least squares problems of astronomy. Wilhelm Jordan described the full reduction in a geodesy handbook in 1888, and the same reduction was independently published by B. I. Clasen in 1888.

Which mistakes are common?

Arithmetic slips in a row operation

Update the whole row, including the right-hand side. Substitute the final answer back into all equations to verify.

Forgetting the free variables

When there are fewer pivots than unknowns, name the free variables explicitly and express the others through them.

Dividing by a pivot that may be zero

If a pivot position holds 0, swap with a row below that has a nonzero entry in the column.

Confusing no solution with the zero solution

A homogeneous system always has the solution 0. “No solution” occurs only for inconsistent systems with b ≠ 0.