3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ $A\mathbf x=B\mathbf y$ is a system of linear equations. So you know algorithmic ways to solve it. $\endgroup$ Commented Mar 9, 2018 at 21:49
  • $\begingroup$ You probably mean to say "nontrivial common elements", for the ranges, being subspaces of the codomain, always both contain the zero vector. $\endgroup$ Commented Mar 9, 2018 at 22:02

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ @John Hughes I corrected the degeneracy. $\endgroup$ Commented Mar 9, 2018 at 22:56
  • $\begingroup$ Much better, and taught me something too. My own first-guess "fix" (check to see that both the "A" part and the "B" part are nontrivial) was clearly wrong, :) $\endgroup$ Commented Mar 9, 2018 at 22:58

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.