How many zero-constraints can be added to a subspace-restricted matrix before no solution exists?

2012-03-10T16:38:28Z

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}$.

Answer by Ngoc Mai Tran for How many zero-constraints can be added to a subspace-restricted matrix before no solution exists?

2012-04-12T21:42:10Z

Just to clarify: are the $q$ entries $(i,j)$ fixed, or are they also chosen uniformly at random over all possible sets of q entries of an $n \times n$ matrix? (This is not so important though).

Assuming that these $q$'s are fixed, here's a proof of sufficiency: suppose $q = k(k+1)/2$, $k < n$. Fix $q$ entries $(i,j)$, and consider the set $M$ of all $n \times n$ matrices with these entries being $0$. Then for any $X \in M$, I claim that the column space of $X$ has codimension at most k-1, and this occurs precisely when up to a permutation, $X$ is a block matrix with a $k \times k$ zero-block that contains the diagonal.

It then follows that the column space of any such $X$ intersects non-trivially with a subspace of codimension $n-k$.

How many zero-constraints can be added to a subspace-restricted matrix before no solution exists? - MathOverflow

How many zero-constraints can be added to a subspace-restricted matrix before no solution exists?

Problem statement

Proof of sufficient condition

Answer by Ngoc Mai Tran for How many zero-constraints can be added to a subspace-restricted matrix before no solution exists?