Weighted Counting of Inversions on Alternating Sign Matrices
- PDF / 565,361 Bytes
- 17 Pages / 439.642 x 666.49 pts Page_size
- 30 Downloads / 161 Views
Weighted Counting of Inversions on Alternating Sign Matrices Masato Kobayashi1 Received: 11 April 2019 / Accepted: 15 November 2019 / © Springer Nature B.V. 2019
Abstract We generalize the author’s formula (2011) on weighted counting of inversions on permutations to one on alternating sign matrices. The proof is based on the sequential construction of alternating sign matrices from the unit matrix which essentially follows from the earlier work of Lascoux-Sch¨utzenberger (1996). Keywords Alternating sign matrix · Bigrassmannian permutation · Bruhat order · Inversion
1 Introduction 1.1 Alternating Sign Matrices and Others Alternating sign matrices (ASMs) are one of the most important topics in combinatorics. There is the long story [1] to the proofs by Zeilberger and Kuperberg (both 1996) on the total number of ASMs of size n being n−1 i=0
(3i + 1)! . (n + i)!
As Propp mentioned [9], there are actually many combinatorial objects which are equinumerous with ASMs (Fig. 1): • • • •
Monotone triangle DPP (Descending plane partition) Square ice FPL (Full packing of loops)
These are numbers in an array or graphs on a grid satisfying certain conditions (we omit details). Among these, we show that entries {−1, 0, 1} of ASMs are numerically meaningful with the connection to its poset structures and inversions often discussed on permutations. Masato Kobayashi
[email protected] 1
Department of Engineering, Kanagawa University, 3-27-1 Rokkaku-bashi, Yokohama 221-8686, Japan
Order
Fig. 1 Monotone triangle, DPP, square ice, FPL
1.2 Main Result We say (i, j ) is an inversion of a permutation w of {1, 2, . . . , n} if i < j and w(i) > w(j ). The inversion number of w is the number of such pairs, i.e., I (w) = |{(i, j ) | i < j and w(i) > w(j )}|. This idea plays a key role on Bruhat order in the theory of Coxeter groups (which has also a wide variety of applications in combinatorics and other areas). Definition 1.1 Define Bruhat order v ≤ w in Sn (the symmetric group) if there exists a sequence of permutations v = v0 , v1 , . . . , vm = w such that vk+1 = vk tik jk (tik jk a transposition) and I (vk ) < I (vk+1 ) for each k. Say a permutation v ∈ Sn is bigrassmannian if there exists a unique pair (i, j ) such that v −1 (i) > v −1 (i + 1) and v(j ) > v(j + 1). Define β : Sn → {0, 1, 2, . . . } by β(w) = |{v ∈ Sn | v ≤ w and v is bigrassmannian}|. The author [6, Theorem] showed that β(w) =
(w(i) − w(j ))
iw(j )
for all w ∈ Sn . We can interpret this formula as weighted counting of inversions on permutations. We can extend this statistic β for alternating sign matrices as follows: Definition 1.2 Let A = (aij ) be a square matrix of size n. We say that A is an alternating sign matrix (ASM) if for all i, j , we have j
aij ∈ {−1, 0, 1}, i k=1
akj ∈ {0, 1}
and
k=1 n k=1
aik ∈ {0, 1}, aik =
n
akj = 1.
k=1
Denote by An the set of all alternating sign matrices of size n.
Order
There is a well-known identification of permutations and permutation matrices: For w ∈ Sn , let 1 j = w(i), wij = δj w(i)
Data Loading...
