1
$\begingroup$

Assuming we have 2 subspaces, $\mathbb W$ and $\mathbb U$ of $\mathbb V$.

How can I get their intersection?

$\endgroup$
3
  • $\begingroup$ What do you mean by "get their intersection"? $\endgroup$
    – Orat
    Feb 28 '13 at 9:46
  • 4
    $\begingroup$ Like this. $\mathbb{W} \cap \mathbb{U}$ $\endgroup$
    – AJY
    Jun 10 '15 at 23:56
  • 2
    $\begingroup$ You should check out the Zassenhaus algorithm: en.wikipedia.org/wiki/Zassenhaus_algorithm $\endgroup$
    – Calle
    Jun 22 '17 at 16:28
10
$\begingroup$

Suppose that $\mathbb{W}=\operatorname{span}(w_1,w_2,\ldots,w_m)$ and $\mathbb{U}=\operatorname{span}(u_1,u_2,\ldots,u_n)$ where each of these is a minimum basis for the respective sets. If a vector $a$ is in the intersection of $\mathbb{W}$ and $\mathbb{U}$, it must be able to be expressed as a linear combination of the spanning set of $\mathbb{W}$ and $\mathbb{U}$. i.e. $$ a=c_1w_1+c_2w_2+\ldots+c_kw_m \text{ and } a=d_1u_1+d_2u_2+\ldots+d_ku_n $$ for some $c_i$ and $d_i$ to be determined. Since $a$ is arbitrary, you must have $$ c_1w_1+c_2w_2+\ldots+c_kw_m=d_1u_1+d_2u_2+\ldots+d_ku_n $$ which is equivalent to $$ c_1w_1+c_2w_2+\ldots+c_kw_m+e_1u_1+e_2u_2+\ldots+e_ku_n=0 $$ where $e_k=-d_k$. Since $a$ was an arbitrary element of $\mathbb{W}$ and $\mathbb{U}$, this system of linear equations must have a solution. Thus, the intersection of $\mathbb{W}$ and $\mathbb{U}$ is the nullspace of the matrix $$ [w_1,w_2,\ldots,w_m,u_1,\ldots,u_n]. $$

$\endgroup$
1
  • 2
    $\begingroup$ I believe there is something wrong: an element in that nullspace is a vector in $\mathbb R^{m+n}$ so it cannot equal $\mathbb W \cap \mathbb U$ in general. However, the first part of these vectors do correspond to the vectors in the intersection, expressed in base $\mathbb W$-coordinates. $\endgroup$
    – Jolien
    Jan 18 '17 at 14:20
6
$\begingroup$

Andreas Cartani's solution only works when the subspace is given as the solution of a linear equation system.

Daryl's solution is incomplete. Let $\operatorname{span}(x_1,\dots,x_l)$ be the nullspace of the last matrix, let $y_1, \dots, y_l$ be the first $m$ components of each vector $x_1, \dots, x_l$, i. e. $x_i \in \mathbb R^{m+n}$ but $y_i \in \mathbb R^m$. Let $z_i = U y_i$ where $U = (u_1, \dots, u_m)$ is the matrix with columns $u_1$ to $u_m$, then $\operatorname{span}(z_1, \dots, z_l) = \mathbb U \cap \mathbb W$. (The $x_i$ are only the $c_j$ and $e_j$ but the quantities of interests are the $a$'s which correstpond to the $z_i$.)

Alternatively, let $\mathbb U = \operatorname{span}(u_1, \dots, u_n)$ and $\mathbb W = \operatorname{span}(w_1, \dots, w_m)$. Let $U = (u_1, \dots, u_n)$ be the matrix with columns $u_1$ to $u_n$ and $W = (w_1, \dots, w_m)$ be the matrix with columns $w_1$ to $w_m$. Solve the equation system $U^T x = 0$ for $x$ and let $\mathbb X = \operatorname{span}(x_1, \dots, x_k)$ be its solution. Solve analogously $W^T y = 0$ for $y$ and let $\mathbb Y = \operatorname{span}(y_1, \dots, y_l)$ its solution. Let $Z = (x_1, \dots, x_k, y_1, \dots, y_l)$ be the matrix consisting of the columns $x_1$ to $x_k$ and $y_1$ to $y_l$. The solution of the equation system $Z^T z = 0$ in $z$ is the subspace $\mathbb Z$ in question for which $\mathbb Z = \mathbb U \cap \mathbb W$.

The reason for the last solution to work ist that it holds in general $\ker(A^T) = \operatorname{ran}(A)^\perp$ and $(\mathbb A \cap \mathbb B)^\perp = \mathbb A^\perp + \mathbb B^\perp$ for matrices $A$ and subspaces $\mathbb A$ and $\mathbb B$ (as well as ${(\mathbb A^\perp)}^\perp = \mathbb A$). Here we have $\mathbb U = \operatorname{ran}(U)$, $\mathbb W = \operatorname{ran}(W)$, $\mathbb X = \ker(U^T)$, $\mathbb Y = \ker(W^T)$ and $\mathbb Z = \ker(Z^T)$. $\operatorname{ran}(Z) = \mathbb X + \mathbb Y$ completes the puzzle.

Daryl's solution is to prefer when the two subspaces have low dimension (compared to their orthogonal complement). The other solution is to prefer for high dimensional subspaces (compared to their orthogonal complement).

$\endgroup$
4
$\begingroup$

If your subspaces are defined by two systems of homogeneous linear equation, just combine them in a single system, and the set of solutions will be the intersection.

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