Q:

cell-by-cell constraints within a positive-definite matrix?

One simple constraint in a positive definite matrix relates each off-diagonal cell to the corresponding on-diagonal cells:
$$ |m_{ij}| \lt \sqrt{m_{ii}m_{jj}}  $$
While this may be a necessary condition, I guess it's not sufficient?
If we take a positive definite matrix and wish to replace one cell, what are the upper and lower bounds on the new value in that cell?  Is it a complex function of every other cell, or just of the two diagonal entries, as above?
Context:
Ultimately, I want a really simple way to estimate a covariance matrix in the context of missing data.  Missing data can cause the matrix of estimated pairwise covariances to be negative definite to not be positive (semi-)definite.  I want a simple way to quickly modify the matrix to make it positive definite.  My current plan is to tweak it, one cell at a time, enforcing any constraints you guys give me.  I would first tweak the cells that suffered from the most 'missingness' - those values are based on the fewest observations and therefore I'm happy to replace them.

A:

It certainly is not sufficient unless the matrix $M$ is $2\times 2$ (or $1\times 1$ in the trivial case). It is only necessary and follows from the fact that a principal submatrix 
$$
\begin{bmatrix}
m_{ii} & m_{ij} \\
m_{ji} & m_{jj}
\end{bmatrix}
$$
of an SPD matrix $M$ is SPD as well (which is iff $|m_{ij}|<\sqrt{m_{ii}m_{jj}}$).
A note on the context: the modified matrix actually can only happen to be indefinite (not negative definite) if the original matrix was positive definite and you changed only off-diagonal entries (since the diagonals remain positive).
Simplest ways I can think of how one could "tweak" the off-diagonal values to do not make the matrix indefinite is to either use the Gershgorin theorem or the perturbation theorem for the eigenvalues.
The first approach could be to allow (symmetric) changes of the off-diagonal entries such that the modified rows and columns (says $i$ and $j$) remain diagonally dominant (symmetric diagonally dominant matrices are known to be positive definite). There are SPD matrices which are not diagonally dominant though.
In the second approach, if you know the minimal eigenvalue of the original matrix $\lambda_{\min}(M)$, the minimal eigenvalue of the changed matrix won't be smaller than $\lambda_{\min}(M)-\|E\|$, where $E$ is the matrix of "changes" and $\|\cdot\|$ is the spectral or Frobenius norm. So the constraint could to keep $\|E\|<\lambda_{\min}(M)$. However, this can be quite restrictive.
This is BTW known as the matrix completion problem. You could probably find more interesting information in the references on the linked page.
Hope this helps.

