“It is by logic that we prove, but by intuition that we discover.” - Henri Poincaré

Provide Context

Todo:

1. Vectors and coordinates

An arrow describes a movement

Suppose we walk three units right and one unit up. The vector x = (3, 1) is a record of that trip. Start at the origin, and you can draw it as an arrow ending at the point (3, 1).

Here’s the slightly sneaky part: we can draw the same movement starting anywhere. As long as the arrow still goes three right and one up, it’s still (3, 1). A vector’s entries describe changes in coordinates, not a fixed starting point.^[3]

Order matters: (1, 3) means one right and three up, which is a different trip. In the ordinary coordinate pictures, the first entry is always the horizontal movement and the second is the vertical one.

Make the arrow longer or shorter

Multiply both entries by two and we get 2x = (6, 2): the same direction, twice as far. Multiply by ½ and it’s half as long.

A negative multiplier also flips the arrow around: −x goes three units left and one unit down. A number we multiply a vector by is called a scalar,^[4] and we apply the same number to every entry.

Follow one arrow, then another

We can also reach (3, 1) in two steps: first move by (1, −1), then by (2, 2). Adding the vectors records the whole journey:

Keep this split in mind. The two pieces are perpendicular, and we’ll use them next. We can scale arrows before adding them, too. If a and b are two vectors, 2a + b means “two copies of a, then one copy of b.” That’s a linear combination, and the numbers 2 and 1 are its coefficients: how much of each ingredient to use.

2. A matrix as an operation

Give the input two rules to follow

How do we turn one vector into another? We’ll use a simple rule throughout this primer: each output is twice its matching input entry, plus the other input entry.

Call the input entries x₁ and x₂. We record the rule as a matrix called M, with one row for each output:

The notation Mx means “the output you get by feeding x to M”:

Read the rows to find the output

For our input (3, 1), the first row gives 2 × 3 + 1 × 1 = 7. The second gives 1 × 3 + 2 × 1 = 5. So the output is Mx = (7, 5).

Keep the matrix fixed and change the input

Two habits of M make it predictable, and the next picture shows both. On the left, double the input from (3, 1) to (6, 2): the output becomes (14, 10), which is exactly (7, 5) doubled. On the right, split the input into two pieces and push each piece through on its own: the two outputs, placed tip to tail, land exactly on Mx.

Together, these two properties make M linear. They let us chop an input into pieces, push each piece through separately, and glue the results back together. We’ll do that constantly. They also mean zero in gives zero out: M never moves the origin.^[5]

Read the columns to see where the unit steps go

What happens to a single horizontal step, e₁ = (1, 0)? M sends it to (2, 1), which is the first column of the matrix. A single vertical step, e₂ = (0, 1), goes to (1, 2), the second column.

Our input (3, 1) is three horizontal unit steps plus one vertical unit step. Since M is linear, its output is three copies of the first column plus one copy of the second:

Rows are for computing the output one coordinate at a time. Columns show how the transformed unit steps build the output. Same answer, two ways of looking at it.

3. The dot product

A test for right angles

Take two vectors a and b, with entries (a₁, a₂) and (b₁, b₂). Multiply matching entries and add the products. The result is a single number called their dot product:

For the arrows a = (2, 1) and b = (1, −2), the products are 2 and −2, and they cancel. The dot product is zero, and these arrows meet at a right angle.

The sign tells you about the angle

For two nonzero vectors, a positive dot product means the angle between them is less than 90°. A negative one means it’s more than 90°. Exactly zero means exactly 90°.

If two vectors are perpendicular, their dot product is zero. We’ll use this rule constantly, starting with finding a perpendicular remainder. Vectors with a zero dot product are called orthogonal, which is “perpendicular” wearing a lab coat.^[6]

Our earlier pair passes the test: (1, −1) and (2, 2) give 1 × 2 + (−1) × 2 = 0. The arithmetic confirms the right angle without trusting anybody’s drawing skills. With more entries, the rule is the same: multiply matching entries and add.

The number also depends on length

Double either arrow and the dot product doubles too, even though the angle hasn’t changed. So the dot product mixes alignment and length together. It isn’t a pure angle meter.

We can at least remove one of the two lengths. Measure against a reference arrow of length one. Then the dot product measures the other arrow along that direction, with a sign that says which way it points. That arrow’s own length still counts, as it should. First we’ll build a unit arrow; then we’ll see why the measurement works.

The same calculation in matrix notation

