Finding the bounds of the missing values of a symmetric positive semidefinite matrix

Question

Suppose we have a symmetric matrix that we know is positive semi-definite and has missing entries. For example:

$ \begin{pmatrix} 1&1&1\\ 1&1&x\\ 1&x&1 \end{pmatrix} $

How can I find (preferably analytically, but algorithmically is ok) the values of $x$ that would make this matrix positive semi-definite?

Extra background for the interested: The matrix I am looking at is a covariance matrix, which we know is PSD. I want to find the possible values of $x$ so that, from the possible values, I choose the one that would render the maximum entropy distribution.

Answer 1

The determinant of your matrix is $-(x-1)^2$. Since a positive semidefinite matrix must have nonnegative determinant, the only possible value is $x=1$. You still need to check that the matrix is actually PSD when $x=1$.

More generally, a matrix is PSD iff all principal minors are nonnegative.

Answer 2

This matrix will fail to be positive definite except in the case that $x = 1$. One way to see this is to consider the Schur complement $$ \pmatrix{1 & x\\x & 1} - \pmatrix{1\\1}(1)^{-1}\pmatrix{1 & 1} = \pmatrix{0&x-1\\x-1&0}. $$ This matrix will have determinant $-(x-1)^2$, which is negative except in the case that $x = 1$.

This method can be applied more generally whenever a principal submatrix of a positive semidefinite matrix is altered.

Answer 3

A Hermitian (or real symmetric) matrix is positive semidefinite if and only if all of its eigenvalues are non-negative, see PSD.
WolframAlpha gives the eigenvalues of the considered matrix $$\lambda_1=1-x, \;\lambda_{2,3}=\frac{1}{2}\left(x+2\pm \sqrt{x^2+8}\right).$$ Clearly, $$\lambda_1\ge 0\iff x\le 1,$$ while $$\lambda_3\ge0\iff x+2 - \sqrt{x^2+8}\ge0 \iff x\ge 1.$$ This gives the unique value $x=1$ that makes the matrix PSD. It is easy to see that also $\lambda_2\ge 0.$