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:

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

 

[v0id]

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