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.(adsbygoogle = window.adsbygoogle || []).push({});

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 X_{ij}=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 M_{V}be the space of symmetric n by n matrices whose column space is contained in V. An orthogonal basis for M_{V}is {Q(e_{i}e_{j}^{T}+e_{j}e_{i}^{T})Q^{T}: [itex]1\leq i \leq j \leq n[/itex]} where the columns of Q[itex]\in[/itex]ℝ^{n[itex]\times[/itex]k}form an orthonormal basis for V and e_{i}are the standard basis vectors for ℝ^{k}, so dim(M_V)=k(k+1)/2.

Let M_{X}be the space of symmetric n[itex]\times[/itex]n matrices that satisfy the q zero constraints. Now suppose no non-zero X satisfying the constraints exist: this implies M_{V}[itex]\cap[/itex] M_{X}={0}. Hence dim(M_{V}+M_{X}) = dim(M_{V})+dim(M_{X}) = k(k+1)/2+n(n+1)/2-q. Since M_{V}+M_{X}is contained within the space of symmetric matrices, its dimension is bounded by n(n+1)/2. Thus "no non-zero X" implies q[itex]\geq[/itex]k(k+1)/2. The contrapositive implies there is a non-zero solution when q<k(k+1)/2.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**