Rational realization of the minimum ranks of nonnegative sign pattern matrices

Wei Fang; Wei Gao; Yubin Gao; Fei Gong; Guangming Jing; Zhongshan Li; Yan Ling Shao; Lihua Zhang

Czechoslovak Mathematical Journal (2016)

  • Volume: 66, Issue: 3, page 895-911
  • ISSN: 0011-4642

Abstract

top
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 𝒜 is the minimum of the ranks of the matrices (rational matrices, respectively) whose entries have signs equal to the corresponding entries of 𝒜 . Using a correspondence between sign patterns with minimum rank r ≥ 2 and point-hyperplane configurations in ℝ 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 ) × ( d + 1 ) triangular submatrix with all diagonal entries positive. It is also shown that there are at most min { 3 m , 3 n } zero entries in any condensed nonnegative m × 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.

How to cite

top

Fang, Wei, et al. "Rational realization of the minimum ranks of nonnegative sign pattern matrices." Czechoslovak Mathematical Journal 66.3 (2016): 895-911. <http://eudml.org/doc/286800>.

@article{Fang2016,
abstract = {A sign pattern matrix (or nonnegative sign pattern matrix) is a matrix whose entries are from the set $\lbrace +, -, 0\rbrace $ ($ \lbrace +, 0 \rbrace $, respectively). The minimum rank (or rational minimum rank) of a sign pattern matrix $\mathcal \{A\}$ is the minimum of the ranks of the matrices (rational matrices, respectively) whose entries have signs equal to the corresponding entries of $\mathcal \{A\}$. Using a correspondence between sign patterns with minimum rank $r\ge 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 \lbrace 3m, 3n \rbrace $ 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.},
author = {Fang, Wei, Gao, Wei, Gao, Yubin, Gong, Fei, Jing, Guangming, Li, Zhongshan, Shao, Yan Ling, Zhang, Lihua},
journal = {Czechoslovak Mathematical Journal},
keywords = {sign pattern (matrix); nonnegative sign pattern; minimum rank; convex polytope; rational minimum rank; rational realization; integer matrix; condensed sign pattern; point-hyperplane configuration},
language = {eng},
number = {3},
pages = {895-911},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Rational realization of the minimum ranks of nonnegative sign pattern matrices},
url = {http://eudml.org/doc/286800},
volume = {66},
year = {2016},
}

TY - JOUR
AU - Fang, Wei
AU - Gao, Wei
AU - Gao, Yubin
AU - Gong, Fei
AU - Jing, Guangming
AU - Li, Zhongshan
AU - Shao, Yan Ling
AU - Zhang, Lihua
TI - Rational realization of the minimum ranks of nonnegative sign pattern matrices
JO - Czechoslovak Mathematical Journal
PY - 2016
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 66
IS - 3
SP - 895
EP - 911
AB - A sign pattern matrix (or nonnegative sign pattern matrix) is a matrix whose entries are from the set $\lbrace +, -, 0\rbrace $ ($ \lbrace +, 0 \rbrace $, respectively). The minimum rank (or rational minimum rank) of a sign pattern matrix $\mathcal {A}$ is the minimum of the ranks of the matrices (rational matrices, respectively) whose entries have signs equal to the corresponding entries of $\mathcal {A}$. Using a correspondence between sign patterns with minimum rank $r\ge 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 \lbrace 3m, 3n \rbrace $ 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.
LA - eng
KW - sign pattern (matrix); nonnegative sign pattern; minimum rank; convex polytope; rational minimum rank; rational realization; integer matrix; condensed sign pattern; point-hyperplane configuration
UR - http://eudml.org/doc/286800
ER -

References

