How to tell whether the ranges of two matrices intersect

Question

Assume that we have two matrices over the complex field i.e. $A\in\mathbb{C}^{m\times n_1}$ and $B\in\mathbb{C}^{m\times n_2}$.

Let their range spaces be the sets $$R(A)=\{A\mathbf{x}|\mathbf{x}\in\mathbb{C}^{n_1}\}$$ and $$R(B)=\{B\mathbf{x}|\mathbf{x}\in\mathbb{C}^{n_2}\}$$ respectively.

I want to know if there is a systematic way to tell whether the range spaces have common elements. I am trying to check this in Matlab thus I am trying to find an algorithm.

In other words if the columns are s.t. $A=\begin{bmatrix}\mathbf{a}_1&\dots&\mathbf{a}_{n_1}\end{bmatrix}$ and $B=\begin{bmatrix}\mathbf{b}_1&\dots&\mathbf{b}_{n_2}\end{bmatrix}$ how to tell if the following is true $$\sum_{i=1}^{n_1}x_i\mathbf{a}_i=\sum_{i=1}^{n_2}y_i\mathbf{b}_i\Leftrightarrow x_i=y_i=0 \text{ for all }i$$

The matrices are fixed, so I am not looking for a way to construct them.

Answer 1

Take the matrix $C\colon=[A|B] \in \mathbb{C}^{m\times (n_1+n_2)}$. Then the dimension of the intersection of the ranges of $A$ and $B$ equals $$\operatorname{rank}(A)+\operatorname{rank}(B)-\operatorname{rank}(C)$$ You can determine the rank of a matrix in MATLAB.

Answer 2

$\DeclareMathOperator{\range}{range}$ $\DeclareMathOperator{\kernel}{kernel}$ You want to find $Ax = By \ne 0$ in $\range(A) \cap \range(B)$, if possible. To eliminate the possibility $Ax = B y = 0$ with $x \ne 0$ or $y \ne 0$, replace $A$ with a matrix $A'$ whose columns form a basis of the column space of $A$ (i.e of the range of $A$) and similarly replace $B$ with a matrix $B'$ whose columns form a basis of the column space of $B$. Do this algorithmically by column reduction.

Now $A'x = B'y \ne 0$ is a non-zero element of $\range(A) \cap \range(B)$ iff $A'x = B'y$ with $\begin{bmatrix} x\\y\end{bmatrix} \ne 0$ iff $\begin{bmatrix} x\\-y\end{bmatrix} $ is a non-zero element of $\kernel \left[A' \vert B'\right]$, where $ \left[A' \vert B'\right]$ is the matrix built by adjoining the columns of $A'$ and those of $B'$.