Skip to main content
2 of 3
clarification
Igor Rivin
  • 96.4k
  • 11
  • 153
  • 366

Intersection of subspaces

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

Igor Rivin
  • 96.4k
  • 11
  • 153
  • 366