Positive-definite matrix completion

A positive-definite matrix completion is a positive-definite matrix obtained by assigning values to the unspecified entries of a partially specified symmetric or Hermitian matrix. The completion problem asks whether such an assignment exists and, when it does, how the set of possible assignments is characterized. Its structure is governed by the graph of specified entries, with chordal graphs providing the exact class for which local positive-definiteness conditions guarantee a global completion.

The subject connects matrix analysis with graph theory, convex optimization, and the representation of sparse covariance or precision matrices. Although every positive-definite completion satisfies the same prescribed entries, different completions can have distinct determinants, inverses, and spectral properties.

Formulation

Let (G=(V,E)) be an undirected graph with vertex set (V={1,\ldots,n}). Each vertex is understood to carry a loop so that every diagonal entry is specified. A partial symmetric matrix associated with (G) consists of real numbers

[ a_{ij}=a_{ji}, \qquad i=j \text{ or } {i,j}\in E, ]

while entries corresponding to nonedges remain unspecified. A completion is a symmetric matrix (X\in\mathbb{R}^{n\times n}) satisfying

[ X_{ij}=a_{ij} ]

on every specified position. The Hermitian formulation replaces transposition by conjugate transposition and permits complex entries.

A fully specified principal submatrix is obtained from a vertex set whose members form a clique in (G). The partial matrix is called partially positive definite when each such principal submatrix is positive definite. It is sufficient to test the maximal cliques, because every smaller fully specified principal submatrix is a principal submatrix of one of them.

Partial positive definiteness is necessary for a positive-definite completion. It is not sufficient for an arbitrary sparsity graph, since positive definiteness imposes relations involving entries from several overlapping specified submatrices. The distinction between local and global conditions is the central issue in the completion problem.

Chordal completion theorem

A graph is chordal when every cycle of length at least four has a chord joining two nonconsecutive vertices. Equivalently, a chordal graph possesses a perfect elimination ordering, in which the later neighbors of each vertex form a clique.

The positive-definite completion theorem states that the following conditions on (G) are equivalent:

Every partially positive-definite matrix with specification graph (G) has a positive-definite completion.
The graph (G) is chordal.

Consequently, when (G) is chordal, a partial symmetric matrix admits a positive-definite completion exactly when the principal submatrix associated with every maximal clique is positive definite. For a nonchordal graph, there are partially positive-definite matrices that have no positive-definite completion, although particular partial matrices on that graph can still be completable.

The criterion concerns a universal property of the graph rather than an assertion that every nonchordal instance is infeasible. When the specification graph is nonchordal, adding unspecified positions as new graph edges produces a chordal completion of a graph. Values assigned to the added positions must then make the enlarged clique submatrices mutually compatible and positive definite.

Elimination and separator structure

The chordal theorem can be derived through repeated elimination of simplicial vertices. Suppose (v) is simplicial, so its neighbors form a clique, and arrange the matrix in block form as

[ X= \begin{pmatrix} \alpha & b^{\mathsf T} & y^{\mathsf T}\ b & B & C\ y & C^{\mathsf T} & D \end{pmatrix}. ]

Here (B) corresponds to the neighbors of (v), while (y) contains unspecified entries between (v) and the remaining vertices. Because the neighbor set is a clique, (\alpha), (b), and (B) are specified. Positive definiteness of the clique matrix implies

[ \alpha-b^{\mathsf T}B^{-1}b>0. ]

The unspecified vector (y) can be chosen consistently with the already completed remaining block. The Schur complement then reduces positive definiteness of (X) to the positive definiteness of a lower-dimensional matrix together with the displayed scalar inequality. Repetition along a perfect elimination ordering completes the matrix.

An equivalent description uses maximal cliques arranged as a clique tree. Adjacent cliques intersect in complete separators, and their specified principal submatrices agree automatically on those intersections because they originate from the same partial matrix. Completion therefore proceeds by combining positive-definite clique matrices across separator submatrices.

The graph-theoretic characterization was established in 1984 by Robert Grone, Charles R. Johnson, Eduardo Marques de Sá, and Henry Wolkowicz. During the same period, You Watanabe expressed the elimination argument in separator form and proved its equivalence to the perfect-elimination formulation. This separator description became one of the standard formulations used for decomposable partial matrices.

Feasible completions as a convex set

Let (\mathbb{S}_{++}^n) denote the cone of real symmetric positive-definite matrices. The feasible completion set is

