Lecture 17: How Eigenvalues Change When a Matrix Changes

What this lecture covers

This lecture asks what happens to a matrix's inverse, eigenvalues, and singular values when the matrix itself changes over time or by a finite perturbation. Professor Strang first finishes a derivative formula for the inverse, then derives a clean formula for the derivative of an eigenvalue, and finally studies what a rank-one change does to the eigenvalues of a symmetric matrix.

It follows the previous lecture's formula for how A inverse changes when A changes by a low-rank update. Watching this lecture, you'll be able to write down the derivative of an eigenvalue in terms of the matrix's rate of change and its left and right eigenvectors, and state the interlacing theorem that bounds how much eigenvalues can move after a positive rank-one or rank-two update.

Key ideas

• Derivative of the inverse: for A(t) invertible, d(A^-1)/dt = -A^-1 (dA/dt) A^-1, the matrix generalization of the single-variable rule d(1/t)/dt = -1/t^2.
• Left and right eigenvectors: A(t)x(t) = lambda(t)x(t) gives the right eigenvector; a row vector y(t) with y(t)A(t) = lambda(t)y(t) gives the left eigenvector, from the eigenvalues of A transpose (equal to those of A).
• Natural normalization: choosing y transpose x = 1 fixes the scale of the paired left and right eigenvectors; in the symmetric case x = y = q, a unit vector.
• Derivative of an eigenvalue: d(lambda)/dt = y transpose (dA/dt) x, with the derivative terms in x and y cancelling out of the calculation.
• Rank-one positive update: adding u u^T to a symmetric matrix S only increases eigenvalues, since u u^T is positive semidefinite with one positive eigenvalue (u^T u, the squared length of u).
• Interlacing theorem: if lambda_i are the eigenvalues of S + u u^T and gamma_i those of S, then lambda_i >= gamma_i >= lambda_(i+1) - eigenvalues rise but can't leapfrog past the next old eigenvalue.
• Removing a row and column: the eigenvalues of an (n-1)x(n-1) principal submatrix interlace the eigenvalues of the full n x n symmetric matrix in the same pattern.

Walkthrough

Recap and today's plan (0:01)

Strang recaps the prior lecture's formula for the change in A inverse when A changes by a low-rank update (the Woodbury-type identity), noting he had cleaned up sign errors in the notes. He lays out this lecture's two tracks: an exact calculus result for infinitesimal changes, dA/dt, and a set of inequalities (rather than an exact formula) for finite-size changes in eigenvalues and singular values.

The derivative of A inverse (4:23)

Starting from the identity B^-1 - A^-1 = B^-1(A - B)A^-1, Strang sets B = A + delta A, divides by delta t, and lets delta t go to zero. The result is d(A^-1)/dt = -A^-1 (dA/dt) A^-1. He points out this is the matrix version of the familiar scalar rule d(1/t)/dt = -1/t^2, completing the previous lecture's low-rank update formula with its calculus counterpart.

Setting up eigenvalues, eigenvectors, and normalization (16:42)

To find how an eigenvalue changes, Strang assembles the facts he needs: A(t)x(t) = lambda(t)x(t) for the right eigenvector, and a row eigenvector y(t) satisfying y(t)A(t) = lambda(t)y(t), coming from the fact that A transpose shares the same eigenvalues as A but generally different eigenvectors. Because x and y each have arbitrary length, he fixes their scale with the normalization y transpose x = 1. In matrix form for all eigenpairs at once, this becomes AX = X(Lambda) and Y transpose X = I. From y transpose A x = lambda, using the normalization, he gets a formula for lambda(t) itself, ready to differentiate.

The product rule and the eigenvalue derivative formula (23:00)

Differentiating lambda(t) = y(t) transpose A(t) x(t) by the product rule produces three terms: one with dy/dt, one with dA/dt, and one with dx/dt. Strang shows the two terms involving dx/dt and dy/dt cancel, because together they equal the derivative of y transpose x, which is constant at 1 and so has derivative zero. What remains is the clean result d(lambda)/dt = y transpose (dA/dt) x: the eigenvalue's rate of change depends only on how A is changing, sandwiched between the left and right eigenvectors, with no need to know how the eigenvectors themselves are changing.

Rank-one changes and the interlacing theorem (30:56)

Turning to finite (not infinitesimal) changes, Strang restricts to a symmetric matrix S updated by a rank-one positive semidefinite matrix u u^T. He shows u is an eigenvector of u u^T with eigenvalue u^T u, so all eigenvalues of the update are nonnegative and adding it can only push the eigenvalues of S up, never down. The interlacing theorem states precisely how far: if lambda_i are the new eigenvalues and gamma_i the old ones, then lambda_1 >= gamma_1 >= lambda_2 >= gamma_2 >= ... - each new eigenvalue exceeds the corresponding old one but cannot pass the old eigenvalue one step ahead. He extends the idea to rank-two updates and to deleting a row and column from a symmetric matrix, where the smaller matrix's eigenvalues interlace the original's. The lecture ends on an open puzzle: if u happens to be an eigenvector of S itself, scaling u by a large number seems to threaten the interlacing bound, which Strang leaves as a question for the next class.

Before you watch

• Review the previous lecture's formula for how A inverse changes under a low-rank update to A, since this lecture completes it with the derivative version.
• Be comfortable with the eigenvalue decomposition Ax = lambda x and with what it means for a matrix to be positive semidefinite.
• Basic single-variable calculus (product rule, limits) is used directly to derive the matrix formulas.

Check your understanding

1. Derive the identity B^-1 - A^-1 = B^-1(A - B)A^-1 and use it to obtain d(A^-1)/dt = -A^-1 (dA/dt) A^-1.
2. Why does the normalization y transpose x = 1 make the derivative of y transpose x equal to zero, and why is that the key step in deriving d(lambda)/dt?
3. For a symmetric matrix S and a rank-one update S + u u^T, explain why every eigenvalue of S can only increase, not decrease.
4. State the interlacing inequality between the eigenvalues of S + u u^T and the eigenvalues of S, and explain in words why an eigenvalue can't jump past the next old eigenvalue.
5. If u is chosen to be an eigenvector of S, why does scaling u by a large constant seem to threaten the interlacing bound? What resolves the apparent contradiction?