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.     

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.     

A direct bijection between descending plane partitions with no special parts and permutation matrices

We present a direct bijection between descending plane partitions with no special parts and permutation matrices. This bijection has the desirable property that the number of parts of the descending plane partition corresponds to the inversion number of the permutation. Additionally, the number of maximum parts in the descending plane partition corresponds to the position of the one in the last column of the permutation matrix. We also discuss the possible extension of this approach to finding a bijection between descending plane partitions and 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.     

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$.     

Punctured plane partitions and the q-deformed Knizhnik-Zamolodchikov and Hirota equations

We consider partial sum rules for the homogeneous limit of the solution of the q-deformed Knizhnik-Zamolodchikov equation with reflecting boundaries in the Dyck path representation of the Temperley-Lieb algebra. We show that these partial sums arise in a solution of the discrete Hirota equation, and prove that they are the generating functions of τ²-weighted punctured cyclically symmetric transpose complement plane partitions where τ=−(q+q−1). In the cases of no or minimal punctures, we prove that these generating functions coincide with τ²-enumerations of vertically symmetric alternating sign matrices and modifications thereof.     

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.     

Bijective proofs of shifted tableau and alternating sign matrix identities

We give a bijective proof of an identity relating primed shifted gl(n)-standard tableaux to the product of a gl(n) character in the form of a Schur function and . This result generalises a number of well-known results due to Robbins and Rumsey, Chapman, Tokuyama, Okada and Macdonald. An analogous result is then obtained in the case of primed shifted sp(2n)-standard tableaux which are bijectively related to the product of a t-deformed sp(2n) character and . All results are also interpreted in terms of alternating sign matrix (ASM) identities, including a result regarding subsets of ASMs specified by conditions on certain restricted column sums.     

Quantum Knizhnik-Zamolodchikov equation, totally symmetric self-complementary plane partitions, and alternating sign matrices

We present multiple-residue integral formulas for partial sums in the basis of link patterns of the polynomial solution of the level-1 quantum Knizhnik-Zamolodchikov equation at arbitrary values of the quantum parameter q. These formulas allow rewriting and generalizing a recent conjecture of Di Francesco connecting these sums to generating polynomials for weighted totally symmetric self-complementary plane partitions. We reduce the corresponding conjectures to a single integral identity, yet to be proved. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 154, No. 3, pp. 387–408, March, 2008.     

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.     

Enumeration of plane partitions and the algebraic Bethe anzatz

We establish a relation between an exactly solvable boson model and plane partitions, i.e., three-dimensional Young diagrams enclosed in a box of finite size, which allows representing the partition generating functions as correlation functions of an integrable model and deriving the MacMahon formulas for enumerating partitions using the quantum inverse scattering method. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 150, No. 2, pp. 193–203, February, 2007.     

On the Betti numbers of sign conditions

Let be a real closed field and let and be finite subsets of such that the set has elements, the algebraic set defined by has dimension and the elements of and have degree at most . For each we denote the sum of the -th Betti numbers over the realizations of all sign conditions of on by . We prove that

This generalizes to all the higher Betti numbers the bound on . We also prove, using similar methods, that the sum of the Betti numbers of the intersection of with a closed semi-algebraic set, defined by a quantifier-free Boolean formula without negations with atoms of the form or for , is bounded by

making the bound more precise.

     

On the purely algebraic data‐sparse approximation of the inverse and the triangular factors of sparse matrices

The approximation of the inverse and the factors of the LU decomposition of general sparse matrices by hierarchical matrices is investigated. In this first approach, we present and motivate a new matrix partitioning algorithm which is based on the matrix graph by proving logarithmic‐linear complexity of the approximant in the case of bounded condition numbers. In contrast to the usual partitioning, the new algorithm allows to treat general grids if the origin of the sparse matrix is the finite element discretization of differential operators. Numerical examples indicate that the restriction to bounded condition numbers has only technical reasons. Copyright © 2010 John Wiley & Sons, Ltd.     

Lattice Paths,q-Multinomials and Two Variants of the Andrews-Gordon Identities

A few years ago Foda, Quano, Kirillov and Warnaar proposed and proved various finite analogs of the celebrated Andrews-Gordon identities. In this paper we use these polynomial identities along with the combinatorial techniques introduced in our recent paper to derive Garrett, Ismail, Stanton type formulas for two variants of the Andrews-Gordon identities.     

On the stability and spectral radius of a finite set of matrices

This paper studies some problems related to the stability and the spectral radius of a finite set of matrices. A seasonal epidemic model is given to illustrate the use of the obtained results. In this example, the relationship between the obtained results and the stability of a discrete time periodic linear system is obtained.     

On the invertibility of “rectangular” bi-infinite matrices and applications in time–frequency analysis

Finite dimensional matrices with more columns than rows have no left inverses while those with more rows than columns have no right inverses. We give generalizations of these simple facts to bi–infinite matrices. Our results are then used to obtain density results for p-frames of time–frequency molecules in modulation spaces and identifiability results for operators with bandlimited Kohn–Nirenberg symbols.     

On the convergence rate and optimization of a numerical method with splitting of boundary conditions for the stokes system in a spherical layer in the axisymmetric case: Modification for thick layers

The convergence rate of a fast-converging second-order accurate iterative method with splitting of boundary conditions constructed by the authors for solving an axisymmetric Dirichlet boundary value problem for the Stokes system in a spherical gap is studied numerically. For R/r exceeding about 30, where r and R are the radii of the inner and outer boundary spheres, it is established that the convergence rate of the method is lower (and considerably lower for large R/r) than the convergence rate of its differential version. For this reason, a really simpler, more slowly converging modification of the original method is constructed on the differential level and a finite-element implementation of this modification is built. Numerical experiments have revealed that this modification has the same convergence rate as its differential counterpart for R/r of up to 5 × 10³. When the multigrid method is used to solve the split and auxiliary boundary value problems arising at iterations, the modification is more efficient than the original method starting from R/r ～ 30 and is considerably more efficient for large values of R/r. It is also established that the convergence rates of both methods depend little on the stretching coefficient η of circularly rectangular mesh cells in a range of η that is well sufficient for effective use of the multigrid method for arbitrary values of R/r smaller than ～ 5 × 10³.