2
$\begingroup$

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.

2 Answers 2

1

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

  • 0
    I started a $M$-independent [answer](http://math.stackexchange.com/a/89606/163) 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...2011-12-08
0

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.