Sherman–Morrison Formula

Compute the inverse of a matrix after it has been updated by a rank-one perturbation.

Sherman-Morrison Formula

The Sherman-Morrison formula provides an efficient way to compute the inverse of a matrix after it has been updated by a rank-one perturbation. Specifically, if A is a nonsingular matrix and B = A + uv^T (where u and v are column vectors), the formula states:

B⁻¹ = (A + uv^T)⁻¹ = A⁻¹ - (A⁻¹uv^TA⁻¹) / (1 + v^TA⁻¹u)

This avoids the costly operation of recomputing the inverse from scratch, requiring only matrix-vector multiplications if A⁻¹ is already known.

Worked example: Rank-one Update

Let's consider A as the 2x2 identity matrix (A = I), and the vectors u = [1, 2]^T, v = [2, 0]^T.

First, we find the outer product uv^T:
u = [1, 2]^T, v^T = [2, 0] ➔ uv^T = [[2, 0], [4, 0]]
We form the updated matrix B = A + uv^T = [[1+2, 0+0], [0+4, 1+0]] = [[3, 0], [4, 1]].
Now, compute the inner product (the denominator):
1 + v^TA⁻¹u = 1 + [2, 0] I [1, 2]^T = 1 + [2, 0] [1, 2]^T = 1 + 2 = 3.
Finally, apply the formula for B⁻¹:
B⁻¹ = I - (I [1, 2]^T [2, 0] I) / 3
B⁻¹ = I - [[2/3, 0], [4/3, 0]] = [[1/3, 0], [-4/3, 1]]

The inverse [[1/3, 0], [-4/3, 1]] matches the actual inverse of [[3, 0], [4, 1]].

Experiment with Matrix Updates

Open Sherman-Morrison Formula. We will observe what happens when the denominator is zero.

Click Reset. Start with the default Identity matrix: A11 = 1, A12 = 0, A21 = 0, A22 = 1.
Change the u vector to u1 = 1, u2 = 0.
Change the v vector to v1 = -1, v2 = 0.
Observe the Outer Product is now [[-1, 0], [0, 0]].
Matrix B becomes A + uv^T = [[0, 0], [0, 1]], which has a zero determinant (singular).
The Denominator (1 + v^TA⁻¹u) calculates to 0. The formula fails here, matching the fact that B is singular and has no inverse.

Limitations

The Sherman-Morrison formula assumes that the base matrix A is nonsingular. If A is singular, A⁻¹ does not exist, and the formula cannot be evaluated, even if the resulting matrix B happens to be nonsingular.

Furthermore, if the denominator 1 + v^TA⁻¹u equals exactly zero, it means the rank-one update has precisely collapsed a dimension, making the updated matrix B singular. In floating-point arithmetic, checking for exact zero can be problematic due to rounding errors, so a small epsilon tolerance is normally used in computational software. Here, bounded integer inputs give exact determinant numerators. The code detects singular A and B with those integers, then evaluates the inverse in floating point and displays six decimals. The residual uses unrounded inverse entries; a small displayed residual does not establish numerical stability for arbitrary large or ill-conditioned matrices.

References

For more details on rank-one updates and their history, refer to:
What Is the Sherman-Morrison-Woodbury Formula? (Nicholas J. Higham)

Sherman–Morrison Formula