A new proof of the refined alternating sign matrix theorem

In the early 1980s, Mills, Robbins and Rumsey conjectured, and in 1996 Zeilberger proved a simple product formula for the number of n×n alternating sign matrices with a 1 at the top of the ith column. We give an alternative proof of this formula using our operator formula for the number of monotone triangles with prescribed bottom row. In addition, we provide the enumeration of certain 0-1-(−1) matrices generalizing alternating sign matrices.     

More refined enumerations of alternating sign matrices

We study a further refinement of the standard refined enumeration of alternating sign matrices (ASMs) according to their first two rows instead of just the first row, and more general “d-refined” enumerations of ASMs according to the first d rows. For the doubly-refined case of d=2, we derive a system of linear equations satisfied by the doubly-refined enumeration numbers A_n,i,j that enumerate such matrices. We give a conjectural explicit formula for A_n,i,j and formulate several other conjectures about the sufficiency of the linear equations to determine the A_n,i,j's and about an extension of the linear equations to the general d-refined enumerations.     

Linear relations of refined enumerations of alternating sign matrices

In recent papers we have studied refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows. The present paper is a first step towards extending these considerations to alternating sign matrices where in addition some left and right columns are fixed. The main result is a simple linear relation between the number of n×n alternating sign matrices where the top row as well as the left and the right column is fixed and the number of n×n alternating sign matrices where the two top rows and the bottom row are fixed. This may be seen as a first indication for the fact that the refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows as well as left and right columns can possibly be reduced to the refined enumerations where only some top and bottom rows are fixed. For the latter numbers we provide a system of linear equations that conjecturally determines them uniquely.     

q-Enumeration of alternating sign matrices with exactly one −1

We enumerate the alternating sign matrices that contain exactly one −1 according to their number of inversions (possibly taking into account the position of the unique non-zero entry in the first row). In conformity with the Mills, Robbins and Rumsey conjectures, this is the same as the enumeration, according to the number of parts, of descending plane partitions with exactly one special part. This is shown by finding a determinantal expression for the generating function of descending plane partitions, transforming it algebraically and extracting recurrences for those with one special part. Finally, we show that the generating function of alternating sign matrices that contain exactly one −1 follows the same recurrences.RésuméOn énumère les matrices à signes alternants qui ne contiennent qu'un seul −1 selon leur nombre d'inversions (en tenant compte possiblement de la position de la seule entrée non nulle de la première ligne). Conformément aux conjectures de Mills, Robbins et Rumsey, ceci revient à l’énumération, selon le nombre de parts, des partitions planes descendantes qui n'ont qu'une seule part spéciale. Pour le démontrer, on obtient d'abord la fonction génératrice des partitions planes descendantes sous forme d'un déterminant qu'on transforme algébriquement pour en extraire des récurrences qui caractérisent celles n'ayant qu'une part spéciale. Finalement, on montre que la fonction génératrice des matrices à signes alternants vérifie les mêmes récurrences.     

Multiply-refined enumeration of alternating sign matrices

Four natural boundary statistics and two natural bulk statistics are considered for alternating sign matrices (ASMs). Specifically, these statistics are the positions of the 1’s in the first and last rows and columns of an ASM, and the numbers of generalized inversions and −1’s in an ASM. Previously-known and related results for the exact enumeration of ASMs with prescribed values of some of these statistics are discussed in detail. A quadratic relation which recursively determines the generating function associated with all six statistics is then obtained. This relation also leads to various new identities satisfied by generating functions associated with fewer than six of the statistics. The derivation of the relation involves combining the Desnanot–Jacobi determinant identity with the Izergin–Korepin formula for the partition function of the six-vertex model with domain-wall boundary conditions.     

Bijective proofs of Gould's and Rothe's identities

We first give a bijective proof of Gould's identity in the model of binary words. Then we deduce Rothe's identity from Gould's identity again by a bijection, which also leads to a double-sum extension of the q-Chu-Vandermonde formula.     

