Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4602745 | Linear Algebra and its Applications | 2008 | 11 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory