7 days · 8 modules · from vectors to attention
Linear Algebra in a Week
Learn to read every matrix as a transformation of space, then use that one picture to understand systems of equations, rank, projections, eigenvectors and the SVD. The course ends inside a transformer, where you trace every matrix product, count its cost and see why decoding is limited by memory bandwidth.
How every module works
- Big ideaOne or two sentences that carry the whole module. Read them first and again at the end.
- Read and playEvery concept gets a full explanation, a worked example and its own lab to drag and adjust. Predict before you move anything.
- Check yourselfEvery concept section ends with a few auto-checked questions, so you test each idea right after you read it. Answers can be numbers, fractions or vectors like 2, -1.
- By handA pencil-and-paper problem with a worked solution to check against.
- BuildA NumPy project that makes the idea concrete and connects it to inference code.
The seven days
Full-time, the course takes seven days of 6 to 9 hours each: modules 1 and 2 on day 1, then one module a day. Eigenvalues (day 5) and the transformer module (day 7) are the longest, so start those days early. Work through the modules in order, because each one supplies the language the next one uses.
A typical day: about an hour of video, two or three hours on the module page and its labs, an hour on paper with the section exercises and By hand problems, and one or two hours on the Build project. Don't skip the By hand problems or the checklists; they are what make this pace safe. If a checklist item doesn't come easily, give that module an extra half day rather than pushing on.
Part-time instead? Take one module a week, or two for eigenvalues and the transformer module. That is about 10 weeks at 4 to 6 hours a week, with exactly the same content.
- Day 11 · VectorsArrows you can stretch and add. The dot product measures how much two arrows agree.3Blue1Brown ch. 1, 2, 9 · MIT 18.06 lecture 1
- Day 12 · Matrices as mapsColumns show where the basis lands. Products chain transformations, so order matters.3Blue1Brown ch. 3, 4, 5 · MIT 18.06 lecture 3
- Day 23 · Solving Ax = bRow and column pictures, elimination, pivots, A = LU, inverses and determinants of any size.3Blue1Brown ch. 6, 7 · MIT 18.06 lectures 2, 4, 18
- Day 34 · The four subspacesRank, column space and null space, and why low rank means compressible.3Blue1Brown ch. 7, 8 · MIT 18.06 lectures 6, 7, 9, 10
- Day 45 · OrthogonalityOrthogonal matrices, complex numbers and RoPE, projections, least squares and QR.MIT 18.06 lectures 14, 15, 16, 17
- Day 56 · EigenvaluesDirections a matrix only stretches, change of basis, diagonalization, Jordan blocks, symmetric matrices and power iteration.3Blue1Brown ch. 13, 14 · MIT 18.06 lectures 21, 22, 24, 25
- Day 67 · SVD and low rankRotate, stretch, rotate. Best low-rank approximations, PCA and compression.MIT 18.06 lectures 29, 31 · MIT 18.065
- Day 78 · The math inside a transformerAttention as dot products, gradients of matmuls, floating-point formats and what decoding costs.Karpathy, Let's build GPT · 3Blue1Brown on attention
Before you start
Every module ends with a NumPy project. Any of your machines will do. Make a virtual environment once and reuse it all course:
The videos are free: 3Blue1Brown's Essence of Linear Algebra for intuition, and Gilbert Strang's MIT 18.06 for depth and problem sets. If you want a second text alongside, Immersive Linear Algebra is free and interactive. Full citations for everything the course uses are on the Sources page.
Your progress
A module counts as done once every item in its end-of-module checklist is ticked. Progress lives in this browser, so it won't follow you to another device.
Module 1 · Day 1
Vectors
The big ideaA vector is an arrow you can stretch and add. Every other idea in this course is built from those two moves, and the dot product tells you how much two arrows point the same way.
Why it matters for inference. Token embeddings are vectors, attention scores are dot products between queries and keys, and the cosine similarity used for retrieval is a dot product of unit vectors.
Concepts
This module tells one story in four parts. First we say what a vector is and which space it lives in. Then we learn the only two moves a space allows: adding vectors and scaling them. Next we ask which points those moves can reach, which is the span. Finally we measure with the dot product, which gives lengths, angles and shadows. Each part builds on the one before, so take them in order.
1. What a vector is
A vector is one object you can look at in two ways. It is an arrow, with a length and a direction. It is also a list of numbers. Pictures use the arrow, code uses the list, and linear algebra needs both. Everything below works in either view, and switching between them is most of the skill.
A vector in \(\mathbb R^n\) is an ordered list of \(n\) real numbers:
The numbers \(v_1, \dots, v_n\) are its entries (or components), and \(n\) is its dimension.
The space \(\mathbb R^n\) (read "R n") is the set of all such lists. Every point in the space is a vector. You can add any two of them, or scale any one by a number, and the result is still in \(\mathbb R^n\). Those two moves are what make it a space.
Here is a concrete one, a vector in \(\mathbb R^2\):
This vector has two numbers, so it is 2-dimensional.
As an arrow: start at the origin, move 3 units right, then 2 units up. The arrow ends at the point \((3, 2)\).
The two numbers are steps along two basic directions. We call them \(\hat\imath\) and \(\hat\jmath\):
So our vector is 3 steps of \(\hat\imath\) plus 2 steps of \(\hat\jmath\):
The same definition covers every space you will meet in this course:
That last one matters for LLMs. In high dimensions the arrow view stops working, because you can't draw a 4096-dimensional arrow. The list view still works. You add it, stretch it and measure it with the same rules you'll learn here in 2D. So build your intuition with pictures in 2D and 3D, then trust the list rules wherever the pictures can't go.
Drag the tip of \(\mathbf v\). The green step walks along \(\hat\imath\) and the orange step walks along \(\hat\jmath\). The two numbers in the list are exactly the lengths of those steps.
2. Adding vectors
The definition promised two moves inside a space: adding and scaling. Every other idea in this course is built from them, so we take them one at a time.
Suppose we have two vectors:
We add them by adding matching entries:
Geometrically, this means doing one movement and then the other. Put the tail of \(\mathbf b\) at the tip of \(\mathbf a\). The sum is the arrow from the start to the end.
The order does not matter:
The two orders trace the two sides of a parallelogram. The sum is its diagonal.
3. Scaling vectors
Multiplying a vector by a number is called scaling. You multiply every entry:
Geometrically:
- A number bigger than 1 stretches the arrow.
- A number between 0 and 1 shrinks it.
- A negative number flips it to point the other way.
In every case the arrow stays on the same line through the origin.
4. Linear combinations
A linear combination uses both moves: scale some vectors, then add them.
For example, with \(\mathbf u = [2, 1]\) and \(\mathbf v = [-1, 1]\):
In general, in the list view, a combination is worked out one entry at a time:
In the arrow view, it means stretching each arrow and then placing them tip to tail.
Almost every question in this course is about linear combinations. Which ones exist? Are they unique? Which one is closest to a target?
Drag \(\mathbf u\) and \(\mathbf v\). The parallelogram shows both routes to \(\mathbf u + \mathbf v\). The slider scales \(\mathbf u\) into the purple arrow \(c\,\mathbf u\): try \(c = 2\), \(c = 0.5\) and \(c = -1\).
5. Span
The span of some vectors is every point you can reach with their linear combinations.
Take two vectors in the plane. There are three cases.
Case 1. They point in different directions. Then they span the whole plane: every point is reachable.
Case 2. They lie on the same line. Then every combination stays on that line. For example:
Whatever \(a\) and \(b\) are, the result is a multiple of \([1, 2]\).
Case 3. Both are zero. Then the span is just the origin.
In 3D the idea is the same. Two vectors in different directions span a plane. A third vector adds a new direction only if it points out of that plane.
A span is always flat and always passes through the origin. Such a set is called a subspace: a space inside a space. It passes the same test as \(\mathbb R^n\) in the definition, because adding or scaling vectors in a span never takes you out of it.
Case 2 is the important one. Two vectors in \(\mathbb R^2\) were not enough to reach all of \(\mathbb R^2\), because one of them brought no new direction. That situation leads to rank, which returns in module 4.
Drag the tips of u and v. The sliders choose the combination \(a\)·\(u\) + \(b\)·\(v\). Line \(u\) and \(v\) up and watch the reachable points collapse onto a line.
6. The dot product
The dot product takes two vectors and returns one number. Multiply matching entries, then add:
For example:
The dot product of a vector with itself gives its squared length. This is the Pythagorean theorem:
Dividing a vector by its length gives a unit vector: same direction, length exactly 1.
A unit vector keeps only the direction. You'll use this in the next section and in the build at the end of this module.
7. Dot product and angle
The dot product also measures the angle between two vectors:
In our example both lengths are 5, so:
The sign tells you how the vectors relate:
Dividing by both lengths removes the effect of size. That gives cosine similarity, which is always between −1 and 1:
Put another way, cosine similarity is the dot product of the two unit vectors, \(\hat{\mathbf u}\cdot\hat{\mathbf v}\). It compares directions only.
In LLMs, attention scores are dot products between a query and each key. Retrieval systems often rank documents by cosine similarity.
Why does the cosine appear?
The law of cosines says:
Expanding the left side with dot products gives:
Both lines describe the same quantity, so \(\mathbf u\cdot\mathbf v = \lVert\mathbf u\rVert\lVert\mathbf v\rVert\cos\theta\).
Turn \(\mathbf u\) around with the angle slider and change its length. The curve on the right is \(\mathbf u\cdot\mathbf v\) for every angle: a cosine wave whose height grows with both lengths.
u · v as θ goes from 0° to 360°
8. Projection
The projection of \(\mathbf u\) onto \(\mathbf v\) is the shadow \(\mathbf u\) casts on the line through \(\mathbf v\).
Suppose:
The shadow is some multiple of \(\mathbf v\), say \(c\,\mathbf v\). We choose \(c\) so that the leftover \(\mathbf u - c\,\mathbf v\) is perpendicular to \(\mathbf v\):
Solve for \(c\):
So the projection is:
Check: the leftover is \([3, 1] - [2, 2] = [1, -1]\), and \([1, -1]\cdot[1, 1] = 0\). It is perpendicular.
The general formula is:
If \(\mathbf v\) has length 1, the bottom is 1. Then the dot product \(\mathbf u\cdot\mathbf v\) is simply the length of the shadow.
Module 5 uses this same idea to derive least squares.
Drag u and v. The blue arrow is the projection of \(u\) onto \(v\); the dashed segment is the leftover, always at a right angle. Find a position where \(u\)·\(v\) = 0.
By hand
1. Write \(\mathbf w = [7, 4]\) as a combination \(a[1, 1] + b[1, -1]\). Then draw it: the two scaled arrows, tip to tail, should land on \((7, 4)\).
2. Using only the definition of the dot product, show that \(\mathbf u - \operatorname{proj}_{\mathbf v}(\mathbf u)\) is perpendicular to \(\mathbf v\).
Show worked solutions
1. Matching entries gives \(a + b = 7\) and \(a - b = 4\). Adding the equations gives \(2a = 11\), so \(a = 5.5\) and \(b = 1.5\). Check: \(5.5[1, 1] + 1.5[1, -1] = [7, 4]\).
2. Let \(c = \dfrac{\mathbf u\cdot\mathbf v}{\mathbf v\cdot\mathbf v}\). Then \(\mathbf v\cdot(\mathbf u - c\mathbf v) = \mathbf u\cdot\mathbf v - c\,(\mathbf v\cdot\mathbf v) = \mathbf u\cdot\mathbf v - \mathbf u\cdot\mathbf v = 0\). That particular \(c\) is the one value that makes the leftover perpendicular.
Build: embedding neighbours
The problem. Word embeddings store each word as a vector, and words with related meanings point in similar directions. You'll write the basic vector operations yourself, then use them to find each word's nearest neighbour in a small embedding table.
Setup. Create vectors.py. Write the four functions with plain Python loops, without NumPy. Use NumPy only to build the data and to check your answers.
Work through these in order and tick each one off as you finish it.
S = En @ En.T holds every cosine at once. That is the same shape of computation as \(QK^\top\) in attention, which you'll build in module 8.Show reference solution
Give every task a real try before opening this. If you're stuck on one step, read only the part you need.
Before you move on
You're ready for module 2 when you can do each of these without looking anything up.
Module 2 · Day 1
Matrices as maps
The big ideaA matrix is a function that moves every point of space, and its columns are exactly where the basis vectors \(\hat\imath\) and \(\hat\jmath\) land. Multiplying matrices chains those moves together, which is why the order matters.
Why it matters for inference. Every linear layer computes \(\mathbf y = W\mathbf x\). Knowing the shapes and cost of a matrix product is how you predict a model's speed and memory before you run it.
Concepts
1. What makes a map linear
A map takes a vector in and gives a vector out. We write it as \(T(\mathbf x)\).
A map is linear if it follows two rules:
In words: adding then mapping gives the same result as mapping then adding. The same goes for scaling.
One consequence: a linear map always sends zero to zero.
Geometrically, a linear map keeps grid lines straight, parallel and evenly spaced.
- Linear: rotations, stretches, shears, reflections.
- Not linear: shifting everything by a fixed amount (it moves the origin), or anything that bends the grid.
In LLMs, a layer computes \(W\mathbf x + \mathbf b\). That is linear plus a shift. Stack two layers with nothing between them and they collapse into one matrix:
The activation function between layers, such as ReLU or GELU, is what prevents this collapse.
Pick a map and drag \(\mathbf u\) and \(\mathbf v\). The solid arrow is \(T(\mathbf u + \mathbf v)\); the dashed path is \(T(\mathbf u) + T(\mathbf v)\). For a linear map they always end at the same point. Watch what the shift and the bend do to the grid and to that test.
2. A matrix stores where î and ĵ land
Every vector can be written using \(\hat\imath\) and \(\hat\jmath\):
Apply a linear map \(A\) to both sides. Linearity lets us apply it to each piece:
So once you know where \(\hat\imath\) and \(\hat\jmath\) land, you know where every vector lands.
A matrix stores exactly those two landing spots, as its columns:
For example, this matrix sends \(\hat\imath\) to \([0, 1]\) and \(\hat\jmath\) to \([-1, 0]\). That is a rotation by 90°:
And this one doubles every x-coordinate and leaves y alone:
3. Multiplying a matrix by a vector
Suppose:
Column view. Combine the columns, using the entries of \(\mathbf x\) as weights:
Row view. Take the dot product of each row with \(\mathbf x\):
Both give the same answer. The column view gives the picture. The row view is how most code computes it.
Set the four entries or pick a preset. The green and orange arrows are the columns, where î and ĵ land. Drag the grey \(x\) and watch Ax get built from the columns.
4. Multiplying matrices
The product \(BA\) means: do \(A\) first, then \(B\).
Read products from right to left, the same way you read \(f(g(x))\).
To build \(BA\), apply \(B\) to each column of \(A\):
Order matters. "Stretch, then rotate" is not the same as "rotate, then stretch". In general:
Grouping does not matter, because both sides mean "\(C\), then \(B\), then \(A\)":
But grouping does change the cost. A LoRA adapter computes \(BA\mathbf x\) with \(A\) of size \(16\times4096\) and \(B\) of size \(4096\times16\):
Same answer, 128 times the work.
Choose two transformations. The left plane applies \(A\) first; the right applies \(B\) first. The letter F shows orientation, so flips are easy to spot.
A first, then B · the product BA
B first, then A · the product AB
5. Shapes and cost
An \(m\times n\) matrix takes in vectors with \(n\) numbers and returns vectors with \(m\) numbers.
To multiply two matrices, the inner sizes must match. The result takes the outer sizes:
Each entry of the result is a dot product of length \(n\):
There are \(m\cdot p\) entries, and each costs \(n\) multiplies and \(n\) adds. So:
For example, one token through a \(4096\times4096\) layer:
The transpose swaps rows and columns. It reverses the order of a product:
FLOPs are only half the story. The other half is memory. A product reads \(A\) and \(B\) and writes \(C\), which moves \(mn + np + mp\) numbers.
The ratio of FLOPs to bytes moved is the arithmetic intensity. A matrix–vector product does only about 1 FLOP per byte in fp16. So it spends most of its time waiting for memory. This is why generating tokens one at a time is limited by memory bandwidth.
| Operation | Shapes | Result | FLOPs |
|---|---|---|---|
| One token through a projection | (1×4096)(4096×4096) | 1×4096 | 33.6 M |
| 32 tokens through an MLP up-projection | (32×4096)(4096×11008) | 32×11008 | 2.89 G |
| Attention scores for 2048 tokens, one head | (2048×128)(128×2048) | 2048×2048 | 1.07 G |
Pick a preset or type your own sizes. Rectangles are drawn to scale. The highlighted row of \(A\) and column of \(B\) combine into the highlighted entry of \(C\). Compare FLOPs per byte for the decode step and the attention scores.
By hand
1. Let \(S = \begin{bmatrix}1&1\\0&1\end{bmatrix}\) (a shear) and \(R = \begin{bmatrix}0&-1\\1&0\end{bmatrix}\) (a 90° rotation). Compute \(RS\) and \(SR\), then apply both to \([1, 0]\) and sketch where it goes.
2. Check \((AB)^\top = B^\top A^\top\) for \(A = \begin{bmatrix}1&2\\0&1\end{bmatrix}\) and \(B = \begin{bmatrix}3&0\\1&1\end{bmatrix}\).
Show worked solutions
1. \(RS = \begin{bmatrix}0&-1\\1&1\end{bmatrix}\) and \(SR = \begin{bmatrix}1&-1\\1&0\end{bmatrix}\). Then \(RS[1, 0] = [0, 1]\): the shear leaves \([1, 0]\) alone and the rotation turns it up. But \(SR[1, 0] = [1, 1]\): the rotation gives \([0, 1]\), then the shear pushes it right. Different results, so \(RS \ne SR\).
2. \(AB = \begin{bmatrix}5&2\\1&1\end{bmatrix}\), so \((AB)^\top = \begin{bmatrix}5&1\\2&1\end{bmatrix}\). And \(B^\top A^\top = \begin{bmatrix}3&1\\0&1\end{bmatrix}\begin{bmatrix}1&0\\2&1\end{bmatrix} = \begin{bmatrix}5&1\\2&1\end{bmatrix}\). They match.
Build: matrix multiply three ways
The problem. For \(A\) of shape \(m\times n\) and \(B\) of shape \(n\times p\), the product \(C = AB\) is \(m\times p\) with \(C_{ij} = \sum_k A_{ik}B_{kj}\). You'll compute it two ways by hand, see how far behind NumPy they are, and confirm that the order of a product matters.
Setup. Create matmul.py. Don't use @ or np.dot inside your two functions. Use them only to check results.
Work through these in order and tick each one off as you finish it.
@ exactly but run thousands of times slower. NumPy hands the work to a BLAS library that tiles the matrices to fit in cache and uses SIMD instructions. GPU kernels use the same two ideas at a much larger scale, and you'll meet them again when you profile your inference engine.Show reference solution
Give every task a real try before opening this. If you're stuck on one step, read only the part you need.
Before you move on
Module 3 · Day 2
Solving Ax = b
The big ideaSolving \(A\mathbf x = \mathbf b\) asks which combination of the columns of \(A\) produces \(\mathbf b\). Elimination finds it by subtracting multiples of rows until the system is triangular, and the multipliers it uses are the \(L\) in \(A = LU\).
Why it matters for inference. You rarely solve linear systems while serving a model, but this is where pivots, singular matrices and numerical stability first show up. The habit of never dividing by a tiny number carries straight over to fp16 and int8 work.
Concepts
1. Two ways to see a system
Suppose we want \(x\) and \(y\) such that:
Row picture. Each equation is a line in the plane. The solution is where the lines cross. Here that is the point \((1, 2)\).
Column picture. Write the same system as a combination of columns:
Now the question is: how much of each column do we need to reach \([0, 3]\)? With \(x = 1\) and \(y = 2\):
Same answer. In matrix form, we write the system as \(A\mathbf x = \mathbf b\):
There are three possible outcomes:
- One solution: the lines cross once.
- No solution: the lines are parallel.
- Infinitely many: both equations describe the same line.
In higher dimensions you can't draw the row picture. The column picture still works. It asks one question: is \(\mathbf b\) in the span of the columns?
The system is a·x + b·y = b₁ and c·x + d·y = b₂. Left: each equation is a line. Right: the columns combine to reach b. Make the determinant zero and see both pictures fail together.
Row picture
Column picture
2. Elimination
Elimination solves a system by removing one unknown at a time. Suppose:
Step 1. Subtract 3 times the first equation from the second. This removes \(x\):
Step 2. Solve for \(y\):
Step 3. Put \(y\) back into the first equation:
Check with the second equation: \(3(-4) + 4(4.5) = -12 + 18 = 6\). Correct.
Two words to know. The entry we divide by is the pivot (here, the 1 in front of \(x\)). The number we multiply by is the multiplier:
On bigger systems, repeat this column by column until the matrix is upper triangular. Then solve from the bottom row up. That last part is called back substitution.
If a pivot is 0, swap in a lower row that has a nonzero entry there. If no such row exists, the matrix is singular: the system has no solution or infinitely many.
Step through Gaussian elimination with exact fractions. The highlighted row just changed; the outlined entry is the pivot in use. Try each preset, then generate random systems and predict the next step before you click.
3. A = LU
Elimination only looks at \(A\), not at \(\mathbf b\). So we can save the work and reuse it.
Take:
Elimination uses the multiplier 3 and produces an upper-triangular matrix:
Store the multiplier in a lower-triangular matrix:
Multiply them back together:
That is the factorization \(A = LU\). \(L\) records the multipliers. \(U\) is the result of elimination.
Why bother? Factoring costs about \(\tfrac23 n^3\) FLOPs, and you pay it once. After that, each new \(\mathbf b\) costs only two quick triangular solves:
If rows were swapped during elimination, the factorization becomes \(PA = LU\). The matrix \(P\) records the swaps.
Choose the matrix size and how many right-hand sides you need to solve. Bars compare total FLOPs for three strategies. The bars are drawn on one linear scale, so a bar that is hard to see really is that much cheaper.
4. The determinant and the inverse
The determinant of a \(2\times2\) matrix is:
For example:
Geometrically, the determinant tells you how much the matrix scales area. The unit square has area 1. After the matrix acts on it, it becomes a parallelogram with area \(|\det A|\). Here, that is 10.
The sign matters too:
- \(\det A \gt 0\): orientation is kept.
- \(\det A \lt 0\): orientation is flipped, like a mirror.
- \(\det A = 0\): the plane is squashed onto a line.
The inverse \(A^{-1}\) undoes \(A\):
For a \(2\times2\) matrix there is a formula:
For our example:
Notice the determinant on the bottom. When \(\det A = 0\), the formula breaks. That matches the picture: once the plane is squashed onto a line, it can't be un-squashed.
Three useful rules:
After elimination, \(\det A\) is the product of the pivots, with one sign flip for each row swap.
np.linalg.solve(A, b): it is faster and more accurate. And a tiny determinant doesn't mean a matrix is badly behaved. \(0.1\,I\) in 100 dimensions has determinant \(10^{-100}\) and is perfectly fine. The condition number in module 7 is the right measure.Drag the tips of the two columns. The dashed square has area 1; the shaded parallelogram has area \(|\det A|\). Make the columns cross over each other to see the sign flip, and line them up to see the area and the inverse disappear.
5. Determinants of bigger matrices
For a \(3\times3\) matrix, the determinant measures volume. The three columns span a slanted box, and \(|\det A|\) is its volume.
There are two ways to compute it. Take the matrix from the By hand section:
Way 1: cofactor expansion. Go along the first row. Each entry multiplies the \(2\times2\) determinant left over when you cross out its row and column. The signs alternate \(+, -, +\):
Work out each small determinant:
Way 2: pivots. Elimination turned \(A\) into a triangular matrix with pivots 2, −8 and 1. The determinant of a triangular matrix is the product of its diagonal:
Same answer. If elimination swaps rows, flip the sign once for each swap.
In practice, always use pivots. Cofactor expansion of an \(n\times n\) matrix takes about \(n!\) steps, while elimination takes about \(n^3\):
The rules from the \(2\times2\) case still hold in every size. A zero determinant means the box is flat, so the columns are dependent and \(A\) has no inverse. And \(\det(AB) = \det A\,\det B\).
Type any \(3\times3\) matrix. The slanted box is spanned by the three columns; drag on it to turn the view. The readouts compute the determinant both ways. Make one column a combination of the others and watch the box go flat.
A (3 × 3)
By hand
Solve by elimination, then write down \(L\) and \(U\) and check that \(LU = A\). Compare your steps with the first preset in Lab 3.2.
Show worked solution
\(R_2 \leftarrow R_2 - 2R_1\) gives \([0, -8, -2 \mid -12]\). \(R_3 \leftarrow R_3 - (-1)R_1\) gives \([0, 8, 3 \mid 14]\). \(R_3 \leftarrow R_3 - (-1)R_2\) gives \([0, 0, 1 \mid 2]\).
Back substitution: \(z = 2\). Then \(-8y - 2(2) = -12\), so \(y = 1\). Then \(2x + 1 + 2 = 5\), so \(x = 1\). The solution is \((1, 1, 2)\).
\(L = \begin{bmatrix}1&0&0\\2&1&0\\-1&-1&1\end{bmatrix}\) and \(U = \begin{bmatrix}2&1&1\\0&-8&-2\\0&0&1\end{bmatrix}\). Row 3 of \(LU\) is \(-[2, 1, 1] - [0, -8, -2] + [0, 0, 1] = [-2, 7, 2]\), matching \(A\). The pivots multiply to \(\det A = 2(-8)(1) = -16\).
Build: LU with partial pivoting
The problem. Elimination turns \(A\) into an upper-triangular \(U\). If you save each multiplier in \(L\) and each row swap in \(P\), you get \(PA = LU\). After that, solving \(A\mathbf x = \mathbf b\) takes just two triangular solves. You'll build this, then see why choosing the pivot matters in floating point.
Setup. Create lu.py. Use NumPy arrays, but don't call np.linalg.solve or any other factorization inside your functions.
Work through these in order and tick each one off as you finish it.
Show reference solution
Give every task a real try before opening this. If you're stuck on one step, read only the part you need.
Before you move on
Module 4 · Day 3
The four subspaces
The big ideaRank is the number of independent directions a matrix keeps. The column space is everything \(A\) can output, the null space is everything \(A\) sends to zero, and their dimensions always add up to the number of columns.
Why it matters for inference. Low rank means compressible. A rank-8 update to a 4096×4096 weight matrix fits in two thin matrices with 0.4% of the parameters, which is the whole idea behind LoRA adapters.
Concepts
1. Linear independence
Vectors are independent if none of them can be built from the others.
For example, \([1, 0]\) and \([0, 1]\) are independent. But \([1, 2]\) and \([2, 4]\) are dependent, because:
The precise test: the only combination that gives zero is the one where every coefficient is zero.
For the dependent pair, \(2[1, 2] - 1[2, 4] = [0, 0]\) uses nonzero coefficients. So one vector is redundant.
2. Basis and dimension
A basis is a set of independent vectors that spans the space. It has just enough vectors: enough to reach everything, and none wasted.
In a basis, every vector has exactly one set of coordinates. Take this basis:
To write \(\mathbf w = [7, 4]\) in this basis, solve:
Adding the two equations gives \(c_1 = 5.5\), and then \(c_2 = 1.5\).
So the same arrow has coordinates \((7, 4)\) in the standard basis and \((5.5, 1.5)\) in this one. Changing the basis changes the coordinates, never the vector.
The number of vectors in a basis is the dimension. \(\mathbb R^n\) has dimension \(n\). So any \(n + 1\) vectors in \(\mathbb R^n\) must be dependent.
Drag the basis vectors \(\mathbf b_1\) and \(\mathbf b_2\) and watch the plane get a new grid. Drag the grey point \(\mathbf w\) to read its coordinates in that grid. Line the basis vectors up and the grid collapses: they are no longer independent.
3. Column space and null space
Every matrix comes with two important subspaces.
The column space \(C(A)\) is every possible output \(A\mathbf x\). It is the span of the columns.
The null space \(N(A)\) is every input that \(A\) sends to zero:
Take:
Both columns are multiples of \([1, 2]\). So \(C(A)\) is the line through \([1, 2]\).
For the null space, solve \(A\mathbf x = \mathbf 0\). Both rows say the same thing:
So \(N(A)\) is the line through \([-2, 1]\).
The column space tells you whether a solution exists: \(A\mathbf x = \mathbf b\) has a solution exactly when \(\mathbf b\) is in \(C(A)\).
The null space tells you whether it is unique. If \(\mathbf x_p\) is one solution, adding anything from \(N(A)\) gives another:
For example, with \(\mathbf b = [3, 6]\), every solution has the form:
And for \(\mathbf b = [1, 0]\), which is not on the line \(C(A)\), there is no solution at all.
Left is the input plane, right is the output plane. With a rank-1 matrix, the red line is the null space. Slide \(t\) to move \(x\) along it and notice that Ax doesn't move at all.
Input plane · ℝ² of x
Output plane · ℝ² of Ax
4. Rank
The rank of a matrix is the number of pivots after elimination. It also equals the number of independent columns.
Take:
Subtract 2 × row 1 from row 2, 3 × row 1 from row 3, then row 2 from row 3. That gives the reduced row echelon form:
The pivots (boxed) are in columns 1 and 3. So the rank is 2.
Columns 2 and 4 have no pivot. They are free columns. Each free column gives one solution to \(A\mathbf x = \mathbf 0\): set that free variable to 1, set the other free variables to 0, and read off the rest from \(R\):
These two vectors are a basis for the null space. Counting gives the rank–nullity theorem:
What the rank tells you:
- Rank = number of columns: solutions are unique, if they exist.
- Rank = number of rows: a solution exists for every \(\mathbf b\).
- Both: the matrix is square and invertible.
Type any 3×4 matrix: integers, decimals or fractions like 1/2. The reduced row echelon form, rank and null space update as you type. Pivots are outlined.
A (3 × 4)
Reduced row echelon form R
5. The four subspaces
Transposing \(A\) gives two more subspaces:
- The row space \(C(A^\top)\): the span of the rows.
- The left null space \(N(A^\top)\): all \(\mathbf y\) with \(A^\top\mathbf y = \mathbf 0\).
These four spaces pair up at right angles.
Why? If \(A\mathbf x = \mathbf 0\), then every row of \(A\) dotted with \(\mathbf x\) is zero. So \(\mathbf x\) is perpendicular to every row. That means the null space is perpendicular to the row space. The same argument shows the column space is perpendicular to the left null space.
| Subspace | Lives in | Dimension | Perpendicular to |
|---|---|---|---|
| Column space C(A) | ℝᵐ | r | Left null space |
| Row space C(Aᵀ) | ℝⁿ | r | Null space |
| Null space N(A) | ℝⁿ | n − r | Row space |
| Left null space N(Aᵀ) | ℝᵐ | m − r | Column space |
This gives the big picture. Every input splits into two parts:
\(A\) sends \(\mathbf x_n\) to zero. It maps the row-space part one-to-one onto the column space. Module 7's SVD finds perpendicular bases for all four spaces at once.
Strang's picture of the four subspaces. The dimensions follow the matrix you typed into the rank finder above, so change it there and come back.
6. Rank-1 matrices
Multiply a column by a row and you get a whole matrix:
This is called an outer product, written \(\mathbf u\mathbf v^\top\).
Every column is a multiple of \([1, 2]\). So the rank is 1.
Any rank-\(r\) matrix is a sum of \(r\) rank-1 matrices:
Stored this way, an \(m\times n\) matrix needs only:
For example, a rank-8 update to a \(4096\times4096\) matrix:
That is about 0.4%. This is how LoRA works: it learns a small-rank weight update \(\Delta W = BA\).
With \(r = 1\) the heat map is \(\mathbf u\mathbf v^\top\): every row is a scaled copy of every other row. Raise \(r\) to add more random rank-1 layers and watch that stripe pattern dissolve. The storage readout shows when the factors stop being a bargain.
By hand
Find the reduced row echelon form, the rank and a basis for the null space of \(A = \begin{bmatrix}1&2&3\\2&4&6\\1&1&1\end{bmatrix}\). Then check your null-space vector by multiplying.
Show worked solution
\(R_2 - 2R_1 = [0, 0, 0]\) and \(R_3 - R_1 = [0, -1, -2]\). Swap them, scale the new row 2 by \(-1\) to get \([0, 1, 2]\), then \(R_1 - 2R_2 = [1, 0, -1]\). So \(R = \begin{bmatrix}1&0&-1\\0&1&2\\0&0&0\end{bmatrix}\) and the rank is 2.
Column 3 is free. Setting \(x_3 = 1\) gives \(x_1 = 1\) and \(x_2 = -2\), so \(N(A)\) is spanned by \([1, -2, 1]\). Check: \(A[1, -2, 1] = [1 - 4 + 3,\; 2 - 8 + 6,\; 1 - 2 + 1] = [0, 0, 0]\). Rank–nullity: \(2 + 1 = 3\) columns.
Build: rank, null space and low-rank matrices
The problem. The rank of a matrix is the number of pivots in its reduced row echelon form (RREF). Its null space, the set of all \(\mathbf x\) with \(A\mathbf x = \mathbf 0\), has one basis vector for each free column. You'll compute both, test them on matrices whose rank you set yourself, and compare the result with the singular values.
Setup. Create subspaces.py. Write the reduction yourself. Use np.linalg.matrix_rank and np.linalg.svd only to compare.
Work through these in order and tick each one off as you finish it.
np.linalg.matrix_rank, and exactly \(r\) singular values are far from zero. The rest print as 0 because they sit near \(10^{-15}\), which is rounding noise. That gap between large and tiny singular values is how you'll spot compressible weight matrices in module 7.Show reference solution
Give every task a real try before opening this. If you're stuck on one step, read only the part you need.
Before you move on
Module 5 · Day 4
Orthogonality
The big ideaPerpendicular directions don't interfere with each other, which makes them easy to compute with. Projection finds the closest point in a subspace, and least squares is projection applied to \(\mathbf b\) when \(A\mathbf x = \mathbf b\) has no exact solution.
Why it matters for inference. Rotary position embeddings (RoPE) rotate pairs of query and key coordinates with orthogonal matrices, and some quantization methods multiply weights by orthogonal matrices to spread outliers out before rounding. Both rely on rotations preserving lengths and dot products.
Concepts
1. Orthogonal vectors
Two vectors are orthogonal (perpendicular) when their dot product is zero:
If they also have length 1, they are orthonormal.
Orthonormal vectors make coordinates easy. Normally you solve a system to find coordinates. With an orthonormal basis, you just take dot products:
For example, take the orthonormal basis and vector:
The coordinates are two dot products:
Check: \(\tfrac{4}{\sqrt2}\mathbf q_1 + \tfrac{2}{\sqrt2}\mathbf q_2 = 2[1, 1] + 1[1, -1] = [3, 1]\). Correct.
2. Orthogonal matrices
Put orthonormal vectors into the columns of a matrix \(Q\). Then:
For a square \(Q\), this means the inverse is just the transpose:
Orthogonal matrices keep lengths and angles the same:
Geometrically, they are rotations and reflections. For example, rotation by an angle \(\theta\):
Each column has length 1, because \(\cos^2\theta + \sin^2\theta = 1\). And the two columns are perpendicular.
In LLMs, RoPE rotates each query and key by an angle that depends on its position. Rotations combine by adding angles, so:
The score depends only on the distance \(n - m\) between the two tokens. That is exactly what RoPE is designed to do.
Drag \(\mathbf x\) and \(\mathbf y\), then rotate the plane. The lengths and the dot product never change. Turn on the reflection: lengths and dot products still survive, but orientation flips and the determinant becomes \(-1\).
3. Complex numbers and unitary matrices
A complex number has a real part and an imaginary part:
Draw it as the point \((a, b)\) in the plane. So a complex number is just a 2D vector with an extra trick: you can multiply two of them.
Multiply out the brackets and use \(i^2 = -1\):
For example, multiply \(1 + i\) by \(i\):
The point \((1, 1)\) moved to \((-1, 1)\). That is a rotation by 90°. Multiplying by \(i\) rotates.
More generally, multiplying by \(\cos\theta + i\sin\theta\) rotates by \(\theta\). This number is written \(e^{i\theta}\). As a matrix acting on \((a, b)\), it is exactly the rotation matrix from section 2:
Two more facts you need. The conjugate flips the sign of the imaginary part, and gives the squared length:
And the real dot product of two points is the real part of one conjugate times the other:
For vectors of complex numbers, the dot product uses the conjugate too. A matrix with orthonormal complex columns is called unitary. It is the complex version of an orthogonal matrix. Here \(U^*\) means "transpose and conjugate every entry":
Complex numbers also explain something you'll meet in module 6: a rotation has no real eigenvectors, but it does have complex eigenvalues, \(e^{i\theta}\) and \(e^{-i\theta}\).
Drag \(z\). The slider picks \(w = e^{i\theta}\) on the unit circle. The product \(z\,w\) is \(z\) rotated by \(\theta\), with its length unchanged.
RoPE in complex numbers. RoPE splits each query and key into pairs of numbers. It treats each pair as one complex number, and multiplies it by a rotation that depends on the token's position:
The score for this pair is the real part of conjugate-times-other:
The positions \(m\) and \(n\) only appear as \(n - m\). Shift both tokens by the same amount and the score doesn't change. Each pair uses a different angle \(\theta_j = 10000^{-2j/d}\), so some pairs rotate fast (good for nearby tokens) and some rotate slowly (good for far-away tokens).
Drag the query \(q\) and key \(k\) for one pair. Set the two positions and the angle per position. The faint arrows are the originals; the solid ones are rotated by position. Press the shift button: both arrows turn, but the score stays the same.
4. Projection onto a subspace
In module 1 we projected onto a line. Now we project \(\mathbf b\) onto the column space of a matrix \(A\).
The idea is the same. We want the point \(\mathbf p = A\hat{\mathbf x}\) whose error \(\mathbf e = \mathbf b - \mathbf p\) is perpendicular to every column:
Rearrange this to get the normal equations:
For example, project \(\mathbf b\) onto the plane spanned by two columns:
Compute both sides of the normal equations:
Then the projection and the error are:
Check: \(\mathbf e\cdot\mathbf a_1 = \tfrac23 - \tfrac23 = 0\) and \(\mathbf e\cdot\mathbf a_2 = -\tfrac23 + \tfrac23 = 0\). The error is perpendicular to the plane.
If the columns are orthonormal, \(A^\top A = I\), and the projection is simply \(\mathbf p = QQ^\top\mathbf b\).
The shaded plane is the column space of \(A\), spanned by \(\mathbf a_1\) and \(\mathbf a_2\). Drag on the picture to turn the view. Move \(\mathbf b\) with the sliders: the projection \(\mathbf p\) stays in the plane, and the dashed error always meets the plane at a right angle.
5. Least squares
Suppose we want a line \(y = c + d\,t\) through three points:
No line passes through all three. So we look for the line with the smallest total squared error.
Each point gives one equation:
Three equations, two unknowns: no exact solution. Least squares solves the normal equations instead:
Solving gives \(c = \tfrac23\) and \(d = \tfrac12\). So the best line is:
The errors are \(-\tfrac16, \tfrac13, -\tfrac16\). They are perpendicular to both columns of \(A\), just as projection promises.
The same method fits any model that is linear in its unknowns. Add a column of \(t^2\) values and you can fit a parabola.
Drag the data points. The blue line is the least-squares fit, with its errors drawn as squares. Use the sliders to set your own orange line and try to get a smaller total squared error. You can tie it, but you can't win.
6. Gram–Schmidt and QR
Gram–Schmidt turns independent vectors into orthonormal ones. Take:
Step 1. Normalize the first vector:
Step 2. Remove the part of \(\mathbf a_2\) that points along \(\mathbf q_1\):
Step 3. Normalize what is left:
Check: \(\mathbf q_1\cdot\mathbf q_2 = 0.6\cdot0.8 + 0.8\cdot(-0.6) = 0\). Perpendicular.
The numbers we used along the way (5, 0.6 and 0.8) form an upper-triangular matrix \(R\), and \(A = QR\):
QR is the reliable way to do least squares. Instead of the normal equations, solve:
This matters because forming \(A^\top A\) squares the condition number, which can lose many digits of accuracy.
Drag a and b. The projection of \(b\) onto \(a\) is blue; the dashed error is perpendicular to \(a\). Turn on Gram–Schmidt to see the error, normalized, become the second orthonormal vector.
By hand
1. Fit \(y = c + d\,t\) to the points \((0, 1)\), \((1, 2)\), \((2, 4)\) by solving the normal equations. Then check that the error vector is perpendicular to both columns of \(A\).
2. Run Gram–Schmidt on \(\mathbf a = [1, 1, 0]\) and \(\mathbf b = [1, 0, 1]\).
Show worked solutions
1. \(A = \begin{bmatrix}1&0\\1&1\\1&2\end{bmatrix}\), \(\mathbf b = [1, 2, 4]\). \(A^\top A = \begin{bmatrix}3&3\\3&5\end{bmatrix}\) and \(A^\top\mathbf b = [7, 10]\). Subtracting the first equation from the second gives \(2d = 3\), so \(d = 1.5\) and \(c = (7 - 4.5)/3 = \tfrac56\). The fitted values are \([\tfrac56, \tfrac73, \tfrac{23}6]\), so \(\mathbf e = [\tfrac16, -\tfrac13, \tfrac16]\). Its entries sum to 0, and \(0\cdot\tfrac16 + 1\cdot(-\tfrac13) + 2\cdot\tfrac16 = 0\).
2. \(\mathbf q_1 = [1, 1, 0]/\sqrt2\). Subtract the projection of \(\mathbf b\): \(\mathbf b - (\mathbf b\cdot\mathbf q_1)\mathbf q_1 = [1, 0, 1] - \tfrac12[1, 1, 0] = [0.5, -0.5, 1]\). Its length is \(\sqrt{1.5}\), so \(\mathbf q_2 = [0.5, -0.5, 1]/\sqrt{1.5} \approx [0.408, -0.408, 0.816]\). Check: \(\mathbf q_1\cdot\mathbf q_2 = (0.5 - 0.5 + 0)/(\sqrt2\sqrt{1.5}) = 0\).
Build: least squares three ways
The problem. You have 50 noisy measurements and want the quadratic \(y \approx c_0 + c_1 t + c_2 t^2\) that fits them best. With 50 equations and only 3 unknowns there's no exact solution, so least squares picks the \(\mathbf x\) that makes \(\lVert A\mathbf x - \mathbf y\rVert\) as small as possible. You'll solve it three ways and compare their accuracy.
Setup. Create least_squares.py. Write QR yourself. Don't use np.linalg.qr.
Work through these in order and tick each one off as you finish it.
Show reference solution
Give every task a real try before opening this. If you're stuck on one step, read only the part you need.
Before you move on
Module 6 · Day 5
Eigenvalues
The big ideaEigenvectors are the directions a matrix only stretches and never turns. Along them the matrix acts like a single number \(\lambda\), so repeated application becomes simple: \(A^k\mathbf v = \lambda^k\mathbf v\).
Why it matters for inference. Power iteration estimates a matrix's largest singular value, which spectral normalization uses. State-space and recurrent layers stay stable only when their state matrix has eigenvalues of magnitude below 1. PCA of activations is an eigenproblem of a covariance matrix.
Concepts
1. Eigenvectors and eigenvalues
Most vectors change direction when you multiply them by a matrix. An eigenvector does not. It only gets stretched, shrunk or flipped:
The number \(\lambda\) is the eigenvalue: how much the eigenvector gets stretched.
For example:
So \([1, 1]\) is an eigenvector with eigenvalue 3.
2. Finding eigenvalues
Rewrite \(A\mathbf v = \lambda\mathbf v\) as:
For a nonzero \(\mathbf v\) to exist, \(A - \lambda I\) must be singular. So its determinant must be zero:
For a \(2\times2\) matrix this becomes a quadratic:
For our matrix, the trace (sum of the diagonal) is 4 and the determinant is 3:
To find each eigenvector, solve \((A - \lambda I)\mathbf v = \mathbf 0\):
Two quick checks that work for any size:
Cases worth knowing:
- A triangular matrix has its eigenvalues on the diagonal.
- A rotation has no real eigenvectors, because every direction turns.
- \(\lambda = 0\) is an eigenvalue exactly when \(A\) is singular.
Drag \(x\) around the unit circle and watch Ax. When the two arrows line up, you've found an eigenvector and the ratio of their lengths is λ. Sweep traces where every unit vector lands: an ellipse.
3. Change of basis
A matrix looks different depending on which basis you describe it in. Choosing a good basis can make it much simpler.
Put the new basis vectors into the columns of a matrix \(P\). If a vector has coordinates \(\mathbf c\) in the new basis, its standard coordinates are:
Now suppose \(A\) acts on standard coordinates. To apply it to new coordinates, do three steps, read right to left:
- \(P\) translates the new coordinates to standard ones.
- \(A\) does its job.
- \(P^{-1}\) translates the result back to new coordinates.
Matrices related this way are called similar. They are the same map seen in two coordinate systems.
For example, take our symmetric matrix and use its eigenvectors as the new basis:
First compute \(AP\). Each column of \(P\) is an eigenvector, so it just gets scaled:
Then multiply by \(P^{-1}\):
In the eigenvector basis, the matrix is diagonal. It just scales one axis by 3 and the other by 1. That is what diagonalization means.
Similar matrices share everything that doesn't depend on coordinates: eigenvalues, trace, determinant and rank. Here the trace is 4 and the determinant is 3 in both forms.
Drag the basis vectors \(\mathbf b_1\) and \(\mathbf b_2\). The dashed arrows show where \(A\) sends them. The readout shows \(A\) in your basis, \(P^{-1}AP\). When each dashed arrow lies along its own basis vector, the matrix turns diagonal.
4. Powers of a matrix
Eigenvectors make repeated multiplication easy. If \(A\mathbf v = \lambda\mathbf v\), then:
Now write any vector as a combination of eigenvectors:
Then each part just gets multiplied by its own \(\lambda\), over and over:
So after many steps, the largest \(|\lambda|\) wins:
- If \(|\lambda| \gt 1\), that part grows.
- If \(|\lambda| \lt 1\), that part fades away.
Written with matrices, this is diagonalization. \(V\) holds the eigenvectors as columns, and \(\Lambda\) holds the eigenvalues on its diagonal:
Example: Fibonacci. Each step \((F_{k+1}, F_k) = (F_k + F_{k-1}, F_k)\) multiplies by:
The \(-0.618\) part fades away. So each Fibonacci number ends up about 1.618 times the one before.
In LLMs, state-space layers such as Mamba repeat a step like \(\mathbf h_{t+1} = A\mathbf h_t + \cdots\). They stay stable only if every \(|\lambda| \lt 1\).
Drag the starting vector \(\mathbf x\) and raise \(k\). The dots trace \(A\mathbf x, A^2\mathbf x, \dots\). The green and orange arrows are the two eigen-components \(c_i\lambda_i^k\mathbf v_i\): one grows or holds while the other shrinks, so the path bends toward the dominant eigenvector.
5. When there aren't enough eigenvectors
Some matrices can't be diagonalized. The simplest example is:
Its only eigenvalue is \(\lambda\), repeated twice. But \(J - \lambda I\) has a one-dimensional null space, so there is only one line of eigenvectors. That is not enough to fill \(P\).
Powers still have a clean formula. Compute a few and the pattern appears:
Notice the extra factor \(k\) in the corner. Even when \(|\lambda| \lt 1\), that corner first grows before it shrinks. For \(\lambda = 0.9\):
So a matrix whose eigenvalues all have \(|\lambda| \lt 1\) can still blow a vector up for a while. Training recurrent networks runs into this kind of temporary growth.
A matrix like \(J\) is called a Jordan block. Every square matrix is similar to a block-diagonal matrix made of Jordan blocks. That is the Jordan form. When every block is \(1\times1\), it is just the diagonal matrix from diagonalization.
You won't compute Jordan forms in practice; they are numerically fragile. What matters is the idea: eigenvalues alone don't tell the whole story about how a matrix behaves over many steps.
Both matrices have the same eigenvalue \(\lambda\). The chart shows the length of \(A^k\mathbf x\) for \(\mathbf x = [0, 1]\). The diagonal matrix shrinks steadily; the Jordan block grows first. Move \(\lambda\) closer to 1 to make the bump bigger.
6. Symmetric matrices
A matrix is symmetric when \(A = A^\top\). Symmetric matrices have two great properties:
- Their eigenvalues are real numbers.
- Their eigenvectors are perpendicular.
So we can write them with an orthogonal matrix \(Q\). This is the spectral theorem:
Our example matrix is symmetric:
And \([1, 1]\cdot[1, -1] = 0\). Perpendicular, as promised.
The eigenvalues also tell you the sign of the quadratic form \(\mathbf x^\top A\mathbf x\):
- All \(\lambda \gt 0\): \(\mathbf x^\top A\mathbf x \gt 0\) for every nonzero \(\mathbf x\). The matrix is positive definite.
- Some positive, some negative: the sign depends on the direction. The matrix is indefinite.
Covariance matrices and \(A^\top A\) are always symmetric with \(\lambda \ge 0\).
Adjust the symmetric matrix \(\begin{bmatrix}a&b\\b&d\end{bmatrix}\). The eigenvector lines always cross at a right angle and line up with the axes of the dashed ellipse. The unit circle is coloured by the sign of \(\mathbf x^\top A\mathbf x\): green where it is positive, red where it is negative.
7. Power iteration
For large matrices you can't solve \(\det(A - \lambda I) = 0\). Power iteration finds the biggest eigenvector using only matrix–vector products. The loop is:
Why it works: write the start as \(\mathbf x = c_1\mathbf v_1 + c_2\mathbf v_2\). After \(k\) steps:
The ratio \(\lambda_2/\lambda_1\) is smaller than 1 in size. So the second term shrinks, and \(\mathbf x\) turns toward \(\mathbf v_1\).
Each step shrinks the error by about \(|\lambda_2/\lambda_1|\). If the two biggest eigenvalues are close, convergence is slow.
To estimate \(\lambda_1\), use the Rayleigh quotient of the current unit vector:
Real eigenvalue solvers, and Google's PageRank, are built on this idea.
A symmetric matrix [[a, b], [b, d]]. Drag the starting vector, then step. The chart shows the error on a log scale next to the predicted rate |λ₂/λ₁|ᵏ. Compare the well-separated preset with the close-eigenvalues one.
Angle error vs. step (log scale)
By hand
Diagonalize \(A = \begin{bmatrix}4&1\\2&3\end{bmatrix}\). Then use the eigenvectors to compute \(A^3\mathbf x\) for \(\mathbf x = [2, -1]\) without multiplying matrices, and check by direct multiplication.
Show worked solution
\(\operatorname{tr}A = 7\) and \(\det A = 10\), so \(\lambda^2 - 7\lambda + 10 = (\lambda - 5)(\lambda - 2)\): \(\lambda_1 = 5\), \(\lambda_2 = 2\). For \(\lambda = 5\), \(A - 5I = \begin{bmatrix}-1&1\\2&-2\end{bmatrix}\) gives \(\mathbf v_1 = [1, 1]\). For \(\lambda = 2\), \(\begin{bmatrix}2&1\\2&1\end{bmatrix}\) gives \(\mathbf v_2 = [1, -2]\). So \(V = \begin{bmatrix}1&1\\1&-2\end{bmatrix}\) and \(\Lambda = \begin{bmatrix}5&0\\0&2\end{bmatrix}\).
Write \([2, -1] = c_1[1, 1] + c_2[1, -2]\): \(c_1 + c_2 = 2\) and \(c_1 - 2c_2 = -1\) give \(c_2 = 1\), \(c_1 = 1\). Then \(A^3\mathbf x = 125[1, 1] + 8[1, -2] = [133, 109]\). Directly: \(A\mathbf x = [7, 1]\), \(A^2\mathbf x = [29, 17]\), \(A^3\mathbf x = [133, 109]\).
Build: power iteration and its uses
The problem. If you keep multiplying a vector by \(A\) and rescaling it, it turns toward the eigenvector with the largest \(|\lambda|\). You'll implement power iteration, see what controls how fast it converges, extend it to the second eigenvalue, and use it to find a Markov chain's steady state.
Setup. Create eigen.py. Use np.linalg.eigh only to check your answers.
Work through these in order and tick each one off as you finish it.
Show reference solution
Give every task a real try before opening this. If you're stuck on one step, read only the part you need.
Before you move on
Module 7 · Day 6
SVD and low rank
The big ideaEvery matrix, square or not, is a rotation, then a stretch along perpendicular axes, then another rotation: \(A = U\Sigma V^\top\). Keeping only the largest stretches gives the best possible low-rank approximation, which is the math behind compression, PCA and LoRA.
Why it matters for inference. LoRA adapters, SVD-based weight compression and latent KV-cache compression all keep a few dominant directions and drop the rest. The singular values tell you exactly how much each choice costs.
Concepts
1. The SVD
Every matrix can be written as a product of three simpler matrices:
Read it from right to left:
- \(V^\top\) rotates.
- \(\Sigma\) stretches along the axes.
- \(U\) rotates again.
The stretch factors on the diagonal of \(\Sigma\) are the singular values, sorted from largest to smallest:
The key property is:
In words: \(A\) takes perpendicular input directions \(\mathbf v_i\) to perpendicular output directions \(\mathbf u_i\), stretched by \(\sigma_i\).
For example:
The biggest stretch is 3, along \(\hat\jmath\), but it comes out flipped. The other stretch is 2, along \(\hat\imath\):
Singular values are never negative. The minus sign moved into \(\mathbf u_1\).
Unlike eigenvectors, the SVD exists for every matrix, including non-square ones. A circle always becomes an ellipse whose semi-axes are \(\sigma_i\mathbf u_i\).
Press play or scrub through the three steps. First \(V^\top\) rotates v₁ and v₂ onto the axes, then Σ stretches, then \(U\) rotates into place. The dashed ellipse is where \(A\) sends the unit circle directly.
2. How to compute it
Multiply \(A\) by its transpose. The rotations cancel in the middle:
So the recipe is:
- Find the eigenvalues and eigenvectors of \(A^\top A\). The eigenvectors are the \(\mathbf v_i\).
- Take square roots of the eigenvalues. Those are the \(\sigma_i\).
- Compute \(\mathbf u_i = A\mathbf v_i/\sigma_i\).
For example:
Its eigenvalues are 45 and 5. So:
The singular values summarize the matrix:
The condition number tells you how much \(A\) can amplify errors. A big value means trouble.
Pick a matrix. On the left, \(A\) turns the unit circle into an ellipse with semi-axes \(\sigma_i\mathbf u_i\). On the right, \(A^\top A\) turns it into an ellipse along the input directions \(\mathbf v_i\), stretched by \(\sigma_i^2\). Same singular vectors, squared stretches.
A · circle → axes σᵢuᵢ
AᵀA · circle → axes σᵢ²vᵢ
3. Low-rank approximation
Multiply out the SVD and you get a sum of rank-1 layers, sorted from most to least important:
Keep only the first \(k\) layers and call the result \(A_k\). The Eckart–Young theorem says no rank-\(k\) matrix comes closer to \(A\). The error is exactly the first singular value you dropped:
For example, if the singular values are 10, 5, 1 and 0.1, then keeping 2 layers gives:
Storage drops from \(mn\) numbers to \(k(m + n)\).
How well it works depends on how fast the singular values drop. Natural images and fine-tuning updates drop fast, so they compress well. Random matrices don't, so they can't be compressed this way.
A 96×96 grayscale image is a 96×96 matrix. Choose how many rank-1 layers to keep. The bar chart shows the singular values on a log scale; the ones you keep are blue. Load your own picture to see how its spectrum differs.
Original · rank 96
Rank k
Singular values relative to σ₁, log scale
4. PCA
PCA finds the directions in which data varies most. The steps are:
- Put \(N\) data points in the rows of a matrix \(X\).
- Subtract the mean of each column, so the data is centred at the origin.
- Take the SVD of \(X\).
The \(\mathbf v_i\) are the principal directions. The variance of the data along each one is:
To compress the data to \(k\) dimensions, project onto the top \(k\) directions:
In LLM work, PCA is used to plot embeddings in 2D. It also revealed that a few activation dimensions in large models carry huge values. Those outliers are one reason quantization is tricky.
Set the cloud's tilt and how stretched it is. The arrows from the mean are the principal directions, scaled to two standard deviations. Turn on the projection to see every point collapsed onto the first component, the best one-dimensional summary of the data.
By hand
Find the SVD of \(A = \begin{bmatrix}3&0\\4&5\end{bmatrix}\) through the eigenvalues of \(A^\top A\). Check that \(\sigma_1\sigma_2 = |\det A|\). Then set the second preset in Lab 7.1, which is this matrix divided by 2, and compare.
Show worked solution
\(A^\top A = \begin{bmatrix}25&20\\20&25\end{bmatrix}\), with trace 50 and determinant 225, so its eigenvalues are 45 and 5. That gives \(\sigma_1 = \sqrt{45} = 3\sqrt5 \approx 6.708\) and \(\sigma_2 = \sqrt5 \approx 2.236\). The eigenvectors are \(\mathbf v_1 = [1, 1]/\sqrt2\) and \(\mathbf v_2 = [1, -1]/\sqrt2\).
Then \(\mathbf u_1 = A\mathbf v_1/\sigma_1 = [3, 9]/(\sqrt2\cdot3\sqrt5) = [1, 3]/\sqrt{10}\) and \(\mathbf u_2 = A\mathbf v_2/\sigma_2 = [3, -1]/(\sqrt2\cdot\sqrt5) = [3, -1]/\sqrt{10}\). Check: \(\sigma_1\sigma_2 = 3\sqrt5\cdot\sqrt5 = 15 = |3\cdot5 - 0\cdot4|\).
Build: compress a weight matrix
The problem. A dense \(d\times d\) layer stores \(d^2\) numbers. When its singular values fall off quickly, keeping only the top \(k\) singular values and their vectors gives two thin factors with \(2dk\) parameters that behave almost like the full matrix. You'll measure that trade-off, check the Eckart–Young theorem, and then use the same SVD for PCA.
Setup. Create low_rank.py. You may use np.linalg.svd and np.linalg.qr.
Work through these in order and tick each one off as you finish it.
Show reference solution
Give every task a real try before opening this. If you're stuck on one step, read only the part you need.
Before you move on
Module 8 · Day 7
The math inside a transformer
The big ideaA transformer layer is mostly matrix multiplications plus a few nonlinear steps. Once shapes, dot products, gradients and floating-point precision are second nature, you can read inference code and predict what each line costs.
Why it matters for inference. This is where the course lands on your inference work: attention as dot products, decoding as a memory-bound matrix–vector product, KV-cache sizing, and the precision trade-offs behind fp16, bf16 and int8.
Concepts
1. Tensors and shapes
Inference code works with tensors: arrays with more than two axes. A batch of hidden states has shape:
For attention, the width is split into \(H\) heads of size \(d = D/H\), and the axes are reordered:
Now each (batch, head) pair is its own \(T\times d\) matrix. A batched matmul multiplies all of them at once:
Shapes are also a memory budget. The scores grow with \(T^2\). For 32 heads and 4096 tokens in fp16:
That is for one layer and one sequence. This is why FlashAttention never stores the full score matrix.
Each sheet is one head. Change the number of heads, the sequence length and the head width: the score sheets grow with \(T^2\) while \(Q\) and \(K\) grow only with \(T\). The memory readout assumes one sequence in fp16.
2. Attention
Each token produces three vectors:
- The query is what this token is looking for.
- The key is what this token offers.
- The value is what this token passes on.
Attention combines them:
It works in three steps.
Step 1. \(QK^\top\) computes the dot product of every query with every key. A big dot product means a good match.
Step 2. Softmax turns each row of scores into weights that are positive and add up to 1:
For example, with two keys scoring 2 and 0:
Step 3. Multiplying by \(V\) averages the value vectors, using those weights.
Why divide by \(\sqrt d\)? A dot product of two random \(d\)-dimensional vectors has variance about \(d\). Without scaling, the scores get huge and softmax picks just one token. Dividing by \(\sqrt d\) brings the variance back to 1.
Five tokens with 2D keys; each token's value is a color. Drag the query or any key. Weights come from softmax of the scaled dot products, and the output is the weighted blend of the value colors. Lower the temperature to make attention sharper.
3. The causal mask and the KV cache
A language model must not see future tokens. So scores for later positions are set to \(-\infty\) before softmax:
After softmax, those weights are exactly 0. Token \(t\) only looks at tokens 1 through \(t\).
This has a useful side effect. When a new token arrives, the earlier rows don't change. Only the new row needs computing.
So the model keeps every key and value in a KV cache. Each decode step computes \(\mathbf q, \mathbf k, \mathbf v\) for the new token only, and reads the rest from the cache.
The cache grows with every token:
The 2 counts keys and values. For 28 layers, \(d_{kv} = 1024\) and fp16:
Each row is one query token and shows how it spreads its attention over the keys; every row sums to 1. Toggle the causal mask to see the upper triangle vanish, and use the step slider to see which row a decode step adds and which cached keys it reads.
4. Gradients of a matrix product
Training needs gradients. Take a linear layer:
Suppose backpropagation gives us \(\mathbf g = \partial L/\partial\mathbf y\). Then:
A shape check confirms the first one. \(\partial L/\partial W\) must have the same shape as \(W\), which is \(m\times n\). The only way to build an \(m\times n\) matrix from \(\mathbf g\) (length \(m\)) and \(\mathbf x\) (length \(n\)) is the outer product \(\mathbf g\mathbf x^\top\).
For a whole batch, \(Y = XW\), the same rules become:
So the backward pass is two more matmuls of the same size. That is why training costs about three times the forward pass:
Switch between the forward product and the two gradient products. Grid cells are individual numbers. Notice that the shared, summed-over dimension is different each time: the feature width \(n\), the output width \(m\), or the batch \(B\).
5. Floating-point numbers
A floating-point number stores three parts: a sign, an exponent and a mantissa.
- The exponent sets the range: how big or small a number can be.
- The mantissa sets the precision: how many digits you keep.
Most decimals can't be stored exactly. For example, in fp16:
| Format | Exponent bits | Mantissa bits | Largest finite | Gap after 1 |
|---|---|---|---|---|
| fp32 | 8 | 23 | 3.4 × 10³⁸ | 1.2 × 10⁻⁷ |
| bf16 | 8 | 7 | 3.4 × 10³⁸ | 7.8 × 10⁻³ |
| fp16 | 5 | 10 | 65,504 | 9.8 × 10⁻⁴ |
Two formats matter most for LLMs:
- bf16 has fp32's range but less precision. It rarely overflows.
- fp16 has more precision but overflows above 65,504.
Both struggle with long sums. Once a running sum is large, small additions round away to nothing. That is why matmul kernels add up in fp32.
Quantization goes further. It stores each weight as a small integer, with one shared scale per row or group:
The error per weight is at most \(s/2\). One huge outlier makes \(s\) large for its whole group. That is why outliers matter so much in 4-bit formats.
Type any number to see how each format stores it, bit by bit. Then run the accumulation test: add a small value many times in each format and watch fp16 stall.
6. What decoding costs
Generating one token multiplies every weight by a single vector. Each weight is read once and used for 2 FLOPs (a multiply and an add). With 2-byte weights:
That is very low. Hardware can do far more math per byte than this, so decoding spends most of its time waiting for memory.
The roofline model makes this precise:
The point where the two limits meet is the ridge point:
Below the ridge you are memory-bound. Above it you are compute-bound.
For decoding, a good estimate ignores FLOPs entirely:
For example, Qwen3-0.6B in fp16 has about 1.19 GB of weights. At 4096 tokens of context its KV cache adds about 0.47 GB. On a 400 GB/s device:
Batching helps. With \(b\) sequences, each weight read is reused \(b\) times, so the intensity grows about \(b\) times.
Enter a model's shape and a device's memory bandwidth. The defaults are Qwen3-0.6B's shape. Parameters assume a gated MLP and grouped-query attention with a tied embedding, and ignore the small norm weights. The speed is a best-case bound: real kernels come in below it. Peak compute depends on your device and number format, so take it from the spec sheet; the roofline uses it to place the ridge point.
Roofline: attainable TFLOP/s vs FLOPs per byte, log scales. Dots are decode at batch 1, 4, 16, 64 and 256. At long contexts each sequence brings its own KV cache, so the dots bunch up well below the ridge.
By hand
1. One query \(\mathbf q = [1, 0]\) attends over two tokens with keys \(\mathbf k_1 = [2, 0]\), \(\mathbf k_2 = [0, 2]\) and values \(\mathbf v_1 = [1, 0]\), \(\mathbf v_2 = [0, 1]\), with \(d = 2\). Compute the scaled scores, the softmax weights and the output.
2. For \(L = \tfrac12\lVert W\mathbf x - \mathbf y\rVert^2\), derive \(\partial L/\partial W\) entry by entry.
Show worked solutions
1. Raw scores: \(\mathbf q\cdot\mathbf k_1 = 2\) and \(\mathbf q\cdot\mathbf k_2 = 0\). Scaled by \(1/\sqrt2\): 1.414 and 0. Softmax: \(e^{1.414} \approx 4.11\) and \(e^0 = 1\), so the weights are \(4.11/5.11 \approx 0.804\) and 0.196. Output: \(0.804[1, 0] + 0.196[0, 1] = [0.804, 0.196]\).
2. \(L = \tfrac12\sum_i\big(\sum_j W_{ij}x_j - y_i\big)^2\). Only term \(i\) depends on \(W_{ij}\), so \(\partial L/\partial W_{ij} = \big(\sum_j W_{ij}x_j - y_i\big)x_j = (W\mathbf x - \mathbf y)_i\,x_j\). As a matrix: \(\partial L/\partial W = (W\mathbf x - \mathbf y)\,\mathbf x^\top\), an outer product. The build below checks this numerically.
Build: attention, gradients and precision from scratch
The problem. This project is five small experiments, each isolating one piece of math that runs inside a language model: causal attention and the KV cache that makes decoding cheap, the gradient of a linear layer, floating-point accumulation, int8 quantization, and LoRA.
Setup. Create transformer_math.py. Use NumPy only. Start with rng = np.random.default_rng(0) at the top.
Work through these in order and tick each one off as you finish it.
Show reference solution
Give every task a real try before opening this. If you're stuck on one step, read only the part you need.
Capstone: annotate your inference engine
Take one transformer block from your from-scratch inference engine. For every matrix product, write down the shapes, the FLOPs per token and the bytes read. Add them up, plug the totals into the decode cost calculator, and compare the predicted tokens per second with what you measure. Then explain the gap: kernel efficiency, the KV cache, or work the model does outside matmuls.
If your prediction lands within a factor of two, you can read inference code the way this course set out to teach.
Before you finish
Reference
Sources
Everything this course draws on, with full publication details. The explanations, worked examples, labs and NumPy projects were written for this course; the results they teach come from the sources below.
Standard results that appear in every textbook (elimination, the spectral theorem, the SVD) are credited to the textbooks rather than to their original authors, except where a named theorem is used, such as Eckart–Young. Each entry lists the modules that rely on it. Web pages show the month they were checked.