TOPICS
Search

Alternating Sign Matrix

An alternating sign matrix is a matrix of 0s, 1s, and -1s in which the entries in each row or column sum to 1 and the nonzero entries in each row and column alternate in sign. The first few for n=1, 2, ... are shown below:

A_1=[1]
A_2=[1 0; 0 1],[0 1; 1 0]
A_3=[ 0 0 1; 0 1 0; 1 0 0],[ 0 0 1; 1 0 0; 0 1 0],[ 0 1 0; 0 0 1; 1 0 0],[ 0 1 0; 1 -1 1; 0 1 0],
[ 0 1 0; 1 0 0; 0 0 1],[ 1 0 0; 0 0 1; 0 1 0],[ 1 0 0; 0 1 0; 0 0 1]

Such matrices satisfy the additional property that -1s in a row or column must have a +1 "outside" it (i.e., all -1s are "bordered" by +1s). The numbers of n×n alternating sign matrices A_n for n=1, 2, ... are given by 1, 2, 7, 42, 429, 7436, 218348, ... (OEIS A005130).

The conjecture that the number A_n of A_n is explicitly given by the formula

A_n=product_(j=0)^(n-1)((3j+1)!)/((n+j)!),
(1)

now proven to be true, was known as the alternating sign matrix conjecture. A_n can be expressed in closed form as a complicated function of Barnes G-functions, but additional simplification is likely possible.

A recurrence relation for A_n is given by

A_n=A_(n-1)(Gamma(n)Gamma(3n-1))/(Gamma(2n)Gamma(2n-1)),
(2)

where Gamma(z) is the gamma function.

Let A(n,k) be the number of n×n alternating sign matrices with one in the top row occurring in the kth position. Then

A_n=sum_(k=1)^nA(n,k).
(3)

The result

(A(n,k+1))/(A(n,k))=((n-k)(n+k-1))/(k(2n-k-1))
(4)

for 0<k<n implies (3) (Mills et al. 1983).

Making a triangular array of the number of A_n^' with a 1 at the top of column k gives

1 1 1 2 3 2 7 14 14 7 42 105 135 105 42

(OEIS A048601), and taking the ratios of adjacent terms gives the array

2/2 2/3 3/2 2/4 5/5 4/2 2/5 7/9 9/7 5/2

(OEIS A029656 and A029638). The fact that these numerators and denominators are respectively the numbers in the (2, 1)- and (1, 2)-Pascal triangles which are different from 1 is known as the refined alternating sign matrix conjecture.

Let B_(n,s) denote the number of n×n alternating sign matrices whose top-left s×s corner consists entirely of zeros. By symmetry, the count is independent of the chosen corner and satisfies B_(n,s)=0 for s>|_n/2_| and B_(2s,s)=A_s^2. Colomo and Pronko (2026) conjectured a determinantal formula for B_(n,s) and verified it numerically for n<=20.

See also

Alternating Sign Matrix Conjecture, Condensation, Descending Plane Partition, Integer Matrix, Permutation Matrix

Explore with Wolfram|Alpha

References

Andrews, G. E. "Plane Partitions (III): The Weak Macdonald Conjecture." Invent. Math. 53, 193-225, 1979.Bressoud, D. Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture. Cambridge, England: Cambridge University Press, 1999.Bressoud, D. and Propp, J. "How the Alternating Sign Matrix Conjecture Was Solved." Not. Amer. Math. Soc. 46, 637-646.Colomo, F. and Pronko, A. G. "Frozen-Corner Enumeration of Alternating Sign Matrices." Elec. J. Combin. 33, No. 3, P3.32, 2026. https://doi.org/10.37236/14640.Finch, S. R. Mathematical Constants. Cambridge, England: Cambridge University Press, p. 413, 2003.Kuperberg, G. "Another Proof of the Alternating-Sign Matrix Conjecture." Internat. Math. Res. Notes, No. 3, 139-150, 1996.Mills, W. H.; Robbins, D. P.; and Rumsey, H. Jr. "Proof of the Macdonald Conjecture." Invent. Math. 66, 73-87, 1982.Mills, W. H.; Robbins, D. P.; and Rumsey, H. Jr. "Alternating Sign Matrices and Descending Plane Partitions." J. Combin. Th. Ser. A 34, 340-359, 1983.Pickover, C. A. "Princeton Numbers." Ch. 79 in Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning. Oxford, England: Oxford University Press, pp. 189-192, 2001.Robbins, D. P. "The Story of 1, 2, 7, 42, 429, 7436, ...." Math. Intell. 13, 12-19, 1991.Robbins, D. P. and Rumsey, H. Jr. "Determinants and Alternating Sign Matrices." Adv. Math. 62, 169-184, 1986.Sloane, N. J. A. Sequences A005130/M1808, A029638, A029656, A048601, and A050204 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. "A Baker's Dozen of Conjectures Concerning Plane Partitions." In Combinatoire énumérative. Proceedings of the Colloquium Held at the Université du Québec, Montreal, May 28-June 1, 1985 (Ed. G. Labelle and P. Leroux). New York: Springer-Verlag, pp. 285-293, 1986.Zeilberger, D. "A Constant Term Identity Featuring the Ubiquitous (and Mysterious) Andrews-Mills-Robbins-Rumsey Numbers 1, 2, 7, 42, 429, ...." J. Combin. Theory A 66, 17-27, 1994.Zeilberger, D. "Proof of the Alternating Sign Matrix Conjecture." Elec. J. Combin. 3, No. 2, R13, 1-84, 1996. https://doi.org/10.37236/1271.Zeilberger, D. "Proof of the Refined Alternating Sign Matrix Conjecture." New York J. Math. 2, 59-68, 1996.

Referenced on Wolfram|Alpha

Alternating Sign Matrix

Cite this as:

Weisstein, Eric W. "Alternating Sign Matrix." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/AlternatingSignMatrix.html

Subject classifications