Alternating sign matrix
An alternating sign matrix (ASM) is an n × n square matrix with entries in the set {0, 1, −1} such that the nonzero entries in each row and each column alternate in sign, beginning and ending with +1, and the sum of the entries in each row and each column equals 1.[1]
Alternating sign matrices were introduced in 1983 by William H. Mills, David P. Robbins, and Howard Rumsey in their study of Dodgson's condensation algorithm for computing determinants, where they observed these matrices arising in the expansion of certain determinants.[1] In the same work, Mills, Robbins, and Rumsey conjectured a product formula for the enumeration of ASMs of order n, given by
\prod_{j=0}^{n-1} \frac{(3j+1)!}{(n+j)!},
which yields the sequence 1, 2, 7, 42, 429, 7436, ... for n = 1, 2, 3, ... .[1] This conjecture was proved in 1996 by Doron Zeilberger using symbolic computation and creative telescoping techniques.[2]
ASMs form a distributive lattice under partial matrix ordering and exhibit rich connections to other areas of combinatorics, including bijections with monotone triangles, fully symmetric plane partitions, and configurations in the six-vertex model of statistical mechanics (also known as square ice).[3] These links have facilitated further enumerative results, such as refined counts tracking statistics like the number of −1 entries, and applications to tilings of Aztec diamonds and other polyominoes.[3] The study of ASMs continues to influence research in algebraic combinatorics, representation theory, and integrable systems.[3]
Fundamentals
Definition
An alternating sign matrix (ASM) is an n \times n square matrix with entries in the set \{-1, 0, 1\} such that the sum of each row and each column is 1, and in every row and every column, the nonzero entries alternate in sign, beginning and ending with +1.[1] This structure generalizes permutation matrices, which form a subset where all nonzero entries are +1.[1]
Formally, an n \times n matrix A = (a_{ij}) is an ASM if it satisfies the following conditions:
- a_{ij} \in \{-1, 0, 1\} for all i, j = 1, \dots, n,
- \sum_{j=1}^n a_{ij} = 1 for each row i = 1, \dots, n,
- \sum_{i=1}^n a_{ij} = 1 for each column j = 1, \dots, n,
- in each row i and each column j, the nonzero entries alternate in sign and the first and last nonzero entries are +1.[1]
The collection of all such n \times n ASMs is denoted by \mathcal{A}_n.[3] This definition ensures compatibility between row and column conditions, as the partial sums of nonzero entries in any prefix or suffix of a row or column must be nonnegative (or equivalently, 0 or 1).[1]
Properties
A fundamental property of alternating sign matrices is the partial sum condition in their rows and columns. For an n × n alternating sign matrix A = (a_{ij}), the partial sum in row i up to column k is S_k = \sum_{j=1}^k a_{ij}, which satisfies 0 \le S_k \le 1 for all k = 1, \dots, n, and S_n = 1. The same condition holds for partial sums in each column. This restriction follows from the alternation of non-zero entries and the requirement that each row and column sums to 1, preventing partial sums from becoming negative or exceeding 1.[4]
The positions of the -1 entries are uniquely determined by the positions of the 1 entries, provided the 1's positions satisfy the partial sum condition when completed with -1's to enforce alternation and unit sums. This uniqueness arises because the alternation rule and partial sum constraints force the -1's into specific locations to balance the matrix without violating row or column conditions.[4]
The gyration property endows the set of alternating sign matrices with a rich symmetry structure. Gyration is a bijection on the set of n × n ASMs, composed of local involutions that reverse edge directions in an associated square ice model or height function representation, effectively implementing a 90-degree rotational symmetry while preserving the ASM properties. This operation ensures compatibility between related configurations, such as endpoint pairings in fully packed loops, and extends to a full dihedral group action on the set.[5]
Alternating sign matrices also exhibit invariance under certain row and column permutations within their poset structure, where reordering preserves the componentwise order and partial sum relations in the corresponding monotone triangles.[3]
Examples
Small Cases
For the smallest order n=1, there is a single alternating sign matrix, the $1 \times 1 matrix with entry 1:
\begin{pmatrix}
1
\end{pmatrix}
This matrix satisfies the row and column sum condition of 1, with the single nonzero entry being positive.90068-7)
For n=2, there are exactly two alternating sign matrices, both of which are permutation matrices without any -1 entries:
\begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}, \quad
\begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix}
In each case, the nonzero entries are all 1s that alternate trivially (as single entries per row and column), and all row and column sums equal 1. No matrices containing -1 exist for this order, as any such entry would violate the sum or alternation properties.90068-7)
For n=3, there are seven alternating sign matrices. Six of these are the standard $3 \times 3 permutation matrices, each corresponding to a permutation of \{1,2,3\} with 1s in the permuted positions and 0s elsewhere. Representative examples include the identity:
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}
and one for the cycle (123):
\begin{pmatrix}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{pmatrix}.
The seventh matrix introduces a -1 entry and is:
\begin{pmatrix}
0 & 1 & 0 \\
1 & -1 & 1 \\
0 & 1 & 0
\end{pmatrix}.
Here, the -1 in the center is bordered by 1s above, below, left, and right, ensuring alternation of nonzero signs in rows and columns (starting and ending with +1), while all row and column sums remain 1. This example highlights how -1 entries can appear in larger ASMs, compensated by adjacent 1s to maintain the required properties.90068-7)
The enumeration for these small cases yields |A_1| = 1, |A_2| = 2, and |A_3| = 7, revealing the onset of combinatorial growth beyond mere permutations.90068-7)
Permutation Matrices
A permutation matrix is an n \times n matrix with exactly one entry equal to 1 in each row and each column, and all other entries equal to 0.[1]
Every permutation matrix is an alternating sign matrix (ASM), as it satisfies the defining conditions of an ASM: the sum of the entries in each row and each column is 1, and the nonzero entries (which consist solely of a single +1 per row and column) alternate in sign in a trivial manner, beginning and ending with +1.[1][3]
The number of n \times n permutation matrices is n!, corresponding to the order of the symmetric group S_n.[1]
For example, the two $2 \times 2 permutation matrices are both ASMs:
and
For n=3, there are six permutation matrices, which form a subset of the seven total $3 \times 3 ASMs.[1] One such permutation matrix is the identity:
1 0 0
0 1 0
0 0 1
1 0 0
0 1 0
0 0 1
[3]
In contrast to permutation matrices, ASMs permit entries of −1 alongside +1, allowing for "cancellations" where a −1 and adjacent +1s sum appropriately to maintain the row and column sums of 1, thereby accommodating more intricate structures beyond permutations.[1][3]
Enumeration
ASM Enumeration Theorem
The ASM Enumeration Theorem provides the exact count of n \times n alternating sign matrices (ASMs), establishing a closed-form product formula for their total number.
The theorem states that the number A_n of n \times n ASMs is
A_n = \prod_{j=0}^{n-1} \frac{(3j+1)!}{(n+j)!}.
[6]
This formula was conjectured in 1983 by William H. Mills, David P. Robbins, and Howard Rumsey, who arrived at it through empirical enumeration of ASMs for small n using connections to descending plane partitions and partial sums yielding monotone triangles.[6]
For verification, the formula yields A_1 = 1, A_2 = 2, A_3 = 7, and A_4 = [42](/page/42), matching direct counts of these cases.[6]
The conjecture was proved in 1996 by Doron Zeilberger using symbolic computation and creative telescoping techniques.[7] [2] An alternative proof was given in the same year by Greg Kuperberg using the six-vertex model and the Yang–Baxter equation.[8] Bijections between ASMs and monotone triangles—a combinatorial object introduced alongside ASMs by Mills, Robbins, and Rumsey—were established in the 1990s by Zeilberger and others, facilitating enumerative equivalences via connections to plane partitions; James Propp and collaborators advanced related bijections during this period.[9] The first fully bijective proof of the enumeration formula was provided in 2020 by Ilse Fischer and Matjaž Konvalinka.[10]
Refined Enumerations
The refined enumeration of alternating sign matrices often involves tracking the number of −1 entries as a key statistic, known as the height ht(A). The refined ASM polynomial is defined as the sum over all n×n ASMs A of q^{ht(A)}, where ht(A) is the number of −1 entries in A. This polynomial provides a q-analog of the total ASM count, specializing to the unrefined enumeration when q=1.[11]
Such refinements can be extended to include other statistics, such as the number of generalized inversions ν(A), defined as the number of pairs (i,j) with i<j where the (i,j) entry is 1 and there is a −1 in row i to the right of column j or in column j above row i. The generating function Z_n(x,y;1,...,1) = sum_A x^{ν(A)} y^{ht(A)} has been computed exactly for small n and expressed in terms of Schur functions for general n using connections to the six-vertex model.[11]
For n=3, there are 6 ASMs with ht(A)=0 (the permutation matrices) and 1 ASM with ht(A)=1 (the matrix with −1 in the center and 1's compensating in rows and columns 2). Thus, the refined polynomial is 6 + q. Including the inversion statistic, the full generating function is 1 + 3q + 2q^2 + q^3.[11]
An alternating permutation σ of [2n-1] is a permutation satisfying σ(1) < σ(2) > σ(3) < ⋯ > σ(2n-1), also called an up-down permutation of odd length. These permutations are enumerated by the Euler zig-zag numbers E_{2n-1}, and their refined enumerations by statistics like the major index maj(σ) = sum of positions of descents or the number of inversions have been studied extensively.[12]
Bijections between ASMs and other objects, such as monotone triangles, allow for the transfer of statistics like height to permutation-like structures. Zeilberger's involution, used in the proof of the refined ASM enumeration theorem, pairs ASMs in a way that cancels terms in generating functions, providing a non-bijective mapping that links ASMs to totally symmetric self-complementary plane partitions and related permutation statistics.[13]
Connections
Alternating Permutations
Alternating permutations, also known as zigzag permutations, are a class of permutations \sigma = (\sigma(1), \sigma(2), \dots, \sigma(n)) of the set = \{1, 2, \dots, n\} that satisfy specific alternating inequality patterns. There are two primary types: up-down alternating permutations, where \sigma(1) < \sigma(2) > \sigma(3) < \sigma(4) > \cdots, and down-up (or reverse) alternating permutations, where \sigma(1) > \sigma(2) < \sigma(3) > \sigma(4) < \cdots. The number of up-down and down-up alternating permutations of $$ is the same for all n, given by the Euler numbers E_n. These objects were first systematically studied in the late 19th century, providing foundational insights into permutation patterns.[14][12]
The enumeration of alternating permutations is captured by the Euler numbers E_n, where E_n denotes the number of up-down alternating permutations of $$. These numbers coincide with the secant numbers for even indices (E_{2m}) and tangent numbers for odd indices (E_{2m+1}), reflecting their classical ties to trigonometric functions. The exponential generating function for the Euler numbers is given by
\sum_{n=0}^{\infty} E_n \frac{x^n}{n!} = \sec x + \tan x,
a result originally established by Désiré André in 1881 through combinatorial interpretations of these series expansions. André's work, published as "Sur les permutations alternées," marked the beginning of modern studies on these permutations by linking them directly to the counts derived from secant and tangent expansions.[14][12]
While alternating permutations share some enumerative and structural similarities with aspects of alternating sign matrices (such as through pattern avoidance generalizations), the core properties remain distinct.[15]
Razumov–Stroganov Conjecture
The Razumov–Stroganov conjecture, proposed in 2001, posits that the components of the ground-state vector in the dense O(1) loop model on a cylinder of even circumference 2n with periodic boundary conditions are proportional to the number of n × n alternating sign matrices (ASMs) compatible with a given link pattern on the boundary, where the link pattern specifies the pairing of the 2n boundary sites.[16] Specifically, if \Psi_\pi denotes the component corresponding to link pattern \pi, then \Psi_\pi / \sqrt{A_n} = \#\{ASMs of size n with boundary word \pi\}, where A_n is the total number of n × n ASMs, and the boundary word is determined by the positions of the 1's and -1's on the first row and column.[16] This equates the refined enumeration of ASMs by their boundary link patterns to the weights of fully packed loop (FPL) configurations in the O(1) model, weighted uniformly.[16]
The conjecture arises in the context of the six-vertex model of statistical mechanics, where ASMs correspond to the ground states or height functions at the integrable point \Delta = -1/2 with domain wall boundary conditions, and the dense O(1) loop model maps to the six-vertex model at the Razumov–Stroganov point via a loop representation of vertex configurations.[17] In this framework, FPL configurations on the grid represent non-intersecting loops covering all vertices, and the boundary conditions fix the link pattern, linking the quantum integrable model's ground state to combinatorial refinements of ASMs by the number of loop turns or perimeters at the boundary.[18]
The conjecture was fully proved in 2010 by Cantini and Sportiello using purely combinatorial methods, generalizing the bijection technique from the proof of the ASM enumeration theorem via a growth process for loop configurations and ASMs.[19] Partial proofs for infinite families of link patterns had been established earlier using integrability and matrix methods.
This resolution has implications for connecting ASMs to broader structures in combinatorics and statistical physics, including bijections with dimer models on planar graphs (where loops dualize to perfect matchings) and the study of arctic curves and limit shapes in the scaling limit of the six-vertex model.[19] For example, for n=2, the two 2 × 2 ASMs correspond exactly to the two FPL configurations on a 2×2 grid with the standard boundary link pattern, each contributing equally to the ground-state components.[16]