So far we’ve written coordinates as pairs. In matrix notation, a vector’s entries are usually stacked in a column. The transpose, written aᵀ, tips that column over into a row. Multiplying the row aᵀ by the column b does exactly the matching-entries calculation above, so aᵀb and a · b are the same dot product in different outfits.

4. Length and unit vectors

Length and squared length describe the same arrow

Before we can build a one-unit arrow, we need to know how long our arrow is right now. Length is how long it is. Squared length is that number multiplied by itself.

For a small example, take any arrow of length 3. (We’ll get to the length of (3, 1) in a moment.) Its squared length is 3 × 3 = 9. Now double every coordinate, which makes it twice as long:

The length doubles, but the squared length quadruples, because both factors in the multiplication doubled. To get back from squared length to length, take the square root: a squared length of 9 means a length of √9 = 3.

Find length from the coordinates

For our arrow (3, 1), the horizontal and vertical steps make a right triangle, so Pythagoras gives squared length 3² + 1² = 10. Its length is √10, about 3.16.^[7]

Dotting x with itself adds up those same squared coordinates. We write the length of x as ‖x‖, with double bars. It’s also called the Euclidean norm:

Make a one-unit measuring step

To measure along a direction, we want a standard step. An arrow of length exactly one does the job. It’s called a unit vector.

Our x has length √10, so dividing every coordinate by √10 makes its length one. Both entries shrink by the same factor, so the direction doesn’t change. Call the new arrow x̂, read “x-hat”:

As a check, x̂ has squared length 9/10 + 1/10 = 1. Dividing a nonzero vector by its length is called normalization.^[8] Keep that word in mind. In Chapter 8 we’ll normalize something else, and the difference will matter.

How the dot product includes both length and angle

Let θ be the angle between two nonzero arrows a and b. Then a · b = ‖a‖ ‖b‖ cos θ. The lengths explain why scaling either arrow changes the dot product. The cosine explains the sign: at 90°, it is zero. If b has length one, only a’s length and its alignment with b remain in the measurement.

5. Projection

Split one arrow into two useful pieces

Start with x = (3, 1). We want the part along the diagonal through d = (1, 1).

Imagine dropping a perpendicular from the tip of x onto that diagonal. The arrow from the origin to the landing point is the projection, or shadow, of x on the line. Call it p. The remaining step from p’s tip to x’s tip is r.

For our example, the two pieces are:

The piece p = (2, 2) follows the diagonal. The remainder r = (1, −1) is perpendicular to it: its dot product with d = (1, 1) is 1 − 1 = 0. These are the two checks that make this the projection split.

Optional: how do we find (2, 2)?

A point on this diagonal has equal coordinates, so write the unknown projection as p = (a, a). The remaining step is then r = (3 − a, 1 − a).

Choose a so that r has dot product zero with the diagonal direction:

(3 − a) + (1 − a) = 0

This gives 4 − 2a = 0, so a = 2. A perpendicular connection is also the shortest connection from x’s tip to the line.

A unit arrow gives us a shortcut

Let u be a length-one arrow along the chosen line. The dot product x · u tells us the signed amount of x along that line. Multiplying that number by u turns it into the projection arrow:

The number x · u is a coefficient: it tells us how many u steps to take. The whole arrow p is the component. A negative coefficient means taking those steps in the opposite direction.

Optional: the same component with two measuring steps

Our diagonal arrow d has length √2. Make it unit length by dividing by √2: u = (1, 1)/√2. Now x · u = (3 + 1)/√2 = 2√2.

p = 2d = 2√2 u = (2, 2)

The coefficient changes because the measuring step changes. The component itself stays the same.

The squared lengths add

Because p and r meet at a right angle, Pythagoras applies. Their squared lengths add to x’s squared length:

This will help us measure how much of an input lies in each of two perpendicular directions.^[9]

6. Eigenvectors and eigenvalues

Watch three arrows go through the same matrix

We are still using the matrix with these two rules: double the first entry and add the second; then add the first entry to twice the second.

Compare our input x = (3, 1) with two diagonal arrows, q₁ = (1, −1) and q₂ = (1, 1). Press Play transformation or drag from Before to After. This shows one application of M. The frames in between are animation steps, not repeated matrix multiplications.

Play transformationReset

Move from input to output

100%

BeforeAfter M

Follow the arrows from where they start to where M sends them. This is one application of M.

Name the arrow and the number

