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.

Given two $n\times m$ matrices $A$ and $B$ and an invertible $n\times n$ matrix $M$, do two other $n\times m$ matrices $C$ and $D$ exist such that the $m\times m$ matrix $X = A^T M^{-1} B$ (assumed to be invertible) is equal to $(C^TMD)^{-1}$ for $n>m$? (The case $n=m$ is obvious, if $A$ and $B$ are invertible, the solution would be $C^T=B^{-1}$ and $D^T=A^{-1}$)

So in brief, do $C$ and $D$ exist (and if so what are their values) such that

$$A^TM^{-1}B=(C^TMD)^{-1}$$

? I guess some minimal requirement would be a maximal rank of $A$ and $B$, but is that sufficient?

edit I am searching for a way to avoid the inversion of the big $n\times n$ matrix $M$ when the inversion of a smaller $m\times m$ matrix $C^TMD$ might be sufficient.

So in extension, if the above-mentioned $C$ and $D$ exist, are there solutions independent of $M$?

edit2 In the case I want to use this, $n$ is a multiple of $m$ such that, as p.s. suggested, using block-matrices might help. I suspect that the minimum requirement for $C$ and $D$ to exist is then that each $m\times m$ block of $A$ and $B$ must be invertible, I'll try to investigate upon that.

share|improve this question
add comment

2 Answers

As p.s. mentioned, the requirement for $C$ and $D$ to exist is that $\mbox{rank}(A^TM^{-1}B)=m$. That implies that $\mbox{rank}(A)=\mbox{rank}(B)=m$, i.e. $A$ and $B$ consist of $m$ linearly independent $n$-dimensional vectors.

Assuming this is the case, one can find (non-unique) invertible matrices $P,Q$ such that $PA=\begin{pmatrix}X\\0\end{pmatrix}$ and $QB=\begin{pmatrix}Y\\0\end{pmatrix}$ with $m\times m$ square matrices $X,Y$ that are also invertible - for example you can use the Gram-Schmidt process to obtain upper triangular matrices $X,Y$. Then $$A^TM^{-1}B = X^T[P^{-T}M^{-1}Q^{-1}]_{1,1}Y$$ where $[...]_{1,1}$ denotes the upper left block of $P^{-T}M^{-1}Q^{-1}=(QMP^T)^{-1}=:H^{-1}$, which is the inverse Schur complement of the lower right block of $H$ such that $$A^TM^{-1}B = (Y^{-1}S_{[H]_{2,2}}X^{-T})^{-1}.$$ The Schur complement is $S_{[H]_{2,2}}= H_{1,1}-H_{1,2}H_{2,2}^{-1}H_{2,1}$

This is not yet a solution for $C$ and $D$, but has reduced the problem to one $(n-m)\times(n-m)$ matrix inversion (from $H_{2,2}$) and some $m\times m$ inversions, but now the same process can be applied recursively to reduce $H_{1,2}H_{2,2}^{-1}H_{2,1}$ to one $(n-2m)\times(n-2m)$ matrix inversion and some more $m\times m$ inversions and so on until some $k$ for which $n-km\le m$, i.e. $k\ge \frac nm-1$.

I'll probably refine this answer at some later point, but please feel free to interrupt me if you have already seen this somewhere else or found an easier solution.

share|improve this answer
add comment

Clearly, this is equivalent to finding $C,D$ such that $C^TMD=(A^T M^{-1} B) ^{-1}$.

If $M$ is $n \times n$ and invertible and $n \ge m$ then for any $m \times m$ matrix $E$, there exist $n \times m$ matrices $C,D$ such that $C^TMD=E$. For example, take $C = F^T\left[ \begin{matrix} I\\0 \end{matrix} \right]$,and $D = (FM)^{-1}\left[ \begin{matrix} E\\0 \end{matrix} \right]$, where $F$ is any invertible $n \times n$ matrix. Note the decomposition is not unique.

So in the specific case $E = (A^T M^{-1} B) ^{-1}$, the only condition we need is that the matrix $(A^T M^{-1} B) ^{-1}$ actually exists. In other words:

$$ \mbox{rank}(A^T M^{-1} B) = m $$

This can be stated in several equivalent ways. However, I'd note that the condition $\mbox{rank}(A) = \mbox{rank}(B) = m$ is not sufficient to imply this unless $n = m$.

share|improve this answer
    
+1 thank you for your answer. I should have mentioned I was trying to avoid inverting $M$ :-/ –  Tobias Kienzler Dec 7 '11 at 15:07
1  
Are you familiar with the Schur complement? It results in many identities for block-matrices that might help. –  p.s. Dec 7 '11 at 15:23
    
Splitting things up in $m\times m, (n−m)\times m$ etc. blocks might help, thanks for pointing that out, I'll try. Especially since in my case, $n$ is a multiple of $m$ such that it all boils down to $m\times m$ blocks... –  Tobias Kienzler Dec 7 '11 at 15:49
    
I started a $M$-independent answer based on your feedback yielding a recursive way to break the inversion down to multiple $m\times m$ inversions, but it's not a closed form solution for $C$ and $D$ yet... –  Tobias Kienzler Dec 8 '11 at 14:07
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.