Row reduction and least squares

Two equations in two unknowns can be a clean crossing of lines. Real measurement piles on more equations than unknowns: redundant surveys, noisy sensors, overdetermined recipes. Exact solution may be impossible. You still need a principled compromise.

Carl Friedrich Gauss (1777-1855) used systematic elimination while wrestling with astronomical and geodetic data, including least-squares calculations. MacTutor and the matrices-and-determinants topic page are the short historical stops. Naming caution: elimination methods are older (Newton and others appear in the lineage); Gauss's notation helped standardize hand computation, and later practice attached his name. Steal the ethic of careful bookkeeping when many equations fight at once, not a monopoly myth.

For a modern rereader, this chapter has two faces that belong together. Row reduction is organized matrix moves that simplify $A\mathbf{x}=\mathbf{b}$. Least squares is what you do when no $\mathbf{x}$ hits $\mathbf{b}$ exactly: project $\mathbf{b}$ onto the column space of $A$, tying straight back to dot products.

A linear system $A\mathbf{x}=\mathbf{b}$ asks whether $\mathbf{b}$ lies in the column space of $A$ (the span of $A$'s columns). Row operations (swap rows, scale a row, add a multiple of one row to another) produce an equivalent system: same solution set, cleaner shape. Gaussian elimination drives the matrix toward row echelon form; back substitution reads the unknowns. Inconsistent systems reveal a contradictory row such as $0=c$ with $c\neq 0$.

When $A\mathbf{x}=\mathbf{b}$ has no exact solution (typical when there are more independent equations than unknowns), least squares seeks

Geometrically, $A\hat{\mathbf{x}}$ is the projection of $\mathbf{b}$ onto the column space of $A$. The residual $\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}$ is orthogonal to every column of $A$:

Those are the normal equations. The orthogonality claim is the same projection story you met with dot products, now in the column space.

Elimination is dishwashing for equations: stack them, cancel variables methodically, do not smuggle arithmetic errors. Each row operation is a legal rewrite that preserves the solution set (for exact arithmetic).

Least squares is shadow-casting. $\mathbf{b}$ is a point hanging off the subspace of reachable $A\mathbf{x}$ vectors. Drop a perpendicular. The foot of the perpendicular is the closest reachable prediction. Squared length of the leftover is the residual sum of squares.

Fitting a line $y \approx mx+c$ through many noisy points is this story in coordinates: stack rows $(x_i, 1)$, form $A$, and solve for $(m,c)$ in the least-squares sense.

Algebrica's Gaussian elimination and systems pages drill the moves; the inner-product page refreshes why orthogonality of the residual is the defining geometry.

Row reduction changes the answer. Done correctly, it changes the costume, not the solution set. Pivoting strategies matter for numerical stability; the exact-arithmetic ideal is equivalence.

Least squares always finds "the truth." It finds the closest point in a chosen model class under Euclidean residual length. Wrong features, wrong subspace, wrong answer - optimally wrong.

Normal equations are always the best computational path. Forming $A^{\mathsf{T}}A$ can worsen conditioning. QR and SVD methods often compute the same geometric projection more stably. The geometry stays; the algorithm can upgrade.

Orthogonal residual means "uncorrelated with reality." It means orthogonal to the column space you chose. Features you did not include can still correlate with the residual.

Overdetermined means inconsistent always. Sometimes the extra equations agree. Overdetermined describes shape (more equations than unknowns), not automatic contradiction.

Elimination solves least squares directly without a criterion. Elimination solves exact linear systems. Least squares adds a projection criterion when exactness fails.

Gauss used elimination and least squares in concrete scientific computation. MacTutor's Gauss biography and the matrices historical topic page keep the story grounded. Legendre published on least squares around the same era; priority disputes exist and need not detain the geometry.

The durable gift is twofold: systematic simplification of linear systems, and a projection ethic when data overconstrain a linear model.

Surveyors collect more measurements than strict degrees of freedom; residuals get distributed rather than ignored. Laboratory calibrations fit lines through noisy instrument readings. Spreadsheet "Add trendline" is ordinary least squares wearing a chart menu.

Anytime you accept that equations disagree and still want one parameter vector, you are in this chapter.