61
$\begingroup$

What is the general way of finding the basis for intersection of two vector spaces in $\mathbb{R}^n$?

Suppose I'm given the bases of two vector spaces U and W: $$ \mathrm{Base}(U)= \left\{ \left(1,1,0,-1\right), \left(0,1,3,1\right) \right\} $$ $$ \mathrm{Base}(W) =\left\{ \left(0,-1,-2,1\right), \left(1,2,2,-2\right) \right\} $$

I already calculated $U+W$, and the dimension is $3$ meaning the dimension of $ U \cap W $ is $1$.

The answer is supposedly obvious, one vector is the basis of $ U \cap W $ but how do I calculate it?

$\endgroup$
3
  • $\begingroup$ The procedure can be described as: (i) put down a list of the basis vectors of $U$ and $W$ (ii) Perform base changes on both list until a common vector appears. Keep that one. Repeat for the other vectors, until no common vectors can be found anymore. $\endgroup$
    – shuhalo
    Mar 7, 2011 at 0:16
  • 3
    $\begingroup$ A = (Base(U) | Base(W)) as columns. The answer is the nullspace of A? $\endgroup$
    – AnnanFay
    Jun 25, 2012 at 10:34
  • $\begingroup$ @Annan I think what it ends up meaning is that the basis for the intersection will be basis vectors for example from U which are linear combinations of basis vectors from W, or the other way around. Another way of thinking about it is that you're looking for vectors which are in the column space / span of both sets which I think can only happen when some basis vector of one set is in the column space of the other set. $\endgroup$ Nov 5, 2012 at 7:28

7 Answers 7

45
$\begingroup$

Assume $\textbf{v} \in U \cap W$. Then $\textbf{v} = a(1,1,0,-1)+b(0,1,3,1)$ and $\textbf{v} = x(0,-1,-2,1)+y(1,2,2,-2)$.

Since $\textbf{v}-\textbf{v}=0$, then $a(1,1,0,-1)+b(0,1,3,1)-x(0,-1,-2,1)-y(1,2,2,-2)=0$. If we solve for $a, b, x$ and $y$, we obtain the solution as $x=1$, $y=1$, $a=1$, $b=0$.

so $\textbf{v}=(1,1,0,-1)$

You can validate the result by simply adding $(0,-1,-2,1)$ and $(1,2,2,-2)$

$\endgroup$
3
  • 22
    $\begingroup$ What would you do if U had dimension 3? So you would have 3+2=5 variables and 4 equations. $\endgroup$ Jan 7, 2012 at 14:15
  • 2
    $\begingroup$ @MartinThoma 10 years later, I too, am curious $\endgroup$ Oct 27, 2022 at 19:12
  • 2
    $\begingroup$ Now I feel old 😄 $\endgroup$ Oct 28, 2022 at 8:28
22
$\begingroup$

The comment of Annan with slight correction is one possibility of finding basis for the intersection space $ U \cap W $, the steps are as follow:

1) Construct the matrix $ A=\begin{pmatrix}\mathrm{Base}(U) & | & -\mathrm{Base}(W)\end{pmatrix} $ and find the basis vectors $ \textbf{s}_i=\begin{pmatrix}\textbf{u}_i \\ \textbf{v}_i\end{pmatrix} $ of its nullspace.

2) For each basis vector $ \textbf{s}_i $ construct the vector $ \textbf{w}_i=\mathrm{Base}(U)\textbf{u}_i=\mathrm{Base}(W)\textbf{v}_i $.

3) The set $ \{ \textbf{w}_1,\ \textbf{w}_2,...,\ \textbf{w}_r \} $ constitute the basis for the intersection space $ span(\textbf{w}_1,\ \textbf{w}_2,...,\ \textbf{w}_r) $.

$\endgroup$
4
  • $\begingroup$ could you please be more specific about $s_i$? suppose my $U$ is $4\times 2$ and $W$ is also $4\times 2$ so $A=[U,W]$ is $4\times 4$ in Matlab I give command $null(A)$ and I get a matrix of order $4\times 1$ now what is my $u_i$ and $v_i$?U=\begin{pmatrix}1& 0\\0 &2\\-1& -1\\0& 1\end{pmatrix} W=\begin{pmatrix}1& 0\\0 &1\\1& -1\\0 &2\end{pmatrix}, null([U,W])=\begin{pmatrix} 0.70711 \\ 0.00000\\ -0.70711\\ \\0.00000\end{pmatrix}$ $\endgroup$
    – Myshkin
    Jun 21, 2017 at 11:12
  • 1
    $\begingroup$ @Urgent You are on the right way. Just be careful, it should be null([U,-W]) (not null([U,W]))! $\endgroup$
    – Pekov
    Jun 21, 2017 at 23:06
  • $\begingroup$ How do you know that $\vec{w}$ produced this way are linearly independent so that we have a basis? $\endgroup$
    – helios321
    May 15, 2018 at 3:16
  • $\begingroup$ @helios321 This is so because the basis vectors $\textbf{u}_i$ are linearly independent as those are part of basis themselves. You can check this one directly form the definition, just do $c_i \textbf{w}_i=\textbf{0}$ and show it is only possible when all $c_i$'s are zero. $\endgroup$
    – Pekov
    May 16, 2018 at 4:47
