Sherman-Morrison-Woodbury formula

Suppose you already know A^-1 and then perturb A by a low-rank piece, A_new = A + U C V^T, where U and V are tall-thin (k columns) and C is a small k-by-k matrix. Recomputing the inverse from scratch costs n^3. The Woodbury formula gives the new inverse exactly, doing all the heavy lifting on a tiny k-by-k matrix instead.

The identity is (A + U C V^T)^-1 = A^-1 - A^-1 U (C^-1 + V^T A^-1 U)^-1 V^T A^-1. The only inverse of nontrivial size on the right is of the k-by-k capacitance matrix C^-1 + V^T A^-1 U. When k is small (often k = 1), that is essentially free. The rank-1 special case A_new = A + u v^T is the famous Sherman-Morrison formula.

It is the algebraic backbone of every cheap re-solve when A changes slightly. Kalman filters, recursive least squares, Gaussian-process updates, and interior-point methods all use it to fold a new observation or constraint into an existing factorization without paying the full inversion cost again.

Two honest cautions. First, it can be numerically unstable: if the capacitance matrix is nearly singular, the subtraction amplifies error, and for that reason an updated triangular factorization is often preferred over the explicit Woodbury inverse. Second, it requires the capacitance matrix to be invertible, which fails exactly when the update would make A_new singular.