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 - The Fusion of Science and Community**

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

Loading...

Similar Threads for Dimension intersection between | Date |
---|---|

A Markov Chain as a function of dimensions | Aug 10, 2017 |

I Intersection & union of closed and open sets? | Sep 7, 2016 |

Dimension of a graphical model | Oct 16, 2014 |

Is it possible to measure Hausdorff dimension for real world objects? | Sep 13, 2014 |

Hausdorff dimension of Hofstadter's Butterfly? | May 1, 2014 |

**Physics Forums - The Fusion of Science and Community**