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}. $$

  • $\begingroup$ Hi thank you for the answer! The Schur complement approach makes a lot of sense. As for the SVD, how do we know that the matrix multiplication achieves that matrix (and consequently, what the inverse of the 3x3 block matrix is)? $\endgroup$ – potionboy Sep 12 '13 at 11:34
  • $\begingroup$ 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? $\endgroup$ – potionboy Sep 12 '13 at 11:41
  • $\begingroup$ @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. $\endgroup$ – user1551 Sep 12 '13 at 11:49
  • $\begingroup$ @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. $\endgroup$ – user1551 Sep 12 '13 at 12:19
  • $\begingroup$ Oh, sorry that makes more sense. (I realized this and deleted the comment when multiplying through $A^*A$.) Thanks again! $\endgroup$ – potionboy Sep 12 '13 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.