Is there any more efficient way to find the basis of the intersection of two subspaces?

Question

Let $V = \mathbb R^6.$

Let $W_1$ be the subspace of $V$ spanned by $$\left ( 1,2,3,4,5,6 \right ) ,\space \left ( 3,4,6,7,9,10 \right ) ,\space \left ( 0,1,0,2,0,3 \right ),\space\left ( 1,-2,3,-4,5,-6 \right ). $$

Let $W_2$ be the subspace of $V$ spanned by $$\left ( 1,1,1,2,2,3 \right ) ,\space \left ( -2,0,-1,0,1,2 \right ) ,\space \left ( 1,0,1,0,2,0 \right ),\space\left ( 0,0,1,0,-2,-2 \right ).$$

Find the dimension of the subspace $W_1\cap W_2$ and find a basis for this subspace.

I know I could take $\forall x=\left ( a,b,c,d,e,f \right ) \in W_1\cap W_2$ $$x=\alpha _1\left ( 1,2,3,4,5,6 \right ) +\space \alpha _2\left ( 3,4,6,7,9,10 \right ) +\space \alpha _3\left ( 0,1,0,2,0,3 \right )+\space\alpha_4 \left ( 1,-2,3,-4,5,-6 \right ) $$

and

$$x=\beta_1 \left ( 1,1,1,2,2,3 \right ) +\space \beta _2\left ( -2,0,-1,0,1,2 \right ) +\space \beta_3\left ( 1,0,1,0,2,0 \right )+\space\beta _4\left ( 0,0,1,0,-2,-2 \right ).$$

Then

$$\begin{bmatrix} 1& 3& 0& 1& a\\ 2& 4& 1& -2& b\\ 3& 6& 0& 3& c\\ 4& 7& 2& -4& d\\ 5& 9& 0& 5& e\\ 6& 10& 3& -6&f\end{bmatrix} \text{and} \begin{bmatrix} 1& -2& 1& 0& a\\ 1& 0& 0& 0& b\\ 1& -1& 1& 1& c\\ 2& 0& 0& 0& d\\ 2& 1& 2& -2& e\\ 3& 2& 0& -2&f\end{bmatrix}.$$

Then takes so much (tedious) effort to get

$$\begin{bmatrix} 1& 3& 0& 1& a\\ 0& 0& 1& -4& b-\frac{2}{3}c \\ 0& 1& 0& 0& a-\frac{1}{3}c \\ 0& 0& 0& 0& a-2b-\frac{1}{3}c+d \\ 0& 0& 0& 0& a-2c+e\\ 0& 0& 0& 0&2a-3b-\frac{2}{3}c+f\end{bmatrix} \text{and} \begin{bmatrix} 1& -2& 1& 0& a\\ 0& 0& -1& -2& b+a-2c \\ 0& 1& 0& 1& c-a \\ 0& 0& 0& 0& d-2b \\ 0& 0& 0& 0& 4e-2a-6c-7f+21b\\ 0& 0& 0& 1&\frac{-1}{4}f-\frac{1}{2}a+\frac{1}{2}c+\frac{3}{4}b \end{bmatrix}.$$

So $\forall x=\left ( a,b,c,d,e,f \right ) \in W_1\cap W_2$, we have

\begin{align} a -2b-\frac{1}{3}c+d &=0 \\ a-2c+e &= 0 \\ 2a-3b-\frac{2}{3}c +f &=0 \\ 4e-2a-6c-7f+21b &=0 \\ d-2b &=0 \end{align}

Finally, we get $$x=\left ( e,f,3e,2f,5e,3f \right ) $$ so $$\left \{ \left (1,0,3,0,5,0 \right ) ,\space \left (0,1,0,2,0,3 \right ) \right \} $$ is a basis for $W_1\cap W_2$.

Is there any efficient way to accomplish this?

Answer 1

You can use the Zaassenhaus algorithm.

Note: it is very similar to what you did, just organized in a different presentation.

If $A$ and $B$ are the representive matrices for $W_1$ and $W_2$ where the vectors are disposed in ROWS (not in columns).

Then construct the following matrix $\begin{pmatrix}A & A\\B & 0\end{pmatrix}$ and reduce it to echelon form by only rows operations to $\begin{pmatrix}T_+ & *\\0 & T_\cap\end{pmatrix}$ (where $T_i$ are "upper triangular", I put quotes because in case of rectangular matrices it is a bit of a language abuse).

Then the rows of $T_+$ form a basis for $W_1+W_2$ and the rows of $T_\cap$ a basis for $W_1\cap W_2$.

Let see what we get in our case, the initial matrix :

$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 4 & 6 & 7 & 9 & 10 & 3 & 4 & 6 & 7 & 9 & 10 \\ 0 & 1 & 0 & 2 & 0 & 3 & 0 & 1 & 0 & 2 & 0 & 3 \\ 1 & -2 & 3 & -4 & 5 & -6 & 1 & -2 & 3 & -4 & 5 & -6 \\ 1 & 1 & 1 & 2 & 2 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ -2 & 0 & -1 & 0 & 1 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & -2 & -2 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$

We clear first column by performing $-3r_1,-r_1,-r_1,+2r_1,-r_1$ on the non zero entries ($r_1$ is the first row), then iterate on the second column and so on.

