Foundations — Least squares — normal equations, QR approach

Before you can read a single boxed formula in the parent note, you need every letter to mean something you can picture. This page builds each symbol from nothing, in an order where each one leans only on the ones before it. Nothing below uses a symbol that an earlier section has not already defined.

1. Numbers stacked up — a vector

The picture. A vector with 2 components is an arrow on a flat sheet of paper (2D). With 3 components it's an arrow in a room (3D). With $m$ components it's an arrow in a space we can't draw but can still reason about, called ${\mathbb{R}}^m$ — "all lists of $m$ real numbers".

Why the topic needs it. Your data (the measurements you want to fit) becomes a vector, and the answer you're solving for becomes another vector. Everything is arrows — so this is the first brick.

2. How long is an arrow — the norm

The picture. In 2D, an arrow with components $(3,4)$ is the hypotenuse of a right triangle with legs $3$ and $4$, so its length is $\sqrt{3^2+4^2}=5$. In higher dimensions we do the same thing — square every component, add, square-root.

Why the topic needs it. "Closest" means "shortest distance". The distance between two arrow-tips is the length of the arrow joining them. Least squares minimises this length. The little "$2$" in $\Vert \cdot {\Vert }_2$ just labels which kind of length (the ordinary Euclidean one).

3. Direction agreement — the dot product

The picture. The dot product measures how much two arrows point the same way.

• Same direction → big positive number.
• Perpendicular (at $90°$) → exactly zero.
• Opposite → negative.

Why the topic needs it. The whole geometric heart of least squares is "the miss-arrow is perpendicular to the menu of reachable points". Perpendicular is detected by the dot product being zero — and zero dot products are exactly what will turn geometry into equations two sections from now.

4. A grid of numbers acting on arrows — the matrix

The picture. Think of the columns ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_n$ as a set of "ingredient" arrows. The numbers $x_1,\dots ,x_n$ inside $\mathbf{x}$ are the amounts of each ingredient. $A\mathbf{x}$ is the arrow you build by mixing them.

Why "tall"? In our problem $m\ge n$: more rows (equations / data points) than columns (unknowns). This is an overdetermined system — too many demands, usually impossible to satisfy all at once.

5. When ingredients aren't wasteful — independent columns and rank

The picture. Two arrows pointing in genuinely different directions sweep out a whole plane. But if a third arrow lies flat inside that same plane, it adds nothing new — it's "dependent". Full column rank means every ingredient arrow points somewhere the others cannot reach.

Why the topic needs it. This is the make-or-break condition. If the columns are independent, the best-fit answer will be unique — there is exactly one recipe $\mathbf{x}$ that lands on the closest point. If some column is redundant, infinitely many recipes give the same closest point, and the answer is no longer unique (you then reach for the Pseudoinverse (Moore-Penrose)). Keep this flag in mind; in Section 8 it is exactly what makes the key matrix invertible. More in Column Space and Rank.

6. Every reachable point — the column space

The picture. With two independent column arrows in 3D, all their mixes sweep out a flat plane through the origin. That plane is the "menu" of reachable points. The target $\mathbf{b}$ usually floats above the plane — not on the menu.

Why the topic needs it. "There is no exact solution" means precisely "$\mathbf{b}$ is not in $\text{Col}(A)$". The best we can do is find the point on the plane nearest to $\mathbf{b}$.

7. The nearest point on the plane — orthogonal projection

The picture. Hold a pencil (that's $\mathbf{b}$) above a table (the plane). The shadow cast by a light directly overhead is the projection $\hat{\mathbf{b}}=A\hat{\mathbf{x}}$. The little arrow from the shadow up to the pencil tip is the residual $\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}$, and it stands straight up, perpendicular to the table.

Why straight up is best. Any other point on the table is farther away — its connecting arrow would be a slanted hypotenuse, and a hypotenuse is always longer than the vertical leg. That is why the minimum-distance point is the perpendicular one. Full detail lives in Orthogonal Projection.

8. From "perpendicular" to the normal equations

Now every symbol is defined, so we can watch geometry turn into algebra — this is the step the parent note boxes, built here from scratch.

Step 1 — write "perpendicular" as dot products. The residual $\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}$ stands straight up off the plane. Standing perpendicular to the plane means being perpendicular to every ingredient arrow ${\mathbf{a}}_j$ that builds the plane. Using the dot product from Section 3, "perpendicular" is "dot product zero": ${\mathbf{a}}_j^{\top }(\mathbf{b}-A\hat{\mathbf{x}})=0\text{for every column }j=1,\dots ,n.$

Step 2 — stack the $n$ separate equations into one. We have $n$ statements, one per column. Stacking the rows ${\mathbf{a}}_1^{\top },\dots ,{\mathbf{a}}_n^{\top }$ on top of each other rebuilds exactly the transpose $A^{\top }$ (transpose turns columns into rows — Section 3). So the whole batch of dot-product-zero conditions is a single matrix equation: $A^{\top }(\mathbf{b}-A\hat{\mathbf{x}})=0.$

Step 3 — multiply out. Distribute $A^{\top }$ across the bracket and move the $\mathbf{b}$ term to the other side: $A^{\top }\mathbf{b}-A^{\top }A\hat{\mathbf{x}}=0⟹\boxed{A^{\top }A\hat{\mathbf{x}}=A^{\top }\mathbf{b}}$

These are the normal equations. The word "normal" is just an old synonym for "perpendicular" — the whole thing is born from that one right angle.

9. An ideal coordinate grid — orthonormal columns and $Q$

The picture. Orthonormal columns are like the clean $x$/$y$/$z$ axes of graph paper: unit length, meeting at right angles. Projecting onto such a grid is effortless — no stretching or shearing to untangle.

10. A staircase of numbers — upper-triangular $R$

The picture. Because the bottom-left is empty, the last equation involves only the last unknown. Solve it, feed the answer upward, solve the next — this bottom-to-top zigzag is called back-substitution.

Why the topic needs it. The QR route reduces least squares to $R\hat{\mathbf{x}}=Q^{\top }\mathbf{b}$. Because $R$ is triangular, this solves instantly by back-substitution, dodging the error-amplifying step of forming $A^{\top }A$ (a danger measured by the Condition Number).

11. How the foundations connect

The map below reads top-to-bottom as a dependency chain: each box is a tool you must own before the box it points to makes sense. The two paths (normal equations and QR) reunite at the same answer.

Full symbol glossary (quick reference)

Equipment checklist

Self-test your readiness. Each line below is written as prompt ::: answer — a reveal format used across this vault: read only the left side, say your answer out loud, then uncover the right side to check. If any answer doesn't come easily, reread its section before moving to the parent note.

Once every line comes easily, the boxed formulas in the parent note will read as plain sentences. Related deep applications: Linear Regression, Pseudoinverse (Moore-Penrose).