# Algorithm to find the basis of intersection of subspaces without gaussian elimination.

Is there an algorithm to find the basis of intersection of subspaces $A_1$ and $A_2$, if we have the bases of subspaces $A_1$ and $A_2$, without using Gaussian elimination?

Thanks.

-
How are these subspaces described? With an equation? Or something else? – Muphrid Dec 28 '12 at 20:22
You could use Gram–Schmidt... – copper.hat Dec 28 '12 at 20:25
@copper.hat Gram-Schmidt, which orthonormalizes a basis? Or is there another alg with that name? If not, it's hard to see how that applies :( I probably missed something... – rschwieb Dec 28 '12 at 20:33
Why would you want to? – Alexander Gruber Dec 28 '12 at 21:14
@rschwieb: I elaborated my comment below. I am guessing that if Gaussian elimination is eliminated (:-)) then using Gram Schmidt is probably disallowed as well. However, Gram Schmidt is a useful, fairly stable tool to have in the arsenal. – copper.hat Dec 29 '12 at 3:54

Suppose there are two subspaces $S_1, S_2$ that are represented as the kernels of two matrices, ie $S_k = \ker A_k$. Form the matrix $A = \begin{bmatrix} A_1 \\ A_2 \end{bmatrix}$, and note that $x \in S_1 \cap S_2$ iff $x \in \ker A$. Then apply the Gram Schmidt process to the columns of $A^T$ to produce an orthonormal set of columns $\tilde{A}^T$. Then $\ker \tilde{A} = \ker A$, ie, $S_1 \cap S_2 = \ker \tilde{A}$.

We can use Gram Schmidt to convert a subspace representation between the range space representation and kernel representation:

If a subspace is represented as $S = {\cal R}(B)$, it can be represented as a kernel by applying Gram Schmidt to $\begin{bmatrix} B & I \end{bmatrix}$ to get $\begin{bmatrix} \tilde{B} & \tilde{C} \end{bmatrix}$ (some columns of $\tilde{B},\tilde{C}$ may be zero). Then ${\cal R}(B) = {\cal R}(\tilde{B})$, and ${\cal R}(\tilde{C}) ={\cal R}(\tilde{B})^\bot = {\cal R}(B)^\bot$. Since ${\cal R}(B) = {\cal R}(\tilde{C})^\bot = \ker \tilde{C}^T$, we have $S = \ker \tilde{C}^T$.

If a subspace is represented as $S = \ker A$, it can be represented as a range space by applying Gram Schmidt to $\begin{bmatrix} A^T & I \end{bmatrix}$ to get $\begin{bmatrix} \tilde{A}^T & \tilde{D}^T \end{bmatrix}$ (some columns of $\tilde{A}^T,\tilde{D}^T$ may be zero). As above, ${\cal R}(A^T) = {\cal R}(\tilde{A}^T)$, and ${\cal R}(\tilde{D}^T) ={\cal R}(\tilde{A}^T)^\bot = {\cal R}(A^T)^\bot = \ker A$. Hence $S = {\cal R}(\tilde{D}^T)$.

An alternative approach if the subspaces are represented as range spaces:

Suppose $S_k = {\cal R}(B_k)$. Note that $z \in S_1 \cap S_2$ iff there exists $x,y$ such that $z = B_1 x = B_2 y$. In other words, if we let $A = \begin{bmatrix} B_1 & -B_2 \end{bmatrix}$, then $S_1 \cap S_2 = \{B_1 x | \binom{x}{y} \in \ker A \}$. As above, we can use Gram Schmidt to obtain $\tilde{D}^T$ such that $\ker A = {\cal R} (\tilde{D}^T)$. If we let $\Pi_x$ be the matrix that returns 'x', ie. $\Pi_x \binom{x}{y} = x$, then $S_1 \cap S_2 = {\cal R} ( B_1 \Pi_x \tilde{D}^T)$. Then one can use Gram Schmidt to obtain the linearly independent columns of $B_1 \Pi_x \tilde{D}^T$.

-
I thought the OP asked for the intersection of spaces. I know he used the term subspaces. Does subspaces mean kernel in general? I was thinking the intersection of range (rowspace or columnspace, wasn't quite clear which he wanted). Your answer is good for the intersection of kernels though. – adam W Dec 29 '12 at 4:03
@adamW: You are correct. Subspaces are frequently represented as either kernels or range spaces. If they are represented as kernels, then obtaining the intersection is almost trivial (as above). If they are represented as range spaces, then the representation can be converted to a kernel representation using Gram Schmidt (as above). The answer can be converted back again using Gram Schmidt (also as above). (The OP didn't say how the subspaces were represented.) – copper.hat Dec 29 '12 at 4:07
@adamW: I added a second approach; but at some level the approaches are basically the same. – copper.hat Dec 29 '12 at 4:25
I think I understand you. I may be referencing this answer later if and when I do such an intersection analysis :) – adam W Dec 29 '12 at 4:35