I jump to the result using an online tool (https://planetcalc.com/8328/) with the entry below (if you want to see the detailed steps)

1 2 3 4 5 6 1 2 3 4 5 6
3 4 6 7 9 10 3 4 6 7 9 10
0 1 0 2 0 3 0 1 0 2 0 3
1 -2 3 -4 5 -6 1 -2 3 -4 5 -6
1 1 1 2 2 3 0 0 0 0 0 0
-2 0 -1 0 1 2 0 0 0 0 0 0
1 0 1 0 2 0 0 0 0 0 0 0
0 0 1 0 -2 -2 0 0 0 0 0 0

The resulting matrix is this one :

$\begin{bmatrix} 1&0&0&0&0&-\frac27&|&0&0&0&0&0&0\\ 0&1&0&0&0&\frac57&|&0&0&-6&-2&-12&-4\\ 0&0&1&0&0&-\frac67&|&0&0&0&0&0&0\\ 0&0&0&1&0&\frac87&|&0&0&3&1&6&2\\ 0&0&0&0&1&\frac47&|&0&0&0&0&0&0\\\hline 0&0&0&0&0&0&|&1&0&3&0&5&0\\ 0&0&0&0&0&0&|&0&1&0&2&0&3\\ 0&0&0&0&0&0&|&0&0&0&0&0&0 \end{bmatrix}$

Where you can identify $(1,0,3,0,5,0)$ and $(0,1,0,2,0,3)$ as a basis of $W_1\cap W_2$.

Note: the online tool does use fractions, but manually you are not forced to. You can just do $3r_i-5r_j$ for instance when it's convenient. Also the upper part represented by $*$ is not needed you can just ignore these terms entirely in your calculation, resulting in massive speed up. Also doing this you will arrive to multiples like $(0,3,0,6,0,9)$ for instance, but you can always divide by the gcd to tidy up things.

Answer 2

A quick glance at the given vector spanning $W_1$ shows that $$(1,2,3,4,5,6)=4(0,1,0,2,0,3)+(1,-2,3,-4,5,-6),$$ and so the last vector is in the span of the former three. Applying a few reduction by eye to the remaining three: $$W_1=\langle(1,0,3,0,5,0),(0,1,0,2,0,3),(1,1,0,1,-1,1)\rangle.\tag{1}.$$ Next note that the last three vectors spanning $W_2$ all have their second and fourth coordinates equal to $0$. Looking at the first vector we see that $W_2$ is contained in the hyperplane $2x_2-x_4=0$. This plane also contains the first two vectors spanning $W_1$ in $(1)$ above, but not the third. It follows that $$W_1\cap W_2\subseteq\langle(1,0,3,0,5,0),(0,1,0,2,0,3)\rangle.\tag{2}$$ Because so many of the coordinates of the vectors spanning $W_2$ are $0$, it is easy to check that \begin{eqnarray*} (1,1,1,2,2,3)&-&(1,0,1,0,2,0)&&&=&(0,1,0,2,0,3),\\ (-2,0,-1,0,1,2)&+3&(1,0,1,0,2,0)&+&(0,0,1,0,-2,-2)&=&(1,0,3,0,5,0), \end{eqnarray*} which shows that we have equality in $(2)$.

Answer 3

My prefered systematic method for calculating an intersection of two subspaces is to have one defined by a basis and the other one defined by equations, and to minimize the number of spanning vectors and equations when choosing which of the two subspaces will play which role. Here, $$\alpha _1( 1,2,3,4,5,6) +\alpha _2( 3,4,6,7,9,10) +\alpha _3( 0,1,0,2,0,3)+\alpha_4 ( 1,-2,3,-4,5,-6)=\vec0$$ $$\iff\alpha_2=0,\alpha_3=-4\alpha_1,\alpha_4=-\alpha_1,$$ hence forgetting for instance the first of the four spanning vectors gives a basis of $W_1:$ $$u=( 3,4,6,7,9,10),\quad v=( 0,1,0,2,0,3),\quad w=( 1,-2,3,-4,5,-6).$$ Now, solving a system, we find that $$( a,b,c,d,e,f)\in W_2\iff d=2b\text{ and }-2a+21b-6c+4e-7f=0$$ and we readily derive: $$\alpha _2u+\alpha _3v+\alpha_4w\in W_2\iff\alpha_2=0.$$ Therefore, a basis of $W_1\cap W_2$ is $(v,w).$

Answer 4

Let $A$ be the $6 \times 4$ matrix of the spanning vectors of $W_1$ , and $ B $ be the $6 \times 4$ of the spanning vectors of $W_2$. The method I used is as follows:

1. Find a basis for the orthogonal complement of $W_1$, by solving $A^T x = 0 $. Let the vectors of this basis form the $6 \times m_1$ matrix $C$

2. Find a basis for the orthogonal complement of $W_2$ by solving $ B^T x = 0 $. Let the vectors of this basis form the $6 \times m_2$ matrix $D$.

The intersection of $W_1$ and $W_2$ is orthogonal to both bases $C$ and $D$, hence, to find a basis for the intersection, solve

$ \begin{bmatrix} C^T \\ D^T \end{bmatrix} x = 0 $