Vol. 7, No. 5, 2014

Download this article
Download this article For screen
For printing
Recent Issues

Volume 17
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
Editors' interests
ISSN (electronic): 1944-4184
ISSN (print): 1944-4176
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

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 ij-th entry (for ij) 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.

zero forcing number, maximum nullity, minimum rank, positive semidefinite, zero forcing, graph, matrix
Mathematical Subject Classification 2010
Primary: 05C50
Secondary: 15A03
Received: 19 July 2011
Revised: 13 December 2011
Accepted: 12 December 2013
Published: 1 August 2014

Communicated by Chi-Kwong Li
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