Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without K5 minors
MetadataShow full item record
For a graph G with p vertices the closed convex cone S≽0(G) consists of all real positive semidefinite p × p matrices whose sparsity pattern is given by G, that is, those matrices with zeros in the off-diagonal entries corresponding to nonedges of G. The extremal rays of this cone and their associated ranks have applications to matrix completion problems, maximum likelihood estimation in Gaussian graphical models in statistics, and Gauss elimination for sparse matrices. While the maximum rank of an extremal ray in S≽0(G), known as the sparsity order of G, has been characterized for different classes of graphs, we here study all possible extremal ranks of S≽0(G). We investigate when the geometry of the (±1)-cut polytope of G yields a polyhedral characterization of the set of extremal ranks of S≽0(G). For a graph G without K5 minors, we show that appropriately chosen normal vectors to the facets of the (±1)-cut polytope of G specify the off-diagonal entries of extremal matrices in S≽0(G). We also prove that for appropriately chosen scalars the constant term of the linear equation of each facet-supporting hyperplane is the rank of its corresponding extremal matrix in S≽0(G). Furthermore, we show that if G is series-parallel then this gives a complete characterization of all possible extremal ranks of S≽0(G). Consequently, the sparsity order problem for series-parallel graphs can be solved in terms of polyhedral geometry.
The article of record as published may be found at http://dx.doi.org/10.1016/j.laa.2016.07.026
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Gonen, Amnon (Monterey, California. Naval Postgraduate School, 1984-06); NPS-53-84-0006The evaluation of the matrix product A *A or A *D*A, where A is an raxn real matrix and D an mxm diagonal matrix, is a fundamental operation for many algorithms. We analyze the evaluation of A *A for several configurations ...
Kang, Wei; Xu, Liang (ArXiv, 2018-10);Several variations of the Kalman filter algorithm, such as the extended Kalman filter (EKF) and the unscented Kalman filter (UKF), are widely used in science and engineering applications. In this paper, we introduce two ...
Bretschneider, Guenter W. (1985-09);An algorithm to solve linear programming problems is presented which is based on Karmarkar's projective method. The algorithm includes a practical method to project a general linear programming problem onto a unit simplex ...