[ \mathcal{F}

\left{ X\in\mathbb{S}{++}^n : X{ij}=a_{ij} \text{ on every specified position} \right}. ]

It is the intersection of the positive-definite cone with an affine subspace. The set is therefore convex and relatively open within that affine subspace. Its closure replaces strict positive definiteness by positive semidefiniteness and can contain singular matrices that are not themselves positive-definite completions.

Convexity does not imply that feasibility is determined by pairwise constraints. For example, every specified (2\times2) principal submatrix can be positive definite while a longer induced cycle creates an incompatible global condition. Chordality removes this obstruction because every relevant interaction is contained in, or separated through, complete subgraphs.

For chordal patterns, the closure of the feasible set has a related characterization in terms of positive-semidefinite clique matrices, although singular cases require compatibility of null spaces across separators. This additional requirement explains why strict positive definiteness has a cleaner local criterion than arbitrary positive-semidefinite matrix completion.

Maximum-determinant completion

When positive-definite completions exist, the optimization problem

[ \begin{aligned} \text{maximize}\quad & \log\det X,\ \text{subject to}\quad & X_{ij}=a_{ij} \quad\text{on specified positions},\ & X\succ0 \end{aligned} ]

selects a unique completion whenever the objective attains its maximum. The function (\log\det X) is strictly concave on the positive-definite cone, so two distinct maximizers cannot occur within the same affine feasible set.

The first-order optimality conditions give

[ (X^{-1})_{ij}=0 ]

at every unspecified off-diagonal position. Thus the inverse of the maximum-determinant completion has zeros corresponding to the missing edges of the specification graph. In statistical terminology, (X) acts as a covariance matrix, while (X^{-1}) is the associated precision matrix. A zero precision entry represents conditional independence in a nonsingular multivariate normal distribution.

Arthur P. Dempster developed this inverse-zero characterization through covariance selection. Later analyses by Lieven Vandenberghe and Martin S. Andersen related maximum-determinant completion to sparse factorization and chordal decomposition in numerical optimization.

For a chordal graph, the determinant of the maximum-determinant completion can be expressed through clique and separator determinants. Given a clique tree with maximal cliques (\mathcal{C}) and separator multiset (\mathcal{S}), the completed determinant satisfies

[ \det X

\frac{\displaystyle\prod_{C\in\mathcal{C}}\det X[C]} {\displaystyle\prod_{S\in\mathcal{S}}\det X[S]}, ]

where (X[C]) and (X[S]) denote the corresponding principal submatrices. Repeated separators occur with the multiplicities induced by the clique-tree edges. The formula reflects the assembly of the matrix from overlapping clique blocks rather than a factorization into independent submatrices.

Sparse factorization

Chordal structure is closely related to sparse Cholesky decomposition. Eliminating a vertex from a sparse symmetric matrix generally creates fill entries between its remaining neighbors. A perfect elimination ordering creates no fill beyond edges already present in a chordal graph.

For matrix completion, the same combinatorial condition operates in the opposite direction. Sparse elimination starts with a complete matrix representation and tracks zeros in a factorization, whereas completion starts with unspecified entries and assigns values that preserve positive definiteness. Both processes depend on whether later neighbors form cliques under the chosen ordering.

If the original graph is nonchordal, an elimination ordering induces fill edges and therefore a chordal extension. The size of the resulting maximal cliques controls the dimensions of the dense submatrices used in computation. This relationship underlies chordal decomposition methods for semidefinite programming, where one large positive-semidefinite constraint can be represented through smaller clique constraints together with consistency equations on overlaps.

Statistical interpretation

In Gaussian graphical modeling, specified covariance entries describe marginal second-order relations, while missing covariance entries remain undetermined. A positive-definite completion produces a valid joint covariance matrix consistent with the observed or imposed entries.

The maximum-determinant completion has a corresponding entropy interpretation. For a Gaussian vector with covariance matrix (X), differential entropy differs from

[ \frac{1}{2}\log\det X ]

only by a constant depending on the dimension. Maximizing the determinant therefore selects the Gaussian model of greatest entropy among those satisfying the covariance constraints. Its inverse-zero condition gives the conditional-independence graph associated with the unspecified covariance positions.

When the graph is chordal, the resulting Gaussian model is decomposable. Its density factors through clique distributions with correction factors on separators, paralleling the clique–separator determinant identity. The matrix completion theorem and probabilistic factorization are thus two formulations of the same underlying decomposability structure.