14. Low Rank Changes in A and Its Inverse

What this lecture covers

The lecture answers a practical question: if you already know the inverse of a matrix and then change that matrix by something small in rank, how do you get the new inverse without starting over? Strang builds up the Sherman-Morrison-Woodbury formula, first for a rank-one change to the identity matrix, then for a rank-K change, and finally for a rank-K change to a general matrix A.

The lecture sits early in the discussion of low-rank structure in the course, and the formula reappears as a computational tool: instead of inverting an n by n matrix from scratch, you invert a much smaller K by K matrix. After watching, you should be able to state the formula, verify it by direct multiplication, and recognize the two main places it is used: updating least-squares solutions as new data arrives, and reusing a matrix factorization when solving a perturbed linear system.

Key ideas

• Rank-one perturbation of the identity: if you change I to I - UV^T, the inverse is I + UV^T / (1 - V^T U), where V^T U is just a number.
• Sherman-Morrison-Woodbury formula: names credited to Sherman, Morrison, and Woodbury (with others contributing pieces); it expresses the inverse of an n by n matrix in terms of the inverse of a K by K matrix.
• Rank-K perturbation: changing a matrix by a rank-K term changes its inverse by a rank-K term as well.
• Columns-times-rows multiplication: seeing A^T A as a sum of rank-one pieces (columns times rows) explains why adding one new data row updates A^T A by a rank-one term.
• Recursive least squares: when a new measurement arrives, you can update the least-squares solution without recomputing the whole normal-equations matrix.
• Kalman filter: described as a more advanced version of recursive least squares for dynamic problems, adding a covariance matrix (for correlated or differently weighted measurements) and a state equation (for a system that is moving over time).
• Reusing a factorization: if you already solved Ax = b, you can solve a rank-one perturbed system by solving one extra system with the same A and combining the two solutions, instead of refactoring A again.

Walkthrough

Perturbing the identity by rank one (1:02)

Strang starts with the simplest case: perturb the identity matrix by a rank-one matrix UV^T and ask for the inverse of I - UV^T. He writes down the claimed answer, I + UV^T / (1 - V^T U), and checks it directly by multiplying the original matrix by the claimed inverse and watching the terms cancel down to the identity. The key observation is that V^T U is a scalar, so the whole formula turns an n by n inverse problem into a problem involving only a 1 by 1 inverse.

From rank one to rank K (9:12)

Strang generalizes U and V from vectors to matrices with K columns, so UV^T becomes a rank-K matrix. He writes the analogous formula for the inverse of I - UV^T, now involving the inverse of the K by K matrix I - V^T U, and works through the same style of check by multiplying it out. He credits the formula to Sherman, Morrison, and Woodbury, noting that different people are thought to have found the rank-one and general-rank versions. The point of the formula is unchanged: instead of inverting a large matrix, you invert a small one.

Updating least squares with a new measurement (18:24)

Strang connects the formula to least squares. Starting from the normal equations A^T A x = A^T b for a tall, thin matrix A, he asks what happens when one new measurement (a new row of A and a new entry of b) arrives. Multiplying the new A^T A out using columns-times-rows shows that the update is the old A^T A plus one new column times one new row, a rank-one change. He emphasizes that the goal is to avoid recomputing A^T A from scratch each time a point is added, since that matrix multiplication is the expensive part of the computation.

The Kalman filter as dynamic least squares (27:42)

Building on the least-squares update, Strang introduces the Kalman filter as recursive least squares extended for tracking a moving target, such as a satellite. He describes two additions beyond the simple update: a covariance matrix that accounts for correlated or unequally reliable measurements (as opposed to the standard case where the covariance is the identity), and a state equation from control theory that predicts how the tracked position should move between measurements. He keeps this part conceptual, aiming to connect the vocabulary of Kalman filtering to the least-squares update just derived, without deriving the filter's equations in full.

Reusing a solved system after a rank-one change (35:48)

Strang turns to a second application: solving (A - UV^T)x = b when you have already solved Aw = b for the same A. Rather than refactoring the new coefficient matrix, he solves one extra system Az = U with the same A, reusing the same elimination work (the same LU factorization), and then combines w and z with the Sherman-Morrison-Woodbury terms to build x. This illustrates the general habit of reusing a factorization across multiple right-hand sides rather than re-eliminating the same matrix.

The full formula for a general matrix A (47:06)

Strang writes the complete Sherman-Morrison-Woodbury formula for (A - UV^T)^-1, replacing the identity matrix from the earlier cases with a general A. The formula starts from A^-1 and subtracts a correction term built from A^-1 U, the inverse of the K by K matrix I - V^T A^-1 U, and V^T A^-1. He notes that this only requires inverting the small K by K matrix in the middle, closing the loop from the rank-one identity case to the general rank-K case with an arbitrary matrix.

Before you watch

• Be comfortable with the normal equations A^T A x = A^T b for least squares, since the lecture builds the update formula directly on top of them.
• Review matrix multiplication as columns times rows, which is used to see why a new data row creates a rank-one change.
• Familiarity with LU factorization and back substitution helps with the section on reusing a solved system for a new right-hand side.

Check your understanding

1. Starting from the claimed formula for (I - UV^T)^-1, how does multiplying it by I - UV^T reduce to the identity matrix?
2. Why does adding one new measurement to a least-squares problem change A^T A by a matrix of rank one rather than some other rank?
3. In the Sherman-Morrison-Woodbury formula for a general matrix A, which piece of the computation is the only one that requires inverting a matrix larger than 1 by 1?
4. Why is it faster to solve Aw = b and Az = U with the same A than to solve (A - UV^T)x = b by factoring the new matrix from scratch?
5. What two features does Strang say make the Kalman filter more than the simplest recursive least-squares update?