---
_id: '1293'
abstract:
- lang: eng
text: 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.
acknowledgement: We wish to thank Alexander Engström and Bernd Sturmfels for various
valuable discussions and insights. We also thank the two anonymous referees for
their thoughtful feedback on the paper. CU was partially supported by the Austrian
Science Fund (FWF) Y 903-N35.
author:
- first_name: Liam T
full_name: Solus, Liam T
id: 2AADA620-F248-11E8-B48F-1D18A9856A87
last_name: Solus
- first_name: Caroline
full_name: Uhler, Caroline
id: 49ADD78E-F248-11E8-B48F-1D18A9856A87
last_name: Uhler
orcid: 0000-0002-7008-0216
- first_name: Ruriko
full_name: Yoshida, Ruriko
last_name: Yoshida
citation:
ama: Solus LT, Uhler C, Yoshida R. Extremal positive semidefinite matrices whose
sparsity pattern is given by graphs without K5 minors. *Linear Algebra and Its
Applications*. 2016;509:247-275. doi:10.1016/j.laa.2016.07.026
apa: Solus, L. T., Uhler, C., & Yoshida, R. (2016). Extremal positive semidefinite
matrices whose sparsity pattern is given by graphs without K5 minors. *Linear
Algebra and Its Applications*, *509*, 247–275. https://doi.org/10.1016/j.laa.2016.07.026
chicago: 'Solus, Liam T, Caroline Uhler, and Ruriko Yoshida. “Extremal Positive
Semidefinite Matrices Whose Sparsity Pattern Is given by Graphs without K5 Minors.”
*Linear Algebra and Its Applications* 509 (2016): 247–75. https://doi.org/10.1016/j.laa.2016.07.026.'
ieee: L. T. Solus, C. Uhler, and R. Yoshida, “Extremal positive semidefinite matrices
whose sparsity pattern is given by graphs without K5 minors,” *Linear Algebra
and Its Applications*, vol. 509, pp. 247–275, 2016.
ista: Solus LT, Uhler C, Yoshida R. 2016. Extremal positive semidefinite matrices
whose sparsity pattern is given by graphs without K5 minors. Linear Algebra and
Its Applications. 509, 247–275.
mla: Solus, Liam T., et al. “Extremal Positive Semidefinite Matrices Whose Sparsity
Pattern Is given by Graphs without K5 Minors.” *Linear Algebra and Its Applications*,
vol. 509, Elsevier, 2016, pp. 247–75, doi:10.1016/j.laa.2016.07.026.
short: L.T. Solus, C. Uhler, R. Yoshida, Linear Algebra and Its Applications 509
(2016) 247–275.
date_created: 2018-12-11T11:51:11Z
date_published: 2016-11-15T00:00:00Z
date_updated: 2020-01-21T13:17:09Z
day: '15'
department:
- _id: CaUh
doi: 10.1016/j.laa.2016.07.026
intvolume: ' 509'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/pdf/1506.06702.pdf
month: '11'
oa: 1
oa_version: Preprint
page: 247 - 275
project:
- _id: 2530CA10-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Y 903-N35
name: 'Gaussian Graphical Models: Theory and Applications'
publication: Linear Algebra and Its Applications
publication_status: published
publisher: Elsevier
publist_id: '6024'
quality_controlled: '1'
status: public
title: Extremal positive semidefinite matrices whose sparsity pattern is given by
graphs without K5 minors
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 509
year: '2016'
...