Unitary Matrix Digraphs and Minimum Semidefinite Rank
For an undirected simple graph G, the minimum rank among all positive semidefinite matrices with graph G is called the minimum semidefinite rank (msr) of G. In this paper, we show that the msr of a given graph may be determined from the msr of a related bipartite graph. Finding the msr of a given bipartite graph is then shown to be equivalent to determining which digraphs encode the zero/nonzero pattern of a unitary matrix. We provide an algorithm to construct unitary matrices with a certain pattern, and use previous results to give a lower bound for the msr of certain bipartite graphs.
Jiang, Y., Mitchell, L., & Narayan, S. (2008). Unitary matrix digraphs and minimum semidefinite rank. Linear Algebra and its Applications, 428)7), 1685-1695. https://doi.org/10.1016/j.laa.2007.10.031.