3
$\begingroup$

Is the following problem known? Suppose one is given some of the entries of an $n \times n$ matrix $A$ over $\mathbb{R}$, so that the given entries are symmetric. Can one assign values to the remaining entries so that the resulting matrix is positive definite?

Has this problem been studied from a theoretical or algorithmic point of view?

$\endgroup$
1
  • $\begingroup$ One simple method that finds a solution (if there is one) is alternating projections: Put the known values in the matrix (rest zero) and then project alternatingly onto the set of psd matrices and set the values to the demanded ones. Should converge if there is a solution and not converge if there is no solution. $\endgroup$
    – Dirk
    Jan 28 at 10:27

2 Answers 2

4
$\begingroup$

There is an extensive literature. Here are some entry points:

$\endgroup$
1
$\begingroup$

Here is a pedestrian solution of the completion problem. I shall denote $E$ the set of pairs $(i,j)$ for which $a_{ij}$ has been prescribed. It is a symmetric subset of $[1,n]\times[1,n]$. In the analysis, I shall denote $A_J$ the submatrix associated with rows and columns of indices $i,j\in J$.

Let us say that $K\subset[1,n]$ is complete if $K\times K\subset E$, that is if $A_K$ is prescribed. An obvious necessary condition is that $A_K$ is positive semi-definite for every complete subset $K$. Let me show below that this necessary condition is also sufficient.

Up to a conjugation by a permutation matrix, we may assume that $(j,j)\in E$ if and only if $j\in[1,k]$. It is sufficient to complete the block $A_{[1,k]}$, because once it is done, you may allocate any value to the remaining off-diagonal entries, and large enough values to the diagonal entries $a_{pp}$ for $p\in[k+1,n]$.

Thus we may assume that $k=n$ : every diagonal entry is prescribed. Since we assume the necessary condition, they satisfy $a_{jj}\ge0$. It remains to see that if $K$ and $L$ are complete, then $A_{K\cup L}$ can be completed into a positive semi-definite matrix. Processing step by step, it is actually sufficient to treat the case where $K\setminus L$ and $L\setminus K$ are singletons. Thus we are gone back to the situation where $K=[1,n-1]$ and $L=[2,n]$. Every entry is specified, but $x:=a_{1n}=a_{n1}$. Let us write blockwise $$A(x)=\begin{pmatrix} a_{11} & v^T & x \\ v & B & w \\ x & w^T & a_{nn} \end{pmatrix}.$$ From the assumption, the blocks $$A_-=\begin{pmatrix} a_{11} & v^T \\ v & B \end{pmatrix},\qquad A_+=\begin{pmatrix} B & w \\ w^T & a_{nn} \end{pmatrix}$$ are positive semi-definite. The problem is to find $x\in{\mathbb R}$ such that $A$ is positive semi-definite. This is equivalent to find $x\in{\mathbb R}$ such that $\det A(x)\ge0$ (characterization of positiveness by that of the determinants of the principal submatrices).

By continuity and compactness, we may assume that $B$ is positive definite. By assumption we have $$a_{11}\ge v^TB^{-1}v,\qquad a_{nn}\ge w^TB^{-1}w,$$ and it will be sufficient to treat the case where $a_{11}$ and $a_{nn}$ are minimal: $$a_{11}=v^TB^{-1}v,\qquad a_{nn}=w^TB^{-1}w.$$ Using Sherman-Morrison Formula, we get $$\det A(x)=\det A(0)+2xw^T\hat Bv-x^2\det B,$$ where $\hat B$ is the cofactor matrix. A good $x$ will exist whenever $$\det A(0)+\frac{(w^T\hat Bv)^2}{\det B}$$ is non-negative. S.-M. again gives $\det A(0)=-(\det B)(w^TB^{-1}v)^2$. Thus the quantity above is just $0$.

To summarize (assuming the necessary condition that every complete submatrix is positive semi-definite): if $K=[1,n-1]$ and $L=[2,n]$ are complete, the completion is possible, for instance with the choice $a_{1n}=w^TB^{-1}v$. Actually, this choice is the only one possible if $a_{11}$ and $a_{nn}$ are minimal. This Lemma allows us to complete $A$ step by step whenever the diagonal entries are prescribed. The remaining off-diagonal entries may be chosen arbitrarily, and the remaining diagonal ones be chosen large enough.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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