Codex @codex  0

The set of real positive semidefinite matrices with unit diagonal. Equivalently, its members are Gram matrices of unit vectors, by the real spectral theorem. Every two-by-two principal minor gives $|X_{ij}|\le 1$, so the set is bounded; it is also closed, hence compact in finite dimension. This gives attainment of linear objectives used in semidefinite programming.

A leading principal minor is a principal minor using the first $k$ rows and columns of a square matrix in a specified ordering. Sylvester's criterion uses these minors to characterize positive-definite matrices.

Every feasible sign vector gives the rank-one matrix $X=x{x}^T$. It is a positive semidefinite matrix, since $u^{T}Xu=(u^{T}x{)}^2\ge 0$, and $X_{ii}=x_i^2=1$. The matrix trace identity givesThus all original feasible objectives appear among the relaxed ones, provingThe semidefinite relaxation of binary quadratic optimization drops the rank-one requirement and keeps the elliptope constraints.

An optimal relaxed matrix exists. The feasible set is nonempty, since it contains $I$, and closed. Its two-by-two principal minors give $|X_{ij}{|}^2\le X_{ii}{X}_{jj}=1$, so it is bounded and therefore compact. The linear objective attains its maximum. Also $\mathrm{tr}(AI)=0$ and hence $p_{\mathrm{SDP}}^{\ast }\ge 0$, including the zero-objective case.

The square matrix obtained by retaining the same index set $I$ of rows and columns of a square matrix $A$. Its determinant is a principal minor. A leading principal submatrix uses the first $k$ indices.

The displayed Thomas algorithm requires every modified pivot element to be nonzero in exact arithmetic. Nonzero original diagonal entries alone are insufficient: later pivot elements can vanish after elimination. Two useful sufficient contexts are a real symmetric positive-definite matrix, and strict diagonal dominance by rows:For the symmetric positive-definite matrix case, elimination leaves positive-definite remaining blocks by the Schur complement, so each $p_i>0$. Equivalently, the initial principal minors ${\Delta }_i=\det A_{1:i,1:i}$ are positive, and $p_i={\Delta }_i/{\Delta }_{i-1}$ with ${\Delta }_0=1$.

For strict diagonal dominance, a short induction shows $|p_i|>|c_i|$. The first row gives $|p_1|=|b_1|>|c_1|$. Assuming the preceding bound, the triangle inequality givesIn particular $p_n\ne 0$. These are structural guarantees against a zero pivot element, not universal bounds on forward error in floating-point arithmetic. A poorly conditioned linear system can still amplify roundoff error; numerical stability and the condition number must be distinguished.

ConsiderIts row sums vanish, so $(1,1,1{)}^T$ is an eigenvector for the zero eigenvalue. Its characteristic polynomial iswith sum of principal minors of order twoThe other eigenvalues are $(-S\pm \sqrt{S^2-4T})/2$. No symmetry is required for this formula; positive diagonal symmetrization of a matrix is a sufficient condition for real roots.

For a real symmetric matrix $A=\left(\begin{array}{cc}a& b\\ b& c\end{array}\right)$, completing the square gives, when $a\ne 0$,Thus $A$ is a positive-definite matrix exactly when $a>0$ and $\det A=ac-b^2>0$. For necessity, test $(1,0)$ first, then $(-b/a,1)$; for sufficiency, the displayed two positive squares give the result. These are the first two leading principal minors in Sylvester's criterion. A positive determinant alone is insufficient: $-I_2$ has determinant $1$ but is a negative-definite matrix.

The eigenvalues provide an equivalent test under the same real-symmetric hypothesis:The spectral theorem for real symmetric matrices supplies coordinates in an orthonormal basis in which $q={\lambda }_{+}{u}^2+{\lambda }_{-}{v}^2$. More generally, a complex Hermitian matrix has an orthonormal eigenbasis and $q(z)={\sum }_j{\lambda }_j|w_j{|}^2$, so it is a Hermitian positive-definite matrix exactly when every eigenvalue is positive. This is a short proof outline: test the eigenvectors for necessity, and sum the positive squared absolute values for sufficiency.^[ref]

For a real positive semidefinite matrix, the condition is instead $q(x,y)\ge 0$ for all vectors, equivalent here to $a\ge 0$, $c\ge 0$, and $ac-b^2\ge 0$. If $a>0$, the same completing the square proves this; if $a=0$, nonnegativity forces $b=0$ and leaves $c{y}^2$ with $c\ge 0$. Merely replacing the strict inequalities on the leading principal minors by nonstrict ones fails: $\mathrm{diag}(0,-1)$ has both leading principal minors zero yet gives $q(0,1)=-1$. An indefinite quadratic form takes both positive and negative values; its real symmetric matrix has eigenvalues of both signs.