On the weighted enumeration of alternating sign matrices and descending plane partitions

We prove a conjecture of Mills, Robbins and Rumsey [Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (3) (1983) 340-359] that, for any n, k, m and p, the number of n×n alternating sign matrices (ASMs) for which the 1 of the first row is in column k+1 and there are exactly m −1?s and m+p inversions is equal to the number of descending plane partitions (DPPs) for which each part is at most n and there are exactly k parts equal to n, m special parts and p nonspecial parts. The proof involves expressing the associated generating functions for ASMs and DPPs with fixed n as determinants of n×n matrices, and using elementary transformations to show that these determinants are equal. The determinants themselves are obtained by standard methods: for ASMs this involves using the Izergin-Korepin formula for the partition function of the six-vertex model with domain-wall boundary conditions, together with a bijection between ASMs and configurations of this model, and for DPPs it involves using the Lindström-Gessel-Viennot theorem, together with a bijection between DPPs and certain sets of nonintersecting lattice paths.     

Bijective proofs of partition identities arising from modular equations

We establish generalizations of certain partition theorems originating with modular equations and give bijective proofs for them. As a special case, we give a bijective proof of the Farkas and Kra partition theorem modulo 7.     

Enumeration of symmetry classes of alternating sign matrices and characters of classical groups

An alternating sign matrix is a square matrix with entries 1, 0 and −1 such that the sum of the entries in each row and each column is equal to 1 and the nonzero entries alternate in sign along each row and each column. To some of the symmetry classes of alternating sign matrices and their variations, G. Kuperberg associate square ice models with appropriate boundary conditions, and give determinant and Pfaffian formulae for the partition functions. In this paper, we utilize several determinant and Pfaffian identities to evaluate Kuperberg's determinants and Pfaffians, and express the round partition functions in terms of irreducible characters of classical groups. In particular, we settle a conjecture on the number of vertically and horizontally symmetric alternating sign matrices (VHSASMs). Dedicated to the memory of David Robbins.     

U-Turn Alternating Sign Matrices,Symplectic Shifted Tableaux and their Weighted Enumeration

Alternating sign matrices with a U-turn boundary (UASMs) are a recent generalization of ordinary alternating sign matrices. Here we show that variations of these matrices are in bijective correspondence with certain symplectic shifted tableaux that were recently introduced in the context of a symplectic version of Tokuyama’s deformation of Weyl’s denominator formula. This bijection yields a formula for the weighted enumeration of UASMs. In this connection use is made of the link between UASMs and certain square ice configuration matrices.     

New enumeration formulas for alternating sign matrices and square ice partition functions

The refined enumeration of alternating sign matrices (ASMs) of given order having prescribed behavior near one or more of their boundary edges has been the subject of extensive study, starting with the Refined Alternating Sign Matrix Conjecture of Mills–Robbins–Rumsey (1983) [25], its proof by Zeilberger (1996) [31], and more recent work on doubly-refined and triply-refined enumerations by several authors. In this paper we extend the previously known results on this problem by deriving explicit enumeration formulas for the “top–left–bottom” (triply-refined) and “top–left–bottom–right” (quadruply-refined) enumerations. The latter case solves the problem of computing the full boundary correlation function for ASMs. The enumeration formulas are proved by deriving new representations, which are of independent interest, for the partition function of the square ice model with domain wall boundary conditions at the “combinatorial point” η=2π/3$\eta =2\pi /3$.     

Alternating sign matrices with one −1 under vertical reflection

We define a bijection that transforms an alternating sign matrix A with one −1 into a pair (N,E) where N is a (so called) neutral alternating sign matrix (with one −1) and E is an integer. The bijection preserves the classical parameters of Mills, Robbins and Rumsey as well as three new parameters (including E). It translates vertical reflection of A into vertical reflection of N. A hidden symmetry allows the interchange of E with one of the remaining two new parameters. A second bijection transforms (N,E) into a configuration of lattice paths called “mixed configuration.”     

Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