A nonzero arrow that the matrix multiplies by one number is an eigenvector.^[11] That number is its eigenvalue. In symbols:

Read this as: “applying M to v has the same effect as multiplying v by λ.” The eigenvector tells us the direction; the eigenvalue tells us the multiplier. For M, λ₁ = 1 and λ₂ = 3.

The direction matters more than the length

Any nonzero multiple of q₁ is still an eigenvector with eigenvalue 1. Any nonzero multiple of q₂ still has eigenvalue 3. Making an arrow longer does not change which eigenvector line it lies on.

For other matrices, a negative eigenvalue reverses the arrow along the same line.^[13] A zero eigenvalue sends a nonzero arrow to the origin. The zero arrow itself is excluded: multiplying it by any number gives zero, so it cannot identify a particular multiplier.

Optional: check every direction, and apply M more than once

The chart shows how much M turns an arrow for each starting direction. The two eigenvector lines are the only lines it leaves unturned.

Other arrows turn toward the q₂ line, by at most 30° in one application. Repeated applications move them closer to that line unless they started exactly on q₁.^[12]

Along q₂, each application multiplies by 3. Two applications multiply by 3 × 3 = 9. An eigenvector direction is sometimes called a mode, and the list of eigenvalues, including repeats, is called the spectrum.^[14]

The moving-grid approach is inspired by 3Blue1Brown’s lesson on eigenvectors and eigenvalues.

7. A different set of coordinates

Describe the same arrow using different steps

In ordinary coordinates, x = (3, 1) means three horizontal steps and one vertical step. We can reach exactly the same point using the eigenvector steps q₁ = (1, −1) and q₂ = (1, 1):

So x has coordinates (1, 2) in this new system: one q₁ step and two q₂ steps. Changing coordinates changes the description of x. It does not move x.

Now let M act on the pieces

M leaves the q₁ piece alone and triples the q₂ piece. The new coordinates therefore change from (1, 2) to (1, 6). Add the output pieces to return to ordinary coordinates:

This works because M is linear: we can transform the pieces separately and then add the results. Eigenvector coordinates make each separate transformation a simple multiplication.

What makes a valid coordinate system?

A set of reference arrows is called a basis when it can describe every vector, and each vector has exactly one description.

In the plane, any two nonparallel arrows form a basis. Our q₁ and q₂ qualify. Two arrows pointing along the same line do not: they cannot reach points away from that line.

Optional: “span” and “linearly independent”

Reference arrows span the plane if their combinations reach every point. They are linearly independent if none is a combination of the others. Together, these properties give enough directions and a unique recipe.

The arrows e₁ and 2e₁ fail both tests. They only reach the horizontal line, and even there a point can have different recipes: (2, 0) is two copies of e₁ or one copy of 2e₁.

We can now understand every input from the matrix’s responses along its eigenvector lines.^[15] Next, we will see why perpendicular reference directions are especially useful.

8. Why perpendicular unit directions help

Perpendicular pieces have squared lengths that add

Our split is x = (1, −1) + (2, 2). The pieces are perpendicular, so each one is the projection of x onto its line. Their squared lengths are 2 and 8, giving x a squared length of 10.

This lets us say exactly how x’s squared length is shared: 20% along the first eigenvector line and 80% along the second. These percentages describe squared length, not ordinary length.

Use reference arrows of length one

Our original reference arrows q₁ and q₂ each have length √2. Divide each by √2 to get unit reference arrows:

This changes the size of a reference step. It does not change x or its pieces. The same pieces now need √2 steps along u₁ and 2√2 steps along u₂.

Because the references are unit length, a coefficient’s absolute value is the length of its piece. Squaring the coefficient gives that piece’s squared length. Projection finds the coefficients with a dot product:

A basis with perpendicular, length-one arrows is called orthonormal. The word packages the two properties we just used.

Why does our matrix allow this?

M has matching entries across its main diagonal: the upper-right and lower-left entries are both 1. A matrix with this mirror property is called symmetric. Swapping its rows and columns leaves it unchanged, written Mᵀ = M.

The spectral theorem says that every real symmetric matrix has an orthonormal basis of eigenvectors, with real eigenvalues. We can choose enough perpendicular unit eigenvectors to describe every input.

For M, the recipe is now simple: project the input onto the two eigenvector lines, multiply each piece by its eigenvalue, then add the results.

Each eigenvector piece stays on its own line. The complete input can still turn. For a different symmetric matrix, a multiplier can also be negative, reversing a piece, or zero, removing it.

Optional: what can go wrong without symmetry?

Consider A with rows (1, 1) and (0, 2). Its eigenvector lines, through (1, 0) and (1, 1), meet at 45° rather than 90°.

We can still use these two directions as coordinates: x = 2(1, 0) + (1, 1). But projecting x onto either line does not recover the corresponding piece, because the other piece also has a component along that line.

The squared lengths of the pieces are 4 and 2. They add to 6, not 10. The full formula has an extra term: ‖a + b‖² = ‖a‖² + 2a · b + ‖b‖². Here that extra term is 4. Perpendicular pieces make it zero.

So eigenvector coordinates alone do not give all our shortcuts. We need perpendicular eigenvectors. Some matrices, such as a 90° rotation, do not even have real eigenvectors.

Optional: why different eigenvalues give perpendicular eigenvectors

Let v and w be eigenvectors of a real symmetric matrix M, with eigenvalues α and β. Symmetry lets us move M from one side of the dot product to the other: vᵀMw = (Mv)ᵀw. Substituting Mw = βw and Mv = αv gives β(v · w) = α(v · w). If α and β are different, this can hold only when v · w = 0. So the vectors are perpendicular. The full spectral theorem also guarantees enough eigenvectors to form a basis, including when eigenvalues repeat; within a repeated eigenvalue’s space we simply choose perpendicular ones.

Optional: two different things can be normalized

Normalize the references: make the measuring steps unit length. The input stays fixed, and its coefficients change.

Normalize the input: resize x itself to length one. The reference steps stay fixed, and all of x’s pieces resize together.

For x, normalizing the input gives x̂ = (3, 1)/√10. Its two squared-length shares are still 20% and 80%.

9. A score from the input and output

First calculate the score at the original size

Our input is x = (3, 1), and its output is Mx = (7, 5). Dot the two together:

The letter Q names the score. Another way to write the same dot product is xᵀMx. Do not confuse this score with the output arrow or its squared length:^[19]

The raw score changes when the input changes size

Double x and Mx also doubles. Both arrows in the dot product are now twice as large, so the score becomes four times as large. This “size squared” behavior is why Q is called a quadratic form.

To compare directions fairly, first give every input length one. Our x has length √10, so its unit version is x̂ = (3, 1)/√10. Dividing the input by √10 also divides the output by √10. Their dot product is therefore divided by 10:

For a unit input, the score is the signed amount of the output along the input’s direction. It measures the output’s projection onto that line. Any sideways part contributes zero to the dot product.^[17]

For x̂, that amount is 2.6. For the unit eigenvectors u₁ and u₂, it is 1 and 3. Along an eigenvector, the whole output stays on the input’s line, so the unit-input score is exactly the eigenvalue.

Why does our direction score 2.6?

Chapter 8 split x’s squared length into 20% along u₁ and 80% along u₂. Resizing x to length one keeps these same shares. M multiplies the first piece by 1 and the second by 3, so:

The score is a weighted average of the eigenvalues. The weights are shares of squared length. They cannot be negative, and they add to 100%.

More share along u₁ moves the score toward 1. More share along u₂ moves it toward 3. Every unit input’s score stays between those two values.

Optional: why each piece contributes its eigenvalue times its squared amount

Let c be the input’s signed coefficient along one unit eigenvector. Its output coefficient is λc. That piece’s contribution to the dot product is therefore c × λc = λc².

For a unit input, the squared coefficients add to one, so they are already shares. For the original x, they add to 10. Its score is 1 × 2 + 3 × 8 = 26.

Written in ordinary coordinates, this same score is Q(x) = 2x₁² + 2x₁x₂ + 2x₂².

Optional: why we cannot score just any pieces and add

The shortcut works for perpendicular eigenvector pieces. Here is why both conditions matter. Split the original input along the ordinary axes: a = (3, 0) and b = (0, 1). Their scores are 18 and 2, adding to 20. But the whole input scores 26. Where are the other 6?

The full score pairs each input piece with each output piece. There are four dot products:

Q(a + b) = Q(a) + Q(b) + a · Mb + b · Ma

The last two are called cross terms. Here each equals 3, so the full total is 18 + 2 + 3 + 3 = 26.

Why does the eigenvector split avoid this? Each output piece stays on its own eigenvector line. Those lines are perpendicular, so an input piece dotted with the other piece’s output gives zero.

