4
$\begingroup$

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.

  • 0
    @rschwieb: I el$a$borated 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.2012-12-29

1 Answers 1

2

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

  • 0
    I *think* I understand you. I may be referencing this answer later if and when I do such an intersection analysis :)2012-12-29