Systems of Linear Equations

Open Instagram and scroll for ten seconds. The app just decided what to show you — which photo, which order, which ad. Behind that decision is a tower of math, and at the very bottom of the tower sits one humble object: a system of linear equations. Same story for the GPS routing you home, the camera autofocusing on a face, and a language model predicting the next word. Sooner or later, every one of them lands on something of the form $A\mathbf{x}=\mathbf{b}$.

But wait — look out the window. Roads curve. Light bends. The stock market zigzags. Almost nothing in real life is a straight line. So why does an entire branch of math — and the engine room of every ML model — obsess over linear things?

Reason ② is the profound one, and you shouldn't take it on faith. Test it yourself:

This zoom trick is the secret engine of this whole course. Calculus is "zoom in until it's linear." Training a neural network is "zoom in, solve the easy linear problem, take a small step, zoom in again" — a million times over. When we meet gradient descent in Unit 9, it will be exactly this widget, running in a loop.

The price of simplicity: a single straight line can't draw a circle or trace a stock chart. Linear things are simple, and simple things are limited. Machine learning's answer is to stack many linear pieces with a sprinkle of non-linear glue (a ReLU or sigmoid) between them — LEGO bricks: each brick is dumb and rectangular, but a million of them build a castle.

The slides say it precisely: linear algebra is the study of vectors and the rules for manipulating them. But a vector is not some mysterious arrow floating in an abstract space. A vector is just an ordered list of numbers — plus the promise that adding two lists, or scaling a list, gives you back the same kind of object. (That promise has a name — closure — and it's the seed of the "vector space" idea that Unit 2 grows into.)

Lists you already use every day: a house in a dataset is a vector $(\text{area},\ \text{bedrooms},\ \text{age},\ \text{price})$. A photo is a vector — one number per pixel, hundreds of thousands of them. A word inside a modern language model is a vector, the famous embedding. Even a polynomial can be treated as a vector — its list of coefficients. Even you, in your bank's risk model, are a vector.

A factory manager solves a version of this every Monday. Translate it, one resource at a time — if you make $x_1$ chairs, $x_2$ tables, $x_3$ cabinets:

Before any theory — just play. Find the production plan with your hands:

One more thing worth noticing: that was four equations for three unknowns — an overdetermined system, which usually has no solution at all. The fact that one exists here means the four constraints happen to agree. Later in this unit you'll be able to detect that directly from the matrix, no guesswork. And when an overdetermined system doesn't have a solution — which is the everyday situation in machine learning — linear regression is exactly the art of finding the best approximate solution. That story starts here.

There are exactly three, and you can generate all of them with your own hands:

The same trichotomy appeared in the slides with three variables, where each equation is a plane in 3D. Add equations ① $x_1+x_2+x_3=3$ and ② $x_1-x_2+2x_3=2$: you get $2x_1+3x_3=5$. If equation ③ says $2x_1+3x_3=1$ — contradiction, no solution. If ③ says $2x_1+3x_3=5$ — it's the other two in disguise, infinitely many, one for every choice of the free variable $x_3$. And if ③ cuts through independently (say $x_2+x_3=2$), the three planes meet at one point $(1,1,1)$. In $n$ dimensions the surfaces are called hyperplanes, we stop trying to draw them, and the story doesn't change: zero, one, or infinity. (In Section 13 you'll fly through those three planes in 3D and read each fate off a single number — the rank.)

An $(m,n)$ matrix is a grid of numbers $a_{ij}$ — $m$ rows, $n$ columns. If you've opened Excel, you've seen one. A row vector is a $(1,n)$ matrix, a column vector an $(m,1)$ matrix, and $\mathbb{R}^{m\times n}$ is the set of all such real grids. Strip our furniture problem of its variable names and plus signs, and keep only the numbers:

An entire system collapses into three letters: $A\mathbf{x}=\mathbf{b}$. This is more than shorthand — it's a doorway. The moment we stop seeing $A$ as "a stack of equations" and start seeing it as a thing that does something to $\mathbf{x}$, the whole subject opens up.

Adding two matrices: same shape, add cell by cell. Scaling by $\lambda$: multiply every cell. Multiplying two matrices is the strange one — row times column: for $A\in\mathbb{R}^{m\times k}$, $B\in\mathbb{R}^{k\times n}$, the product $C=AB$ has $c_{ij}=\sum_{l=1}^{k} a_{il}\,b_{lj}$. Trace it with your cursor:

Facts you'll use forever: $(AB)C=A(BC)$, $A(B+C)=AB+AC$, $I_mA=AI_n=A$, $\lambda(AB)=(\lambda A)B$, and for transposes — writing rows as columns, $b_{ij}=a_{ji}$ — the order-flipping rules $(A^T)^T=A$, $(A+B)^T=A^T+B^T$, $(AB)^T=B^T A^T$. A few matrices to greet by name: the identity $I$ (the do-nothing filter), the zero matrix (destroy everything), diagonal matrices (stretch each axis independently), and symmetric matrices $A=A^T$ — the nicest citizens of linear algebra; Unit 4 is very fond of them.

This is the most important section of the unit. One tiny system, three ways of seeing it — and switching between them at will is the single most useful skill in linear algebra. Whenever you're stuck, ask: which window would let me see this clearly? Our toy system:

Here's the picture to burn into your brain. Feed $A$ the two basis arrows $\hat\imath=\binom{1}{0}$ and $\hat\jmath=\binom{0}{1}$. Then $A\hat\imath$ is literally the first column of $A$, and $A\hat\jmath$ is the second column. That's not a coincidence — that's the entire game. Once you know where those two arrows land, linearity fixes everything else: $A\mathbf{x}=x_1(A\hat\imath)+x_2(A\hat\jmath)$. Four numbers, two arrows, one whole transformation of the plane.

And the determinant? The unit square (area 1) becomes a parallelogram; $\det A$ is the factor by which area got scaled — with a sign that records whether the plane got mirror-flipped. For a $2\times2$ matrix, $\det A = a_{11}a_{22}-a_{12}a_{21}$. Don't memorize first — watch first:

Nothing about the area story was special to 2D. In 3D, a matrix $A\in\mathbb{R}^{3\times3}$ carries the unit cube (volume 1) to a slanted box — a parallelepiped — and $\det A$ is its signed volume. In $n$ dimensions, $\det A$ scales hyper-volume: the same idea, just past where drawing stops working. Grab the box below and spin it:

If $A$ is "translate to French," $A^{-1}$ is "translate back." The matrix that exactly reverses $A$ satisfies $A^{-1}A = AA^{-1} = I$ — do, then undo, and you're back where you started. If it exists, solving becomes one line: $A\mathbf{x}=\mathbf{b}\Rightarrow \mathbf{x}=A^{-1}\mathbf{b}$.

Does every square matrix have one? The slides settle it constructively for $2\times 2$: pair $A$ with the candidate $B=\begin{pmatrix}a_{22}&-a_{12}\\-a_{21}&a_{11}\end{pmatrix}$ and multiply — everything cancels except $AB=(a_{11}a_{22}-a_{12}a_{21})\,I_2$. So

The determinant sits downstairs — divide by zero and the formula explodes. That's the algebra shaking hands with the geometry you just played with: the inverse exists iff space wasn't squashed flat. (Non-square matrices don't get a true inverse at all; their story — least squares — comes later in the course.)

"Fragile" deserves to be felt, not just read. Here is a system whose true answer is always $(1,1)$ — and a dial that slides its matrix toward singularity:

Before building the general algorithm, the slides hand us a system so friendly it solves itself — if we look through the column window:

Two equations, four unknowns — underconstrained, so expect infinitely many solutions. But look at the first two columns: $\binom{1}{0}$ and $\binom{0}{1}$. They can build any target instantly. So read $\mathbf{b}$ straight off: take 42 of column 1, 8 of column 2, none of the rest —

Any other solutions? Here's the trick that unlocks the whole topic: you can add zero to a solution and it stays a solution — provided you write zero cleverly, as a blend of columns that cancels out. Column 3 is buildable from the first two: $8\mathbf{c}_1+2\mathbf{c}_2-\mathbf{c}_3=\mathbf{0}$. In matrix form:

— and likewise for column 4: $-4\mathbf{c}_1+12\mathbf{c}_2+0\mathbf{c}_3-\mathbf{c}_4=\mathbf{0}$. Any multiple $\lambda_1(8,2,-1,0)^T$ or $\lambda_2(-4,12,0,-1)^T$ is an invisible ingredient: add it to $\mathbf{x}_p$ and the machine still outputs exactly $\mathbf{b}$. The complete answer:

Two honest questions before moving on. Why isn't the particular solution unique? Because any point of the solution set can play the "anchor" role — the pre-made sandwich could just as well be a different sandwich from the menu. Why aren't the wiggle vectors unique? Any two independent blends of them span the same null space. What is unique is the solution set itself — the flat sheet they describe. But wait — those "invisible ingredients" just quietly became the most important object in this unit. Before we build the big algorithm, they deserve their own spotlight.

Every matrix has a blind spot like that beam (sometimes it's just the trivial one). It has a name and a definition worth engraving:

— the null space: every input the machine sends to zero. (The subscript is a habit worth copying: $\mathbf{x}_n$ for "null solution," the inputs that answer the homogeneous question $A\mathbf{x}=\mathbf{0}$.) It's never empty: $A\mathbf{0}=\mathbf{0}$ always, so the origin is in every null space. The interesting question is whether anything else is — and here is exactly why you should care:

Watch the whole story run live. The system below is singular on purpose — $A=\begin{pmatrix}1&2\\2&4\end{pmatrix}$ (rank 1, second row a copy of the first), $\mathbf{b}=\binom{4}{8}$, null direction $\mathbf{x}_n=\binom{-2}{1}$ (check: $A\mathbf{x}_n = \binom{-2+2}{-4+4}=\mathbf{0}$). Slide $\lambda$ and keep one eye on each panel:

How big is the blind spot? Each independent null direction is one dimension of invisibility — a line, a plane, or more. The exact count will fall out of elimination in Sections 11–12: one free variable per missing pivot, $\dim N(A)=n-\operatorname{rank}(A)$. And when the blind spot is just $\{\mathbf{0}\}$? Then aliases don't exist, and solutions — when they exist — are unique. You already know that case by its other names: full rank, $\det\neq 0$, invertible.

Hand-elimination worked for chairs and tables, but a million-variable regression needs a procedure with no moods and no choices: same kind of step every time, guaranteed to finish, and a verdict — which of the three fates — at the end. That's what an algorithm is. Here it is.

First, glue $A$ and $\mathbf{b}$ into one grid — the augmented matrix $[A\,|\,\mathbf{b}]$. Then use exactly three legal moves, each one an honest re-statement of the equations: ① swap two rows (re-order the equations); ② scale a row by $\lambda\neq 0$ (multiply both sides); ③ add a multiple of one row to another (add equal things to equal things). Each move is reversible, so the solution set never changes. We are not solving a different problem — we're rewriting the same problem until the answer becomes obvious. The target shape: pivots marching down-and-right in a staircase, zeros below — row-echelon form (REF).

Formally, a matrix is in row-echelon form when all-zero rows sit at the bottom, and each row's first non-zero entry — its pivot — lies strictly to the right of the pivot above, with only zeros beneath it. Variables owning a pivot column are basic (bound); the rest are free. And notice what the last row of the big example did for us: it distilled the entire system's fate into one sentence, "$0 = a+1$" — consistent only when $a=-1$. Elimination doesn't just solve systems; it diagnoses them.

REF is making your bed: sheets tucked, sleepable. Reduced row-echelon form is hospital corners: keep going until every pivot equals 1 and is the only non-zero entry in its column — sweep upward too. Pivot columns become canonical basis vectors, and the answers sit on the right of the bar, ready to read. Unlike REF (which depends on your route), RREF is unique — it's the matrix's fingerprint.

Trick 1: solving $A\mathbf{x}=\mathbf{0}$ by inspection. Take this RREF from the slides:

The pivot columns (1, 3, 4) are "strong enough" to build the non-pivot columns (2, 5). Column 2 = 3×column 1, so 3·c₁ − 1·c₂ = 0 gives the solution $(3,-1,0,0,0)^T$. Column 5 = 3c₁ + 9c₃ − 4c₄, giving $(3,0,9,-4,-1)^T$. Spot the pattern — copy the non-pivot column's recipe, then put a −1 in that column's own slot. Every free column donates one null-space direction, and the general solution is their span.

Now the full dish — an infinite-solutions system, cooked end to end. Same matrix, but with a target on the right:

Because the pivot columns are canonical basis vectors, the particular solution is read straight off the bar: put each right-hand entry into its pivot variable's slot, zeros for the free variables — $\mathbf{x}_p=(2,0,1,-1,0)^T$. Bolt on the two null-space directions we just found, and the entire infinite family is:

Trick 2: the inverse, for free. If $A$ is invertible, its RREF is $I$ itself. Now stack $[A\,|\,I]$ and row-reduce the left half to $I$: the right half silently becomes $A^{-1}$. Why? Solving $A\mathbf{x}=\mathbf{e}_i$ for each basis vector recovers column $i$ of $A^{-1}$ — and the augmented block runs all $n$ of those systems at once: $[A\,|\,I]\to[I\,|\,A^{-1}]$. Elimination "knows" how to invert — even though (Section 8!) you'll rarely ask it to.

One digit can change everything:

In $B$, row₃ − 2·row₂ + row₁ = 0 — one row is hiding inside the other two, an agreeing friend. Change the 9 to a 10 and the dependency snaps: three real voices. Headline fact: a square $n\times n$ matrix is invertible $\iff$ rank $=n$ $\iff$ $\det\neq 0$ $\iff$ columns independent. One fact, now four languages.

Here's the profound part. Think of a matrix as a message. Rank counts the words that aren't repeats — the genuinely non-redundant information it carries. And you can count from two different sides. The row rank asks: how many of the rows are independent rules (rules that aren't blends of other rules)? The column rank asks: how many of the columns are independent ingredients (directions the recipe can actually reach)? These are different questions about different objects — rows live in $\mathbb{R}^n$, columns in $\mathbb{R}^m$ — and yet:

And rank answers the existence question completely — the three lines the whole unit was building toward:

Watch all three lines come true in 3D. Same first two planes every time; only the third equation changes — and the rank chips tell each fate before your eyes do:

① Linear systems matter because the world is locally linear, and ML is stacks of linear pieces with non-linear glue. ② $A\mathbf{x}=\mathbf{b}$ is three pictures at once — row rules, column recipe, machine — keep all three windows open. ③ $\mathbf{x}=A^{-1}\mathbf{b}$ is beautiful theory and poor practice: solve, don't inv. ④ Gaussian elimination → staircase → read off solutions, rank, inverse, and the system's fate. ⑤ Everything else this semester — LU, Cholesky, QR, even SVD — is a smarter flavor of the same elimination move.