Variants of zero forcing and their applications to the minimum rank problem

Abstract

<p>The minimum rank problem refers to finding the smallest possible rank, or equivalently the largest possible nullity, among matrices under certain restrictions. These restrictions can be the zero-nonzero pattern, conditions on the inertia, or other properties of a matrix. Zero forcing is a powerful technique for controlling the nullity and plays a significant role in the minimum rank problem. This thesis introduces several zero forcing parameters and their applications on the minimum rank problem.</p> <p>Zero-nonzero patterns can be described by graphs: The edges (including the loops) represent the nonzero entries, while the non-edges correspond to the zero entries. For simple graphs, where no loops are allowed, the diagonal entries can be any real numbers. The maximum nullity of a graph is the maximum nullity among symmetric matrices with the pattern described by the graph. In Chapter 2, the odd cycle zero forcing number Zoc(G) and the enhanced odd cycle zero forcing number Ẑoc(G) are introduced as bounds for the maximum nullities of loop graphs G and simple graphs G, respectively. Also, a relation between loop graphs and simple graphs through graph blowups is developed.</p> <p>The Colin de Verdià  à ¨re type parameter ξ(G) is defined as the maximum nullity of real symmetric matrices A with the pattern described by G and with the Strong Arnold Property (SAP), which means X = O is the only symmetric matrix that satisfies A ○ X = I ○ X = AX = O (here ○ is the entrywise product). Chapter 3 introduces zero forcing parameters Zsap(G) and Zvc(G); we show that Zsap(G) = 0 implies every symmetric matrix with the pattern described by G has the SAP and that the inequality M(G) − Zvc(G) ≤ ξ(G) holds for every graph G. Also, the values of ξ(G) are computed for all graphs up to 7 vertices, establishing ξ(G) = ⌊Z⌋(G) for these graphs.</p>