×

zbMATH — the first resource for mathematics

Smith normal form in combinatorics. (English) Zbl 1343.05026
Summary: This paper surveys some combinatorial aspects of Smith normal form, and more generally, diagonal form. The discussion includes general algebraic properties and interpretations of Smith normal form, critical groups of graphs, and Smith normal form of random integer matrices. We then give some examples of Smith normal form and diagonal form arising from (1) symmetric functions, (2) a result of L. Carlitz et al. [J. Comb. Theory, Ser. A 11, 258–271 (1971; Zbl 0227.05007)], and (3) the Varchenko matrix of a hyperplane arrangement.

MSC:
05A15 Exact enumeration problems, generating functions
15A21 Canonical forms, reductions, classification
11B99 Sequences and sets
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Berlekamp, E. R., A class of convolutional codes, Inf. Control, 6, 1-13, (1963) · Zbl 0214.47201
[2] Berlekamp, E. R., Unimodular arrays, Comput. Math. Appl., 20, 77-83, (2000) · Zbl 0953.05010
[3] Bessenrodt, C.; Stanley, R. P., Smith normal form of a multivariate matrix associated with partitions, J. Algebraic Combin., 41, 73-82, (2015) · Zbl 1307.05009
[4] Biggs, N. L., Chip-firing and the critical group of a graph, J. Algebraic Combin., 9, 25-45, (1999) · Zbl 0919.05027
[5] T.W. Cai, L. Mu, On the Smith normal form of the q-Varchenko matrix of a real hyperplane arrangement, preprint.
[6] Cai, T. W.X.; Stanley, R. P., The Smith normal form of a matrix associated with Young’s lattice, Proc. Amer. Math. Soc., 143, 4695-4703, (2015) · Zbl 1320.05138
[7] Carlitz, L.; Roselle, D. P.; Scoville, R. A., Some remarks on ballot-type sequences, J. Combin. Theory, 11, 258-271, (1971) · Zbl 0227.05007
[8] Chandler, D. B.; Sin, P.; Xiang, Q., The Smith and critical groups of Paley graphs, J. Algebraic Combin., 41, 1013-1022, (2015) · Zbl 1316.05058
[9] Cigler, J., q-Catalan und q-motzkinzahlen, Sitzungsber. - Österr. Akad. Wiss., 208, 3-20, (1999) · Zbl 1003.05010
[10] Cigler, J., q-Catalan numbers and q-Narayana polynomials, preprint · Zbl 1003.05010
[11] Clancy, J.; Leake, T.; Payne, S., A note on Jacobians, Tutte polynomials, and two-variable zeta functions of graphs, Exp. Math., 24, 1-7, (2015) · Zbl 1310.05121
[12] Denham, G.; Hanlon, P., On the Smith normal form of the varchenko bilinear form of a hyperplane arrangement, Pacific J. Math., 181, 123-146, (1997) · Zbl 0921.52003
[13] Denham, G.; Hanlon, P., Some algebraic properties of the schechtman-varchenko bilinear forms, (New Perspectives in Algebraic Combinatorics, Berkeley, CA, 1996-97, Math. Sci. Res. Inst. Publ., vol. 38, (1999), Cambridge University Press Cambridge), 149-176 · Zbl 1050.52501
[14] Dhar, D., Theoretical studies of self-organized criticality, Phys. A, 369, 29-70, (2006)
[15] Di Francesco, P., Bessenrodt-Stanley polynomials and the octahedron recurrence, Electron. J. Combin., 22, (2015) · Zbl 1323.05014
[16] Duval, A. M.; Klivan, C. J.; Martin, J. L., Critical groups of simplicial complexes, Ann. Comb., 7, 53-70, (2013) · Zbl 1263.05124
[17] Eğecioğlu, Ö.; Redmond, T.; Ryavec, C., From a polynomial Riemann hypothesis to alternating sign matrices, Electron. J. Combin., 8, (2001) · Zbl 0996.05120
[18] Ekedahl, T., An infinite version of the Chinese remainder theorem, Comment. Math. Univ. St. Pauli, 40, 1, 53-59, (1991) · Zbl 0749.11004
[19] Fuchs, L.; Salce, L., Modules over non-Noetherian domains, Mathematical Surveys and Monographs, vol. 84, (2001), American Mathematical Society Providence, RI · Zbl 0973.13001
[20] Y. Gao, A.Y. Zhang, Diagonal form of the Varchenko matrices of oriented matroids, in preparation.
[21] Gessel, I. M.; Xin, G., The generating function of ternary trees and continued fractions, Electron. J. Combin., 13, (2006) · Zbl 1098.05006
[22] Hanlon, P.; Stanley, R. P., A q-deformation of a trivial symmetric group action, Trans. Amer. Math. Soc., 350, 4445-4459, (1998) · Zbl 0921.20009
[23] Jacobson, B., Critical groups of graphs, (2003), University of Minnesota, Honors Thesis
[24] Kaplansky, I., Elementary divisors and modules, Trans. Amer. Math. Soc., 66, 464-491, (1949) · Zbl 0036.01903
[25] Krattenthaler, C., Advanced determinant calculus, Sém. Lothar. Combin., 42, (1999) · Zbl 0923.05007
[26] Krattenthaler, C., Advanced determinant calculus: a complement, Linear Algebra Appl., 411, 68-166, (2005) · Zbl 1079.05008
[27] Kuperberg, G., Kasteleyn cokernels, Electron. J. Combin., 9, (2002) · Zbl 1006.05005
[28] Larsen, M. D.; Lewis, W. J.; Shores, T. S., Elementary divisor rings and finitely presented modules, Trans. Amer. Math. Soc., 187, 231-248, (1974) · Zbl 0283.13002
[29] Levine, L.; Propp, J., WHAT IS a sandpile?, Notices Amer. Math. Soc., 57, 976-979, (2010) · Zbl 1203.82061
[30] Lombardi, H.; Quitté, C., Commutative algebra: constructive methods: finite projective modules, Algebra and Its Applications, vol. 20, (2015), Springer Dordrecht · Zbl 1327.13001
[31] Lorenzini, D., Elementary divisor domains and Bézout domains, J. Algebra, 371, 609-619, (2012) · Zbl 1266.13014
[32] Maples, K., Cokernels of random matrices satisfy the Cohen-lentra heuristics
[33] Miller, A. R.; Reiner, V., Differential posets and Smith normal forms, Order, 26, 197-228, (2009) · Zbl 1228.05096
[34] A.R. Miller, D. Stanton, Orthogonal polynomials and Smith normal form, in preparation.
[35] Z. Nie, On nice extensions and Smith normal form, in preparation.
[36] Propp, J., Enumeration of matchings: problems and progress, (Billera, L. J.; Björner, A.; Greene, C.; Simion, R. E.; Stanley, R. P., New Perspectives in Algebraic Combinatorics, Math. Sci. Res. Inst. Publ., vol. 38, (1999), Cambridge University Press Cambridge), 255-291 · Zbl 0937.05065
[37] Shah, S. W.A., Smith normal form of matrices associated with differential posets
[38] Shiu, W. C., Invariant factors of graphs associated with hyperplane arrangements, Discrete Math., 288, 135-148, (2004) · Zbl 1056.05120
[39] Smith, H. J.S., On systems of linear indeterminate equations and congruences, Philos. Trans. R. Soc. Lond., 151, 293-326, (1861)
[40] Stanley, R. P., Enumerative combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, (1999), Cambridge University Press Cambridge · Zbl 0928.05001
[41] Stanley, R. P., An introduction to hyperplane arrangements, (Miller, E.; Reiner, V.; Sturmfels, B., Geometric Combinatorics, IAS/Park City Mathematics Series, vol. 13, (2007), American Mathematical Society Providence, RI), 389-496 · Zbl 1136.52009
[42] Stanley, R. P., Enumerative combinatorics, vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, (2012), Cambridge University Press Cambridge · Zbl 1247.05003
[43] Stanley, R. P., The Smith normal form of a specialized Jacobi-trudi matrix, preprint · Zbl 1358.05025
[44] Tao, T.; Vu, V. H., Random matrices: the universality phenomenon for Wigner ensembles, (Vu, V. H., Modern Aspects of Random Matrix Theory, Proc. Symp. Applied Math., vol. 72, (2014), American Mathematical Society Providence, RI), 121-172 · Zbl 1310.15077
[45] Varchenko, A., Bilinear form of real configuration of hyperplanes, Adv. Math., 97, 110-144, (1993) · Zbl 0777.52006
[46] Wang, Y.; Stanley, R. P., The Smith normal form distribution of a random integer matrix · Zbl 1372.05006
[47] Wood, M. M., The distribution of sandpile groups of random graphs · Zbl 1366.05098
[48] Wood, M. M., Random integral matrices and the Cohen Lenstra heuristics
[49] Young, A.; de B. Robinson, G., The collected papers of Alfred Young, Proc. Lond. Math. Soc., Mathematical Expositions, vol. 21, 92-128, (1977), University of Toronto Press Toronto
[50] Zagier, D., Realizability of a model in infinite statistics, Comm. Math. Phys., 147, 199-210, (1992) · Zbl 0789.47042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.