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

Dimension of an intersection between a random subspace and a fixed subspace

  1. Mar 15, 2012 #1
    I've been struggling with this problem for about two weeks. My supervisor is also stumped - though the problem is easy to state, I don't know the proper approach to tackle it. I'd appreciate any hints or advice.

    Let V be an random k-dimensional vector subspace of ℝn, chosen uniformly over all possible k-dimensional subspaces. Let X[itex]\in[/itex]ℝn[itex]\times[/itex]n be a symmetric matrix whose column space is contained in V. Now I add constraints to X: given some pairs (i,j) such that [itex]1\leq i < j\leq n[/itex], I need Xij=0. The pairs are fixed and independent of V. How many of these zero constraints can I satisfy before (with high probability) the only solution is X=0?

    I've found a sufficient condition for a non-zero solution to exist: the number of constraints q must satisfy q< k(k+1)/2. From simulations, I think it is also a necessary condition (with probability one), but I can't seem to show it. I'd appreciate any ideas on how I might proceed.

  2. jcsd
  3. Apr 7, 2012 #2
    I'm still struggling with this. It seems to be related to Grassmannian manifolds, which provide a distribution over all possible random subspaces. However I can't find any papers that address this problem. Perhaps I'm using the wrong terminology? Does anyone have alternative keywords or anything that might help?

    Thanks again.
  4. Apr 7, 2012 #3

    Stephen Tashi

    User Avatar
    Science Advisor

    I probably couldn't solve this problem if I understood it, but for the sake of someone who could, I think you should clarify it.

    I don't understand the use of "Let X be..." in combination with the request to find X as a solution to something. Is "high probability" any non-zero probability?

    I'm also curious how you implement a uniform distribution over all k dimensional subspaces of real n-space.
  5. Apr 7, 2012 #4
    You're right, my choice of words is poor. X is a matrix lying in the space MV[itex]\cap[/itex]MX (using the notation from the proof in the original post). That is, X's column space is contained in V and X satisfies the zero constraints. When I said "a non-zero solution exists", I should have said "MV[itex]\cap[/itex]MX contains a non-zero element".

    If my conjecture is right, P(MV[itex]\cap[/itex]MX contains a non-zero element) is 1 for q< k(k+1)/2 and 0 for q>= k(k+1)/2. However, a result with any non-zero probability would be equally useful.

    I had the exact same question when I started looking into this. The distribution has support on a so-called "Grassmann manifold", the theory of which seems very well developed. My favourite paper is this one - they use a nice graphical approach to relate random subspaces to random points on a sphere. Hopefully, P(MV[itex]\cap[/itex]MX contains a non-zero element) has a transition point from 1 to 0 at q= k(k+1)/2, so we can ignore the exact specification of the distribution over the Grassmannian. However, that might be the correct approach: I just haven't had any luck with it so far, it gets very complex very quickly.
  6. Apr 9, 2012 #5

    Stephen Tashi

    User Avatar
    Science Advisor

    I don't know enough about this problem to make any suggestions. However, maybe if you answer some of my questions, you'll be struck by a blinding flash of inspiration.

    I've always been impressed by the utility of the singular value decomposition of a matrix and the most natural interpetation of a matrix (to me) is to view it as defining a linear mapping. So what would this point of view say in the case of your symmetric matrix and how would the SVD exhibit the column span of the matrix?

    ( Another thing that currently puzzles me is whether sunjin09's observation in the thread https://www.physicsforums.com/showthread.php?p=3849082#post3849082 is something that "anybody can see" from the geometric interpretation of the SVD. I can't see it! A summary of that is on another forum: http://www.sosmath.com/CBB/viewtopic.php?f=5&t=57763
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook