Factorizing a block symmetric matrix - MathOverflow

Factorizing a block symmetric matrix

2012-02-17T15:40:25Z

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?

Answer by S. Sra for Factorizing a block symmetric matrix

2012-02-17T18:43:38Z

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

Answer by Victor Liu for Factorizing a block symmetric matrix

2012-02-17T20:22:26Z

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.