Matrix $A$ and $B$ have the same size and column space, can we determine the invertibility of matrix $Q$ satisfying $AQ=B$?

Question

In the following discussion, we are always under the assumption that both $\boldsymbol{A}$ and $\boldsymbol{B}$ are $m$-by-$n$ matrix. Then there are three statements:

1. There exists an invertible matrix $\boldsymbol{Q}$ satisfying $\boldsymbol{A}\boldsymbol{Q}=\boldsymbol{B}$.
2. There exists a singular matrix $\boldsymbol{Q}$ satisfying $\boldsymbol{A}\boldsymbol{Q}=\boldsymbol{B}$.
3. The column vectors of $\boldsymbol{A}$ and $\boldsymbol{B}$ are equivalent, i.e., each column vector of $\boldsymbol{A}$ is a linear combination of column vectors of $\boldsymbol{B}$, and vice versa. (i.e., $\operatorname{rank}(\boldsymbol{A})=\operatorname{rank}(\boldsymbol{B})=\operatorname{rank}([\boldsymbol{A},\boldsymbol{B}])$, $[\boldsymbol{A},\boldsymbol{B}]$ represents the matrix formed by the columns of $\boldsymbol{A}$ and $\boldsymbol{B}$)

It is apparent that "statement 1 $\implies$ statement 3" is correct.

But I'm not sure if "statement 3$ \implies$ statement 1" and "statement 3 $\implies$ statement 2" are correct. If they are correct, how to prove them? Otherwise, could you show me an example of $\boldsymbol{A}$ and $\boldsymbol{B}$ that all matrices $\boldsymbol{Q}$ satisfying $\boldsymbol{A}\boldsymbol{Q}=\boldsymbol{B}$ are invertible/singular while the column vectors of $\boldsymbol{A}$ and $\boldsymbol{B}$ are equivalent. Thanks!

---

Edit

Thanks to everyone, now we can prove that

• if $\operatorname{rank}(\boldsymbol{A})=n$, then "statement 3 $\implies$ statement 1" and "statement 3 $\nRightarrow$ statement 2" hold;
• if $\operatorname{rank}(\boldsymbol{A})<n$, then "statement 3 $\implies$ statement 2" holds.

So the only problem left is to determine whether "statement 3 $\implies$ statement 1" holds when $\operatorname{rank}(\boldsymbol{A})<n$.

Answer 1

With the help of many people, I suppose the problem is resolved. I shall make a summary here.

• if $\operatorname{rank}(\boldsymbol{A})=n$, then "statement 3 $\implies$ statement 1" and "statement 3 $\nRightarrow$ statement 2";
• if $\operatorname{rank}(\boldsymbol{A})<n$, then "statement 3 $\implies$ statement 1" and "statement 3 $\implies$ statement 2".

---

Proof

Assume that statement 3 holds.

First, let's analyze the situation when $\operatorname{rank}(\boldsymbol{A})=n$, which is simpler.

As $n=\operatorname{rank}(\boldsymbol{A})=\operatorname{rank}([\boldsymbol{A},\boldsymbol{B}])$, there exists and only exists one matrix $\boldsymbol{Q}$ satisfying $\boldsymbol{A}\boldsymbol{Q}=\boldsymbol{B}$. Because $\boldsymbol{Q}$ is a $n$-by-$n$ matrix and $\boldsymbol{A}\boldsymbol{Q}=\boldsymbol{B}$, we have $n\geq\operatorname{rank}(\boldsymbol{Q})\geq\operatorname{rank}(\boldsymbol{B})=\operatorname{rank}(\boldsymbol{A})=n$. Therefore, $\operatorname{rank}(\boldsymbol{Q})=n$, i.e., $\boldsymbol{Q}$ is invertible.

Second, let's analyze the situation when $\operatorname{rank}(\boldsymbol{A})<n$.

In both KBS's answer and Sassatelli Giulio's comment, a singular $\boldsymbol{Q}$ is found/constructed. The construction of an invertible $\boldsymbol{Q}$ is as follows.

