| Title:
|
Rational realization of the minimum ranks of nonnegative sign pattern matrices (English) |
| Author:
|
Fang, Wei |
| Author:
|
Gao, Wei |
| Author:
|
Gao, Yubin |
| Author:
|
Gong, Fei |
| Author:
|
Jing, Guangming |
| Author:
|
Li, Zhongshan |
| Author:
|
Shao, Yanling |
| Author:
|
Zhang, Lihua |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
66 |
| Issue:
|
3 |
| Year:
|
2016 |
| Pages:
|
895-911 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
sign pattern (matrix) |
| Keyword:
|
nonnegative sign pattern |
| Keyword:
|
minimum rank |
| Keyword:
|
convex polytope |
| Keyword:
|
rational minimum rank |
| Keyword:
|
rational realization |
| Keyword:
|
integer matrix |
| Keyword:
|
condensed sign pattern |
| Keyword:
|
point-hyperplane configuration |
| MSC:
|
15A23 |
| MSC:
|
15B35 |
| MSC:
|
15B36 |
| MSC:
|
52C35 |
| idZBL:
|
Zbl 06644040 |
| idMR:
|
MR3556874 |
| DOI:
|
10.1007/s10587-016-0299-1 |
| . |
| Date available:
|
2016-10-01T15:33:56Z |
| Last updated:
|
2023-10-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145878 |
| . |
| Reference:
|
[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. |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 1157.15020, MR 2460493 |
| Reference:
|
[4] Arav, M., Hall, F., Li, Z., Rao, B.: Rational solutions of certain matrix equations.Linear Algebra Appl. 430 (2009), 660-663. Zbl 1166.15005, MR 2469319 |
| Reference:
|
[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. MR 3386529, 10.13001/1081-3810.3077 |
| Reference:
|
[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. Zbl 1179.05070, MR 2383445 |
| Reference:
|
[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. |
| Reference:
|
[8] Brualdi, R. A., Shader, B. L.: Matrices of Sign-Solvable Linear Systems.Cambridge Tracts in Mathematics 116 Cambridge University Press, Cambridge (1995). Zbl 0833.15002, MR 1358133 |
| Reference:
|
[9] Chen, G., Hall, F. J., Li, Z., Wei, B.: On ranks of matrices associated with trees.Graphs Comb. 19 (2003), 323-334. Zbl 1023.05093, MR 2007894, 10.1007/s00373-002-0522-8 |
| Reference:
|
[10] Delsarte, P., Kamp, Y.: Low rank matrices with a given sign pattern.SIAM J. Discrete Math. 2 (1989), 51-63. Zbl 0677.15007, MR 0976788, 10.1137/0402006 |
| Reference:
|
[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. |
| Reference:
|
[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. Zbl 1310.15057, MR 3314328 |
| Reference:
|
[13] Forster, J.: A linear lower bound on the unbounded error probabilistic communication complexity.J. Comput. Syst. Sci. 65 (2002), 612-625. Zbl 1058.68058, MR 1964645, 10.1016/S0022-0000(02)00019-3 |
| Reference:
|
[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. Zbl 1026.68112, MR 2042049, 10.1023/A:1022905618164 |
| Reference:
|
[15] Friesen, M., Hamed, A., Lee, T., Theis, D. O.: Fooling-sets and rank.Eur. J. Comb. (2015), 143-153. Zbl 1314.05028, MR 3339019 |
| Reference:
|
[16] Graham, R. L., Grötschel, M., Lovász, L., eds.: Handbook of Combinatorics.MIT Press, Cambridge (1995). |
| Reference:
|
[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). |
| Reference:
|
[18] Hershkowitz, D., Schneider, H.: Ranks of zero patterns and sign patterns.Linear Multilinear Algebra 34 (1993), 3-19. Zbl 0793.05027, MR 1334927, 10.1080/03081089308818204 |
| Reference:
|
[19] Johnson, C. R.: Some outstanding problems in the theory of matrices.Linear Multilinear Algebra 12 (1982), 99-108. Zbl 0494.15002, MR 0670716, 10.1080/03081088208817476 |
| Reference:
|
[20] Johnson, C. R., Zhang, Y.: On the possible ranks among matrices with a given pattern.Discrete Math. Algorithms Appl. 2 (2010), 363-377. Zbl 1210.15002, MR 2728832, 10.1142/S1793830910000711 |
| Reference:
|
[21] Kopparty, S., Rao, K. P. S. B.: The minimum rank problem: a counterexample.Linear Algebra Appl. 428 (2008), 1761-1765. Zbl 1151.15002, MR 2388655 |
| Reference:
|
[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. MR 3175334, 10.1080/03081087.2012.716431 |
| Reference:
|
[23] Matoušek, J.: Lectures on Discrete Geometry.Graduate Texts in Mathematics 212 Springer, New York (2002). Zbl 0999.52006, MR 1899299 |
| Reference:
|
[24] Paturi, R., Simon, J.: Probabilistic communication complexity.J. Comput. Syst. Sci. 33 (1986), 106-123. Zbl 0625.68029, MR 0864082, 10.1016/0022-0000(86)90046-2 |
| Reference:
|
[25] Razborov, A. A., Sherstov, A. A.: The sign rank of AC$^0$.SIAM J. Comput. 39 (2010), 1833-1855. Zbl 1211.68213, MR 2592035, 10.1137/080744037 |
| Reference:
|
[26] Mor, A. Ribó, Rote, G., Schulz, A.: Small grid embeddings of 3-polytopes.Discrete Comput. Geom. 45 (2011), 65-87. MR 2765520, 10.1007/s00454-010-9301-0 |
| Reference:
|
[27] Shitov, Y.: Sign patterns of rational matrices with large rank.Eur. J. Comb. 42 (2014), 107-111. Zbl 1314.15022, MR 3240139, 10.1016/j.ejc.2014.06.001 |
| Reference:
|
[28] Ziegler, G. M.: Lectures on Polytopes.Graduate Texts in Mathematics 152 Springer, Berlin (1995). Zbl 0823.52002, MR 1311028 |
| . |
