PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2016 | 4 | 1 | 247-254
Tytuł artykułu

Essential sign change numbers of full sign pattern matrices

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Czasopismo
Rocznik
Tom
4
Numer
1
Strony
247-254
Opis fizyczny
Daty
otrzymano
2015-04-04
zaakceptowano
2016-06-03
online
2016-06-16
Twórcy
  • College of Math and Stat, Chongqing Jiaotong University, Chongqing, China
autor
  • School of Instrument & Electronics, North University of China, Shanxi, China
autor
  • Dept of Math and Stat, Georgia State University, Atlanta, GA 30302, USA
autor
  • Dept of Math, North University of China, Taiyuan, Shanxi, China
  • Dept of Math and Stat, Georgia State University, Atlanta, GA 30302, USA
autor
  • Dept of Math and Stat, Georgia State University, Atlanta, GA 30302, USA
autor
  • Dept of Math, North University of China, Taiyuan, Shanxi, China
autor
  • 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_1515_spma-2016-0023
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.