Factorizing a block symmetric matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T13:51:40Z http://mathoverflow.net/feeds/question/88728 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/88728/factorizing-a-block-symmetric-matrix Factorizing a block symmetric matrix Federico Poloni 2012-02-17T15:40:25Z 2012-02-20T15:04:10Z <p>Let $X,Y\in\mathbb{R}^{n\times n}$ be symmetric matrices. You may assume that $X$ is positive semidefinite and $Y$ negative semidefinite, if needed, but not that they are invertible.</p> <p>I would like to find a way to factor the $2n\times 2n$ block matrix $$\begin{bmatrix} X &amp; I\\ I &amp; Y \end{bmatrix}$$ into some form of the kind $MDM^T$, where:</p> <ul> <li>$D$ should be a "simple" matrix, ideally diagonal or of the form $D=\begin{bmatrix}0 &amp; I\\I &amp; 0\end{bmatrix}$, or something similar;</li> <li>The factorization should take explicit advantage of the identities being there, without treating them as general matrices and thus depending on too many parameters, so the Cholesky factorization is ruled out.</li> </ul> <p>Is there some nice identity that I am missing?</p> http://mathoverflow.net/questions/88728/factorizing-a-block-symmetric-matrix/88748#88748 Answer by S. Sra for Factorizing a block symmetric matrix S. Sra 2012-02-17T18:43:38Z 2012-02-20T15:04:10Z <p>Assuming that $X$ and $Y$ are invertible (if not, probably a perturbation argument will yield the generalization). Then, the following choice of $M$ works, i.e., $MDM^T$ equals your original matrix with $D$ being the anti-diagonal identity matrix as desired. </p> <p>(Also, <strong>note slightly different notation</strong>, I write $-Y$ instead of $Y$ as in the original question, so that both $X$ and $Y$ are positive).</p> <p>A solution is given by: \begin{equation*} M = \begin{bmatrix} a &amp; b\\ c &amp; d \end{bmatrix}, \end{equation*}</p> <p>where</p> <p>\begin{equation*} a = X^{1/2},\quad b=\frac{X^{1/2}}{2},\quad c = X^{-1/2} - (X^{-1}+Y)^{1/2},\quad d = \frac{X^{-1/2} + (X^{-1}+Y)^{1/2}}{2}. \end{equation*}</p> <p><strong>Edit.</strong> Typo in $d$ fixed now.</p> <hr> <p>To see that the above matrix provides a solution, simply verify</p> <p>\begin{equation*} \begin{bmatrix} a &amp; b\\ c &amp; d \end{bmatrix}\begin{bmatrix} 0 &amp; I\\ I &amp; 0\end{bmatrix}\begin{bmatrix} a^T &amp; c^T\\ b^T &amp; d^T\end{bmatrix} = \begin{bmatrix} X &amp; I\\ I &amp; -Y\end{bmatrix}, \end{equation*} which boils down to checking the following four equations: \begin{eqnarray*} ad^T + bc^T &amp;=&amp; I\\ cb^T + da^T &amp;=&amp; I\\ ab^T + ba^T &amp;=&amp; X\\ cd^T + dc^T &amp;=&amp; -Y. \end{eqnarray*}</p> http://mathoverflow.net/questions/88728/factorizing-a-block-symmetric-matrix/88761#88761 Answer by Victor Liu for Factorizing a block symmetric matrix Victor Liu 2012-02-17T20:22:26Z 2012-02-18T07:32:39Z <p>Suvrit's answer can be interpreted sort of as an application of the Cholesky factorization on the 2x2 block structure. I will add an answer that may help if $X$ and $Y$ share a similar sparsity structure. You can apply an interlacing permutation $P$ such that if your matrix is $A$, then $PAP^T$ interlaces the rows and columns from each of the two halves. You would have diagonal blocks like $$\begin{bmatrix} x_{ii} &amp; 1 \\ 1 &amp; y_{ii} \end{bmatrix}$$ and off diagonal blocks like $$\begin{bmatrix} x_{ij} &amp; 0 \\ 0 &amp; y_{ij} \end{bmatrix}$$ Now if $X$ and $Y$ are both sparse, the $LDL^T$ factorization likely exists since each diagonal 2x2 block is more likely full rank, so you can apply the factorization in 2x2 blocks.</p>