Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
sign pattern (matrix); nonnegative sign pattern; minimum rank; convex polytope; rational minimum rank; rational realization; integer matrix; condensed sign pattern; point-hyperplane configuration
sign pattern (matrix); nonnegative sign pattern; minimum rank; convex polytope; rational minimum rank; rational realization; integer matrix; condensed sign pattern; point-hyperplane configuration
Summary:
A sign pattern matrix (or nonnegative sign pattern matrix) is a matrix whose entries are from the set $\{+, -, 0\}$ ($ \{ +, 0 \}$, respectively). The minimum rank (or rational minimum rank) of a sign pattern matrix $\cal A$ is the minimum of the ranks of the matrices (rational matrices, respectively) whose entries have signs equal to the corresponding entries of $\cal A$. Using a correspondence between sign patterns with minimum rank $r\geq 2$ and point-hyperplane configurations in $\mathbb R^{r-1}$ and Steinitz's theorem on the rational realizability of 3-polytopes, it is shown that for every nonnegative sign pattern of minimum rank at most 4, the minimum rank and the rational minimum rank are equal. But there are nonnegative sign patterns with minimum rank 5 whose rational minimum rank is greater than 5. It is established that every $d$-polytope determines a nonnegative sign pattern with minimum rank $d+1$ that has a $(d+1)\times (d+1)$ triangular submatrix with all diagonal entries positive. It is also shown that there are at most $\min \{ 3m, 3n \}$ zero entries in any condensed nonnegative $m \times n$ sign pattern of minimum rank 3. Some bounds on the entries of some integer matrices achieving the minimum ranks of nonnegative sign patterns with minimum rank 3 or 4 are established.
References:
[1] Alon, N., Frankl, P., Rödl, V.: Geometric realization of set systems and probabilistic communication complexity. Proc. 26th Annual Symp. on Foundations of Computer Science IEEE Computer Society, Portland (1985),272-280.
[2] Arav, M., Hall, F., Koyuncu, S., Li, Z., Rao, B.: Rational realizations of the minimum rank of a sign pattern matrix. Linear Algebra Appl. 409 (2005), 111-125. MR 2170271
[3] Arav, M., Hall, F., Li, Z., Merid, A., Gao, Y.: Sign patterns that require almost unique rank. Linear Algebra Appl. 430 (2009), 7-16. MR 2460493 | Zbl 1157.15020
[4] Arav, M., Hall, F., Li, Z., Rao, B.: Rational solutions of certain matrix equations. Linear Algebra Appl. 430 (2009), 660-663. MR 2469319 | Zbl 1166.15005
[5] Arav, M., Hall, F., Li, Z., Holst, H. van der, Sinkovic, J. H., Zhang, L.: Minimum ranks of sign patterns via sign vectors and duality. Electron. J. Linear Algebra 30 (2015), 360-371. DOI 10.13001/1081-3810.3077 | MR 3386529
[6] Berman, A., Friedland, S., Hogben, L., Rothblum, U. G., Shader, B.: Minimum rank of matrices described by a graph or pattern over the rational, real and complex numbers. Electron. J. Comb. 15 (2008), 1-19. MR 2383445 | Zbl 1179.05070
[7] Brualdi, R., Fallat, S., Hogben, L., Shader, B., Driessche, P. van den: Final Report: Workshop on Theory and Applications of Matrices described by Patterns. Banff International Research Station (2010),20 pages.
[8] Brualdi, R. A., Shader, B. L.: Matrices of Sign-Solvable Linear Systems. Cambridge Tracts in Mathematics 116 Cambridge University Press, Cambridge (1995). MR 1358133 | Zbl 0833.15002
[9] Chen, G., Hall, F. J., Li, Z., Wei, B.: On ranks of matrices associated with trees. Graphs Comb. 19 (2003), 323-334. DOI 10.1007/s00373-002-0522-8 | MR 2007894 | Zbl 1023.05093
[10] Delsarte, P., Kamp, Y.: Low rank matrices with a given sign pattern. SIAM J. Discrete Math. 2 (1989), 51-63. DOI 10.1137/0402006 | MR 0976788 | Zbl 0677.15007
[11] Fang, W., Gao, W., Gao, Y., Gong, F., Jing, G., Li, Z., Shao, Y., Zhang, L.: Minimum ranks of sign patterns and zero-nonzero patterns and point-hyperplane configurations. Submitted to Linear Algebra Appl.
[12] Fiedler, M., Gao, W., Hall, F. J., Jing, G., Li, Z., Stroev, M.: Ranks of dense alternating sign matrices and their sign patterns. Linear Algebra Appl. 471 (2015), 109-121. MR 3314328 | Zbl 1310.15057
[13] Forster, J.: A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci. 65 (2002), 612-625. DOI 10.1016/S0022-0000(02)00019-3 | MR 1964645 | Zbl 1058.68058
[14] Forster, J., Schmitt, N., Simon, H. U., Suttorp, T.: Estimating the optimal margins of embeddings in Euclidean half spaces. Mach. Learn. 51 (2003), 263-281. DOI 10.1023/A:1022905618164 | MR 2042049 | Zbl 1026.68112
[15] Friesen, M., Hamed, A., Lee, T., Theis, D. O.: Fooling-sets and rank. Eur. J. Comb. (2015), 143-153. MR 3339019 | Zbl 1314.05028
[16] Graham, R. L., Grötschel, M., Lovász, L., eds.: Handbook of Combinatorics. MIT Press, Cambridge (1995).
[17] Hall, F. J., Li, Z.: Sign Pattern Matrices. Handbook of Linear Algebra L. Hogben Discrete Mathematics and Its Applications Chapman & Hall/CRC, Boca Raton (2014).
[18] Hershkowitz, D., Schneider, H.: Ranks of zero patterns and sign patterns. Linear Multilinear Algebra 34 (1993), 3-19. DOI 10.1080/03081089308818204 | MR 1334927 | Zbl 0793.05027
[19] Johnson, C. R.: Some outstanding problems in the theory of matrices. Linear Multilinear Algebra 12 (1982), 99-108. DOI 10.1080/03081088208817476 | MR 0670716 | Zbl 0494.15002
[20] Johnson, C. R., Zhang, Y.: On the possible ranks among matrices with a given pattern. Discrete Math. Algorithms Appl. 2 (2010), 363-377. DOI 10.1142/S1793830910000711 | MR 2728832 | Zbl 1210.15002
[21] Kopparty, S., Rao, K. P. S. B.: The minimum rank problem: a counterexample. Linear Algebra Appl. 428 (2008), 1761-1765. MR 2388655 | Zbl 1151.15002
[22] Li, Z., Gao, Y., Arav, M., Gong, F., Gao, W., Hall, F. J., Holst, H. van der: Sign patterns with minimum rank 2 and upper bounds on minimum ranks. Linear Multilinear Algebra 61 (2013), 895-908. DOI 10.1080/03081087.2012.716431 | MR 3175334
[23] Matoušek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics 212 Springer, New York (2002). MR 1899299 | Zbl 0999.52006
[24] Paturi, R., Simon, J.: Probabilistic communication complexity. J. Comput. Syst. Sci. 33 (1986), 106-123. DOI 10.1016/0022-0000(86)90046-2 | MR 0864082 | Zbl 0625.68029
[25] Razborov, A. A., Sherstov, A. A.: The sign rank of AC$^0$. SIAM J. Comput. 39 (2010), 1833-1855. DOI 10.1137/080744037 | MR 2592035 | Zbl 1211.68213
[26] Mor, A. Ribó, Rote, G., Schulz, A.: Small grid embeddings of 3-polytopes. Discrete Comput. Geom. 45 (2011), 65-87. DOI 10.1007/s00454-010-9301-0 | MR 2765520
[27] Shitov, Y.: Sign patterns of rational matrices with large rank. Eur. J. Comb. 42 (2014), 107-111. DOI 10.1016/j.ejc.2014.06.001 | MR 3240139 | Zbl 1314.15022
[28] Ziegler, G. M.: Lectures on Polytopes. Graduate Texts in Mathematics 152 Springer, Berlin (1995). MR 1311028 | Zbl 0823.52002
Search
Partner of
