5

I have a strong suspicion this is a textbook linear algebra problem, but I have been unsuccessful in finding an answer.

Let $A$ be an $n \times m$ matrix and let $B$ be an $m \times n$ matrix where $n < m$. Suppose than $A$ has rank $n$ ($A$ has a right-inverse) and $B$ also has rank $n$ ($B$ has a left-inverse).

When is $AB$ invertible?

Here is what I have so far. Say that $AB$ is invertible and the inverse is $C$. Then,

$\left(CA\right) B = I_{n}$

And,

$A\left(B C\right) = I_{n}$.

Or: $BC$ must be a right-inverse of $A$ and $CA$ must be a left-inverse of $B$.

$CA = B^{-1}_{left} \implies C = B^{-1}_{left} A^{-1}_{right}$

$BC = A^{-1}_{right} \implies C = B^{-1}_{left}A^{-1}_{right}$

So, if $C$ exists, then I know what it is. If I know there is a $C$ such that $CA$ is a left-inverse of $B$ and $BC$ is a right-inverse of $A$, then the product is invertible. What I'm looking for are more primitive conditions on the matrices $A$ and $B$ that guarantee such a matrix exists.

John
  • 320
  • 2
    What kind of condition are you hoping for? You need $\ker A \cap \operatorname{im} B = {0}.$ You can try to do some kind of decomposition on $A$ (SVD or QR) to check this, but to be honest, this amounts to the same as inspecting the invertibility of $AB$. – user7530 Jan 07 '18 at 03:53
  • 1
    Exactly. I am looking for conditions on $A$ and $B$ (which will probably take the form of "given $A$, if $B$ satisfies this condition which depends on $A$, then") that in addition to the assumption that $A$ and $B$ both have full-rank leads to $\text{ker} A \cap \text{im} B = \emptyset$. $A$ and $B$ having full rank ensures that the dimension of the kernel of $A$ and the image of $B$ are compatible, for example, and my hope was that there was an easy-to-verify sufficient condition to determine when the intersection is empty. – John Jan 07 '18 at 05:15
  • 1
    I really doubt there is anything useful. – Mariano Suárez-Álvarez Jan 07 '18 at 05:36
  • Bummer. I think I may be able to solve this for the particular problem I'm most immediately interested in by directly computing the kernel and image, but I was hoping there was some more general principle to use for future problems like this. Thanks! – John Jan 07 '18 at 05:51
  • It might help to look separately at the cases of whether $n$ is greater than or less than $m$. They seem conceptually different here. – Paul Jan 07 '18 at 19:19

1 Answers1

1

If you already have $A$ and $B$ in hand, simply check that $AB$ is invertible. You can do this by computing $\det (AB)$, of course, but in practice it is more robust to perform a rank-revealing decompostion (like QR decomposition) on $AB$.

It is hard to imagine a simpler approach, especially if $n \ll m$.

Some intuition for why you should not expect a "simpler" condition: you are trying to check the condition that $\ker A$ and $\operatorname{im} B$ are linearly independent, so any kind of calculation that checks this condition is going to boil down to computing the dimension of some linear space. You can explicitly construct $\ker A$ and $\operatorname{im} B$ using e.g. the singular value decomposition of the two matrices, and check linear dependence explicitly, but this decomposition will end up no less computationally expensive than numerically computing the rank of $AB$.

user7530
  • 49,280
  • I accepted because it sounds like there is no simpler condition and the answer states that. Thank you! Clearly, checking whether $AB$ is invertible would be the way to go with $A$ and $B$ in hand, but I am trying to show a certain result in a larger class of problems and I only know formulas for $A$ and $B$ in terms of moments of the data. The goal of the question was to know whether $AB$ was invertible more generally if $A$ is right-invertible and $B$ is left-invertible because those are properties that I can show are true for any data generating process. Thanks again to all! – John Jan 07 '18 at 23:07