Let $\operatorname{rank}(\boldsymbol{A})=\operatorname{rank}(\boldsymbol{B})=\operatorname{rank}([\boldsymbol{A},\boldsymbol{B}])=r<n$. First, we can perform a combination of elementary column operations on $\boldsymbol{A}$ and $\boldsymbol{B}$ to make their first $r$ columns linearly independent. Therefore, we have invertible matrices $\boldsymbol{M}$ and $\boldsymbol{N}$ such that $\boldsymbol{A}\boldsymbol{M}=\boldsymbol{R}=(\boldsymbol{\alpha}_1,\dots,\boldsymbol{\alpha}_r,\boldsymbol{\alpha}_{r+1},\dots,\boldsymbol{\alpha}_n)$, $\boldsymbol{B}\boldsymbol{N}=\boldsymbol{S}=(\boldsymbol{\beta}_1,\dots,\boldsymbol{\beta}_r,\boldsymbol{\beta}_{r+1},\dots,\boldsymbol{\beta}_n)$, and both $\boldsymbol{\alpha}_1,\dots,\boldsymbol{\alpha}_r$ and $\boldsymbol{\beta}_1,\dots,\boldsymbol{\beta}_r$ are bases of $\operatorname{col}\boldsymbol{A}$ which is the same as $\operatorname{col}\boldsymbol{B}$.

Then we have an $r$-by-$r$ change-of-basis matrix $\boldsymbol{P}$ which is of course invertible satisfying $$ \boldsymbol{R}\begin{pmatrix} \boldsymbol{P}&\boldsymbol{0}\\ \boldsymbol{0}&\boldsymbol{I}_{n-r} \end{pmatrix}=(\boldsymbol{\beta}_1,\dots,\boldsymbol{\beta}_r,\boldsymbol{\alpha}_{r+1},\dots,\boldsymbol{\alpha}_n). $$

Because $\boldsymbol{\alpha}_i$ and $\boldsymbol{\beta}_i$ ($i=1,\dots,n$) are in the same column space, whose basis can be $\boldsymbol{\beta}_1,\dots,\boldsymbol{\beta}_r$, there must exist an $r$-by-($n-r$) matrix $\boldsymbol{C}$ satisfying $$ (\boldsymbol{\beta}_1,\dots,\boldsymbol{\beta}_r)\boldsymbol{C}=(\boldsymbol{\beta}_{r+1}-\boldsymbol{\alpha}_{r+1},\dots,\boldsymbol{\beta}_{n}-\boldsymbol{\alpha}_n). $$

So we have $$ \begin{aligned} &\boldsymbol{R}\begin{pmatrix} \boldsymbol{P}&\boldsymbol{0}\\ \boldsymbol{0}&\boldsymbol{I}_{n-r} \end{pmatrix} \begin{pmatrix} \boldsymbol{I}_r&\boldsymbol{C}\\ \boldsymbol{0}&\boldsymbol{I}_{n-r} \end{pmatrix}\\ ={}&(\boldsymbol{\beta}_1,\dots,\boldsymbol{\beta}_r,\boldsymbol{\alpha}_{r+1},\dots,\boldsymbol{\alpha}_n) \begin{pmatrix} \boldsymbol{I}_r&\boldsymbol{C}\\ \boldsymbol{0}&\boldsymbol{I}_{n-r} \end{pmatrix}\\ ={}&(\boldsymbol{\beta}_1,\dots,\boldsymbol{\beta}_r,\boldsymbol{\beta}_{r+1},\dots,\boldsymbol{\beta}_n)=\boldsymbol{S}. \end{aligned} $$

i.e. $$ \boldsymbol{A}\boldsymbol{M}\begin{pmatrix} \boldsymbol{P}&\boldsymbol{0}\\ \boldsymbol{0}&\boldsymbol{I}_{n-r} \end{pmatrix} \begin{pmatrix} \boldsymbol{I}_r&\boldsymbol{C}\\ \boldsymbol{0}&\boldsymbol{I}_{n-r} \end{pmatrix}\boldsymbol{N}^{-1}=\boldsymbol{B}. $$

