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?
There is an extensive literature. Here are some entry points:
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.
