How to find a basis for the intersection of two vector spaces in $\mathbb{R}^n$?

Question

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?

Answer 1

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)$

Answer 2

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) $.

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

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