So, $\boldsymbol{M}\begin{pmatrix} \boldsymbol{P}&\boldsymbol{0}\\ \boldsymbol{0}&\boldsymbol{I}_{n-r} \end{pmatrix} \begin{pmatrix} \boldsymbol{I}_r&\boldsymbol{C}\\ \boldsymbol{0}&\boldsymbol{I}_{n-r} \end{pmatrix}\boldsymbol{N}^{-1}$ is the contructed invertible $\boldsymbol{Q}$ satisfying $\boldsymbol{A}\boldsymbol{Q}=\boldsymbol{B}$.

---

A small improvement (learn from this video)

In the first step of constructing the invertible matrix $\boldsymbol{Q}$ when $\operatorname{rank}(\boldsymbol{A})<n$, it's ok to just let the first $r$ columns of $\boldsymbol{A}$ and $\boldsymbol{B}$ linearly independent and leave the other columns alone, as mentioned above, but actually, we can perform a further combination of elementary column operations to also make the last $n-r$ columns be zeros. In other words, we have invertible matrices $\boldsymbol{M}$ and $\boldsymbol{N}$ such that $\boldsymbol{A}\boldsymbol{M}=\boldsymbol{R}=(\boldsymbol{\alpha}_1,\dots,\boldsymbol{\alpha}_r,\boldsymbol{0}_{m\times(n-r)})$, $\boldsymbol{B}\boldsymbol{N}=\boldsymbol{S}=(\boldsymbol{\beta}_1,\dots,\boldsymbol{\beta}_r,\boldsymbol{0}_{m\times(n-r)})$, and both $\boldsymbol{\alpha}_1,\dots,\boldsymbol{\alpha}_r$ and $\boldsymbol{\beta}_1,\dots,\boldsymbol{\beta}_r$ are bases of $\operatorname{col}\boldsymbol{A}$ which is the same as $\operatorname{col}\boldsymbol{B}$.

So at this time, we have $$ \boldsymbol{R}\begin{pmatrix} \boldsymbol{P}&\boldsymbol{0}\\ \boldsymbol{0}&\boldsymbol{I}_{n-r} \end{pmatrix}=(\boldsymbol{\beta}_1,\dots,\boldsymbol{\beta}_r,\boldsymbol{0}_{m\times(n-r)})=\boldsymbol{S}. $$

Then, $\boldsymbol{M}\begin{pmatrix} \boldsymbol{P}&\boldsymbol{0}\\ \boldsymbol{0}&\boldsymbol{I}_{n-r} \end{pmatrix}\boldsymbol{N}^{-1}$ is the contructed invertible $\boldsymbol{Q}$ satisfying $\boldsymbol{A}\boldsymbol{Q}=\boldsymbol{B}$, which looks simpler, as we don't need matrix $\boldsymbol{C}$ to participate.

Answer 2

Assume that 3. holds. Then, $A$ and $B$ have the same column space. Therefore, there exists a matrix $Q$ such that $AQ=B$. Moreover, we have that

$$Q=A^+B+(I-A^+A)Z$$

where $A^+$ is the Moore-Penrose pseudoinverse and $Z$ s an arbitrary matrix of approximate dimension. Assume for now that $Z=0$.

• If $B$ has nontrivial kernel, then $Q=A^+B$ is singular.
• If $B$ is square and invertible, then so is $A$ and we have that $Q=A^{-1}B$, which is obviously invertible. So, 2. does not hold in that case.
• If $B$ has a trivial kernel, then $Q$ is invertible since we have that $Bu\ne 0$ for all $u\in\mathbb{R}^n$, this implies that $AQu\ne0$, which implies that $Q$ must be nonsingular.

So, 3. implies 2. only when $A$ has a nontrivial kernel.

I am currently addressing the case where we can pick $Z$ to hopefully make $Q$ nonsingular and prove that 3. implies 1. even when $A$ has a non-trivial kernel, and will update the answer soon.