Computing positive semidefinite minimum rank for small graphs

Osborne, Steven; Warnberg, Nathan

doi:10.2140/involve.2014.7.595

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Computing positive semidefinite minimum rank for small graphs

Steven Osborne and Nathan Warnberg

Vol. 7 (2014), No. 5, 595–609

DOI: 10.2140/involve.2014.7.595

Abstract

The positive semidefinite minimum rank of a simple graph $G$ is defined to be the smallest possible rank over all positive semidefinite real symmetric matrices whose $i j$ -th entry (for $i \neq j$ ) is nonzero whenever ${i, j}$ is an edge in $G$ and is zero otherwise. The computation of this parameter directly is difficult. However, there are a number of known bounding parameters and techniques which can be calculated and performed on a computer. We programmed an implementation of these bounds and techniques in the open-source mathematical software Sage. The program, in conjunction with the orthogonal representation method, establishes the positive semidefinite minimum rank for all graphs of order $7$ or less.

Keywords

zero forcing number, maximum nullity, minimum rank, positive semidefinite, zero forcing, graph, matrix

Mathematical Subject Classification 2010

Primary: 05C50

Secondary: 15A03

Milestones

Received: 19 July 2011

Revised: 13 December 2011

Accepted: 12 December 2013

Published: 1 August 2014

Communicated by Chi-Kwong Li

Authors

Steven Osborne
Department of Mathematics Iowa State University Ames, IA 50011 United States

Nathan Warnberg
Department of Mathematics Iowa State University Ames, IA 50011 United States

Vol. 7, No. 5, 2014