Maximum determinant positive semidefinite matrix completion. We consider a matrix A∈Sn, with some entries specified, and the others not specified. The positive semidefinite matrix completion problem is to determine values of the unspecified entries of the matrix so that A⪰0 (or to determine that such a completion does not exist).
(a) Explain why we can assume without loss of generality that the diagonal entries of A are specified.
(b) Show how to formulate the positive semidefinite completion problem as an SDP feasibility problem.
(c) Assume that A has at least one completion that is positive definite, and the diagonal entries of A are specified (i.e., fixed). The positive definite completion with largest determinant is called the maximum determinant completion. Show that the maximum determinant completion is unique. Show that if A⋆ is the maximum determinant completion, then (A⋆)−1 has zeros in all the entries of the original matrix that were not specified. Hint. The gradient of the function f(X)=logdetX is ∇f(X)=X−1 (see \S A.4.1).
(d) Suppose A is specified on its tridiagonal part, i.e., we are given A11,…,Ann and A12,…,An−1,n. Show that if there exists a positive definite completion of A, then there is a positive definite completion whose inverse is tridiagonal.