I'm trying to develop an estimator for the concentration matrix of a Gaussian Graphical Model. I've become stuck in trying to find conditions for the estimator to exist. I have a sufficient condition and I *think* it is also necessary, but I can't prove it. I'd greatly appreciate any suggestions on how to proceed.

# Problem statement

Let $V$ be an arbitrary $k$-dimensional vector subspace of $\mathbb R^n$. Let $X\in\mathbb R^{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 $X_{ij}=0$. How many of these zero constraints can I satisfy before 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< \frac{k(k+1)}{2}$. I think its also a necessary condition, but I could use a hand in showing that.

# Proof of sufficient condition

Let $M_V$ be the space of symmetric $n\times n$ matrices whose column space is contained in $V$. An orthonormal basis for $M_V$ is $\{\frac{1}{2}Q(e_ie_j^T+e_je_i^T)Q^T : 1\leq i \leq j \leq n\}$ where the columns of $Q\in\mathbb R^{n\times k}$ form an orthonormal basis for $V$ and $e_i$ are the standard basis vectors for $\mathbb R^k$, so $\dim(M_V)=\frac{k(k+1)}{2}$.

Let $M_X$ 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 $M_V\cap M_X=\{0\}$. Hence $\dim(M_V+M_X) = \dim(M_V)+\dim(M_X) = \frac{k(k+1)}{2}+\left(\frac{n(n+1)}{2}-q\right)$. Since $M_V+M_X$ is contained within the space of symmetric $n\times n$ matrices, its dimension is bounded by $\frac{n(n+1)}{2}$. Thus "no non-zero $X$" implies $q\geq\frac{k(k+1)}{2}$.