top
  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. (1985) 
  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. (2005) MR2170271
  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. (2009) Zbl1157.15020MR2460493
  4. Arav, M., Hall, F., Li, Z., Rao, B., Rational solutions of certain matrix equations, Linear Algebra Appl. 430 (2009), 660-663. (2009) Zbl1166.15005MR2469319
  5. Arav, M., Hall, F., Li, Z., Holst, H. van der, Sinkovic, J. H., Zhang, L., 10.13001/1081-3810.3077, Electron. J. Linear Algebra 30 (2015), 360-371. (2015) MR3386529DOI10.13001/1081-3810.3077
  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. (2008) Zbl1179.05070MR2383445
  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. (2010) 
  8. Brualdi, R. A., Shader, B. L., Matrices of Sign-Solvable Linear Systems, Cambridge Tracts in Mathematics 116 Cambridge University Press, Cambridge (1995). (1995) Zbl0833.15002MR1358133
  9. Chen, G., Hall, F. J., Li, Z., Wei, B., 10.1007/s00373-002-0522-8, Graphs Comb. 19 (2003), 323-334. (2003) Zbl1023.05093MR2007894DOI10.1007/s00373-002-0522-8
  10. Delsarte, P., Kamp, Y., 10.1137/0402006, SIAM J. Discrete Math. 2 (1989), 51-63. (1989) Zbl0677.15007MR0976788DOI10.1137/0402006
  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. (2015) Zbl1310.15057MR3314328
  13. Forster, J., 10.1016/S0022-0000(02)00019-3, J. Comput. Syst. Sci. 65 (2002), 612-625. (2002) Zbl1058.68058MR1964645DOI10.1016/S0022-0000(02)00019-3
  14. Forster, J., Schmitt, N., Simon, H. U., Suttorp, T., 10.1023/A:1022905618164, Mach. Learn. 51 (2003), 263-281. (2003) Zbl1026.68112MR2042049DOI10.1023/A:1022905618164
  15. Friesen, M., Hamed, A., Lee, T., Theis, D. O., Fooling-sets and rank, Eur. J. Comb. (2015), 143-153. (2015) Zbl1314.05028MR3339019
  16. Graham, R. L., Grötschel, M., Lovász, L., eds., Handbook of Combinatorics, MIT Press, Cambridge (1995). (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). (2014) 
  18. Hershkowitz, D., Schneider, H., 10.1080/03081089308818204, Linear Multilinear Algebra 34 (1993), 3-19. (1993) Zbl0793.05027MR1334927DOI10.1080/03081089308818204
  19. Johnson, C. R., 10.1080/03081088208817476, Linear Multilinear Algebra 12 (1982), 99-108. (1982) Zbl0494.15002MR0670716DOI10.1080/03081088208817476
  20. Johnson, C. R., Zhang, Y., 10.1142/S1793830910000711, Discrete Math. Algorithms Appl. 2 (2010), 363-377. (2010) Zbl1210.15002MR2728832DOI10.1142/S1793830910000711
  21. Kopparty, S., Rao, K. P. S. B., The minimum rank problem: a counterexample, Linear Algebra Appl. 428 (2008), 1761-1765. (2008) Zbl1151.15002MR2388655
  22. Li, Z., Gao, Y., Arav, M., Gong, F., Gao, W., Hall, F. J., Holst, H. van der, 10.1080/03081087.2012.716431, Linear Multilinear Algebra 61 (2013), 895-908. (2013) MR3175334DOI10.1080/03081087.2012.716431
  23. Matoušek, J., Lectures on Discrete Geometry, Graduate Texts in Mathematics 212 Springer, New York (2002). (2002) Zbl0999.52006MR1899299
  24. Paturi, R., Simon, J., 10.1016/0022-0000(86)90046-2, J. Comput. Syst. Sci. 33 (1986), 106-123. (1986) Zbl0625.68029MR0864082DOI10.1016/0022-0000(86)90046-2
  25. Razborov, A. A., Sherstov, A. A., 10.1137/080744037, SIAM J. Comput. 39 (2010), 1833-1855. (2010) Zbl1211.68213MR2592035DOI10.1137/080744037
  26. Mor, A. Ribó, Rote, G., Schulz, A., 10.1007/s00454-010-9301-0, Discrete Comput. Geom. 45 (2011), 65-87. (2011) MR2765520DOI10.1007/s00454-010-9301-0
  27. Shitov, Y., 10.1016/j.ejc.2014.06.001, Eur. J. Comb. 42 (2014), 107-111. (2014) Zbl1314.15022MR3240139DOI10.1016/j.ejc.2014.06.001
  28. Ziegler, G. M., Lectures on Polytopes, Graduate Texts in Mathematics 152 Springer, Berlin (1995). (1995) Zbl0823.52002MR1311028

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.