Perpendicular inputs alone are not enough: M can turn their outputs. Eigenvector inputs alone are not enough either: their lines also need to be perpendicular.

A practical example: how bumpy is a list?

Take the list (3, 1, 2). To measure its bumpiness, subtract neighboring entries, square each difference, and add:

A step up and a step down of the same size cost the same. Larger steps cost more. A flat list costs zero because every neighboring difference is zero.

This is another quadratic form. It can be written zᵀBz, using a three-entry input z and a new symmetric matrix B.^[18] B is different from our two-by-two M, but the same reasoning applies: perpendicular eigenvector pieces explain its score.

Chapter 11 will show how to remove the effect of input size without first drawing a unit arrow. Chapter 13 will use that fair comparison to find a smooth pattern in the three-entry list.

10. Can a nonzero input have score zero?

Our matrix M always gives a positive score

M’s eigenvalues are 1 and 3. Each eigenvector piece contributes a positive multiplier times its squared length. A nonzero input has at least one nonzero piece, so its total score is positive.

A real symmetric matrix whose score is positive for every nonzero input is called positive definite.

A different matrix can ignore a direction

Consider N, which keeps the horizontal coordinate and removes the vertical one:

The unit vertical input (0, 1) goes to (0, 0). Its score is zero, even though the input has length one. It is an eigenvector of N with eigenvalue zero.

For any input (a, b), N’s raw score is (a, b) · (a, 0) = a². It can be positive or zero, but never negative.

A real symmetric matrix whose scores are never negative is called positive semidefinite. It allows zero scores for nonzero inputs, but does not require them. Positive definite matrices are included in this broader group.^[20]

Why zero matters in a search

If we search for N’s lowest-scoring unit input, a vertical arrow wins with zero. That tells us which direction N ignores. To study its other directions, we would need to exclude that direction from the search.^[21]

The bumpiness score has a similar issue: a nonzero flat list scores zero because none of its entries differ. Chapter 13 removes that shared, flat component before comparing the remaining patterns.

Optional: compare all directions for M and N

M’s unit-input scores stay between 1 and 3. N’s stay between 0 and 1: its score is simply the share of squared length along the horizontal direction.

Optional: what eigenvalues and sums of squares tell us

For a real symmetric matrix, all positive eigenvalues mean the matrix is positive definite. Eigenvalues that are all zero or positive mean it is positive semidefinite. A negative eigenvalue gives a negative score along its eigenvector.

For a positive semidefinite matrix, a zero score means the input lies entirely in directions that the matrix sends to zero. This conclusion needs the nonnegative eigenvalues. Otherwise, positive and negative contributions can cancel even when the output is not zero.^[22]

Sometimes a sum of squares proves the sign directly. For M:

Q(x) = x₁² + x₂² + (x₁ + x₂)²

If x is nonzero, at least one of the first two squares is positive. So the sum is positive. Bumpiness is also a sum of squares, which explains why it can never be negative.

11. Compare directions at the same size

Why the raw score needs a size correction

Our input x scores 26. Half of x scores only 6.5. It points in exactly the same direction, so the smaller score has not found a better direction. It has only made the input smaller.

When an input’s length doubles, both its raw score and its squared length multiply by four. Their ratio stays the same. This ratio is called the Rayleigh quotient, written R(x).^[23] “Quotient” simply means the result of a division.

For x, it is 26/10 = 2.6. For half of x, it is 6.5/2.5 = 2.6. The quotient is the score the same direction would get at length one. The input must be nonzero, so the denominator is not zero.

Optional: see why dividing by squared length works

A unit version of x is x/‖x‖. Its output is Mx/‖x‖. Dotting them divides the original score by ‖x‖ × ‖x‖ = ‖x‖². That is exactly the Rayleigh quotient.

Turn the input and watch the score change

Every input in the next experiment has length one. Drag to turn it, or use the buttons to select our running direction and the two eigenvector directions.

Turn the unit input

18.4°

Along u₁Along x̂Along u₂

Score for this unit input: 2.6

20% of squared length along u₁; 80% along u₂.

Drag to turn the arrow around the circle; the angle is measured from the positive horizontal axis. Watch the dashed remainder vanish at the eigenvectors, the pieces trade shares, and the dot ride the curve.

Along u₁, the quotient is 1. Along u₂, it is 3. Along x̂, it is 2.6. At an eigenvector, the dashed sideways remainder disappears because the whole output stays on the input’s line.

