45
$\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$
  • $\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 '11 at 0:16
  • 2
    $\begingroup$ A = (Base(U) | Base(W)) as columns. The answer is the nullspace of A? $\endgroup$ – AnnanFay Jun 25 '12 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$ – Robert S. Barnes Nov 5 '12 at 7:28
34
$\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)$

| cite | improve this answer | |
$\endgroup$
  • 14
    $\begingroup$ What would you do if U had dimension 3? So you would have 3+2=5 variables and 4 equations. $\endgroup$ – Martin Thoma Jan 7 '12 at 14:15
13
$\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) $.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Marso Jun 21 '17 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 '17 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 '18 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 '18 at 4:47
5
$\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.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ any nonzero vector that is in both... $\endgroup$ – Arturo Magidin Mar 6 '11 at 22:45
3
$\begingroup$

I will use the same ideas as this other answer, but will add some more detail on some of the steps.

Let $\mathcal U$ and $\mathcal V$ be two finite-dimensional vector spaces. I 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, the problem is that of finding the non-zero solutions for $x,y$ to the matrix equation $$Ux=Vy.\tag A$$ Indeed, $z\in\operatorname{Range}(U)\cap \operatorname{Range}(V)$ iff there are $x,y$ such that $z=Ux=Vy$, and $z\neq0$ implies $x\neq0$ and $y\neq0$. Moreover, if $Ux=Vy$ and $x,y\neq0$, then we must have $Ux,Vy\neq0$ (we are using that the way $U,V$ are defined implies that $Ux=0\Longrightarrow x=0$, and similarly for $V$).

Now, to solve (A) we can define $A\equiv(U|-V)$ (this is the matrix with columns the full set of the vectors in both the bases of $\mathcal U$ and $\mathcal V$), and find its nullspace. Indeed, $AX=0$ where $X\equiv\begin{pmatrix}x\\y\end{pmatrix}$ implies $Ux=Vy$.

Once we have a full basis set for the nullspace of $A$, in the form of an orthonormal set of vectors $\{X_i\}$ (with each $X_i$ corresponding to a pair $x_i,y_i$), we can compute the corresponding set of vectors in the intersection that we are looking for, by simply computing $w_i\equiv Ux_i=Vy_i$ for each $i$.

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

| cite | improve this answer | |
$\endgroup$
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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.