# Inverse of a certain block matrix

So I'm trying to compute the inverse of a block matrix that's a subset of a larger consideration I was attempting (this particular matrix comes from the normal and orthogonal equations for least squares). Let $A$ be an $m\times n$ matrix with full column rank, and I'm trying to compute the inverse of this guy: $$\begin{bmatrix} A^* & A^*A\\ I+AA^* & A \end{bmatrix}$$ Following through straightforward Gaussian elimination and augmenting by the identity, I right multiply $A^*$ with its right inverse (which exists since it has full row rank), and then I zero out the bottom left corner by $\text{new_row}_2=-(I+AA^*)\text{row}_1+\text{row}_2$. $$\left[\begin{array}{cc|cc} A^* & A^*A & I & 0\\ I+AA^* & A & 0 & I \end{array}\right] \to \left[\begin{array}{cc|cc} I & A^*A(A^*)^{-1} & (A^*)^{-1} & 0\\ 0 & -(I+AA^*)A^*A(A^*)^{-1}+A & -(I+AA^*)(A^*)^{-1} & I \end{array}\right]$$ However, here's where I'm stuck. The bottom-right entry is far too convoluted for me to find an inverse and get an identity matrix out of. Also, the $A^*)A^*$ part of the term doesn't even make any sense, as this is multiplying $n\times m$ with $n\times m$ (and likely true for the $A(A^*)^{-1}$ as well). I assume I can't just right-multiply like that and follow through. Is there a way to simplify this?

-

\begin{align*} \begin{bmatrix} A^\ast & A^\ast A\\ I_m+AA^\ast & A \end{bmatrix}^{-1} &= \left(\begin{bmatrix} A^\ast A&A^\ast\\ A&I_m+AA^\ast \end{bmatrix} \begin{bmatrix} 0&I_n\\ I_m&0 \end{bmatrix}\right)^{-1}\\ &= \begin{bmatrix} 0&I_m\\ I_n&0 \end{bmatrix} \color{red}{\begin{bmatrix} A^\ast A&A^\ast\\ A&I_m+AA^\ast \end{bmatrix}}^{-1}. \end{align*} Since both $A^\ast A$ and the Schur complement $S=I_m + AA^\ast - A(A^\ast A)^{-1}A^\ast$ are invertible, you can compute the inverse on the last line by the matrix inversion formula $$\begin{bmatrix}A&B\\ C&D\end{bmatrix}^{-1} = \begin{bmatrix}A^{-1}+A^{-1}BS^{-1}CA^{-1} & -A^{-1}BS^{-1}\\ -S^{-1}CA^{-1} & S^{-1} \end{bmatrix}$$ where $S=D-CA^{-1}B$ (to apply this formula, you should replace $A$ by $A^\ast A$ and $B$ by $A^\ast$ etc.).
Alternatively, if you perform a singular value decomposition $A=U_{m\times m}\begin{bmatrix}\Sigma_{n\times n}\\ 0_{(m-n)\times n}\end{bmatrix}V_{n\times n}^\ast$, where $U$ and $V$ are unitary, it is easy to see that $$\color{red}{\begin{bmatrix} A^\ast A&A^\ast\\ A&I_m+AA^\ast \end{bmatrix}} = \begin{bmatrix}V\\ &U\end{bmatrix} \begin{bmatrix}\Sigma^2&\Sigma&0\\ \Sigma&I_n+\Sigma^2&0\\ 0&0&I_{m-n}\end{bmatrix} \begin{bmatrix}V^\ast\\ &U^\ast\end{bmatrix}$$ and hence $$\color{red}{\begin{bmatrix} A^\ast A&A^\ast\\ A&I_m+AA^\ast \end{bmatrix}}^{-1} = \begin{bmatrix}V\\ &U\end{bmatrix} \begin{bmatrix}\Sigma^{-2}+\Sigma^{-4}&-\Sigma^{-3}&0\\ -\Sigma^{-3}&\Sigma^{-2}&0\\ 0&0&I_{m-n}\end{bmatrix} \begin{bmatrix}V^\ast\\ &U^\ast\end{bmatrix}.$$
I guess I'm having trouble making sure the dimensions here are fine. As I'm interpreting this, don't $\Sigma_{m\times m}$ and $0_{(m-n)\times n}$ have a different # of columns? –  potionboy Sep 12 '13 at 11:41
@potionboy I don't understand what your first question means. As for the second question, there was a typo. $\Sigma$ should be an $n\times n$ invertible diagonal matrix. –  user1551 Sep 12 '13 at 11:49
@potionboy Huh? No, Some authors use the notation $\Sigma$ to denote the rectangular diagonal matrix in the SVD (so that it is $m\times n$), but the $\Sigma^2$ in my answer means $\Sigma_{n\times n}^2$, which is still $n\times n$. I simply dropped the dimension subscript. –  user1551 Sep 12 '13 at 12:19
Oh, sorry that makes more sense. (I realized this and deleted the comment when multiplying through $A^*A$.) Thanks again! –  potionboy Sep 12 '13 at 12:21