Positive semidefinite maximum nullity and zero forcing number
Is Version Of
The zero forcing number is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by a simple, undirected graph. We study the positive semidefinite zero forcing number and some of its properties. In addition, we compute the positive semidefinite maximum nullity and zero forcing number for a variety of graph families. We establish the field independence of the hypercube, by showing there is a positive semidefinite matrix that is universally optimal. Given a graph G with some vertices S colored black and the remaining vertices colored white, the positive semidefinite color-change rule is: If W_1, W_2,..., W_k are the sets of vertices of the k components of G-S, w is an element of W_i, u is an element of S, and w is the only white neighbor of u in the subgraph of G induced by W_i union S, then change the color of w to black. The positive semidefinite zero forcing number is the smallest number of vertices needed to be initially colored black so that repeated applications of the positive semidefinite color-change rule will result in all vertices being black. The positive semidefinite zero forcing number is a variant of the (standard) zero forcing number, which uses the same definition except with a different color-change rule: If u is black and w is the only white neighbor of u, then change the color of w to black.