A sign pattern (matrix) is a matrix whose entries are from the set {+, −, 0} and a sign vector is a vector whose entries are from the set {+, −, 0}. A sign pattern or sign vector is full if it does not contain any zero entries. The minimum rank of a sign pattern matrix A is the minimum of the ranks of the real matrices whose entries have signs equal to the corresponding entries of A. The notions of essential row sign change number and essential column sign change number are introduced for full sign patterns and condensed sign patterns. By inspecting the sign vectors realized by a list of real polynomials in one variable, a lower bound on the essential row and column sign change numbers is obtained. Using point-line confiurations on the plane, it is shown that even for full sign patterns with minimum rank 3, the essential row and column sign change numbers can differ greatly and can be much bigger than the minimum rank. Some open problems concerning square full sign patterns with large minimum ranks are discussed.
@article{bwmeta1.element.doi-10_1515_spma-2016-0023,
author = {Xiaofeng Chen and Wei Fang and Wei Gao and Yubin Gao and Guangming Jing and Zhongshan Li and Yanling Shao and Lihua Zhang},
title = {Essential sign change numbers of full sign pattern matrices},
journal = {Special Matrices},
volume = {4},
year = {2016},
pages = {247-254},
zbl = {1342.15025},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_1515_spma-2016-0023}
}
Xiaofeng Chen; Wei Fang; Wei Gao; Yubin Gao; Guangming Jing; Zhongshan Li; Yanling Shao; Lihua Zhang. Essential sign change numbers of full sign pattern matrices. Special Matrices, Tome 4 (2016) pp. 247-254. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_1515_spma-2016-0023/
[1] N. Alon, P. Frankl, and V. Rödl, Geometric realization of set systems and probabilistic communication complexity, Proc. 26th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Portland, 1985.
[2] N. Alon, Tools from higher algebra, in Handbook of combinatorics, Vol. 1, 2, 1749–1783, Elsevier, Amsterdam. | Zbl 0848.05073
[3] N. Alon and J. H. Spencer, The probabilistic method, second edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.
[4] M. Arav et al., Rational realizations of the minimum rank of a sign pattern matrix, Linear Algebra Appl. 409 (2005), 111–125. MR2170271 [WoS] | Zbl 1079.15001
[5] M. Arav et al., Sign patterns that require almost unique rank, Linear Algebra Appl. 430 (2009), no. 1, 7–16. [WoS] | Zbl 1157.15020
[6] M. Arav et al., Rational solutions of certain matrix equations, Linear Algebra Appl. 430 (2009), no. 2-3, 660–663. [WoS] | Zbl 1166.15005
[7] M. Arav et al., Minimum ranks of sign patterns via sign vectors and duality, Electron. J. Linear Algebra 30 (2015), 360–371. | Zbl 1326.15045
[8] A. Berman et al., Minimum rank of matrices described by a graph or pattern over the rational, real and complex numbers, Electron. J. Combin. 15 (2008), no. 1, Research Paper 25, 19 pp. | Zbl 1179.05070
[9] R. A. Brualdi and B. L. Shader, Matrices of sign-solvable linear systems, Cambridge Tracts in Mathematics, 116, Cambridge Univ. Press, Cambridge, 1995. | Zbl 0833.15002
[10] R. Brualdi, S. Fallat, L. Hogben, B. Shader, and P. van den Driessche, Final report: Workshop on Theory and Applications of Matrices described by Patterns, Banff International Research Station, Jan. 31–Feb. 5, 2010.
[11] G. Chen et al., On ranks of matrices associated with trees, Graphs Combin. 19 (2003), no. 3, 323–334. [Crossref] | Zbl 1023.05093
[12] L. M. DeAlba et al., Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns, Linear Algebra Appl. 418 (2006), no. 2-3, 394–415. | Zbl 1106.05059
[13] P. Delsarte and Y. Kamp, Low rank matrices with a given sign pattern, SIAM J. Discrete Math. 2 (1989), no. 1, 51–63. [Crossref] | Zbl 0677.15007
[14] W. Fang, W. Gao, Y.Gao, F. Gong, G. Jing, Z. Li, Y. Shao, L. Zhang, Minimum ranks of sign patterns and zero-nonzero patterns and point–hyperplane configurations, submitted.
[15] W. Fang, W. Gao, Y.Gao, F. Gong, G. Jing, Z. Li, Y. Shao, L. Zhang, Rational realization of the minimum ranks of nonnegative sign pattern matrices, Czechoslovak Math. J., In press. | Zbl 06644040
[16] M. Fiedler et al., Ranks of dense alternating sign matrices and their sign patterns, Linear Algebra Appl. 471 (2015), 109–121. [WoS] | Zbl 1310.15057
[17] J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity, J. Comput. System Sci. 65 (2002), no. 4, 612–625. | Zbl 1058.68058
[18] J. Forster, N. Schmitt, H.U. Simon, T. Suttorp, Estimating the optimal margins of embeddings in Euclidean half spaces, Machine Learning 51 (2003), 263–281. | Zbl 1026.68112
[19] M. Friesen et al., Fooling-sets and rank, European J. Combin. 48 (2015), 143–153. | Zbl 1314.05028
[20] B. Grünbaum, Configurations of points and lines, Graduate Studies in Mathematics, 103, Amer. Math. Soc., Providence, RI, 2009. | Zbl 1205.51003
[21] F. J. Hall, Z. Li and B. Rao, From Boolean to sign pattern matrices, Linear Algebra Appl. 393 (2004), 233–251. | Zbl 1062.15011
[22] F.J. Hall and Z. Li, Sign Pattern Matrices, in Handbook of Linear Algebra, 2nd ed., (L. Hogben et al., editors), Chapman and Hall/CRC Press, Boca Raton, 2014.
[23] D. Hershkowitz and H. Schneider, Ranks of zero patterns and sign patterns, Linear and Multilinear Algebra 34 (1993), no. 1, 3–19. | Zbl 0793.05027
[24] C. R. Johnson, Some outstanding problems in the theory ofmatrices, Linear andMultilinear Algebra 12 (1982), no. 2, 91–108.
[25] S. Kopparty and K. P. S. Bhaskara Rao, The minimum rank problem: a counterexample, Linear Algebra Appl. 428 (2008), no. 7, 1761–1765. [WoS] | Zbl 1151.15002
[26] Z. Li et al., Sign patterns with minimum rank 2 and upper bounds on minimum ranks, Linear Multilinear Algebra 61 (2013), no. 7, 895–908. [WoS] | Zbl 1278.15033
[27] J. Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, 212, Springer, New York, 2002.
[28] R. Paturi and J. Simon, Probabilistic communication complexity, J. Comput. System Sci. 33 (1986), no. 1, 106–123. | Zbl 0625.68029
[29] A. A. Razborov and A. A. Sherstov, The sign-rank of AC0, SIAM J. Comput. 39 (2010), no. 5, 1833–1855. [WoS] | Zbl 1211.68213
[30] Y. Shitov, Sign patterns of rational matrices with large rank, European J. Combin. 42 (2014), 107–111. | Zbl 1314.15022
[31] G. M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, 152, Springer, New York, 1995. | Zbl 0823.52002