Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

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

where

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

share|improve this answer
    
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$... –  Federico Poloni Feb 17 '12 at 22:04
    
@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). –  Suvrit Feb 18 '12 at 3:06
    
You're right, it does. –  Federico Poloni Feb 18 '12 at 20:38
    
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$. –  Federico Poloni Feb 20 '12 at 8:49
1  
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). –  Suvrit Feb 20 '12 at 22:45
show 2 more comments

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.

share|improve this answer
    
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. –  Federico Poloni Feb 20 '12 at 10:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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