You hold A^{-1} for A = I_3 and update to B = A + u v^T with u = v = (1, 1, 1)^T. Give the (1, 2) entry of B^{-1}, and state the cost of this update against a fresh inversion for an n by n matrix.

You hold A^{-1} for A = I_3 and update to B = A + u v^T with u = v = (1, 1, 1)^T. Give the (1, 2) entry of B^{-1}, and state the cost of this update against a fresh inversion for an n by n matrix.

Approach: Apply the Sherman-Morrison formula for a rank one update, computing the scalar 1 + v^T A^{-1} u first, then compare the flop counts of the update and a full inversion.

-1/4. The Sherman-Morrison formula gives B^{-1} = A^{-1} - (A^{-1} u v^T A^{-1})/(1 + v^T A^{-1} u). With A = I the denominator is 1 + v^T u = 1 + 3 = 4 and the numerator is u v^T, the all ones matrix J, so B^{-1} = I - J/4 and the off diagonal entry is -1/4. The diagonal entries are 1 - 1/4 = 3/4, and a check gives (I + J)(I - J/4) = I + J - J/4 - 3J/4 = I. The rank one update costs O(n^2) flops because it only needs two matrix vector products, against O(n^3) for a fresh matrix inverse, which is the whole reason a recursive least squares filter uses it. It fails when 1 + v^T A^{-1} u = 0, since B is singular there.

Follow-up: How does the same idea extend to a rank k update, and at what k does re-inverting become cheaper?

Key concepts: sherman-morrison formula, rank one update, matrix inverse, computational cost.