Algorithms for quantifying intersections of subspaces

[v0id]

Greetings,

I'd like to know how one goes about finding a basis for the intersection of two subspaces V and W of a given vector space U. I am aware of the identity $$V \cap W = (V^{\per} \cup W^{\per})^{\per}$$ (essentially the orthogonal space of the union of orthogonal spaces of V and W), but this isn't computationally efficient. Furthermore it requires an inner product to be defined on U. Are there any other methods of computing a basis for $$V \cap W$$ if given bases for both V and W (methods that may not require conditions such as the one mentioned above)?

EDIT: My perpendicular symbols didn't show.

 

[Hurkyl]

There are two good ways of representing a subspace

(1) As the image of a linear transformation
(2) As the kernel of a linear transformation

(Note that a basis is just (1) in disguise; put your basis vectors in as the columns of a matrix)

Either way, you just work through the algebra. If you used (1) for both of your subspaces, then (if V is m dimensional, and W is n dimensional)

V = {Ax | x in R^m}
W = {By | y in R^n}

Then, you're looking for the set
$V \cap W$ = {z : there exists x and y such that Ax = By = z}
= {Ax : x in R^m and there exists y such that Ax = By}



Oh, just in case it's not clear, Ax = By if and only if:

$$\left[<br /> \begin{array}{c|c} A & -B \end{array}<br /> \right] \left[ \begin{array}{c} x \\\hline y \end{array}<br /> \right] = 0$$

 

[v0id]

I see. That makes perfect sense, Hurkyl. Thank you so much.