Assume an $N \times N$ matrix $A$ and a length $N$ vector $b$. I've already solved the system $Ax = b$ for $x$ using standard methods. (If you want you can assume that I have the inverse of $A$ as well.)
Now, I have a block matrix A' = \begin{pmatrix} A & V \\ U & 0 \\ \end{pmatrix}
and a block vector b' = (b, b^*)^T. $U$ is an $1 \times N$ matrix, $V$ is an $N \times 1$ matrix, and the zero in the lower right corner is a scalar (or $1 \times 1$ matrix if you prefer).
In other words A' is a matrix created by adding one row and one column onto $A$ and b' is a vector created by adding one element onto $b$. I want to solve the system A'x' = b' for x'. This is the same system as $Ax=b$ except that it has one extra equation and one extra variable to be solved for. Is there an efficient (less than $O(N^3)$) algorithm for this given that I've already computed the solution to $Ax=b$?