The basis for intersection of two subspaces

Question

I know there are other posts on how to do this, but I was wondering if there is a slicker method.

$X = Span\{(1,1,0,-1),(1,2,3,0),(2,3,3,-1)\}$ $Y = Span\{(1,2,2,-2),(2,3,2,-3),(1,3,4,-3)\}$

I want to find a basis for $X \cap Y$

The method I have been trying to use is by letting $v \in X$ and $v \in Y$ and attempting to solve the equation $v - v = 0$. However it seems very long and tedious. I was thinking there may be a better method.

Answer 1

Well, for this particular problem, there are some shortcuts that make life a bit easier. Let $X = \operatorname{span} \left\{v_1,v_2,v_3 \right\}$ and $Y = \operatorname{span} \left\{w_1,w_2,w_3 \right\}$, where $v_1=(1,1,0,-1)$, $v_2=(1,2,3,0)$ etc.

You could firstly note that $$(1,1,0,-1)+(1,2,3,0)=(2,3,3,-1) \implies v_3 \in \operatorname{span}\left\{v_1, v_2\right\},$$ and $$3(1,2,2,-2)-(2,3,2,-3)= (1,3,4,-3) \implies w_3 \in \operatorname{span} \left\{w_1, w_2 \right\},$$ and so your problem reduces to finding a basis for $X \cap Y$, where $X = \operatorname{span} \left\{v_1,v_2 \right\}$ and $Y = \operatorname{span} \left\{w_1,w_2 \right\}$.

Now, taking a similar approach with the resulting sets $X$ and $Y$, we could note that $$(2,3,2,-3) - (1,2,2,-2)=(1,1,0,-1) \implies v_1 \in \operatorname{span} \left\{w_1, w_2 \right\},$$ and so on.

Answer 2

This is a perfect situation where changing the point of view can provide some good insight. You are trying to find the intersection of two vectors subspaces of $\mathbb{R}^4$ and you are given those spaces as the spans of sets of vectors. In other words you are given X and Y as the column spaces of matrix $V=[v_i]$ an $W=[w_i]$ (where the columns are the vectors you gave above). At first glance it's not clear how to find the intersection. Indeed, what do we do? Write a matrix / take echelon form? But there are two matrices... Hmm... However...

In general - there are straightforward efficient ways to find the null space or column space of a matrix. In this case, thinking about null spaces turns out to help a lot!

Indeed, suppose instead we were give these (same) spaces not as the column space of matrices, but instead as the null space of a matrix, say $X = \mathrm{Nul }A$ and $Y = \mathrm{Nul }B$, then it would be easy to find the intersection of $X$ and $Y$. Indeed, we can think of $X$ as solutions to $Ax=0$ and $Y$ as solutions to $Bx=0$, and so to find $X\cap Y$ we just need to combine all of these linear equations into one big system, namely the matrix with $A$ and $B$ stacked on top of each other. Then if we solve: $$\begin{bmatrix}A \\ B \end{bmatrix} x = 0$$ then the set of solutions will be $X\cap Y$ so we just need to row-reduce this bigger matrix and then we can read off the null space from that.

Ok, I know what you're thinking - how do we find the matrices $A$ and $B$. Well this is where some more linear algebra magic can come to the rescue. So the question is: Given that $X = Col(V)$ how can you find an $A$ so that $X = Nul(V)$. Well here's a sneaky trick, the answer is ``Find a basis for the null space of $V^T$ (a null space calculation) and then write these basis vectors as columns of a matrix, call it $P$. Then by construction we have that $V^TP = 0$. Now if we take the transpose we get $P^TV = 0$, which means that the columns of $V$ (i.e. our original vectors in your problem) are in the null space of $P^T$. So $P^T$ is the matrix that you want.''

I don't know how much linear algebra you've seen, and this is surely not the fastest way to do this, but you sound like you'd be interested in learning a bit more and I'd be happy to fill in more details.

In pseudocode if you want to flip this from a "span" problem to a "null space" problem the ideas you want are:

X = col(V); Y = col(W);

A = transpose ( null transpose( V ) );

B = transpose ( null transpose( W ) );

Then $X\cap Y$ = null space of $\begin{bmatrix} A\\ B\end{bmatrix}$