Geodesic
Rational realization of the minimum ranks of nonnegative sign pattern matrices
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 895-911
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-016-0299-1
Classification : 15A23, 15B35, 15B36, 52C35
Keywords: sign pattern (matrix); nonnegative sign pattern; minimum rank; convex polytope; rational minimum rank; rational realization; integer matrix; condensed sign pattern; point-hyperplane configuration 
@article{10_1007_s10587_016_0299_1,
     author = {Fang, Wei and Gao, Wei and Gao, Yubin and Gong, Fei and Jing, Guangming and Li, Zhongshan and Shao, Yanling and Zhang, Lihua},
     title = {Rational realization of the minimum ranks of nonnegative sign pattern matrices},
     journal = {Czechoslovak Mathematical Journal},
     pages = {895--911},
     year = {2016},
     volume = {66},
     number = {3},
     doi = {10.1007/s10587-016-0299-1},
     mrnumber = {3556874},
     zbl = {06644040},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0299-1/}
}
TY  - JOUR
AU  - Fang, Wei
AU  - Gao, Wei
AU  - Gao, Yubin
AU  - Gong, Fei
AU  - Jing, Guangming
AU  - Li, Zhongshan
AU  - Shao, Yanling
AU  - Zhang, Lihua
TI  - Rational realization of the minimum ranks of nonnegative sign pattern matrices
JO  - Czechoslovak Mathematical Journal
PY  - 2016
SP  - 895
EP  - 911
VL  - 66
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0299-1/
DO  - 10.1007/s10587-016-0299-1
LA  - en
ID  - 10_1007_s10587_016_0299_1
ER  - 
%0 Journal Article
%A Fang, Wei
%A Gao, Wei
%A Gao, Yubin
%A Gong, Fei
%A Jing, Guangming
%A Li, Zhongshan
%A Shao, Yanling
%A Zhang, Lihua
%T Rational realization of the minimum ranks of nonnegative sign pattern matrices
%J Czechoslovak Mathematical Journal
%D 2016
%P 895-911
%V 66
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0299-1/
%R 10.1007/s10587-016-0299-1
%G en
%F 10_1007_s10587_016_0299_1
Fang, Wei; Gao, Wei; Gao, Yubin; Gong, Fei; Jing, Guangming; Li, Zhongshan; Shao, Yanling; Zhang, Lihua. Rational realization of the minimum ranks of nonnegative sign pattern matrices. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 895-911. doi: 10.1007/s10587-016-0299-1

[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

[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 | Zbl

[4] Arav, M., Hall, F., Li, Z., Rao, B.: Rational solutions of certain matrix equations. Linear Algebra Appl. 430 (2009), 660-663. | MR | Zbl

[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 | MR

[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 | Zbl

[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 | Zbl

[9] Chen, G., Hall, F. J., Li, Z., Wei, B.: On ranks of matrices associated with trees. Graphs Comb. 19 (2003), 323-334. | DOI | MR | Zbl

[10] Delsarte, P., Kamp, Y.: Low rank matrices with a given sign pattern. SIAM J. Discrete Math. 2 (1989), 51-63. | DOI | MR | Zbl

[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 | Zbl

[13] Forster, J.: A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci. 65 (2002), 612-625. | DOI | MR | Zbl

[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 | MR | Zbl

[15] Friesen, M., Hamed, A., Lee, T., Theis, D. O.: Fooling-sets and rank. Eur. J. Comb. (2015), 143-153. | MR | Zbl

[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 | MR | Zbl

[19] Johnson, C. R.: Some outstanding problems in the theory of matrices. Linear Multilinear Algebra 12 (1982), 99-108. | DOI | MR | Zbl

[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 | MR | Zbl

[21] Kopparty, S., Rao, K. P. S. B.: The minimum rank problem: a counterexample. Linear Algebra Appl. 428 (2008), 1761-1765. | MR | Zbl

[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 | MR

[23] Matoušek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics 212 Springer, New York (2002). | MR | Zbl

[24] Paturi, R., Simon, J.: Probabilistic communication complexity. J. Comput. Syst. Sci. 33 (1986), 106-123. | DOI | MR | Zbl

[25] Razborov, A. A., Sherstov, A. A.: The sign rank of AC$^0$. SIAM J. Comput. 39 (2010), 1833-1855. | DOI | MR | Zbl

[26] Mor, A. Ribó, Rote, G., Schulz, A.: Small grid embeddings of 3-polytopes. Discrete Comput. Geom. 45 (2011), 65-87. | DOI | MR

[27] Shitov, Y.: Sign patterns of rational matrices with large rank. Eur. J. Comb. 42 (2014), 107-111. | DOI | MR | Zbl

[28] Ziegler, G. M.: Lectures on Polytopes. Graduate Texts in Mathematics 152 Springer, Berlin (1995). | MR | Zbl

Cité par Sources :