What if we resize a copy of the input?

Keep the circle experiment at length one. Here we resize a separate copy of its current input. The copy and all its pieces change length together; the unit reference arrows stay fixed.

Length of the input copy

1

Copy's squared length1

Copy's raw score2.6

Copy's quotient2.6

Changing the copy's length changes its raw score and its squared length by the same factor, so their ratio doesn't budge. The circle picture above keeps showing the unit input.

For the original x, halving its length lowers the score from 26 to 6.5 and the squared length from 10 to 2.5. Both ratios are still 2.6. The shrink ray strikes out.

Read the quotient from the shares

For our symmetric M, the quotient is a weighted average of the eigenvalues. Find the fraction of squared length in each eigenvector direction, multiply each fraction by its eigenvalue, and add.

Our x has squared-length shares 2/10 = 0.2 and 8/10 = 0.8:

The shares are never negative and always add to one. Turning the input changes the shares. Resizing it leaves them unchanged. This explains why the quotient compares directions fairly.

Optional: why the graph has a wave shape

As the unit input turns, its projections on the eigenvector lines change smoothly. Squaring their lengths gives the changing shares. If s is the share along u₂, the other share is 1 − s, so the score is 1 × (1 − s) + 3 × s = 1 + 2s.

If θ is the input’s angle from the horizontal axis, its u₂ share is cos²(θ − 45°). The score is therefore 2 + sin(2θ). You do not need this trigonometry to use the weighted-average rule.

Optional: what the quotient measures in the output picture

The output’s projection onto the input line is R(x)x. For our example this is 2.6x = (7.8, 2.6). The remaining step to Mx = (7, 5) is (−0.8, 2.4), perpendicular to x.

To check the formula, call the projection multiplier k. Its remainder Mx − kx must have dot product zero with x. Thus x · Mx = k(x · x), giving k = R(x).

The quotient measures the output along the input’s line. It is generally different from the ratio of the full output length to the input length, because the full output can also have a sideways part.^[24]

Optional: the same weighted average in more dimensions

For a real symmetric matrix, choose perpendicular unit eigenvectors uᵢ. Let cᵢ be the input’s coefficient along uᵢ, and λᵢ its eigenvalue. The index i identifies a direction; Σ means to add over all directions.

The squared length is Σᵢ cᵢ², and the raw score is Σᵢ λᵢcᵢ². Each share is wᵢ = cᵢ² / Σⱼ cⱼ². Therefore R(x) = Σᵢ wᵢλᵢ: the same weighted-average rule.

The experiment suggests where the smallest and largest scores occur. Next, the weighted-average rule will prove it for every direction.

12. Finding the minimum and maximum

Every score stays between 1 and 3

Chapter 11 showed that each quotient for M is a weighted average of its eigenvalues, 1 and 3. The weights are nonnegative and add to one. Such an average cannot fall below 1 or rise above 3.

So 1 is a floor for every possible direction. We do not need to test directions one at a time to know this.

The eigenvectors reach both limits

Choose q₁ = (1, −1). All its squared length lies along the eigenvector with eigenvalue 1, so R(q₁) = 1. That proves the minimum is exactly 1: no direction goes lower, and this direction reaches it.

Choose q₂ = (1, 1) for the other end. Its quotient is 3, so the maximum is exactly 3.

The arrows can be resized or reversed without changing their quotients. We are finding directions, not one particular arrow length.

Why one trial is not a proof of the minimum

Our trial x gives 2.6. That tells us the minimum is at most 2.6: a direction with that score exists. It does not tell us that every other direction scores more.

To prove a minimum, we need both parts of the argument: a floor that applies to every candidate, and a candidate that reaches the floor.

The same rule works in more dimensions

For any real symmetric matrix, the smallest eigenvalue is the smallest Rayleigh quotient, and an eigenvector with that eigenvalue achieves it. The largest eigenvalue gives the maximum in the same way.^[25]

This gives the extreme eigenvalues two meanings: they are multipliers along special directions, and they are the best and worst values of this fair score. If an extreme eigenvalue repeats, more than one independent direction can achieve the same extreme score.

We can therefore search for a minimum by finding the smallest eigenvalue and a corresponding eigenvector. The weighted-average argument still works when there are too many dimensions to draw. Spielman, Chapter 2.

Optional: why the symmetry condition matters

The nonsymmetric matrix A from Chapter 8 has rows (1, 1) and (0, 2). Its eigenvalues are 1 and 2, but its quotients range from about 0.79 to 2.21.

