Variants on the minimum rank problem: A survey II

Abstract

The minimum rank problem for a (simple) graph $G$ is to determine the smallest possible rank over all real symmetric matrices whose $ij$th entry (for $i\ne j$) is nonzero whenever $\{i,j\}$ is an edge in $G$ and is zero otherwise. This paper surveys the many developments on the (standard) minimum rank problem and its variants since the survey paper \cite{FH}. In particular, positive semidefinite minimum rank, zero forcing parameters, and minimum rank problems for patterns are discussed.

3 figures This survey was originally posted in Feb. 2011. However, this paper is now outdated and interested readers should consult Chapter 46 of the Handbook of Linear Algebra, 2nd Edition for a more recent and comprehensive survey