4
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Commented Sep 26, 2012 at 16:06
  • $\begingroup$ 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... $\endgroup$
    – Anthony Quas
    Commented Sep 26, 2012 at 23:07
  • 1
    $\begingroup$ Put one basis on top of the other and compute the nullspace by row reduction. This writes the intersection in both bases. $\endgroup$
    – John Wiltshire-Gordon
    Commented Sep 27, 2012 at 2:19
  • $\begingroup$ 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... $\endgroup$
    – Igor Rivin
    Commented Sep 27, 2012 at 13:22
  • 2
    $\begingroup$ Note that the $^t$ in the Anderson-Duffin formula is not a transpose, but the Moore-Penrose pseudoinverse, usually denoted by $^+$. $\endgroup$
    – Mateus Araújo
    Commented May 28, 2015 at 20:06

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .