Inertia possibilities for completions of partial hermitian matrices *

A partial Hermitian matrix is one in which some entries are specified and others are considered to be free (complex) variables. Assuming the undirected graph of the specified entries is chordal, it is shown that, with certain mild restrictions, a partial Hermitian matrix may be completed to a Hermitian matrix with any inertia allowed by the specified principal submatrices through the interlacing inequalities. This generalizes earlier work dealing with the existence of positive definite completions, and. as before, the chordality assumption is, in general, necessary. Further related observations dealing with Toeplitz completions and the minimum eigenvalues of completions are also made, and these raise additional questions.     

Inertia possibilities for completions of partial hermitian matrices

A partial Hermitian matrix is one in which some entries are specified and others are considered to be free (complex) variables. Assuming the undirected graph of the specified entries is chordal, it is shown that, with certain mild restrictions, a partial Hermitian matrix may be completed to a Hermitian matrix with any inertia allowed by the specified principal submatrices through the interlacing inequalities. This generalizes earlier work dealing with the existence of positive definite completions, and. as before, the chordality assumption is, in general, necessary. Further related observations dealing with Toeplitz completions and the minimum eigenvalues of completions are also made, and these raise additional questions.     

The positive definite completion problem revisited

In [R. Grone, C.R. Johnson, E. Sa, H. Wolkowicz, Positive definite completions of partial Hermitian matrices, Linear Algebra Appl. 58 (1984) 109-124] the positive definite (semi-) completion problem in which the underlying graph is chordal was solved. For the positive definite case, the process was constructive and the completion was obtained by completing the partial matrix an entry at a time. For the positive semidefinite case, they obtained completions of a particular sequence of partial positive definite matrices with the same underlying graph and noted that there is a convergent subsequence of these completions that converges to the desired completion. Here, in the chordal case, we provide a constructive solution, based entirely on matrix/graph theoretic methods, to the positive (semi-)definite completion problem. Our solution associates a specific tree (called the “clique tree” [C.R. Johnson, M. Lundquist, Matrices with chordal inverse zero-patterns, Linear and Multilinear Algebra 36 (1993) 1-17]) with the (chordal) graph of the given partial positive (semi-)definite matrix. This tree structure allows us to complete the matrix a “block at a time” as opposed to an “entry at a time” (as in Grone et al. (1984) for the positive definite case). In Grone et al. (1984), using complex analytic techniques, the completion for the positive definite case was shown to be the unique determinant maximizing completion and was shown to be the unique completion that has zeros in its inverse in the positions corresponding to the unspecified entries of the partial matrix. Here, we show the same using only matrix/graph theoretic tools.     

Completion problem with partial correlation vines

This paper extends the results in [D. Kurowicka, R.M. Cooke, A parametrization of positive definite matrices in terms of partial correlation vines, Linear Algebra Appl. 372 (2003) 225-251]. We show that a partial correlation vine represents a factorization of the determinant of the correlation matrix. We show that the graph of an incompletely specified correlation matrix is chordal if and only if it can be represented as an m-saturated incomplete vine, that is, an incomplete vine for which all edges corresponding to membership-descendents (m-descendents for short) of a specified edge are specified. This enables us to find the set of completions, and also the completion with maximal determinant for matrices corresponding to chordal graphs.     

A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices

Agler, Helton, McCullough, and Rodman proved that a graph is chordal if and only if any positive semidefinite (PSD) symmetric matrix, whose nonzero entries are specified by a given graph, can be decomposed as a sum of PSD matrices corresponding to the maximal cliques. This decomposition is recently exploited to solve positive semidefinite programming efficiently. Their proof is based on a characterization for PSD matrix completion of a chordal-structured matrix due to Grone, Johnson, Sá, and Wolkowicz. This note gives a direct and simpler proof for the result of Agler et al., which leads to an alternative proof of Grone et al.     

The completely positive and doubly nonnegative completion problems

We prove the following. Let G be an undirected graph. Every partially specified symmetric matrix, the graph of whose specified entries is G and each of whose fully specified submatrices is completely positive (equal to BB^T for some entrywise nonnegative matrix B), may be completed to a completely positive matrix if and only if G is a block-clique graph (a chordal graph in which distinct maximal cliques overlap in at most one vertex). The same result holds for matrices that are doubly nonnegative (entrywise nonnegative and positive semidefinite).     

Singular, nonsingular, and bounded rank completions of ACI-matrices

An affine column independent matrix is a matrix whose entries are polynomials of degree at most 1 in a number of indeterminates where no indeterminate appears with a nonzero coefficient in two different columns. A completion is a matrix obtained by giving values to each of the indeterminates. Affine column independent matrices are more general than partial matrices where each entry is either a constant or a distinct indeterminate. We determine when the rank of all completions of an affine column independent matrix is bounded by a given number, generalizing known results for partial matrices. We also characterize the square partial matrices over a field all of whose completions are nonsingular. The maximum number of free entries in such matrices of a given order is determined as well as the partial matrices with this maximum number of free entries.     

The elliptic matrix completion problem

Completions of partial elliptic matrices are studied. Given an undirected graph G, it is shown that every partial elliptic matrix with graph G can be completed to an elliptic matrix if and only if the maximal cliques of G are pairwise disjoint. Further, given a partial elliptic matrix A with undirected graph G, it is proved that if G is chordal and each specified principal submatrix defined by a pair of intersecting maximal cliques is nonsingular, then A can be completed to an elliptic matrix. Conversely, if G is nonchordal or if the regularity condition is relaxed, it is shown that there exist partial elliptic matrices which are not completable to an elliptic matrix. In the process we obtain several results concerning chordal graphs that may be of independent interest.     

Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming

