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

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$\in$ℝn$\times$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 $1\leq i < j\leq n$, 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.

 Proof of sufficient condition Let MV be the space of symmetric n by n matrices whose column space is contained in V. An orthogonal basis for MV is {Q(ei ejT+ej eiT)QT : $1\leq i \leq j \leq n$} where the columns of Q$\in$ℝn$\times$k form an orthonormal basis for V and ei are the standard basis vectors for ℝk, so dim(M_V)=k(k+1)/2. Let MX be the space of symmetric n$\times$n matrices that satisfy the q zero constraints. Now suppose no non-zero X satisfying the constraints exist: this implies MV$\cap$ MX={0}. Hence dim(MV+MX) = dim(MV)+dim(MX) = k(k+1)/2+n(n+1)/2-q. Since MV+MX is contained within the space of symmetric matrices, its dimension is bounded by n(n+1)/2. Thus "no non-zero X" implies q$\geq$k(k+1)/2. The contrapositive implies there is a non-zero solution when q
 PhysOrg.com science news on PhysOrg.com >> Ants and carnivorous plants conspire for mutualistic feeding>> Forecast for Titan: Wild weather could be ahead>> Researchers stitch defects into the world's thinnest semiconductor
 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.

Recognitions:
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.

 Quote by Petawa Let X$\in$ℝn$\times$n be a symmetric matrix whose column space is contained in V.
 How many of these zero constraints can I satisfy before (with high probability) the only solution is X=0?
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.

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

You're right, my choice of words is poor. X is a matrix lying in the space MV$\cap$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$\cap$MX contains a non-zero element".

 Is "high probability" any non-zero probability?
If my conjecture is right, P(MV$\cap$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'm also curious how you implement a uniform distribution over all k dimensional subspaces of real n-space.
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$\cap$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.
 Recognitions: 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 http://www.physicsforums.com/showthr...82#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