4.3 Linear systems: solving Ax = b

The everyday task of linear algebra: given an $n \times n$ matrix $A$ and an $n$ -vector $\mathbf{b}$ , find the vector $\mathbf{x}$ such that

A \mathbf{x} \;=\; \mathbf{b}.

Concretely this is a system of $n$ linear equations in $n$ unknowns. For example,

\begin{aligned} 2 x_1 + \phantom{1}x_2 - \phantom{1}x_3 &= 8, \\ -3 x_1 - \phantom{1}x_2 + 2 x_3 &= -11, \\ -2 x_1 + \phantom{1}x_2 + 2 x_3 &= -3, \end{aligned}

written as the single matrix equation

\begin{pmatrix} 2 & 1 & -1 \\ -3 & -1 & 2 \\ -2 & 1 & 2 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} \;=\; \begin{pmatrix} 8 \\ -11 \\ -3 \end{pmatrix}.

There are infinitely many ways to phrase this problem and one canonical algorithm that solves it: Gaussian elimination. The algorithm is simple, deterministic, and is exactly the row-reduction procedure that high-school algebra teaches without ever using the matrix word.

Three things that can happen

Before the algorithm, the structure. A square linear system $A \mathbf{x} = \mathbf{b}$ has one of exactly three outcomes:

A unique solution. This is the generic case — it happens precisely when $A$ is invertible, equivalently when $\det A \neq 0$ , equivalently when the columns of $A$ are linearly independent.
No solution. The system is inconsistent: the equations contradict each other. Geometrically (for two equations in two unknowns): two parallel lines that never meet. Algebraically: Gaussian elimination produces a row of the form ” $0 =$ nonzero”, which can’t be satisfied.
Infinitely many solutions. The equations are consistent but redundant: some are linear combinations of others. Geometrically (for three planes in 3-D): they intersect in a line or a plane rather than a point. Algebraically: elimination produces a row of all zeros, and at least one variable is free — it can take any value, with the other variables determined by it.

Cases 2 and 3 both correspond to $\det A = 0$ — a singular matrix. The distinction between them is whether $\mathbf{b}$ happens to lie in the span of $A$ ‘s columns (case 3) or doesn’t (case 2). Gaussian elimination tells you which case you’re in without you having to think about it: it just runs and you read off the answer from the final form.

The algorithm

Gaussian elimination works on the augmented matrix $[A \mid \mathbf{b}]$ — the matrix $A$ with the right-hand-side vector tacked on as an extra column:

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

Three elementary row operations are allowed, each of which preserves the solution set of the underlying linear system:

Swap two rows.
Multiply a row by a non-zero scalar.
Add a scalar multiple of one row to another.

The procedure is to use these operations to bring the matrix into upper-triangular form (zeros below the diagonal) — also called row echelon form. Once you have that, you read the answer from the bottom up by back substitution.

The standard pattern is: pick the top-left entry as the first pivot, use operation 3 to zero out everything below it in column 1, move to position (2, 2) as the next pivot, zero out below it, and so on. If the pivot position is already zero, swap rows to bring a non-zero entry there first.

Initial augmented matrix [A | b]

⎡

2	1	-1	\|	8
-3	-1	2	\|	-11
-2	1	2	\|	-3

⎤

system:

step 1 of 5

Each step performs one elementary row operation — a row swap or a "subtract a multiple of one row from another". The pivot column for the current step is highlighted. Once the matrix is in upper-triangular form (echelon), the solution is read off by back-substitution from the last row up. The inconsistent and dependent-rows presets show the two ways a 3×3 system can fail to have a unique solution: an "0 = nonzero" contradiction (no solution) or a "0 = 0" tautology (a whole line or plane of solutions).

Step through the algorithm on four representative systems: a standard $3 \times 3$ with a unique solution, one that needs a row swap to find a pivot, an inconsistent system that produces a " $0 = \text{nonzero}$ " contradiction, and a dependent system whose third equation is a linear combination of the first two.

Worked example

▶ Worked example: every step, no shortcuts

The problem. Solve

\begin{aligned} 2 x_1 + x_2 - x_3 &= 8, \\ -3 x_1 - x_2 + 2 x_3 &= -11, \\ -2 x_1 + x_2 + 2 x_3 &= -3. \end{aligned}

Step 1 — Write the augmented matrix.

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

Step 2 — Eliminate the first column below the pivot $a_{11} = 2$ . We want zeros in positions $(2, 1)$ and $(3, 1)$ .

For row 2: $R_2 \to R_2 - (-3/2) R_1 = R_2 + (3/2) R_1$ .

R_2 \to \bigl(-3 + (3/2)(2),\; -1 + (3/2)(1),\; 2 + (3/2)(-1),\; -11 + (3/2)(8)\bigr) = (0,\; 1/2,\; 1/2,\; 1).

