Essential sign change numbers of full sign pattern matrices

 Access to full text

 Full (PDF)

1. [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. [2] N. Alon, Tools from higher algebra, in Handbook of combinatorics, Vol. 1, 2, 1749–1783, Elsevier, Amsterdam.  Zbl0848.05073
3. [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. [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] Zbl1079.15001
5. [5] M. Arav et al., Sign patterns that require almost unique rank, Linear Algebra Appl. 430 (2009), no. 1, 7–16. [WoS] Zbl1157.15020
6. [6] M. Arav et al., Rational solutions of certain matrix equations, Linear Algebra Appl. 430 (2009), no. 2-3, 660–663. [WoS] Zbl1166.15005
7. [7] M. Arav et al., Minimum ranks of sign patterns via sign vectors and duality, Electron. J. Linear Algebra 30 (2015), 360–371.  Zbl1326.15045
8. [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.  Zbl1179.05070
9. [9] R. A. Brualdi and B. L. Shader, Matrices of sign-solvable linear systems, Cambridge Tracts in Mathematics, 116, Cambridge Univ. Press, Cambridge, 1995.  Zbl0833.15002
10. [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. [11] G. Chen et al., On ranks of matrices associated with trees, Graphs Combin. 19 (2003), no. 3, 323–334. [Crossref] Zbl1023.05093
12. [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.  Zbl1106.05059
13. [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] Zbl0677.15007
14. [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. [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.  Zbl06644040
16. [16] M. Fiedler et al., Ranks of dense alternating sign matrices and their sign patterns, Linear Algebra Appl. 471 (2015), 109–121. [WoS] Zbl1310.15057
17. [17] J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity, J. Comput. System Sci. 65 (2002), no. 4, 612–625.  Zbl1058.68058
18. [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.  Zbl1026.68112
19. [19] M. Friesen et al., Fooling-sets and rank, European J. Combin. 48 (2015), 143–153.  Zbl1314.05028
20. [20] B. Grünbaum, Configurations of points and lines, Graduate Studies in Mathematics, 103, Amer. Math. Soc., Providence, RI, 2009.  Zbl1205.51003
21. [21] F. J. Hall, Z. Li and B. Rao, From Boolean to sign pattern matrices, Linear Algebra Appl. 393 (2004), 233–251.  Zbl1062.15011
22. [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. [23] D. Hershkowitz and H. Schneider, Ranks of zero patterns and sign patterns, Linear and Multilinear Algebra 34 (1993), no. 1, 3–19.  Zbl0793.05027
24. [24] C. R. Johnson, Some outstanding problems in the theory ofmatrices, Linear andMultilinear Algebra 12 (1982), no. 2, 91–108.  
25. [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] Zbl1151.15002
26. [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] Zbl1278.15033
27. [27] J. Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, 212, Springer, New York, 2002.  
28. [28] R. Paturi and J. Simon, Probabilistic communication complexity, J. Comput. System Sci. 33 (1986), no. 1, 106–123.  Zbl0625.68029
29. [29] A. A. Razborov and A. A. Sherstov, The sign-rank of AC0, SIAM J. Comput. 39 (2010), no. 5, 1833–1855. [WoS] Zbl1211.68213
30. [30] Y. Shitov, Sign patterns of rational matrices with large rank, European J. Combin. 42 (2014), 107–111.  Zbl1314.15022
31. [31] G. M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, 152, Springer, New York, 1995.  Zbl0823.52002