Abstract
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.
References
[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. 10.1109/SFCS.1985.30Search in Google Scholar
[2] N. Alon, Tools from higher algebra, in Handbook of combinatorics, Vol. 1, 2, 1749–1783, Elsevier, Amsterdam. Search in Google Scholar
[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. Search in Google Scholar
[4] M. Arav et al., Rational realizations of the minimum rank of a sign pattern matrix, Linear Algebra Appl. 409 (2005), 111–125. MR2170271 10.1016/j.laa.2005.05.001Search in Google Scholar
[5] M. Arav et al., Sign patterns that require almost unique rank, Linear Algebra Appl. 430 (2009), no. 1, 7–16. Search in Google Scholar
[6] M. Arav et al., Rational solutions of certain matrix equations, Linear Algebra Appl. 430 (2009), no. 2-3, 660–663. Search in Google Scholar
[7] M. Arav et al., Minimum ranks of sign patterns via sign vectors and duality, Electron. J. Linear Algebra 30 (2015), 360–371. 10.13001/1081-3810.3077Search in Google Scholar
[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. 10.37236/749Search in Google Scholar
[9] R. A. Brualdi and B. L. Shader, Matrices of sign-solvable linear systems, Cambridge Tracts in Mathematics, 116, Cambridge Univ. Press, Cambridge, 1995. 10.1017/CBO9780511574733Search in Google Scholar
[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. Search in Google Scholar
[11] G. Chen et al., On ranks of matrices associated with trees, Graphs Combin. 19 (2003), no. 3, 323–334. Search in Google Scholar
[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. Search in Google Scholar
[13] P. Delsarte and Y. Kamp, Low rank matrices with a given sign pattern, SIAM J. Discrete Math. 2 (1989), no. 1, 51–63. Search in Google Scholar
[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. Search in Google Scholar
[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. Search in Google Scholar
[16] M. Fiedler et al., Ranks of dense alternating sign matrices and their sign patterns, Linear Algebra Appl. 471 (2015), 109–121. 10.1016/j.laa.2014.12.034Search in Google Scholar
[17] J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity, J. Comput. System Sci. 65 (2002), no. 4, 612–625. Search in Google Scholar
[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. 10.1023/A:1022905618164Search in Google Scholar
[19] M. Friesen et al., Fooling-sets and rank, European J. Combin. 48 (2015), 143–153. 10.1016/j.ejc.2015.02.016Search in Google Scholar
[20] B. Grünbaum, Configurations of points and lines, Graduate Studies in Mathematics, 103, Amer. Math. Soc., Providence, RI, 2009. 10.1090/gsm/103Search in Google Scholar
[21] F. J. Hall, Z. Li and B. Rao, From Boolean to sign pattern matrices, Linear Algebra Appl. 393 (2004), 233–251. 10.1016/j.laa.2004.08.005Search in Google Scholar
[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. Search in Google Scholar
[23] D. Hershkowitz and H. Schneider, Ranks of zero patterns and sign patterns, Linear and Multilinear Algebra 34 (1993), no. 1, 3–19. Search in Google Scholar
[24] C. R. Johnson, Some outstanding problems in the theory ofmatrices, Linear andMultilinear Algebra 12 (1982), no. 2, 91–108. Search in Google Scholar
[25] S. Kopparty and K. P. S. Bhaskara Rao, The minimum rank problem: a counterexample, Linear Algebra Appl. 428 (2008), no. 7, 1761–1765. Search in Google Scholar
[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. Search in Google Scholar
[27] J. Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, 212, Springer, New York, 2002. 10.1007/978-1-4613-0039-7Search in Google Scholar
[28] R. Paturi and J. Simon, Probabilistic communication complexity, J. Comput. System Sci. 33 (1986), no. 1, 106–123. Search in Google Scholar
[29] A. A. Razborov and A. A. Sherstov, The sign-rank of AC0, SIAM J. Comput. 39 (2010), no. 5, 1833–1855. Search in Google Scholar
[30] Y. Shitov, Sign patterns of rational matrices with large rank, European J. Combin. 42 (2014), 107–111. 10.1016/j.ejc.2014.06.001Search in Google Scholar
[31] G. M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, 152, Springer, New York, 1995. 10.1007/978-1-4613-8431-1Search in Google Scholar
©2016 Xiaofeng Chen et al.
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.
