Welcome to MathOverflow

Question

4

1

If you have two linear subspaces $V_1$ and $V_2$ of a vector space $V,$ both given by their bases, there is fairly heavy handed way of computing their intersection: write down the projection matrices onto both subspaces, then multiply them, then compute the column span by row reduction. This is $O(n^3),$ where $n$ is the dimension of $V,$ even if $V_1$ and $V_2$ are (e.g.) two dimensional, but has the advantage of being very easy to code.

Is there a faster elegant method?

EDIT

To address @Will's comment (by correcting the muddled statement above): There is a famous (in some circles) Anderson-Duffin formula for the orthogonal projector onto the intersection of $V_1$ and $V_2,$ thus:

$P(V_1\cap V_2) = 2 P(V_1) (P(V_1) + P(V_2))^t P(V_2).$

Notice that if $V_1$ is given by a matrix $A$ of column vectors, the orthogonal projector onto $V_1$ is given by $P(V_1) = A (A^t A)^{-1} A^t,$ so is fairly heavy-weight to compute.

edited Sep 26 at 16:33

asked Sep 26 at 15:59

Igor Rivin
31.2k●3●37●71

6

1. How fast is it to view the bases as the columns of two tall thin matrices, concatenate them horizontally, take the kernel, then look at the image of that subspace under the left matrix only? 2. As far as I can tell your method fails when $V_1$ and $V_2$ are disjoint but not orthogonal. – Will Sawin Sep 26 at 16:06

Here is what I see as a more elegant method: Column(-echelon?) reduce the base matrices for the subspaces. Use these matrices to write the subspaces as kernels of a family of independent linear functionals (one for each non-principal row in the column reduction). Combine these matrices and row reduce. Deduce the kernel of the combined matrix, which is of course the intersection of the two subspaces. I haven't thought about the time... – Anthony Quas Sep 26 at 23:07

1

Put one basis on top of the other and compute the nullspace by row reduction. This writes the intersection in both bases. – John Wiltshire-Gordon Sep 27 at 2:19

All these are good ideas, thanks (I had something along these lines implemented)! I guess elegance is in the eye of the beholder -- treating subspaces as projections seems to have a certain appeal... – Igor Rivin Sep 27 at 13:22

Intersection of subspaces

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.