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.

I would like to find a way to factor the $2n\times 2n$ block matrix $$ \begin{bmatrix} X & I\\\\ I & Y \end{bmatrix} $$ into some form of the kind $MDM^T$, where:

  • $D$ should be a "simple" matrix, ideally diagonal or of the form $D=\begin{bmatrix}0 & I\\\\I & 0\end{bmatrix}$, or something similar;
  • 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.

Is there some nice identity that I am missing?


2 Answers 2


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.

(Also, note slightly different notation, I write $-Y$ instead of $Y$ as in the original question, so that both $X$ and $Y$ are positive).

A solution is given by: \begin{equation*} M = \begin{bmatrix} a & b\\\\ c & d \end{bmatrix}, \end{equation*}


\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*}

Edit. Typo in $d$ fixed now.

To see that the above matrix provides a solution, simply verify

\begin{equation*} \begin{bmatrix} a & b\\\\ c & d \end{bmatrix}\begin{bmatrix} 0 & I\\\\ I & 0\end{bmatrix}\begin{bmatrix} a^T & c^T\\\\ b^T & d^T\end{bmatrix} = \begin{bmatrix} X & I\\\\ I & -Y\end{bmatrix}, \end{equation*} which boils down to checking the following four equations: \begin{eqnarray*} ad^T + bc^T &=& I\\\\ cb^T + da^T &=& I\\\\ ab^T + ba^T &=& X\\\\ cd^T + dc^T &=& -Y. \end{eqnarray*}

  • $\begingroup$ Nice. I arrived at something similar using the Schur complement formula, but what I really would like to get rid of is the requirement of nonsingularity of X$... $\endgroup$ Commented Feb 17, 2012 at 22:04
  • $\begingroup$ @Federico: roughly speaking, won't using $X \gets X + \epsilon I$, doing the math with that, and then letting $\epsilon \to 0$ yield the desired answer? (I say that because originally, I had derived the answer in terms of matrix geometric means, which can be extended using the $\epsilon$ trick). $\endgroup$
    – Suvrit
    Commented Feb 18, 2012 at 3:06
  • $\begingroup$ You're right, it does. $\endgroup$ Commented Feb 18, 2012 at 20:38
  • $\begingroup$ Hmm, can you double-check that identity? Numerically it does not hold, and what is fishier is that $b=a/2$ and $d=c/2$, so your factor matrix $M$ has rank at most $n/2$. $\endgroup$ Commented Feb 20, 2012 at 8:49
  • 1
    $\begingroup$ I obtained another solution (the matlab code seems to require invertible $Y$) via Riccati equations: $d=I$, $c=-Y/2$, $BYB+2B=X$, and $A=I+BY/2$. I tested this solution in Matlab---works fine. Using similar ideas, I think one could overcome the dependence on $Y$ being invertible---by appropriately defining solutions to $BYB+2B=X$ for rank deficient $X$ and $Y$ (extreme case $X=0$ gives $B=0$, and $Y=0$ forces $B=X/2$, so maybe the method can be extended). $\endgroup$
    – Suvrit
    Commented Feb 20, 2012 at 22:45

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} & 1 \\\\ 1 & y_{ii} \end{bmatrix} $$ and off diagonal blocks like $$ \begin{bmatrix} x_{ij} & 0 \\\\ 0 & 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.

  • $\begingroup$ Those diagonal blocks being nonsingular is not a problem, since $x_{ii}\geq 0$ and $y_{ii}\leq 0$ under the semidefiniteness assumption. However, if I am not mistaken, after the first $LDL^T$ step, you need to take a Schur complement that spoils the $1$'s in your structure. $\endgroup$ Commented Feb 20, 2012 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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