# Can $A^T M^{-1} B$ be calculated as $(C^TMD)^{-1}$ for non-square matrices $A,B$?

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.

-

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.

-

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$.

-
+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
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