Degree Type
Dissertation
Date of Award
2017
Degree Name
Doctor of Philosophy
Department
Mathematics
Major
Mathematics
First Advisor
Leslie Hogben
Second Advisor
Steve Butler
Abstract
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.
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.
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.
DOI
https://doi.org/10.31274/etd-180810-4977
Copyright Owner
Chin-Hung Lin
Copyright Date
2017
Language
en
File Format
application/pdf
File Size
75 pages
Recommended Citation
Lin, Chin-Hung, "Variants of zero forcing and their applications to the minimum rank problem" (2017). Graduate Theses and Dissertations. 15349.
https://lib.dr.iastate.edu/etd/15349