A system of linear equations asks: which values of the unknowns satisfy several linear constraints at once? This is the oldest problem in the subject and still its computational core — training a linear model, balancing a chemical equation, and solving a circuit all reduce to it. The goal of this chapter is the algorithm of elimination and, more importantly, the two geometric pictures that make solvability obvious.
What a linear system is
A linear equation in unknowns \(x_1,\dots,x_n\) has the form \(a_1x_1+\cdots+a_nx_n=b\) — each unknown appears only to the first power, never multiplied together or inside a nonlinear function. A system of \(m\) such equations can be written compactly as \[\mA\vx = \vb,\qquad \mA\in\R^{m\times n},\ \vx\in\R^n,\ \vb\in\R^m,\] where \(\mA\) holds the coefficients, \(\vx\) the unknowns, and \(\vb\) the right-hand sides.
The system \(\;2x+y=5,\ \ x-y=1\;\) becomes \[\underbrace{\begin{bmatrix}2&1\\1&-1\end{bmatrix}}_{\mA} \underbrace{\begin{bmatrix}x\\y\end{bmatrix}}_{\vx} =\underbrace{\begin{bmatrix}5\\1\end{bmatrix}}_{\vb}.\] Its solution is \(x=2,\ y=1\).
Two geometric pictures
There are two ways to “see” \(\mA\vx=\vb\), and Gilbert Strang’s central teaching is that the second is the more powerful.
Row picture. Each equation is a line (in \(\R^2\)), plane (in \(\R^3\)), or hyperplane. A solution is a point lying on all of them — the intersection.
Column picture. Write the system as a linear combination of the columns of \(\mA\): \[x\begin{bmatrix}2\\1\end{bmatrix} + y\begin{bmatrix}1\\-1\end{bmatrix} = \begin{bmatrix}5\\1\end{bmatrix}.\] Now the question is: what combination of the column vectors produces \(\vb\)? The system is solvable exactly when \(\vb\) lies in the span of the columns of \(\mA\).
The column picture is the one to internalize: solving \(\mA\vx=\vb\) means expressing \(\vb\) as a linear combination of \(\mA\)’s columns. This reframing is what later turns “does a solution exist?” into “is \(\vb\) in the column space?” — the question at the heart of Chapter [ch:vectorspaces].
Gaussian elimination
The systematic method to solve any linear system is Gaussian elimination: use simple row operations to reduce the system to an easily-solved triangular form.
The three elementary row operations do not change the solution set:
swap two rows;
multiply a row by a nonzero scalar;
add a multiple of one row to another.
Applying these to drive entries below the diagonal to zero yields row echelon form; back-substitution then solves from the bottom up. The leading nonzero entry in each row is a pivot.
Solve \(\;x+2y+z=2,\ \ 2x+5y+3z=7,\ \ x+3y+3z=6.\) The augmented matrix and its reduction: \[\left[\begin{array}{ccc|c} 1&2&1&2\\ 2&5&3&7\\ 1&3&3&6\end{array}\right] \xrightarrow{\substack{R_2-2R_1\\ R_3-R_1}} \left[\begin{array}{ccc|c} 1&2&1&2\\ 0&1&1&3\\ 0&1&2&4\end{array}\right] \xrightarrow{R_3-R_2} \left[\begin{array}{ccc|c} 1&2&1&2\\ 0&1&1&3\\ 0&0&1&1\end{array}\right].\] Back-substitution: \(z=1\), then \(y=3-z=2\), then \(x=2-2y-z=2-4-1=-3\). Solution \((-3,2,1)\). The three pivots (\(1,1,1\)) sit on the diagonal — a full set of pivots signals a unique solution.
Reduced row echelon form (RREF)
Continuing until each pivot equals \(1\) and is the only nonzero entry in its column gives the reduced row echelon form, the canonical endpoint of elimination. RREF makes the solution (and the structure of all solutions) readable directly, and it is the engine we will use to compute the four fundamental subspaces.
Existence and uniqueness
After elimination, three outcomes are possible, and the pivots tell you which.
| Situation | Geometric meaning | Solutions |
|---|---|---|
| pivot in every column, consistent | lines meet at one point | exactly one |
| a free column (fewer pivots than unknowns) | lines/planes overlap | infinitely many |
| a pivot in the augmented column only | parallel, no common point | none (inconsistent) |
A column without a pivot corresponds to a free variable — it can take any value, and each choice yields a different solution. The presence of free variables is exactly why a system has infinitely many solutions.
“More equations than unknowns” does not guarantee a unique solution, and “more unknowns than equations” does not guarantee infinitely many. What matters is the number of pivots (the rank), not the raw counts of rows and columns. A tall system can still be inconsistent; a wide one can still be uniquely solvable on its pivot variables.
Homogeneous systems
When \(\vb=\vzero\), the system \(\mA\vx=\vzero\) is homogeneous. It always has at least the trivial solution \(\vx=\vzero\). It has nontrivial solutions exactly when there is a free variable. The set of all solutions is the null space of \(\mA\) (Chapter [ch:vectorspaces]) — our first fundamental subspace, hiding in plain sight.
“Solve \(\mA\vx=\vb\)” is the skeleton of linear regression: stacking data rows into \(\mA\) and targets into \(\vb\), we seek weights \(\vx\). Real data has more equations (samples) than unknowns (features) and no exact solution, so we will not solve it exactly — we will find the closest fit by least squares (Chapter [ch:orthogonality]). When features are redundant, free variables appear, the solution is non-unique, and regularization is needed to pick one. Elimination is also how libraries actually solve the linear systems inside Newton’s method and Gaussian processes.
import numpy as np
A = np.array([[1,2,1],[2,5,3],[1,3,3]], float)
b = np.array([2,7,6], float)
x = np.linalg.solve(A, b) # prefer solve(...) over inv(A) @ b
print(x) # [-3. 2. 1.]
print(np.linalg.matrix_rank(A)) # 3 pivots -> unique solutionChapter summary
A linear system is \(\mA\vx=\vb\); read it through the row picture (intersecting hyperplanes) and the more powerful column picture (combination of columns equal to \(\vb\)).
Gaussian elimination with three row operations reduces any system to (reduced) row echelon form; pivots drive the analysis.
Solutions number one, infinitely many, or none — determined by pivots and consistency, not by counting equations.
Free variables cause infinitely many solutions; the homogeneous system’s solutions form the null space.