Why Positive Semidefiniteness Matters
A patient-similarity matrix gives a numerical similarity for each pair of patients. But symmetry and plausible-looking entries do not by themselves guarantee that the matrix behaves like inner products in a feature space. Positive semidefiniteness supplies that guarantee: it ensures that every weighted combination of patients has a nonnegative squared length under the similarities. This matters because many geometric interpretations and calculations with kernels rely on that structure.
Here, \(K\) denotes a finite \(n\times n\) matrix of similarities for \(n\) patients. The focus is on the mathematical guarantee and on checking it for a given matrix. This does not imply that a valid matrix must have nonnegative entries: negative inner products are possible. Nor does checking one finite matrix prove that a rule for computing similarities will produce valid matrices for every possible data set.
The vector \(c\) can be viewed as a set of weights on the patients. The quadratic form \(c^\mathsf{T}Kc\) combines all pairwise similarities using those weights. The PSD condition says that no choice of weights produces a negative squared length. The weights need not be nonnegative.
The Feature-Space Guarantee
A Gram matrix is a matrix of inner products: its \((i,j)\) entry is the inner product of feature vectors for patients \(i\) and \(j\). The key result is that, for a finite real symmetric matrix, being PSD is exactly the condition needed for such a representation.
For one direction, suppose \(K_{ij}=\phi_i^\mathsf{T}\phi_j\). For any vector \(c\),
The matrix is symmetric because inner products are symmetric, and the quadratic form is nonnegative because it is a squared norm. This proves that every Gram matrix is PSD.
For the other direction, the spectral theorem states that a real symmetric matrix has an orthonormal eigenvector decomposition \(K=Q\Lambda Q^\mathsf{T}\), where \(Q^\mathsf{T}Q=I\) and \(\Lambda\) is diagonal with the real eigenvalues \(\lambda_1,\ldots,\lambda_n\). If \(K\) is PSD, each eigenvalue is nonnegative: for a unit eigenvector \(q_r\), \(q_r^\mathsf{T}Kq_r=\lambda_r\), which must be at least zero. Define
Then \(\phi_i^\mathsf{T}\phi_j=\sum_{r=1}^n\lambda_r Q_{ir}Q_{jr}=K_{ij}\). Coordinates associated with zero eigenvalues are zero, so they can be omitted; the remaining number of coordinates is \(\operatorname{rank}(K)\). This completes the construction and the proof.
Worked Examples: Representations and Eigenvalue Checks
Worked Example: Recovering Feature Vectors From a PSD Matrix
Suppose three hypothetical patients have the symmetric similarity matrix
One way to verify the feature-space interpretation is to propose vectors \(\phi_1=(1,0)\), \(\phi_2=(1,1)\), and \(\phi_3=(0,1)\). Their inner products are \(\phi_1^\mathsf{T}\phi_1=1\), \(\phi_1^\mathsf{T}\phi_2=1\), \(\phi_1^\mathsf{T}\phi_3=0\), \(\phi_2^\mathsf{T}\phi_2=2\), \(\phi_2^\mathsf{T}\phi_3=1\), and \(\phi_3^\mathsf{T}\phi_3=1\). By symmetry these fill exactly the entries of \(K\).
The quadratic form gives a second check. For \(c=(a,b,d)^\mathsf{T}\), \(c^\mathsf{T}Kc=a^2+2ab+2b^2+2bd+d^2=(a+b)^2+(b+d)^2\), which is nonnegative for all real \(a,b,d\). Thus \(K\) is PSD. The two displayed feature coordinates also show that its rank is at most 2; the two vectors \(\phi_1\) and \(\phi_3\) are linearly independent, so its rank is exactly 2.
Worked Example: Detecting a Matrix That Cannot Be a Gram Matrix
Consider the hypothetical symmetric matrix \(K=\begin{pmatrix}1&1.2\\1.2&1\end{pmatrix}\). Its eigenvectors are proportional to \((1,1)^\mathsf{T}\) and \((1,-1)^\mathsf{T}\), with eigenvalues \(2.2\) and \(-0.2\), respectively. Since one eigenvalue is negative, \(K\) is not PSD.
The failure can be checked directly with \(c=(1,-1)^\mathsf{T}\):
Therefore no real Euclidean feature vectors can have this matrix as their Gram matrix. Notice that all four entries are positive, and the off-diagonal similarity is quite close to the diagonal entries. Those facts do not override the negative quadratic form. Similarity values that look reasonable individually can still be incompatible as a whole matrix.
Worked Example: Interpreting a Tiny Negative Eigenvalue
Suppose a hypothetical two-patient matrix, recorded to finite precision, is \(K=\begin{pmatrix}1&1\\1&1-10^{-10}\end{pmatrix}\). Its trace is \(2-10^{-10}\) and its determinant is \(-10^{-10}\), so it has one positive and one negative eigenvalue. Solving its characteristic equation gives eigenvalues
Mathematically, the displayed matrix is not PSD: its smaller eigenvalue is negative. For example, the vector \(c=(1,-1)^\mathsf{T}\) gives \(c^\mathsf{T}Kc=-10^{-10}\). Yet this negative value is tiny compared with the matrix entries. If the entries came from rounded calculations, it could reflect numerical precision rather than a meaningful departure from a PSD matrix.
A scale-aware numerical check might compare the smallest eigenvalue with a tolerance \(\tau=10^{-8}\max(1,\|K\|_2)\), where \(\|K\|_2\) is the largest absolute eigenvalue for a symmetric matrix. Here \(\|K\|_2\approx2\), so \(\tau\approx2\times10^{-8}\). The negative eigenvalue is smaller in magnitude than this tolerance. The appropriate report is that the matrix is numerically consistent with PSD at this tolerance, not that the exact displayed matrix is PSD. Higher-precision computation or checking how the entries were generated can resolve the ambiguity.
Checking Positive Semidefiniteness in Practice
For a real symmetric matrix, the eigenvalue condition follows directly from its orthonormal eigenvector decomposition. Write any vector as \(c=Qz\). Then
If every \(\lambda_r\geq0\), every term in the sum is nonnegative, so \(K\) is PSD. If some \(\lambda_r<0\), choosing \(c=q_r\), the corresponding eigenvector, gives \(c^\mathsf{T}Kc=\lambda_r<0\), so \(K\) is not PSD. This proves the equivalence and explains why checking eigenvalues is informative rather than merely a computational convention.
A practical assessment should include both a symmetry check and an eigenvalue check. Eigenvalue methods designed for symmetric matrices assume symmetry; for a matrix with noticeable asymmetry, first investigate the source rather than treating its eigenvalues as a definitive PSD test. Small asymmetry can arise from rounding, but silently replacing \(K\) by \((K+K^\mathsf{T})/2\) changes the matrix and should be reported if done.
Confirm that the matrix is square, its entries are finite, and its asymmetry is negligible relative to the numerical precision and scale of the entries.
For a symmetric matrix, use a symmetric eigensolver and record the smallest and largest eigenvalues.
Nonnegative eigenvalues establish PSD. A clearly negative eigenvalue disproves it. A negative value close to zero calls for a stated tolerance and, where consequential, a precision or construction check.
Distinguish exact PSD, numerical compatibility with PSD at a stated tolerance, and clear indefiniteness. Do not present a tolerance decision as an exact mathematical proof.
Alternatives, Diagnostics, and Limitations
| Check | What it establishes | Main caution |
|---|---|---|
| Eigenvalues | For a symmetric matrix, all eigenvalues nonnegative is equivalent to PSD. | Near-zero signs can be sensitive to numerical precision; symmetry must be checked. |
| Quadratic form | A vector with \(c^\mathsf{T}Kc<0\) proves the matrix is not PSD. | Testing a few vectors cannot establish PSD for every possible vector. |
| Principal minors | For a symmetric matrix, nonnegative determinants of all principal submatrices characterize PSD. | There are many such determinants; checking only leading principal minors is not a sufficient PSD test. |
| Cholesky factorization | A standard Cholesky factorization is a check for positive definiteness. | Failure does not by itself imply indefiniteness: a valid PSD matrix may be singular. |
These checks answer related but different questions. A negative quadratic form is a useful diagnostic because it identifies a concrete direction of failure. But a handful of nonnegative quadratic forms is not a certificate. Principal-minor checks can characterize PSD in theory, though eigenvalue computation is generally more direct for assessing a numerical matrix. Standard Cholesky factorization is most naturally suited to positive definite matrices, so a zero eigenvalue can cause it to fail even when the matrix is PSD.
Several failure modes deserve attention. First, PSD is a joint property: positive diagonal entries and nonnegative pairwise similarities do not guarantee it. Second, symmetry alone is not enough. Third, a small negative eigenvalue should not be automatically rounded up to zero without stating the tolerance or the resulting change. If a matrix is modified by clipping negative eigenvalues, that creates a new matrix; it does not retroactively prove the original one was PSD. Finally, a finite matrix check concerns only the patients and entries under examination. It cannot establish that an underlying similarity rule will produce a PSD matrix on every future data set.
A common mistake is to argue, “Every similarity is nonnegative, so the matrix must be PSD.” The correction is that PSD requires \(c^\mathsf{T}Kc\geq0\) for all real weight vectors, including vectors with negative components. In the second worked example every entry is positive, yet \(c=(1,-1)^\mathsf{T}\) gives a negative quadratic form. The eigenvalue check reveals the same incompatibility.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- Why does a Gram matrix of real feature vectors have a nonnegative quadratic form for every real vector \(c\)?
- A symmetric matrix has eigenvalues \(3\), \(0\), and \(0.4\). Is it PSD or positive definite? What does the zero eigenvalue imply for the feature representation?
- A symmetric matrix has eigenvalues \(2\) and \(-0.01\). Can it be a Gram matrix of real Euclidean feature vectors? Give a reason.
- Why does checking that all entries of a similarity matrix are nonnegative fail to establish positive semidefiniteness?
Solutions. (1) If \(K_{ij}=\phi_i^\mathsf{T}\phi_j\), then \(c^\mathsf{T}Kc=\|\sum_i c_i\phi_i\|^2\geq0\). (2) It is PSD but not positive definite, because one eigenvalue is zero. The feature vectors can be represented in at most two dimensions, since the rank is two. (3) No. The negative eigenvalue means that the quadratic form is negative along its eigenvector, which is impossible for a Gram matrix. (4) PSD constrains every weighted combination, including weights of mixed signs; positive entries alone do not guarantee that every quadratic form is nonnegative.