Systems of Linear Equations

Linear algebra was born from one deceptively simple question: given several linear constraints, what values satisfy all of them at once? That question is a system of linear equations, and it shows up everywhere — from mixing ingredients in a factory to fitting a regression line through data.

The book opens the entire chapter with it, and for a reason worth stating up front: “many problems can be formulated as systems of linear equations, and linear algebra gives us the tools for solving them.”

What you’ll learn

• What makes an equation linear, and why that restriction is what makes the subject tractable.
• The three — and only three — possible solution sets, and how to tell them apart geometrically.
• The compact forms $\mathbf{A}\mathbf{x} = \mathbf{b}$ and $\sum_j x_j \mathbf{a}_j = \mathbf{b}$, and why the second is the more revealing one.
• Why “no exact solution” is the normal case in machine learning, not a failure.
• What LinAlgError: Singular matrix is actually telling you.

Intuition: the production plan

Imagine a small workshop that makes two products, tables and chairs. Each needs wood and labour:

• A table uses 4 units of wood and 2 hours of labour.
• A chair uses 1 unit of wood and 2 hours of labour.

This week you have 5 units of wood and 6 hours of labour, and you want to use them up exactly — no waste. How many tables $x_1$ and chairs $x_2$ should you make?

Each resource gives you one equation:

$$\begin{aligned} 4x_1 + 1x_2 &= 5 \quad \text{(wood)}\\ 2x_1 + 2x_2 &= 6 \quad \text{(labour)} \end{aligned}$$

Two equations, two unknowns. This is a system of linear equations, and it is the book’s own motivating example in miniature: products consuming resources, and an optimal plan being exactly a solution with nothing left over.

