Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
I should add that $V$ is a random subspace whose distribution is uniform over all possible $k$-dimensional subspaces of $\mathbb R^n$, while the zero constraints are independent of $V$. There are pathological choices of $V$ where $q<\frac{k(k+1)}{2}$ is not a necessary condition (e.g, we could have $M_V\subseteq M_X$). However, I think these pathological choices have probability zero. –  Peter Mar 10 '12 at 16:59

1 Answer 1

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

share|improve this answer
    
Thank you for your answer. The $q$ entries are indeed fixed. The original question proves that $q<k(k+1)/2$ is sufficient for $M_V\cap M_X$ to have a non-trivial intersection. Your answer seems to extend the result to $q\leq k(k+1)/2$. This is indeed helpful, but what I really need is a necessary condition for $M_V\cap M_X$ to have a non-trivial intersection. Also, I am having some difficulty following your proof. You write "I claim that the column space of X has codimension at most k-1", but this assertion isn't obvious to me. Could you please explain why it is true? Thank you. –  Peter Apr 13 '12 at 8:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.