An operator formula for the number of halved monotone triangles with prescribed bottom row

Monotone triangles are certain triangular arrays of integers, which correspond to n×n alternating sign matrices when prescribing (1,2,…,n) as bottom row of the monotone triangle. In this article we define halved monotone triangles, a specialization of which correspond to vertically symmetric alternating sign matrices. We derive an operator formula for the number of halved monotone triangles with prescribed bottom row which is analogous to our operator formula for the number of ordinary monotone triangles [I. Fischer, The number of monotone triangles with prescribed bottom row, Adv. in Appl. Math. 37 (2) (2006) 249-267].     

The affine equivariant sign covariance matrix: asymptotic behavior and efficiencies

We consider the affine equivariant sign covariance matrix (SCM) introduced by Visuri et al. (J. Statist. Plann. Inference 91 (2000) 557). The population SCM is shown to be proportional to the inverse of the regular covariance matrix. The eigenvectors and standardized eigenvalues of the covariance matrix can thus be derived from the SCM. We also construct an estimate of the covariance and correlation matrix based on the SCM. The influence functions and limiting distributions of the SCM and its eigenvectors and eigenvalues are found. Limiting efficiencies are given in multivariate normal and t-distribution cases. The estimates are highly efficient in the multivariate normal case and perform better than estimates based on the sample covariance matrix for heavy-tailed distributions. Simulations confirmed these findings for finite-sample efficiencies.     

Bounds on the k-th generalized base of a primitive sign pattern matrix

You et al. [L. You, J. Shao, and H. Shan, Bounds on the bases of irreducible generalized sign pattern matrices, Lin. Alg. Appl. 427 (2007), pp. 285–300] extended the concept of the base of a powerful sign pattern matrix to the nonpowerful, irreducible sign pattern matrices. The key to their generalization was to view the relationship A ^l =A ^l?+?p as an equality of generalized sign patterns rather than of sign patterns. You, Shao and Shan showed that for primitive generalized sign patterns, the base is the smallest positive integer k such that all entries of A ^k are ambiguous. In this paper we study the k-th generalized base for nonpowerful primitive sign pattern matrices. For a primitive, nonpowerful sign pattern A, this is the smallest positive integer h such that A^k has h rows consisting entirely of ambiguous entries. Extending the work of You, Shao and Shan, we obtain sharp upper bounds on the k-th generalized base, together with a complete characterization of the equality cases for those bounds. We also show that there exist gaps in the k-th generalized base set of the classes of such matrices.     

Rook-by-rook rook theory: Bijective proofs of rook and hit equivalences

Suppose μ and ν are integer partitions of n, and N>n. It is well known that the Ferrers boards associated to μ and ν are rook-equivalent iff the multisets [μ_i+i:1iN] and [ν_i+i:1iN] are equal. We use the Garsia–Milne involution principle to produce a bijective proof of this theorem in which non-attacking rook placements for μ are explicitly matched with corresponding placements for ν. One byproduct is a direct combinatorial proof that the matrix of Stirling numbers of the first kind is the inverse of the matrix of Stirling numbers of the second kind. We also prove q-analogues and p,q-analogues of these results. We also use the Garsia–Milne involution principle to show that for any two rook boards B and B^′, if B and B^′ are bijectively rook-equivalent, then B and B^′ are bijectively hit-equivalent.     

Proof of the Razumov-Stroganov conjecture

The Razumov-Stroganov conjecture relates the ground-state coefficients in the periodic even-length dense O(1) loop model to the enumeration of fully-packed loop configurations on the square, with alternating boundary conditions, refined according to the link pattern for the boundary points.Here we prove this conjecture, by means of purely combinatorial methods. The main ingredient is a generalization of the Wieland proof technique for the dihedral symmetry of these classes, based on the ‘gyration’ operation, whose full strength we will investigate in a companion paper.