I agree with your example. I think you can remove the row/column if there are no known 0s on the diagonal, and I also think you can first WLOG remove any rows and columns with 0s on the diagonal (since if there are any other known non-zero entries in their row or column then the matrix has no PSD completions).
I’m also happy to just assume the diagonal entries are known. I think these are pretty weird corner cases.
It’s not quite this simple, the same issue arises if every PSD completion of the known-diagonal minor has zero determinant (e.g. ((?, 1, 2), (1, 1, 1), (2, 1, 1))). But I think in that case making the remaining diagonal entries large enough still makes the eigenvalues at least −ε, which is good enough.
What matters is not whether or not there is another 0 on the diagonal, but whether or not there is another PSD non definite matrix on the diagonal. For example, in the comment from Jacob_Hilton, they introduce the 2x2 matrix ((1,1),(1,1)), with eigenvalues [0,1], which is a PSD non definite.
I agree with assuming that all diagonal entries are known. You can even assume that all entries are 1 on the diagonal WLOG.
Just to spell it out, am I right in thinking that you can scale all the matrix elements so that each entry on the diagonal is the sign of its original value, i.e. −1 or 1, but if the resulting diagonal contains any −1s then it can’t be PSD?
Yes indeed. One definition of a PSD matrix is some matrix M such that, for any vector X, XTMX≥0 (so, it defines some kind of scalar product).
If Mi,i=y, then you can always divide the whole row/column by √y, which is equivalent to applying some scaling, this won’t change the fact that M is PSD or not.
If Mi,i=−1, then if you try the vector X:∀j≠i,Xj=0;Xi=1, you can check that XTMX=−1, thus the matrix isn’t PSD.
I agree with your example. I think you can remove the row/column if there are no known 0s on the diagonal, and I also think you can first WLOG remove any rows and columns with 0s on the diagonal (since if there are any other known non-zero entries in their row or column then the matrix has no PSD completions).
I’m also happy to just assume the diagonal entries are known. I think these are pretty weird corner cases.
It’s not quite this simple, the same issue arises if every PSD completion of the known-diagonal minor has zero determinant (e.g. ((?, 1, 2), (1, 1, 1), (2, 1, 1))). But I think in that case making the remaining diagonal entries large enough still makes the eigenvalues at least −ε, which is good enough.
What matters is not whether or not there is another 0 on the diagonal, but whether or not there is another PSD non definite matrix on the diagonal. For example, in the comment from Jacob_Hilton, they introduce the 2x2 matrix ((1,1),(1,1)), with eigenvalues [0,1], which is a PSD non definite.
I agree with assuming that all diagonal entries are known. You can even assume that all entries are 1 on the diagonal WLOG.
I changed the statement to assume the diagonal is known, I agree this way is cleaner and prevents us from having to think about weird corner cases.
Just to spell it out, am I right in thinking that you can scale all the matrix elements so that each entry on the diagonal is the sign of its original value, i.e. −1 or 1, but if the resulting diagonal contains any −1s then it can’t be PSD?
Yes indeed. One definition of a PSD matrix is some matrix M such that, for any vector X, XTMX≥0 (so, it defines some kind of scalar product).
If Mi,i=y, then you can always divide the whole row/column by √y, which is equivalent to applying some scaling, this won’t change the fact that M is PSD or not.
If Mi,i=−1, then if you try the vector X:∀j≠i,Xj=0;Xi=1, you can check that XTMX=−1, thus the matrix isn’t PSD.