How many zero-constraints can be added to a subspace-restricted matrix before no solution exists? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T14:34:45Z http://mathoverflow.net/feeds/question/90829 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90829/how-many-zero-constraints-can-be-added-to-a-subspace-restricted-matrix-before-no How many zero-constraints can be added to a subspace-restricted matrix before no solution exists? Peter 2012-03-10T16:38:28Z 2012-08-31T03:22:01Z <p>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 <em>think</em> it is also necessary, but I can't prove it. I'd greatly appreciate any suggestions on how to proceed.</p> <h1>Problem statement</h1> <p>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 &lt; j\leq n$, I need $X_{ij}=0$. How many of these zero constraints can I satisfy before the only solution is $X=0$?</p> <p>I've found a sufficient condition for a non-zero solution to exist: the number of constraints $q$ must satisfy $q&lt; \frac{k(k+1)}{2}$. I think its also a necessary condition, but I could use a hand in showing that.</p> <h1>Proof of sufficient condition</h1> <p>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}$.</p> <p>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}$. </p> http://mathoverflow.net/questions/90829/how-many-zero-constraints-can-be-added-to-a-subspace-restricted-matrix-before-no/93910#93910 Answer by Ngoc Mai Tran for How many zero-constraints can be added to a subspace-restricted matrix before no solution exists? Ngoc Mai Tran 2012-04-12T21:42:10Z 2012-04-12T21:42:10Z <p>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). </p> <p>Assuming that these $q$'s are fixed, here's a proof of sufficiency: suppose $q = k(k+1)/2$, $k &lt; 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. </p> <p>It then follows that the column space of any such $X$ intersects non-trivially with a subspace of codimension $n-k$. </p>