13
$\begingroup$

Let $\mathcal U$ and $\mathcal V$ be two finite-dimensional vector spaces. We want to find a basis for the intersection $\mathcal U\cap\mathcal V$.

Let $U$ and $V$ be matrices whose columns are the basis vectors of $\mathcal U$ and $\mathcal V$, respectively. The problem is then equivalent to that of characterising $\operatorname{Range}(U)\cap \operatorname{Range}(V)$. In other words, we are looking for non-zero $x,y$ such that $$Ux=Vy.\tag A$$ In fact, $z\in\operatorname{Range}(U)\cap \operatorname{Range}(V)$ iff there are $x,y$ such that $z=Ux=Vy$.

Solving (A) amounts to finding the nullspace of $A\equiv(U|-V)$, the matrix placing $U$ and $-V$ one next to the other. This is because $AX=0$ with $X\equiv\begin{pmatrix}x\\y\end{pmatrix}$ implies $Ux=Vy$.

Once we have a basis for the nullspace of $A$, in the form of a set of vectors $\{X_i\}$ (with each $X_i$ corresponding to a pair $x_i,y_i$), we obtain the corresponding set of vectors in the intersection computing $w_i\equiv Ux_i=Vy_i$ for each $i$.

To prove that $\{w_i\}_i$ is linearly independent. Suppose $\sum_i c_i w_i=0$. Then $U(\sum_i c_i x_i)=0$ and $V(\sum_i c_i y_i)=0$. But because $\operatorname{Ker}(U)=\operatorname{Ker}(V)=\{0\}$, this means that $\sum_i c_i x_i=\sum_i c_i y_i=0$. But this is, in turn, equivalent to $\sum_i c_i X_i=0$, and because $\{X_i\}$ is a linearly independent set, this implies $c_i=0$.

We conclude that $\{w_i\}$, where $w_i\equiv U x_i=V y_i$ and $\{(x_i, y_i)\}_i$ is a basis for $\operatorname{Ker}[(U|-V)]$, is a basis for $\mathcal U \cap\mathcal V$.

$\endgroup$
1
  • $\begingroup$ ${X_i}$ doesn't necessarily need to be orthonormal, am I right? $\endgroup$
    – Jay Lee
    Jun 28, 2021 at 13:35
6
$\begingroup$

Parameterize both vector spaces (using different variables!) and set them equal to each other. Then you will get a system of 4 equations and 4 unknowns, which you can solve. Your solutions will be in both vector spaces.

$\endgroup$
4
$\begingroup$

It is a one dimensional vector space, so find any non-zero vector which is in both spaces and it will be a basis.

$\endgroup$
1
  • 2
    $\begingroup$ any nonzero vector that is in both... $\endgroup$ Mar 6, 2011 at 22:45
2
$\begingroup$

Let me try to describe another interpretation of common techniques to compute intersections of two vector subspaces.

Fix a base field $k$.

First, there is a well known method to compute the kernel and the cokernel of a linear map. To be more precise, let $E,F$ be two vector spaces and let $T\colon E\to F$ be a linear map. The recipe is to consider the matrix $\begin{pmatrix}T\\I\end{pmatrix}$ and perform elementary column operations to a matrix like $\begin{pmatrix}J&0&0\\J'&K&0\end{pmatrix}$ where $J$ has the same number of rows as $T$ and $J,K$ are of full column rank. Then the column vectors of $K$ freely generate $\ker T$ and the column vectors of $J$ freely generate $\operatorname{Im}T$.

Now return to the question of computing the intersection. Let $V=k^n$ be a vector space and $E,F\subseteq V$ be two vector subspaces. Consider the map $T\colon E\oplus F\to V, x\oplus y\mapsto x+y$. Note that $\ker T\cong E\cap F$ (realized by the linear map $E\cap F\to\ker T,x\mapsto x\oplus(-x)$) and $\operatorname{Im}T=E+F$. Then we can apply the preceding recipe to compute $E\cap F$ and $E+F$ in the same time.

Explicitly, we start with taking bases $B_E$ and $B_F$ of $E$ and $F$ respectively. Let $B=\begin{pmatrix}B_E&B_F\end{pmatrix}$, and we form the matrix $\begin{pmatrix}B\\I\end{pmatrix}$. As before, we perform elementary column operations to get a matrix like $\begin{pmatrix}J&0&0\\J'&K&0\end{pmatrix}$ where $J,K$ are of full column rank. Then the columns of $J$ freely generate $E+F$ in $V$ and the columns of $K$ freely generate the image of the injective linear map $E\cap F\to E\oplus F,x\mapsto x\oplus(-x)$. To recover a base of $E\cap F$, it suffices to take the preimages, that is, take the first $\dim E$ coordinates and perform a linear combination with the chosen base $B_E$ of $E$. This is more-or-less same as other answers but interpreted in a slightly different way.

$\endgroup$
1
$\begingroup$

You can use Zassenhaus Sum-Intersection algorithm. See here: https://en.wikipedia.org/wiki/Zassenhaus_algorithm or here: https://kito.wordpress.ncsu.edu/files/2021/03/ma405-l.pdf

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .