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.
 A: 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$.