Let G=(V,E) be a graph. In matrix completion theory, it is known that the following two conditions are equivalent: (i) G is a chordal graph; (ii) Every G-partial positive semidefinite matrix has a positive semidefinite matrix completion. In this paper, we relate these two conditions to constraint nondegeneracy condition in semidefinite programming and prove that they are each equivalent to (iii) For any G-partial positive definite matrix that has a positive semidefinite completion, constraint nondegeneracy is satisfied at each of its positive semidefinite matrix completions.     

Completely positive completion of partial matrices whose entries are completely bounded maps

We study completion problems of partial matrices associated with a graph where entries are completely bounded maps on aC ^*-algebra. We characterize a graph for which every -partial completely positive matrix has a completely positive completion. As a special case we study -partial functional matrices. We give a necessary and sufficient condition for a -partial functional matrix to have a positive completion and a representation for such matrices. These generalize some results on inflated Schur product maps due to Paulsen, Power and Smith. As an application, we study completely positive completions of partial matrices whose entries are completely bounded multipliers of the Fourier algebra of a locally compact group.     

Subdirect sums of P(P0)-matrices and totally nonnegative matrices

In this paper, the problem of when the sub-direct sum of two strictly diagonally dominant P-matrices is a strictly diagonally dominant P-matrix is studied. In particular, it is shown that the subdirect sum of overlapping principal submatrices of strictly diagonally dominant P-matrices is a strictly diagonally dominant P-matrix. It is also established that the 2-subdirect sum of two totally nonnegative matrices is a totally nonnegative matrix under some conditions. It is obtained that a partial totally nonnegative matrix, whose graph of the specified entries is a monotonically labeled 2-chordal graph, has a totally nonnegative completion. Finally, a positive answer to the question (IV) in Fallat and Johnson [Shaun M. Fallat, C.R. Johnson, J.R. Torregrosa, A.M. Urbano, P-matrix completions under weak symmetry assumptions, Linear Algebra Appl. 312 (2000) 73-91] is given for P₀-matrices.     

矩阵方程X-A~*X~(-1)A=Q的Hermite正定解及其扰动分析

考虑非线性矩阵方程X-A*X-1A=Q,其中A是n阶复矩阵,Q是n阶Hermite正定解,A*是矩阵A的共轭转置.本文证明了此方程存在唯一的正定解,并推导出此正定解的扰动边界和条件数的显式表达式.以上结果用数值例子加以说明.     

Matrix Completions and Chordal Graphs

In a matrix-completion problem the aim is to specifiy the missing entries of a matrix in order to produce a matrix with particular properties. In this paper we survey results concerning matrix-completion problems where we look for completions of various types for partial matrices supported on a given pattern. We see that the existence of completions of the required type often depends on the chordal properties of graphs associated with the pattern.     

非负定阵元素的扰动和正定完备化

在保持非负定性不变的前提下,本文对矩阵每一元素容许多大的扰动作了进一步的研究, 将本文的结论和C．R．Johnson提出的部分正定阵的正定完备化进行比较,容易发现对已知的正定矩阵求扰动,本文的结论比用C．R.Johnson的正定完备化计算扰动形式上更简单,同时也给出了不同于C．R．Johnson的部分正定阵的正定完备化表示的另外一个公式,推出了这些正定完备化矩阵应具有的若干性质．     

The symmetric inverse M-matrix completion problem

Necessary and sufficient conditions are given on the data for completability of a partial symmetric inverse M-matrix, the graph of whose specified entries is a cycle, and these conditions coincide with those we identify to be necessary in the general (nonsymmetric) case. Graphs for which all partial symmetric inverse M-matrices have symmetric inverse M-matrix completions are identified and these include those that arise in the general (positionally symmetric) case. However, the identification of all such graphs is more subtle than the general case. Finally, we show that our new cycle conditions are sufficient for completability of all partial symmetric inverse M-matrices, the graph of whose specified entries is a block graph.     

Complete controllability and contractibility in multimodal systems

The concept of a strictly positive definite set of Hermitian matrices is introduced. It is shown that a strictly positive definite set is always a positive definite set, and conditions are found under which a positive definite set is strictly positive definite. We also show that a set of Hermitian matrices is strictly positive definite if and only if some nonnegative linear combination of these matrices is a positive definite matrix. For state dimension two, we use this concept to find necessary and sufficient conditions for a two-mode completely controllable irreducible multimodal system to be contractible relative to an elliptic norm. For general state dimensions, we give necessary and sufficient conditions for a special-type two-mode completely controllable irreducible system to be contractible relative to a weakly monotone norm. Applying the above results, we show that, for state dimension two, there exists a completely controllable two-mode system which is not contractible relative to either an elliptic or a weakly monotone norm. We leave open the question whether or not complete controllability implies contractibility, relative to some norm, for multimodal systems of two or more modes.     

Superoptimal completions of triangular matrices

We construct the unique completion of a partial triangular matrix with compact operator entries that has the property that its sequence of singular values is minimal in lexicographical order among all completions. In addition some partial results regarding the singular values of this superoptimal completion are presented.The research was done while the author visited the Department of Mathematics at the George Washington University.Supported by the College of William and Mary     

Matrices with chordal inverse zero-patterns

We study matrices whose inverses exhibit a sparsity pattern that may be described with a chordal graph. Such matrices are characterized in terms of a special vanishing-minor structure, and an explicit entry-wise formula that is useful in certain matrix completion problems is derived.We also study an interesting graph-inheritance principle in the context of chordal graphs.