- #1

Petawa

- 7

- 0

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.