Its eigenvectors still score their eigenvalues. They simply do not achieve the extremes. Because the eigenvector lines are not perpendicular, the squared-length shares do not give the weighted-average formula we used for M. The spectral theorem supplies that formula for real symmetric matrices.

13. Remove the average to reveal the pattern

Separate the shared level from the pattern

Return to the three-entry list z = (3, 1, 2). Its average is 2. Subtract 2 from every entry:

The first part is the shared level. The second tells us how far each entry is above or below the average. Subtracting the average is called centering. The centered entries always add to zero.

Centering preserves the differences between neighboring entries. The raw bumpiness is therefore still 5:

This preserves raw bumpiness, not necessarily the quotient. Subtracting an average changes the input’s squared length. We center first because we want that length to measure only the variation around the mean.

Centering and normalizing do different jobs

Our centered list is r = (1, −1, 0), with squared length 2. We could normalize it to r/√2. Or use Chapter 11’s shortcut and divide its raw score by its squared length:

A flat list leaves the zero vector after centering. There is then no remaining pattern to normalize, and its quotient is undefined. Our search considers nonzero, centered patterns.

Optional: why subtracting the average is a projection

The all-equal direction is h = (1, 1, 1). The shared part p = (2, 2, 2) lies along it. Our remainder r is perpendicular to h because r · h = 1 − 1 + 0 = 0. This is the same projection split as in Chapter 5.

To find the shared part directly, write it as (a, a, a). Requiring the remainder to be perpendicular to h gives (3 − a) + (1 − a) + (2 − a) = 0, so a = 2. For any list, this calculation gives its average.

Three-entry centered lists satisfy r₁ + r₂ + r₃ = 0. The first two entries can vary freely; the third is then fixed. They form a plane perpendicular to h. Requiring length one selects a circle inside that plane.

We now have another circle of candidate directions, just as in Chapter 11, but every point on this circle already has average zero.

Which centered pattern is smoothest?

We are using the three-entry bumpiness matrix B introduced in Chapter 9. Its raw score is the sum of squared neighboring differences. Its fair score divides that sum by the centered input’s squared length.

The ramp (1, 0, −1) has raw bumpiness 2 and squared length 2, so it scores 1. The zigzag (1, −2, 1) has raw bumpiness 18 and squared length 6, so it scores 3.

The ramp and zigzag are perpendicular eigenvectors of B, with eigenvalues 1 and 3.^[26] Together they describe every centered three-entry pattern. Each such pattern’s quotient is a weighted average of 1 and 3.

Therefore the lowest quotient among centered patterns is 1, achieved by the ramp direction. Its reverse is equally smooth. Our centered list has 25% of its squared length along the ramp and 75% along the zigzag, giving 0.25 × 1 + 0.75 × 3 = 2.5.

Why the second-smallest eigenvalue appears

B has eigenvalues 0, 1, and 3. The flat direction has eigenvalue 0. Centering removes that entire component from every candidate, leaving the directions with eigenvalues 1 and 3.

The smallest remaining eigenvalue is 1, which was the second-smallest eigenvalue of B. We often call it λ₂. Its eigenvector gives the smoothest centered pattern for this score.

This explains the step used in the next primer: remove a known flat component, then find the smoothest remaining pattern. On a network, such patterns help reveal groups of strongly connected points. Spielman, Chapters 1–2.

Keep the two example matrices separate. For this bumpiness matrix B, the flat direction has the smallest eigenvalue, 0. For our earlier matrix M, the all-equal direction has the largest eigenvalue, 3. Centering always removes the average; which eigenvalue it removes depends on the matrix.

Footnotes

