Update inverse of cross product

Question

I have a problem where I have a matrix $\bf{A}$ which is non-square, I compute the cross product ($\bf{B} = \bf{A}^T * \bf{A}$), and then invert the symmetric matrix $\bf{B}$ to get $\bf{B}^{-1}$. Then $\bf{A}$ is updated by having the first row removed and a new final row added. This has to be done many times, so I am wondering whether I have missed something about how to compute $\bf{B}^{-1}$ directly from knowing the new row in $\bf{A}$. Thanks in advance.

Answer 1

Assume that $A\in{\mathbb R}^{m\times n}$ for $n<m$, and that $B = A^TA$ is invertible.

Let {$e_k$} be the standard base vectors for ${\mathbb R}^m$, and define the upshift matrix $$\eqalign{ &U = [\,e_m\,\,e_1\,\,e_2 \ldots e_{m-1}\,] \cr &U^{-1} = U^T \cr }$$ The product $(UA)$ shifts the rows of $A$ upward and moves the first row to the last row.

The first row of $A$ is given (as a column vector) by: $\,\,a=A^Te_1$
The replacement row is given by the (column) vector: $\,\,v$
Their difference is the vector: $\,\,w = (v-a)$
The updated $A$ matrix is: $\,\,Z = UA + e_mw^T$

Let $Y$ denote the updated $B$ matrix, which can be calculated as $$\eqalign{ Y &= Z^TZ \cr &= A^TU^TUA + A^TU^Te_mw^T + we_m^TUA + we_m^Te_mw^T \cr &= A^TA + A^Te_1w^T + we_1^TA + ww^T \cr &= B + aw^T + wa^T + ww^T \cr &= B + vw^T + wa^T \cr }$$ To calculate the inverse of $Y\,$ apply the Sherman-Morrison formula to the following sequence of matrices $$\eqalign{ X &= B + vw^T \cr Y &= X + wa^T \cr }$$ which will look something like this $$\eqalign{ X^{-1} &= B^{-1} - \tfrac{B^{-1}vw^TB^{-1}}{1+w^TB^{-1}v} \cr Y^{-1} &= X^{-1} - \tfrac{X^{-1}wa^TX^{-1}}{1+a^TX^{-1}w} \cr }$$