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

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}), 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}).

• Any condition on $n$ and $m$?
– KBS
Commented Sep 20, 2022 at 15:11
• Is $[A,B]$ the commutator, $AB-BA$? If so, 3 only makees sense when $A$ and $B$ are square. Commented Sep 20, 2022 at 15:18
• @Aaron It is not the commutator, it is the matrix formed by the columns of $A$ and $B$.
– KBS
Commented Sep 20, 2022 at 15:19
• @Aaron Just a matrix formed by the columns of $A$ and $B$, like KBS said. Commented Sep 20, 2022 at 15:32
• @KBS no conditions on $n$ and $m$ Commented Sep 20, 2022 at 15:33

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}), 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}).

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. 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}), 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.

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.