Eigendecomposition

Decomposing a matrix

As with prime factors, shows structure the digits hide. A decomposition does the same for a matrix.

An eigendecomposition splits a matrix into eigenvectors and eigenvalues. (Added here, not from the book: German eigen means “own”.)

Picture as a machine. Is there an input that comes out pointing the same way? Drag the black dot and hunt for it.

On Symmetric the curve touches zero at 45° and 135°. At 45° the violet arrow is 3 times longer and points the same way. At 135° it keeps its length. Those two lines are the matrix’s own directions.

Skewed has two such lines, but not at right angles. Shear has only one. Rotation has none, because it turns every arrow. The rest of this page makes that precise.

Eigenvectors and eigenvalues

The direction you found has a name. An eigenvector of a square matrix is a non-zero vector that only rescales:

The number is its eigenvalue, the stretch factor along that direction. Above 1 it stretches, between 0 and 1 it shrinks, below 0 it flips the arrow, and 0 squashes it onto the origin. Think of pulling a rubber sheet: the lines along the pull stay lines.

The word “non-zero” matters. The zero vector satisfies the equation for every and tells you nothing.

Now drag the tip of the black arrow . The violet arrow is . When do they line up?

Slide the tip along a line where the arrows match. The arrow gets longer or shorter, but the factor stays the same. That is the book’s rescaling remark: if is an eigenvector, so is for any , with the same eigenvalue.

Since every multiple works, the book looks only for unit eigenvectors. Length is free. The direction is what counts.

Finding eigenvalues

The book states Equation 2.39 and moves on. To compute eigenvalues you need one more step (added here, not printed in the book). Rewrite the equation as . A non-zero can solve it only if squashes some direction to zero, so that matrix is singular and has determinant 0:

For a 2 by 2 matrix this is a parabola in . Its coefficients are the trace , the sum of the diagonal entries, and the determinant , the number that is zero exactly when the matrix squashes a direction:

The plotted curve is , and the eigenvalues are its roots. Drag the dot along it, or reshape the parabola with the matrix entries, and watch where it hits zero.

Two crossings give two real eigenvalues. A parabola that only touches zero gives one repeated eigenvalue. A parabola floating above zero has no real root, so the eigenvalues are complex (Section 5). Software finds the roots of bigger matrices with iterative methods and never expands the polynomial.

The eigendecomposition

Suppose an by matrix has linearly independent eigenvectors , meaning none is a mix of the others. Put them side by side as the columns of , and the eigenvalues into a vector . The eigendecomposition is

Read it from the right, like a recipe. Converting cups to grams, doubling the flour, then converting back is one way to scale a recipe. The three factors work the same way.

• converts the arrow into eigen-coordinates, measured along the eigenvectors.
• scales each coordinate by its own eigenvalue. This is the cheap diagonal operation of Section 2.6.
• converts back to the original axes.

A complicated stretch is a plain scaling seen from a tilted viewpoint. Drag the ring to put a point of your own through the three moves, then slide or press Play.

In the first third the eigenvector arrows swing onto the axes. In the second third only the axes are stretched. In the last third everything swings back. The arrows end at , which is , as Equation 2.39 says.

Build one yourself

Now run it backwards. Choose the eigenvector arrows and the eigenvalues, and the machine builds . Push the two arrows onto one line and see what breaks.

Symmetric matrices are the ones whose eigenvector arrows are at right angles (Section 4). Any other angle gives a matrix that is not symmetric but is still fully described by its arrows and eigenvalues.

Why the form is useful

The book compares the decomposition with prime factors: it shows properties the raw entries hide. One example, added here, is repeated multiplication. In the middle cancels to the identity, so only the eigenvalues get squared. In general

The first row multiplies by itself times. The second raises two numbers to the power and sandwiches them between and . The two agree up to rounding, and the second needs only powers of numbers.

Real symmetric matrices

Some matrices cannot be decomposed, and some need complex numbers. Section 5 shows both. The book needs only one friendly class, real symmetric matrices (those with , from Section 2.6), and for them the news is good. Everything stays real:

Here is an orthogonal matrix whose columns are eigenvectors of , and is a diagonal matrix with eigenvalue for column of . This is Equation 2.40 with a bonus: the eigenvectors are perpendicular unit arrows, so and the expensive inverse disappears.

Figure 2.3, rebuilt

Perpendicular axes mean scales space by along . The left plot holds every unit vector , a circle. The right plot holds every point . Grab the arrow tips and pull.

The ellipse always has its axes along the eigenvectors, stretched by the eigenvalues. A negative also mirrors the ellipse. Equal eigenvalues give a circle at any angle, because when every direction is stretched equally, every direction is an eigenvector.

Beyond two dimensions

Pictures stop at two dimensions. The decomposition does not. Type any symmetric 3 by 3 matrix and the lab finds and with the Jacobi method (added here: the book does not describe it), which rotates away the off-diagonal entries one at a time. It then multiplies the factors back and checks that Equation 2.41 holds.

Eigenvalues come out sorted, largest first. The rebuild error is printed as below , the level of rounding. That is Equation 2.41’s guarantee for any symmetric input.

Uniqueness and failure

When the decomposition is not unique

Every real symmetric matrix has an eigendecomposition, but it may not be unique. If eigenvalues repeat, any orthogonal vectors in their span are eigenvectors too, so a different works. With the entries of sorted in descending order, the decomposition is unique only if all eigenvalues are distinct.

Turn your guess for (drag on the plane) until the dashed ellipse built from covers the solid ellipse, .

With distinct eigenvalues the error is zero at one angle only. With equal eigenvalues the target is , every basis reproduces it, and the error is zero everywhere. One more remark, added here: each eigenvector can be negated without changing the product, so “unique” means unique up to signs.

When the decomposition fails

The book says it plainly: not every matrix can be decomposed this way. Sometimes the decomposition needs complex numbers. Sometimes has fewer than independent eigenvectors, and then has no inverse. Try to break it.

A rotation turns every vector, so no real direction survives. The eigenvalues are the complex pair . The decomposition exists, but over the complex numbers. A shear has the repeated eigenvalue 1 and one eigenvector line, so cannot be inverted. A symmetric matrix always has two real perpendicular lines.

What the eigenvalues reveal

The decomposition hands you several facts for free. First, a matrix is singular if and only if one of its eigenvalues is zero. A zero eigenvalue means for some non-zero : a whole line is squashed onto the origin, and a squashed line cannot be restored.

With one eigenvalue at 0, different inputs share one output, and no inverse can tell them apart.

Optimizing a quadratic expression

The decomposition also solves a classic optimization problem. For a real symmetric , consider

The book states three results. When is a unit eigenvector, equals the matching eigenvalue. The maximum of on the unit circle is the largest eigenvalue, and the minimum is the smallest. The reason, added here: write for the coordinates of along the eigenvectors. Then

Since keeps lengths, the numbers are non-negative and add to 1. So is a weighted average of the eigenvalues. An average cannot beat the biggest value or fall under the smallest, and it reaches them when all the weight sits on one eigenvector.

Drag around the circle. The ring is teal where is positive and orange where it is negative. The lower plot unrolls it.

The wave rises to the largest eigenvalue and sinks to the smallest. Peaks sit where lies along an eigenvector. Turn the eigenvectors and the wave slides sideways without changing height. Change the eigenvalues and the peak and trough follow them.

Definiteness

The signs of the eigenvalues give symmetric matrices a vocabulary. All eigenvalues positive: positive definite. All positive or zero: positive semidefinite. All negative: negative definite. All negative or zero: negative semidefinite.

These names promise something about . A positive semidefinite matrix guarantees

A positive definite matrix adds that only the zero vector makes the expression vanish:

Both follow from the weighted average. If every eigenvalue is at least 0, so is any average of them. If every eigenvalue is above 0, the average hits 0 only when every weight is 0, which forces .

Before you see the picture, commit to a guess. Each round shows the eigenvalues of a symmetric matrix. Say what does, then the map is revealed.

Now play freely. The map shows the sign of over the whole plane.

Two positive eigenvalues give a bowl, teal everywhere except the origin. Send to 0 and a whole line of vectors makes the expression vanish. Opposite signs split the plane into teal and orange: the matrix is indefinite (a name added here, not defined in the book), and none of the four names fits. Both negative flips every sign.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 2.7 (pages 42–44), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.