A new lower bound for the positive semidefinite minimum rank of a graph. (English) Zbl 1257.05092
Summary: The real positive semidefinite minimum rank of a graph is the minimum rank among all real positive semidefinite matrices that are naturally associated via their zero-nonzero pattern to the given graph.
In this paper, we use orthogonal vertex removal and sign patterns to improve the lower bound for the real positive semidefinite minimum rank determined by the OS-number and the positive semidefinite zero forcing number.
In this paper, we use orthogonal vertex removal and sign patterns to improve the lower bound for the real positive semidefinite minimum rank determined by the OS-number and the positive semidefinite zero forcing number.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15A03 | Vector spaces, linear dependence, rank, lineability |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 15B35 | Sign pattern matrices |
| 15B57 | Hermitian, skew-Hermitian, and related matrices |
Keywords:
positive semidefinite minimum rank; minimum rank; sign patterns; zero forcing number; positive semidefinite zero forcing number; ordered set numberReferences:
| [1] | Barioli, Francesco; Barrett, Wayne; Fallat, Shaun M.; Tracy Hall, H.; Hogben, Leslie; Shader, Bryan; van den Driessche, P.; Holst, Hein van der, Zero forcing parameters and minimum rank problems, Linear Algebra Appl., 433, 2, 401-411 (2010) · Zbl 1209.05139 |
| [2] | Barioli, Francesco; Barrett, Wayne; Fallat, Shaun M.; Tracy Hall, H.; Hogben, Leslie; Holst, Hein van der, On the graph complement conjecture for minimum rank, Linear Algebra Appl., 436, 12, 4373-4391 (2012), Special Issue on Matrices Described by Patterns · Zbl 1241.05064 |
| [3] | Booth, Matthew; Hackney, Philip; Harris, Benjamin; Johnson, Charles R.; Lay, Margaret; Lenker, Terry; Mitchell, Lon H.; Narayan, Sivaram K.; Pascoe, Amanda; Sutton, Brian D., On the minimum semidefinite rank of a simple graph, Linear and Multilinear Algebra, 59, 5, 483-506 (2011) · Zbl 1223.05170 |
| [4] | Booth, Matthew; Hackney, Philip; Harris, Benjamin; Johnson, Charles R.; Lay, Margaret; Mitchell, Lon H.; Narayan, Sivaram K.; Pascoe, Amanda; Steinmetz, Kelly; Sutton, Brian D.; Wang, Wendy, On the minimum rank among positive semidefinite matrices with a given graph, SIAM J. Matrix Anal. Appl., 30, 2, 731-740 (2008) · Zbl 1226.05151 |
| [5] | DeAlba, Luz Maria; Hardy, Timothy L.; Hentzel, Irvin Roy; Hogben, Leslie; Wangsness, Amy, Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns, Linear Algebra Appl., 418, 2-3, 394-415 (2006) · Zbl 1106.05059 |
| [6] | Ekstrand, Jason; Erickson, Craig; Hay, Diana; Hogben, Leslie; Roat, Jolie, Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial 2-trees, Electron. J. Linear Algebra, 23, 79-87 (2012) · Zbl 1252.05118 |
| [7] | Fallat, Shaun M.; Hogben, Leslie, The minimum rank of symmetric matrices described by a graph: a survey, Linear Algebra Appl., 426, 2-3, 558-582 (2007) · Zbl 1122.05057 |
| [8] | Shaun M. Fallat, Leslie Hogben, Variants on the minimum rank problem: a survey II, preprint, 2011. · Zbl 1122.05057 |
| [9] | AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428, 7, 1628-1648 (2008) · Zbl 1135.05035 |
| [10] | Hackney, Philip; Harris, Benjamin; Lay, Margaret; Mitchell, Lon H.; Narayan, Sivaram K.; Pascoe, Amanda, Linearly independent vertices and minimum semidefinite rank, Linear Algebra Appl., 431, 8, 1105-1115 (2009) · Zbl 1188.05085 |
| [11] | Hall, Frank J.; Li, Zhongshan, Sign pattern matrices, (Hogben, Leslie, Handbook of Linear Algebra. Handbook of Linear Algebra, Discrete Mathematics and its Applications (Boca Raton) (2007), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton, FL) · Zbl 0997.15010 |
| [12] | Hogben, Leslie, A note on minimum rank and maximum nullity of sign patterns, Electron. J. Linear Algebra, 22, 203-213 (2011) · Zbl 1223.15037 |
| [13] | Satyanarayana V. Lokam, Complexity lower bounds using linear algebra, Foundations and Trends® in Theoretical Computer Science 4(1-2):front matter, 1-155 (2009), 2008. · Zbl 1176.68084 |
| [14] | Mitchell, Lon H.; Narayan, Sivaram K.; Zimmer, Andrew M., Lower bounds in minimum rank problems, Linear Algebra Appl., 432, 1, 430-440 (2010) · Zbl 1220.05077 |
| [15] | Mitchell, Lon H.; Narayan, Sivaram K.; Zimmer, Andrew M., Lower bounds for minimum semidefinite rank from orthogonal removal and chordal supergraphs, Linear Algebra Appl., 436, 3, 525-536 (2012) · Zbl 1229.05204 |
| [16] | Parsons, T. D.; Pisanski, Tomaž, Vector representations of graphs, Discrete Math., 78, 1-2, 143-154 (1989) · Zbl 0693.05058 |
| [17] | Šiňajová, Edita, A note on vector representation of graphs, Discrete Math., 89, 3, 315-317 (1991) · Zbl 0752.05053 |
| [18] | Holst, Hein van der, On the maximum positive semi-definite nullity and the cycle matroid of graphs, Electron. J. Linear Algebra, 18, 192-201 (2009) · Zbl 1173.05031 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