diagram Diagram mermaid

  flowchart TD
  P["one resource
= one equation"] --> S["system of
linear equations"]
  Q["one product
= one unknown"] --> S
  S --> G["geometry:
intersect the constraints"]
  G --> A["exactly ONE solution
lines cross at a point"]
  G --> B["NO solution
parallel, never meet"]
  G --> C["INFINITELY many
identical, fully overlap"]
  A --> ML["the rare, lucky case"]
  B --> ML2["the NORMAL case in ML
more data than parameters
-> least squares, Ch 9"]
  C --> ML3["redundant features
-> regularisation, Ch 9"]

The math

The general form

With $m$ equations and $n$ unknowns $x_1, \dots, x_n$:

$$\begin{aligned} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &= b_1\\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &= b_2\\ &\;\;\vdots\\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n &= b_m \end{aligned}$$

The $a_{ij}$ are known coefficients, the $b_i$ known constants, and the $x_j$ the unknowns. Any $n$-tuple $(x_1, \dots, x_n)$ satisfying every equation simultaneously is a solution.

The word “linear”

Every unknown appears to the first power only — no $x^2$, no $x_1 x_2$, no $\sin(x)$. That single restriction is what makes these systems solvable in closed form, and it is why so much of machine learning is built on top of them. When a model is “nonlinear”, the usual move is to apply a nonlinear feature map and then solve a linear system in the transformed features (§9.2) — the linearity is too useful to give up.

Two compact forms, and why the second one matters more

Collecting coefficients into a matrix gives the form everyone knows:

$$\begin{bmatrix} a_{11} & \cdots & a_{1n}\\ \vdots & & \vdots\\ a_{m1} & \cdots & a_{mn}\end{bmatrix} \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} b_1 \\ \vdots \\ b_m \end{bmatrix} \qquad\Longleftrightarrow\qquad \mathbf{A}\mathbf{x} = \mathbf{b}$$

But the book writes it a second way first, and that ordering is deliberate:

$$x_1\begin{bmatrix} a_{11}\\ \vdots\\ a_{m1}\end{bmatrix} + x_2\begin{bmatrix} a_{12}\\ \vdots\\ a_{m2}\end{bmatrix} + \cdots + x_n\begin{bmatrix} a_{1n}\\ \vdots\\ a_{mn}\end{bmatrix} = \begin{bmatrix} b_1\\ \vdots\\ b_m\end{bmatrix}$$

Read that carefully. The unknowns are scaling the columns. So solving $\mathbf{A}\mathbf{x} = \mathbf{b}$ is asking: can $\mathbf{b}$ be built as a weighted combination of the columns of $\mathbf{A}$, and if so, with which weights?

That reframing is the single most useful sentence in this chapter, because it converts a question about equations into a question about reach: is $\mathbf{b}$ inside the set of things the columns can build? §2.5 names that set the span, §2.6 measures it as the rank, and §2.7 calls it the image. Three sections, one question, first asked here.

Exactly three outcomes

For a real-valued system there are only three possibilities: no solution, exactly one, or infinitely many. Nothing else can happen — you cannot have exactly two.

With two unknowns, each equation is a line in the $x_1x_2$-plane, and a solution must lie on all lines at once, so the solution set is their intersection:

lines	intersection	solutions
cross at a point	a point	exactly one
parallel, distinct	empty	none
identical	the whole line	infinitely many

With three unknowns each equation is a plane, and intersecting planes gives a plane, a line, a point, or nothing — the same three outcomes, one dimension up. The book states this generalisation explicitly and it keeps holding: in $\mathbb{R}^n$ each equation is a hyperplane, and the solution set is an intersection of hyperplanes.

Why “exactly two” is impossible is worth seeing, because it is the first place the structure shows. Suppose $\mathbf{x}$ and $\mathbf{y}$ are both solutions. Then for any $\lambda$,

$$\mathbf{A}\bigl(\lambda\mathbf{x} + (1-\lambda)\mathbf{y}\bigr) = \lambda\mathbf{A}\mathbf{x} + (1-\lambda)\mathbf{A}\mathbf{y} = \lambda\mathbf{b} + (1-\lambda)\mathbf{b} = \mathbf{b},$$

so the whole line through them is made of solutions. Two solutions therefore force infinitely many. Linearity does not permit a finite crowd.

Worked example by hand

Back to the tables and chairs:

$$\begin{aligned} 4x_1 + x_2 &= 5\\ 2x_1 + 2x_2 &= 6 \end{aligned}$$

From the second equation, $x_1 + x_2 = 3$, so $x_2 = 3 - x_1$. Substituting into the first:

$$4x_1 + (3 - x_1) = 5 \;\Longrightarrow\; 3x_1 = 2 \;\Longrightarrow\; x_1 = \tfrac{2}{3}, \qquad x_2 = 3 - \tfrac{2}{3} = \tfrac{7}{3}.$$

Two-thirds of a table is not a useful production plan, which is a nice reminder that “solvable” and “meaningful” are different questions — but it is the unique solution.

Now the book’s own geometric example, and every step by hand:

$$\begin{aligned} 4x_1 + 4x_2 &= 5\\ 2x_1 - 4x_2 &= 1 \end{aligned}$$

Adding the two equations kills $x_2$ outright: $6x_1 = 6$, so $x_1 = 1$. Back-substituting into the first, $4 + 4x_2 = 5$, so $x_2 = \tfrac14$. The solution is $(1, \tfrac14)$ — exactly the point the book’s Figure 2.3 marks.

And a system of each of the three kinds, checked in full:

system	manipulation	outcome
$x_1 + x_2 = 3$, $x_1 - x_2 = 1$	add: $2x_1 = 4$	one: $(2, 1)$
$x_1 + x_2 = 3$, $x_1 + x_2 = 1$	subtract: $0 = 2$	none — a contradiction
$x_1 + x_2 = 3$, $2x_1 + 2x_2 = 6$	halve the second: identical	infinitely many: $(t, 3-t)$

The middle row is the one to remember. Elimination did not fail or get stuck; it produced the perfectly well-formed statement $0 = 2$, which is false. Inconsistency shows up as a false arithmetic claim, and that is precisely what §2.3’s elimination procedure is built to surface.

See it move

Two lines. The amber one is fixed; the blue one sweeps through all three regimes. The white dot marks the solution when it exists — watch it fly off to infinity as the lines become parallel, then the lines merge.

sketch The three solution regimes of a 2-variable system p5.js Pause Restart

Two lines on the plane. The amber line is fixed; the blue line sweeps from crossing it (one solution) to parallel (no solution) to coincident (infinitely many). The white dot is the unique solution when it exists.

Watch the det readout in the corner. It slides towards zero as the lines become parallel and hits zero exactly when the regime changes. That number is the determinant (§4.1), and it is the single quantity deciding which of the three cases you are in — the sketch is showing you §4.1’s punchline two chapters early.

And the same system, solved step by step

Elimination on the workshop system, one row operation per frame. The pivot is ringed; the row being rewritten is amber, and the row doing the rewriting is blue.

matrixThe workshop system, eliminatedreduced row echelon form

415226

pivot columns none yetrank 0

1r = 0                                  # current pivot row2for c in range(n_cols):                # walk the columns3    p = first row >= r with A[p][c] != 04    if p is None: continue             # no pivot in this column5    if p != r: swap(A[r], A[p])6    for i in range(r + 1, n_rows):     # clear below the pivot7        f = A[i][c] / A[r][c]8        A[i] -= f * A[r]9    r += 110# reduced form: normalise each pivot to 1, then clear upwards11for each pivot (r, c) in reverse:12    A[r] /= A[r][c]13    for i in range(r):14        A[i] -= A[i][c] * A[r]

pivots0rank so far0

setupThe augmented matrix. The last column is the right-hand side; every row is one equation.

Play‹›1/13⟲

Two pivots for two unknowns means exactly one solution, and the reduced form puts it in the right-hand column.

Two pivots for two unknowns — that is what “exactly one solution” looks like mechanically, and §2.3 turns the observation into the general procedure.

From scratch

solve_system.py

import numpy as np
 
# ---- the workshop system -------------------------------------------------
# 4*x1 + 1*x2 = 5   (wood)
# 2*x1 + 2*x2 = 6   (labour)
A = np.array([[4.0, 1.0],
              [2.0, 2.0]])
b = np.array([5.0, 6.0])
 
x = np.linalg.solve(A, b)
print("tables x1 =", round(x[0], 4), " chairs x2 =", round(x[1], 4))
print("check A @ x =", A @ x)
print("determinant :", np.linalg.det(A))
 
# ---- the columns view: x scales the columns ------------------------------
c1, c2 = A[:, 0], A[:, 1]
print("x1*c1 + x2*c2 =", x[0] * c1 + x[1] * c2, " == b:", np.allclose(x[0] * c1 + x[1] * c2, b))
 
# ---- the book's Figure 2.3 system ---------------------------------------
A2 = np.array([[4.0, 4.0], [2.0, -4.0]])
b2 = np.array([5.0, 1.0])
print("\nFigure 2.3 solution:", np.linalg.solve(A2, b2))
 
# ---- the three regimes, detected rather than guessed --------------------
def classify(A, b):
    """Rank of A versus rank of the augmented matrix decides the regime."""
    rank_A = np.linalg.matrix_rank(A)
    rank_Ab = np.linalg.matrix_rank(np.c_[A, b])
    n = A.shape[1]
    if rank_A < rank_Ab:
        return "no solution"
    return "exactly one" if rank_A == n else f"infinitely many ({n - rank_A} free)"
 
cases = {
    "crossing":  (np.array([[1.0, 1.0], [1.0, -1.0]]), np.array([3.0, 1.0])),
    "parallel":  (np.array([[1.0, 1.0], [1.0,  1.0]]), np.array([3.0, 1.0])),
    "identical": (np.array([[1.0, 1.0], [2.0,  2.0]]), np.array([3.0, 6.0])),
}
print()
for name, (M, v) in cases.items():
    print(f"{name:10s} rk(A)={np.linalg.matrix_rank(M)}  "
          f"rk(A|b)={np.linalg.matrix_rank(np.c_[M, v])}  ->  {classify(M, v)}")
 
# ---- what solve does when there is not exactly one solution -------------
try:
    np.linalg.solve(cases["parallel"][0], cases["parallel"][1])
except np.linalg.LinAlgError as e:
    print("\nsolve on the parallel case:", e)

text

tables x1 = 0.6667  chairs x2 = 2.3333
check A @ x = [5. 6.]
determinant : 6.0
x1*c1 + x2*c2 = [5. 6.]  == b: True
 
Figure 2.3 solution: [1.   0.25]
 
crossing   rk(A)=2  rk(A|b)=2  ->  exactly one
parallel   rk(A)=1  rk(A|b)=2  ->  no solution
identical  rk(A)=1  rk(A|b)=1  ->  infinitely many (1 free)
 
solve on the parallel case: Singular matrix

The classify function is worth more than it looks. Comparing $\operatorname{rk}(\mathbf{A})$ with $\operatorname{rk}(\mathbf{A}\mid\mathbf{b})$ decides the regime without trying to solve anything — and that is exactly the criterion §2.6 states as a property of rank. The three-line function is that theorem, executed.

On real data

figure The three regimes, with the determinant of each system matplotlib

The determinant is nonzero only in the left panel. Zero determinant does not distinguish 'none' from 'infinitely many' — that needs the augmented rank.

figure Twelve equations, two unknowns: no exact solution exists matplotlib

Each data point demands the line pass through it — twelve constraints on two parameters. The residuals cannot all be zero, so least squares finds the closest miss instead.

Reading the plot

The second figure is the case machine learning actually lives in. Twelve data points give twelve equations in two unknowns (slope and intercept). The system is overdetermined, and unless the points happen to be exactly collinear there is no solution at all — the middle panel of the first figure, in twelve dimensions.

So the correct response is not to hunt for a better solver. It is to change the question: instead of “which line passes through every point”, ask “which line minimises the total squared miss”. That is least squares, it always has an answer, and Chapter 9 derives it. §3.8 then shows the answer is a solution to a related system — the normal equations — so the machinery of this chapter is not abandoned, it is redeployed.

From the book

Mathematics for Machine Learning §2.1 motivates the whole chapter with a production example (Example 2.1): a company makes products $N_1,\dots,N_n$ each consuming known amounts of resources $R_1,\dots,R_m$, and an optimal plan that leaves nothing over is exactly a solution to a system of linear equations (Equations 2.2–2.3). Example 2.2 gives one system of each kind — no solution, the unique solution $(1,1,1)$, and an infinitely-many case parameterised by a free variable (Equations 2.4–2.7). The Remark on the geometric interpretation states that each equation in two variables is a line and the solution set is their intersection, illustrated in Figure 2.3 for the system $4x_1+4x_2=5$, $2x_1-4x_2=1$ with solution $(1,\tfrac14)$, and notes the generalisation to planes in three variables. The columns-scaled form is Equation 2.9 and the matrix form $\mathbf{A}\mathbf{x}=\mathbf{b}$ is Equation 2.10; the book observes there that ”$x_1$ scales the first column, $x_2$ the second one”, and forward-references linear combinations to §2.5. It also notes that linear regression (Chapter 9) solves a version of Example 2.1 when we cannot solve the system.

Pitfalls

A singular matrix error is an answer, not a bug

np.linalg.solve requires a square matrix with exactly one solution. On the parallel and identical cases it raises LinAlgError: Singular matrix. That error does not distinguish “no solution” from “infinitely many” — both are singular. To tell them apart, compare $\operatorname{rk}(\mathbf{A})$ with $\operatorname{rk}(\mathbf{A}\mid\mathbf{b})$, or use np.linalg.lstsq, which returns something in every case.

A zero determinant does not mean “no solution”

It means “not exactly one”. The identical-lines case has determinant zero and infinitely many solutions. Conflating the two is the most common misreading of §4.1’s punchline.

More equations than unknowns is the normal case

An overdetermined system almost never has an exact solution, and in machine learning that is the default situation, not an error. The response is least squares (Chapter 9), not a better solver.

Fewer equations than unknowns cannot pin anything down

With $n$ unknowns and fewer than $n$ independent equations, the solution set is at least a line. Every underdetermined system either has none or infinitely many solutions — never one. In modelling terms this is an under-specified model, and the fix is more constraints, whether from data or from a regulariser.

Linearity is about the unknowns, not the data

$3x_1 + 4x_2 = 7$ is linear in $x$. So is $3\log(t)\,x_1 + 4t^2 x_2 = 7$ — the coefficients may be as nonlinear a function of the data as you like, and the system is still linear in the unknowns. That is the loophole feature maps exploit (§9.2), and missing it makes polynomial regression look like magic instead of a change of variables.

Compare

situation	shape	typically	what to do
$m = n$, independent rows	square	exactly one solution	np.linalg.solve
$m > n$ (overdetermined)	tall	no exact solution	least squares — lstsq, Chapter 9
$m < n$ (underdetermined)	wide	infinitely many	add constraints, or take the minimum-norm solution via pinv
$m = n$, dependent rows	square, singular	none or infinitely many	check $\operatorname{rk}(\mathbf{A}\mid\mathbf{b})$

pch.quizTag Check yourself

1. A system of linear equations has two distinct solutions. How many does it have in total?

   A Exactly two B Infinitely many C It depends on the number of unknowns D Two, unless the matrix is singular
   pch.quizShowAnswer

   B — Infinitely many — Any weighted average of two solutions is also a solution, because the map is linear. So two solutions force the whole line through them to be solutions — a finite crowd larger than one is impossible.

2. In the columns view, what is the equation Ax = b actually asking?

   A Whether the rows of A are independent B Whether b can be built as a weighted combination of the columns of A, and with which weights C Whether A is square D Whether the determinant is nonzero
   pch.quizShowAnswer

   B — Whether b can be built as a weighted combination of the columns of A, and with which weights — The unknowns scale the columns. That turns solvability into a question about reach — is b inside what the columns can build — which sections 2.5, 2.6 and 2.7 name the span, the rank and the image.

3. You get LinAlgError Singular matrix. What do you know?

   A There is no solution B There are infinitely many solutions C There is not exactly one solution — it could be none or infinitely many D The matrix was not square
   pch.quizShowAnswer

   C — There is not exactly one solution — it could be none or infinitely many — Both the parallel and the identical cases are singular. Distinguishing them needs the rank of A compared against the rank of the augmented matrix.

4. Twelve data points, a straight-line model with two parameters. What is the situation?

   A Twelve equations in two unknowns, almost certainly with no exact solution B Two equations in twelve unknowns, with infinitely many solutions C A square system with a unique solution D Not expressible as a linear system
   pch.quizShowAnswer

   A — Twelve equations in two unknowns, almost certainly with no exact solution — Each point demands the line pass through it, so it is overdetermined. Unless the points are exactly collinear no line satisfies all twelve, which is why the answer is least squares rather than a solver.

🧪 Try It Yourself

Exercise 1 – Solve a 2×2 system

pch.exerciseTag pch.exerciseTitle

Exercise 2 – The unknowns scale the columns

pch.exerciseTag pch.exerciseTitle

Exercise 3 – Classify a system without solving it

pch.exerciseTag pch.exerciseTitle

Exercise 4 – Two solutions force infinitely many

pch.exerciseTag pch.exerciseTitle

Exercise 5 – Overdetermined, so least squares

pch.exerciseTag pch.exerciseTitle

Recall card

• A system of linear equations asks for values satisfying several linear constraints at once, and every unknown appears to the first power only.
• Linearity is a condition on the unknowns, not the data — coefficients may be arbitrarily nonlinear functions of the inputs, which is the loophole feature maps exploit.
• The unknowns scale the columns, so solving asks whether b is reachable as a weighted combination of the columns of A.
• There are exactly three outcomes — none, one, or infinitely many — because two distinct solutions force the whole line through them to be solutions.
• Geometrically the solution set is an intersection: of lines in two variables, planes in three, hyperplanes in general.
• Inconsistency surfaces as a false arithmetic statement like $0 = 2$, rather than as a stuck computation.
• Singular matrix means “not exactly one”, not “none” — the parallel and identical cases are both singular.
• Comparing the rank of A with the rank of the augmented matrix decides the regime without solving anything.
• Overdetermined systems are the normal case in machine learning, and the response is least squares rather than a better solver.

Next: compress the whole system into one object — the matrix — which both stores data and transforms it.