Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithms for quantifying intersections of subspaces

  1. Sep 24, 2006 #1

    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 [tex]V \cap W = (V^{\per} \cup W^{\per})^{\per}[/tex] (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 [tex]V \cap W[/tex] 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.
    Last edited: Sep 24, 2006
  2. jcsd
  3. Sep 24, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
    [itex]V \cap W[/itex] = {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:

    \begin{array}{c|c} A & -B \end{array}
    \right] \left[ \begin{array}{c} x \\\hline y \end{array}
    \right] = 0
    Last edited: Sep 24, 2006
  4. Sep 24, 2006 #3
    I see. That makes perfect sense, Hurkyl. Thank you so much.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Algorithms for quantifying intersections of subspaces
  1. Eigenvalue Algorithm (Replies: 0)

  2. Householder algorithm (Replies: 13)