Essential sign change numbers of full sign pattern matrices

• Autorzy: Xiaofeng Chen , Wei Fang , Wei Gao , Yubin Gao , Guangming Jing , Zhongshan Li , Yanling Shao , Lihua Zhang
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

sign pattern (matrix); full sign pattern; minimum rank; sign change number; essential row signchange number; essential column sign change number; sign vectors of a list of polynomials

• Wydawca: De Gruyter Open
• Czasopismo: Special Matrices
• Rocznik: 2016
• Tom: 4
• Numer: 1
• Strony: 247-254

Daty

otrzymano

2015-04-04

zaakceptowano

2016-06-03

online

2016-06-16

Twórcy

autor

Xiaofeng Chen

• College of Math and Stat, Chongqing Jiaotong University, Chongqing, China

autor

Wei Fang

• School of Instrument & Electronics, North University of China, Shanxi, China

autor

Wei Gao

• Dept of Math and Stat, Georgia State University, Atlanta, GA 30302, USA

autor

Yubin Gao

• Dept of Math, North University of China, Taiyuan, Shanxi, China

autor

Guangming Jing

• Dept of Math and Stat, Georgia State University, Atlanta, GA 30302, USA

autor

Zhongshan Li

• Dept of Math and Stat, Georgia State University, Atlanta, GA 30302, USA

autor

Yanling Shao

• Dept of Math, North University of China, Taiyuan, Shanxi, China

autor

Lihua Zhang

• Dept of Math and Stat, Georgia State University, Atlanta, GA 30302, USA

Bibliografia

• [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.
• [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]
• [5] M. Arav et al., Sign patterns that require almost unique rank, Linear Algebra Appl. 430 (2009), no. 1, 7–16. [WoS]
• [6] M. Arav et al., Rational solutions of certain matrix equations, Linear Algebra Appl. 430 (2009), no. 2-3, 660–663. [WoS]
• [7] M. Arav et al., Minimum ranks of sign patterns via sign vectors and duality, Electron. J. Linear Algebra 30 (2015), 360–371.
• [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.
• [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] 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]
• [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.
• [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]
• [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.
• [16] M. Fiedler et al., Ranks of dense alternating sign matrices and their sign patterns, Linear Algebra Appl. 471 (2015), 109–121. [WoS]
• [17] J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity, J. Comput. System Sci. 65 (2002), no. 4, 612–625.
• [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.
• [19] M. Friesen et al., Fooling-sets and rank, European J. Combin. 48 (2015), 143–153.
• [20] B. Grünbaum, Configurations of points and lines, Graduate Studies in Mathematics, 103, Amer. Math. Soc., Providence, RI, 2009.
• [21] F. J. Hall, Z. Li and B. Rao, From Boolean to sign pattern matrices, Linear Algebra Appl. 393 (2004), 233–251.
• [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.
• [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]
• [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]
• [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.
• [29] A. A. Razborov and A. A. Sherstov, The sign-rank of AC0, SIAM J. Comput. 39 (2010), no. 5, 1833–1855. [WoS]
• [30] Y. Shitov, Sign patterns of rational matrices with large rank, European J. Combin. 42 (2014), 107–111.
• [31] G. M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, 152, Springer, New York, 1995.

Identyfikatory

DOI

10.1515/spma-2016-0023