Alternating sign matrix
In mathematics, an alternating sign matrix is a square matrix of 0s, 1s, and −1s such that the sum of each row and column is 1 and the nonzero entries in each row and column alternate in sign. These matrices generalize permutation matrices and arise naturally when using Dodgson condensation to compute a determinant.[1] They are also closely related to the six-vertex model with domain wall boundary conditions from statistical mechanics. They were first defined by William Mills, David Robbins, and Howard Rumsey in the former context.
Examples
A permutation matrix is an alternating sign matrix, and an alternating sign matrix is a permutation matrix if and only if no entry equals −1.
An example of an alternating sign matrix that is not a permutation matrix is
Alternating sign matrix theorem
The alternating sign matrix theorem states that the number of alternating sign matrices is
The first few terms in this sequence for n = 0, 1, 2, 3, … are
- 1, 1, 2, 7, 42, 429, 7436, 218348, … (sequence A005130 in the OEIS).
This theorem was first proved by Doron Zeilberger in 1992.[2] In 1995, Greg Kuperberg gave a short proof[3] based on the Yang–Baxter equation for the six-vertex model with domain-wall boundary conditions, that uses a determinant calculation due to Anatoli Izergin.[4] In 2005, a third proof was given by Ilse Fischer using what is called the operator method.[5]
Razumov–Stroganov problem
In 2001, A. Razumov and Y. Stroganov conjectured a connection between O(1) loop model, fully packed loop model (FPL) and ASMs.[6] This conjecture was proved in 2010 by Cantini and Sportiello.[7]
References
- ^ Hone, Andrew N. W. (2006), "Dodgson condensation, alternating signs and square ice", Philosophical Transactions of the Royal Society of London, 364 (1849): 3183–3198, doi:10.1098/rsta.2006.1887, MR 2317901
- ^ Zeilberger, Doron, "Proof of the alternating sign matrix conjecture", Electronic Journal of Combinatorics 3 (1996), R13.
- ^ Kuperberg, Greg, "Another proof of the alternating sign matrix conjecture", International Mathematics Research Notes (1996), 139-150.
- ^ "Determinant formula for the six-vertex model", A. G. Izergin et al. 1992 J. Phys. A: Math. Gen. 25 4315.
- ^ Fischer, Ilse (2005). "A new proof of the refined alternating sign matrix theorem". Journal of Combinatorial Theory, Series A. 114 (2): 253–264. arXiv:math/0507270. Bibcode:2005math......7270F. doi:10.1016/j.jcta.2006.04.004.
- ^ Razumov, A.V., Stroganov Yu.G., Spin chains and combinatorics, Journal of Physics A, 34 (2001), 3185-3190.
- ^ L. Cantini and A. Sportiello, Proof of the Razumov-Stroganov conjectureJournal of Combinatorial Theory, Series A, 118 (5), (2011) 1549–1574,
Further reading
- Bressoud, David M., Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, MAA Spectrum, Mathematical Associations of America, Washington, D.C., 1999.ISBN 978-0521666466
- Bressoud, David M. and Propp, James, How the alternating sign matrix conjecture was solved, Notices of the American Mathematical Society, 46 (1999), 637–646.
- Mills, William H., Robbins, David P., and Rumsey, Howard Jr., Proof of the Macdonald conjecture, Inventiones Mathematicae, 66 (1982), 73–87.
- Mills, William H., Robbins, David P., and Rumsey, Howard Jr., Alternating sign matrices and descending plane partitions, Journal of Combinatorial Theory, Series A, 34 (1983), 340–359.
- Propp, James, The many faces of alternating-sign matrices, Discrete Mathematics and Theoretical Computer Science, Special issue on Discrete Models: Combinatorics, Computation, and Geometry (July 2001).
- Razumov, A. V., Stroganov Yu. G., Combinatorial nature of ground state vector of O(1) loop model, Theor. Math. Phys., 138 (2004), 333–337.
- Razumov, A. V., Stroganov Yu. G., O(1) loop model with different boundary conditions and symmetry classes of alternating-sign matrices], Theor. Math. Phys., 142 (2005), 237–243, arXiv:cond-mat/0108103
- Robbins, David P., The story of , The Mathematical Intelligencer, 13 (2), 12–19 (1991), doi:10.1007/BF03024081.
- Zeilberger, Doron, Proof of the refined alternating sign matrix conjecture, New York Journal of Mathematics 2 (1996), 59–68.
External links
- Alternating sign matrix entry in MathWorld
- Alternating sign matrices entry in the FindStat database
- v
- t
- e
- Alternant
- Anti-diagonal
- Anti-Hermitian
- Anti-symmetric
- Arrowhead
- Band
- Bidiagonal
- Bisymmetric
- Block-diagonal
- Block
- Block tridiagonal
- Boolean
- Cauchy
- Centrosymmetric
- Conference
- Complex Hadamard
- Copositive
- Diagonally dominant
- Diagonal
- Discrete Fourier Transform
- Elementary
- Equivalent
- Frobenius
- Generalized permutation
- Hadamard
- Hankel
- Hermitian
- Hessenberg
- Hollow
- Integer
- Logical
- Matrix unit
- Metzler
- Moore
- Nonnegative
- Pentadiagonal
- Permutation
- Persymmetric
- Polynomial
- Quaternionic
- Signature
- Skew-Hermitian
- Skew-symmetric
- Skyline
- Sparse
- Sylvester
- Symmetric
- Toeplitz
- Triangular
- Tridiagonal
- Vandermonde
- Walsh
- Z
- Adjugate
- Alternating sign
- Augmented
- Bézout
- Carleman
- Cartan
- Circulant
- Cofactor
- Commutation
- Confusion
- Coxeter
- Distance
- Duplication and elimination
- Euclidean distance
- Fundamental (linear differential equation)
- Generator
- Gram
- Hessian
- Householder
- Jacobian
- Moment
- Payoff
- Pick
- Random
- Rotation
- Seifert
- Shear
- Similarity
- Symplectic
- Totally positive
- Transformation
- Cabibbo–Kobayashi–Maskawa
- Density
- Fundamental (computer vision)
- Fuzzy associative
- Gamma
- Gell-Mann
- Hamiltonian
- Irregular
- Overlap
- S
- State transition
- Substitution
- Z (chemistry)
- Mathematics portal
- List of matrices
- Category:Matrices