Vol. 7, No. 5, 2014

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

Volume 11
Issue 5, 721–900
Issue 4, 541–720
Issue 3, 361–540
Issue 2, 181–359
Issue 1, 1–179

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
Editorial Board
Editors’ Addresses
Editors’ Interests
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
Author Index
Coming Soon
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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