Let A be an n by n symmetric positive definite matrix and let C be its Cholesky factor so that $A= CC^T$. Assume C has positive diagonal entries. Describe how to efficiently solve the matrix equation $Bx = b$, where $B = A + \hat{A}$, and $\hat{A}$ has zeros everywhere except for the kth column, whose ith entry is i.
I know that $\hat{A} = UV^T$, where $U=[1,2,\cdots, n]^T$ and $V_j = \delta_{j,k}$, where $\delta_{j,k}$ is the Kronecker delta function.
The Sherman-Morrison-Woodbury formula guarantees that for n by 1 column vectors U and V, $(A+UV^T)^{-1} = A^{-1} - A^{-1}U(I + V^T A^{-1}U)^{-1}V^TA^{-1}.$ One can plug in A,U,V above into this formula and one can note that with G, one can efficiently compute $c^T A^{-1}b$ for any n by 1 vectors c and b. But how can one efficiently compute $A^{-1} - (A+UV^T)^{-1}$?
Some hints.
Having $A$ in Cholesky form allows you to solve equations of the form $Ax=y$ efficiently.
The problem is to solve $(A+UV^T) x = b$. This is equivalent to $(I + (A^{-1}U) V^T) x = A^{-1} b$.
The Cholesky factorisation lets you compute $A^{-1} U, A^{-1} b$ efficiently.
Using the Sherman Morrison Woodbury formula gives a straightforward formula for $(I + (A^{-1}U) V^T)^{-1}$ in terms of $A^{-1}U, V$.