1. The search term is spectral clustering. The same idea ranks web pages, finds communities in social networks, and segments images. All of it starts with the question in this paragraph. ↩
2. Hi. Footnotes hold the jokes that didn't fit in the main text, plus the occasional “technically…” that keeps everything honest. ↩
3. Unlike most directions you get from relatives, these work no matter where you start. ↩
4. William Rowan Hamilton gave “scalar” and “vector” their mathematical meanings in the mid-1840s, while developing his quaternions. Real numbers, he explained, sit on a single scale running from negative to positive infinity. “Vector” comes from the Latin for “carrier.” ↩
5. This is why the rule “add 1 to every entry” isn't linear in this sense, even though in one dimension f(x) = x + 1 draws a perfectly straight line. It moves the origin. That kind of rule is called affine, and someone will point this out if you get it wrong. ↩
6. For two nonzero arrows in the plane, “orthogonal” and “perpendicular” mean the same thing. “Orthogonal” also works in more dimensions, and for things like functions, where “perpendicular” starts to sound odd. Technically the zero vector is orthogonal to everything, which is about as meaningful as it sounds. ↩
7. √10 ≈ 3.162 is close enough to π that Zhang Heng in 2nd-century China and Brahmagupta in 7th-century India both used it as a value for π. We are not doing that here. ↩
8. The zero vector can't be normalized: its length is zero, and dividing by zero remains, as ever, not allowed. ↩
9. Without the right angle there would be an extra cross term: ‖p + r‖² = ‖p‖² + 2 p · r + ‖r‖². Here p · r = 0, so it vanishes. Cross terms will be back in Chapter 9, looking suspicious. ↩
10. The wobble in the hand-drawn grid is drawn on the plane itself, so M transforms the wobbles along with everything else. That's what a linear map does to any drawing you make on the plane. (The arrow tips sit exactly where the math says, though.) ↩
11. “Eigen” is German for “own,” as in “the matrix's own vectors.” English borrowed half the word and never gave it back. ↩
12. Keep applying M and almost every arrow swings closer and closer to the q₂ line, because each application triples the q₂ component and leaves the q₁ component alone. Repeating a matrix to find its dominant eigenvector is called the power method; Google's original PageRank was computed this way. (The “almost”: arrows exactly on the q₁ line have no q₂ component to triple, so they stay put.) ↩
13. Flipping still counts as staying on the line. The arrow is on the same line through the origin, just facing the other way down the hallway. ↩
14. David Hilbert made “spectrum” the standard word in the early 1900s (Wilhelm Wirtinger had borrowed it from optics a few years before). A couple of decades later, quantum mechanics showed that the lines in atomic spectra really are computed from eigenvalues. Hilbert reportedly said he'd used the name with no idea it would apply to the actual spectra of physics. The word went from optics to math and straight back again. ↩
15. Of which there are a lot. Uncountably many, in fact. ↩
16. Rotation by 180° is sneakier: it flips every arrow, which counts as staying on the line, so every nonzero arrow is an eigenvector with eigenvalue −1. ↩
17. Remember the job interview in Chapter 6? x started explaining that it turns a little, and M said “Next!” The chart there says how little: about 17°. That turn is the sideways part in the picture. ↩
18. For a three-entry list z, B has rows (1, −1, 0), (−1, 2, −1) and (0, −1, 1). Multiplying gives zᵀBz = z₁² + 2z₂² + z₃² − 2z₁z₂ − 2z₂z₃ = (z₁ − z₂)² + (z₂ − z₃)². The next primer builds this kind of matrix from a network. ↩
19. One input, three different answers. Linear algebra is like this sometimes. ↩
20. Positive semidefinite is the matrix version of “no complaints.” Not necessarily any compliments. Just no complaints. ↩
21. Hold that thought. Chapter 13 removes one direction from a search for exactly this reason. ↩
22. Without nonnegativity, a zero can be a coincidence. The matrix with rows (1, 0) and (0, −1) gives (1, 1) a score of 1 − 1 = 0, yet sends it to (1, −1), not to zero. ↩
23. Named after Lord Rayleigh, who also explained why the sky is blue and shared in the discovery of argon, which won him the 1904 Nobel Prize in Physics. He was having a good few decades. ↩
24. For our x, ‖Mx‖/‖x‖ = √74/√10 ≈ 2.72, which is bigger than R(x) = 2.6. The sideways remainder adds length without adding anything along x. ↩
25. Mathematicians call this the variational characterization of eigenvalues: “variational” because it comes from varying the direction and looking for the lowest and highest values. Physics is full of these. A soap film settles into a shape that (locally) minimizes its area, and light follows a path whose travel time is stationary, which is usually a minimum. ↩
26. Check with the matrix B from Chapter 9's footnote. B(1, 0, −1) = (1, 0, −1): eigenvalue 1. B(1, −2, 1) = (3, −6, 3): eigenvalue 3. The flat list is the third eigenvector, B(1, 1, 1) = (0, 0, 0): eigenvalue 0. And (1, 0, −1) · (1, −2, 1) = 1 + 0 − 1 = 0, so the two in the plane are perpendicular, as the spectral theorem promised. ↩