For row 3: $R_3 \to R_3 - (-2/2) R_1 = R_3 + R_1$ .

R_3 \to (-2 + 2,\; 1 + 1,\; 2 + (-1),\; -3 + 8) = (0,\; 2,\; 1,\; 5).

Matrix now:

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

Step 3 — Eliminate the second column below the pivot $a_{22} = 1/2$ . We want a zero in position $(3, 2)$ . Multiplier: $2 / (1/2) = 4$ .

$R_3 \to R_3 - 4 R_2$ :

R_3 \to (0,\; 2 - 4 \cdot 1/2,\; 1 - 4 \cdot 1/2,\; 5 - 4 \cdot 1) = (0,\; 0,\; -1,\; 1).

Matrix now in upper-triangular form:

\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 1/2 & 1/2 & 1 \\ 0 & 0 & -1 & 1 \end{array} \right].

Step 4 — Back-substitute. Read from the bottom up.

Row 3 says $-x_3 = 1$ , so $x_3 = -1$ .

Row 2 says $(1/2) x_2 + (1/2) x_3 = 1$ . Substitute $x_3 = -1$ : $(1/2) x_2 - 1/2 = 1$ , so $x_2 = 3$ .

Row 1 says $2 x_1 + x_2 - x_3 = 8$ . Substitute $x_2 = 3$ and $x_3 = -1$ : $2 x_1 + 3 - (-1) = 8$ , so $2 x_1 = 4$ and $x_1 = 2$ .

Step 5 — Final answer.

\boxed{\;\mathbf{x} = (x_1, x_2, x_3) = (2, 3, -1).\;}

Step 6 — Sanity-check by substitution.

$2(2) + 1(3) + (-1)(-1) = 4 + 3 + 1 = 8.$ ✓
$-3(2) + (-1)(3) + 2(-1) = -6 - 3 - 2 = -11.$ ✓
$-2(2) + 1(3) + 2(-1) = -4 + 3 - 2 = -3.$ ✓

What if A isn’t square?

If the system $A \mathbf{x} = \mathbf{b}$ has more equations than unknowns (overdetermined) or fewer equations than unknowns (underdetermined), the same elimination machinery still applies, but the answer is no longer a single point.

Overdetermined systems (more equations than unknowns) typically have no solution, because the equations over-constrain the unknowns. The best we can do is find the $\mathbf{x}$ that minimises $\|A \mathbf{x} - \mathbf{b}\|$ — the least-squares solution, computed using the normal equations $A^T A \mathbf{x} = A^T \mathbf{b}$ . This is the algorithm behind every regression model.
Underdetermined systems (fewer equations than unknowns) typically have infinitely many solutions, forming an affine subspace. Elimination produces free variables that parameterise the solution space.

Both extensions belong to “applied linear algebra” rather than the working subset this chapter covers. Knowing they exist is enough; the algorithms reduce, under the hood, to the same elimination procedure used here.

Connection to invertibility

Gaussian elimination also tells you whether $A$ is invertible without computing the inverse: $A$ is invertible if and only if reducing $[A \mid I]$ produces $[I \mid A^{-1}]$ without running into a row of zeros on the $A$ side. This is the same algorithm as solving $A \mathbf{x} = \mathbf{b}$ , run with $\mathbf{b}$ replaced by the columns of $I$ one at a time.

Computing inverses directly is rarely what one wants in practice — solving $A \mathbf{x} = \mathbf{b}$ by elimination is faster and more numerically stable. The conceptual point (” $A$ is invertible $\Leftrightarrow$ $A \mathbf{x} = \mathbf{b}$ has a unique solution for every $\mathbf{b}$ ”) matters; the practical action — “compute the inverse” — usually does not.

What we use this for

Linear systems are everywhere. A short, representative list:

Discretised differential equations. Every numerical method for a PDE — finite differences, finite elements, spectral collocation — turns the continuous problem into a large linear system $A \mathbf{x} = \mathbf{b}$ . The methods of Foundations 10 all reduce to “solve this linear system efficiently.”
Mode amplitudes. In separation of variables (Foundations 6.3), the Fourier-projection step that pins down the coefficients $\{A_n\}$ is, when the basis is non-orthogonal, a linear system in the coefficients.
Circuit analysis, mechanics of trusses, network flow problems, balance laws of every kind. Anything where conserved quantities are accumulated at nodes produces a linear system on those node values.
Least-squares regression. The “best fit line through these points” is the least-squares solution of an overdetermined linear system.

The next lesson, 4.4 — Eigenvalues and eigenvectors, takes us in a different direction: rather than solving $A \mathbf{x} = \mathbf{b}$ for arbitrary $\mathbf{b}$ , we ask which special inputs $\mathbf{v}$ the matrix sends to scalar multiples of themselves. The answer turns out to be the unifying concept across linear algebra.