Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a problem proving a matrix identity that comes from a data validation and reconciliation problem. So far, we could "see" numerically that the following identity seems to hold, but could not prove it. Here it goes:

Let $S\in \mathbb{R}^{m\times m}$ be a symmetric, positive definite matrix, and $F\in \mathbb{R}^{l\times m}$ and $G\in \mathbb{R}^{l\times n}$ matrices with full rank. Define $$Z=\begin{bmatrix}S^{-1} & 0 & F^T \\ 0 & 0 & G^T \\ F & G & 0 \end{bmatrix}$$ and assume $Z$ to be invertible. Now define $P_m=\begin{bmatrix}I_m&0_{m,n+l}\end{bmatrix}$ and $P_l=\begin{bmatrix}0_{l,m+n}&I_l\end{bmatrix}$.

What we need to compute is the following matrix $$T = (P_m Z^{-1} P_l^T) (FSF^T) (P_m Z^{-1} P_l^T)^T$$ It seems, however, that $T$ can also be computed easier, namely by $$\tilde T=S - P_m Z^{-1} P_m^T = (P_m Z P_m^T)^{-1} - P_m Z^{-1} P_m^T.$$ Numerical experiments up to $l=50$ and choosing arbitrary $m$ and $n$ such that $n\leq l$ and $l\leq m+n$ (otherwise $Z$ is not invertible) showed that $\|T-\tilde T\|_F<10^{-7}\|S\|_F$ for randomly generated matrices $S,F,G$, fulfilling the stated assumptions.

However, I cannot prove it analytically. So far, I've tried using the Schur's complement, the Woodbury matrix identity and the binomial inversion theorem on $Z$, but can't make much progress there, because all those identities seem to take me nowhere. One more observation is that $T$ can also be written as $T = USU^T$ with $U=P_m Z^{-1} P_l^T F$ where $U$ is a projection matrix (i.e. $U^2=U$) with rank $l-n$ and the image of of $P_mZ^{-1}P_m^T$ seems to be equal to the kernel of $P_m Z^{-1} P_m^T$.

Note: just a short explanation what all those matrices mean: $S$ is the covariance matrix of the input data, $F$ and $G$ are constrained matrices of measured and unmeasured input data, $T$ is the covariance matrix of the reconciliation vector, i.e. the correction that need to be applied to the input data. The formula for $T$ is just the typical forward error propagation under the assumption that everything is nicely linear and Gaussian. The blocks in $Z$ correspond to measured data, unmeasured data and Lagrangian multipliers respectively.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

In general, $Z$ may be singular. For example, consider $m=n=1<l=2$ and $$ Z=\begin{pmatrix} 1&0&1&0\\ 0&0&1&0\\ 1&1&0&0\\ 0&0&0&0 \end{pmatrix}. $$ So, suppose that $Z$ is invertible. Then we can prove the identity using Schur complement. The Schur complement of $S^{-1}$ in $X$ is given by $Y = \begin{pmatrix}0&G^T\\G&-FSF^T\end{pmatrix}$. Then $$ Z^{-1} = \begin{pmatrix} S + S (0, F^T) Y^{-1} \begin{pmatrix}0\\F\end{pmatrix}S & -S(0, F^T) Y^{-1}\\ \\ \ast & \ast \end{pmatrix}. $$ Now, let $Y^{-1} = \begin{pmatrix}\ast&R^T\\R&Q\end{pmatrix}$, where $Q$ is symmetric because $Y$ is symmetric. Then $P_m Z^{-1} P_l^T = -S F^T Q$ and \begin{align*} H &:= FSF^T,\\ T &= S F^T Q (FSF^T) QF S = SF^T QHQFS,\\ \widetilde{T} &= S - P_m Z^{-1} P_m^T = S - \left(S + S (0, F^T) Y^{-1} \begin{pmatrix}0\\F\end{pmatrix} S \right) = - S F^T Q F S. \end{align*} Therefore, to show that $T=\widetilde{T}$, we need to show $SF^T QHQFS=- SF^T QFS$. Hence it suffices to verify that $QHQ=-Q$. From the identity $YY^{-1}=I$, we get \begin{align*} G^TQ&=0,\\ GR^T-HQ&=I. \end{align*} Left multiply the second identity by $Q$, we get $Q(GR^T-HQ)=Q$. Yet, by the first identity, we have $Q(GR^T-HQ) = (RG^TQ)^T - QHQ = -QHQ$. Hence we are done.

share|improve this answer
    
Thanks a lot for your work. There is just one caveat: the matrix $H=FSF^T$ is not invertible in general. I've checked the rest and of the prove, which seemed to be fine. So, if it were possible to show $QHQ+Q=0$ without using $H^{-1}$ that would indeed prove it. –  Elmar Zander Feb 12 '13 at 14:37
    
Ah, I just saw that you assumed $l\leq m$. Then, of course, $H^{-1}$ does exist; however, this case would not be relevant for me. To rule out cases like in your first example it would be better (and relevant) to assume that $[F G]$ has full rank instead of $F$ and $G$ separately. –  Elmar Zander Feb 12 '13 at 15:03
    
@ElmarZander Nice observation. I have reworked the proof to show that $QHQ+Q=0$ in general. See my new edit. –  user1551 Feb 12 '13 at 16:28
    
Great! And this is much more elegant than with the Schur complement of $Y$. Actually, that's where I got stuck when I was trying to prove it myself. –  Elmar Zander Feb 13 '13 at 9:42
    
BTW: if this should go into a paper (it probably will, as part of some larger thing), I would like to acknowledge your contribution. So, if you're interested, you could send me your contact information and I would put you in. –  Elmar Zander Feb 13 '13 at 9:47

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.