Bounds for minimum semidefinite rank from superpositions and cutsets

Jonathan Beagley, Lon H. Mitchell, Sivaram K. Narayan, Eileen Radzwion, Sara P. Rimer, Rachael Tomasino, Jennifer Wolfe, Andrew M. Zimmer

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The real (complex) minimum semidefinite rank of a graph is the minimum rank among all real symmetric (complex Hermitian) positive semidefinite matrices that are naturally associated via their zero-nonzero pattern to the given graph. In this paper we give an upper bound on the minimum semidefinite rank of a graph when the graph is modified from the superposition of two graphs by cancelling some number of edges. We also provide a lower bound for the minimum semidefinite rank of a graph determined by a given cutset. When the complement of the cutset is a star forest these lower and upper bounds coincide and we can compute the minimum semidefinite rank in terms of smaller graphs. This result encompasses the previously known case in which the cut set has order two or smaller. Next we provide results for when the cut set has order three. Using these results we provide an example where the positive semidefinite zero forcing number is strictly greater than the maximum positive semidefinite nullity.

Original languageEnglish
Pages (from-to)4041-4061
Number of pages21
JournalLinear Algebra and Its Applications
Volume438
Issue number10
DOIs
StatePublished - May 15 2013

Keywords

  • Cutsets
  • Minimum semidefinite rank
  • Superposition of graphs
  • Vector representation of a graph

Fingerprint

Dive into the research topics of 'Bounds for minimum semidefinite rank from superpositions and cutsets'. Together they form a unique fingerprint.

Cite this