Part II — Linear Algebra & Matrix Decompositions · Chapter 3

Matrix multiplication as projection & subspace mapping

Hook

Ax=bAx = b has no guarantee of a solution — AA can only ever produce outputs inside its column space, and bb might simply live outside it. So what does "solving" Ax=bAx=b even mean when an exact solution doesn't exist?

Intuition
a = (2.0, 1.0) (the column space, a line) | b = (3.0, 4.0) | p = proj of b onto a = (4.0, 2.0) | Ax=b exactly solvable: no | residual·a = 0.000000

Here AA's column space has collapsed to a single line (drawn through aa). Drag bb anywhere on the plane and watch pp — the closest point on that line to bb — barely budge in comparison. pp is the best AxAx can ever do.

Formalize

The projection of bb onto the line spanned by aa is the point p=tap=ta that's closest to bb, found by requiring the leftover piece to be perpendicular to aa:

p=abaaap = \frac{a \cdot b}{a \cdot a}\, a
  • aa — the vector spanning the column space (here, a single column, so the column space is a line).
  • bb — the target vector being projected.
  • pp — the projection: the closest point on the line to bb.
  1. Where this scalar comes from

    Writing p=tap=ta and demanding a(bp)=0a\cdot(b-p)=0 (the residual is perpendicular to the line) gives abt(aa)=0a\cdot b - t(a\cdot a)=0, which solves directly to t=(ab)/(aa)t=(a\cdot b)/(a\cdot a).

  2. This is exactly what Ax=b means geometrically

    When AA has one column aa, solving Ax=bAx=b means finding a scalar xx with xa=bxa=b — possible only when bb already lies on the line. pp is the nearest point on that line when it doesn't.

  3. The residual is never part of the column space

    bpb - p is perpendicular to aa by construction, so it has zero component along the only direction AA can reach — it's the part of bb that gets permanently left behind.

Play
p = (4.0, 2.0) | residual r = b - p = (-1.0, 2.0) | |r| = 2.236

Ax = b exactly solvable: no

Toggle between a bb that sits off the line (no exact solution — pp is a genuine approximation) and a bb that sits exactly on it (an exact solution exists, and p=bp=b).

Worked example

For a=(2,1)a=(2,1) and b=(3,4)b=(3,4):

  1. Compute the scalar

    ab=2(3)+1(4)=10a\cdot b = 2(3)+1(4)=10, and aa=4+1=5a\cdot a = 4+1=5, so t=10/5=2t = 10/5 = 2.

  2. Compute the projection

    p=2(2,1)=(4,2)p = 2(2,1) = (4,2) — the closest point on the line through aa to bb.

  3. Verify the residual is perpendicular to a

    bp=(3,4)(4,2)=(1,2)b-p = (3,4)-(4,2) = (-1,2). Check: a(bp)=2(1)+1(2)=2+2=0a\cdot(b-p) = 2(-1)+1(2) = -2+2 = 0 — exactly perpendicular, confirming pp really is the closest point.

Checkpoint

Drag b until its projection p onto the line spanned by a = (2.0, 1.0) lands on (4.0, 2.0). Any b that projects there will do — there's more than one right answer.

p = (0.0, 0.0)
Drag b to try it
Summary
p=abaaap = \frac{a \cdot b}{a \cdot a}\, a

Every matrix's column space is some subspace of its output space — sometimes the whole space, sometimes (as here) a lower-dimensional slice of it. Ax=bAx=b only has an exact solution when bb happens to fall inside that subspace; otherwise the best you can do is project bb onto it. This exact mechanism — minimize the perpendicular residual — is what least-squares regression solves in full generality, just with a column space spanned by many columns instead of one.