Generalized Rank Functions and Quilts of Alternating Sign Matrices

Sara C. Billey 1, Matjaž Konvalinka 2 · 2024

Read Generalized Rank Functions and Quilts of Alternating Sign Matrices by Sara C. Billey 1, Matjaž Konvalinka 2 (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03236.txt.

Introduction

Sara Billey and Matjaz Konvalinka introduce a new math object in a 2024 paper, called a quilt of alternating sign matrices. Quilts are built from two ordered sets and generalize several known ideas at once. A rank rule on parts of a matrix gives a quilt. When both orders are simple chains, a quilt matches a classic alternating sign matrix and its corner sums.

Quilts form a lattice with rich structure, holding famous sublattices such as matroids of a fixed rank. Counting quilts is hard in general. The authors prove two large counting results. One covers the case where one order has no links, and one covers the case where one is a chain. They also bound the count for a Boolean order.

Catalog record

CREATORSara C. Billey 1, Matjaž Konvalinka 2
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE113 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-03236

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Generalized Rank Functions and Quilts of Alternating Sign Matrices Sara C. Billey 1, Matjaž Konvalinka 2 Abstract . In this paper, we present new objects, quilts of alternating sign matrices with respect to two given posets. Quilts generalize several commonly used concepts in mathematics. For example, the rank function on submatrices of a matrix gives rise to a quilt with respect to two Boolean lattices. When the two posets are chains, a quilt is equivalent to an alternating sign matrix and its corresponding corner sum matrix. Quilts also generalize the monotone Boolean functions counted by the Dedekind numbers. Quilts form a distributive lattice with many beautiful properties and contain many classical and well-known sublattices, such as the lattice of matroids of a given rank and ground set. While enumerating quilts is hard in general, we prove two major enumerative results, when one of the posets is an antichain and when one of them is a chain. We also give some bounds for the number of quilts when one poset is the Boolean lattice. 1. Introduction The rank of a matrix is fundamental in mathematics, science, and engineering. The notion of rank can also be associated to graphs, matroids, and partial orders. One can refine the rank function to submatrices, subgraphs, etc. as well to get a family of ranks to associate to each object. We observe that such families always follow certain Boolean growth rules leading to the concept of a generalized rank function, which we call a quilt. The goal of this paper is to consider families of generalized rank functions and their connection with the well-studied alternating sign matrices (ASMs). We present some applications and some related enumerative questions. One motivating example of generalized rank functions comes from the Bruhat decomposition of the general linear group, permutations, and the geometry of flag manifolds. Given a matrix M\in GL_{n} , let \operatorname{rank}_{M}(i,j) be the rank of the submatrix of M on rows [i,n]=\{i,i+1,\dotsc,n\}\subseteq[n] and columns [j]=\{1,2,\dotsc,j\}\subseteq[n] . We call the n\times n matrix of values \operatorname{rank}_{M}(i,j) for i,j\in[n] the southwest rank table of M . The southwest rank tables of all n\times n invertible matrices can be classified by permutations in the symmetric group S_{n} and their associated permutation matrices. To find the permutation matrix to associate to M with the same southwest rank table, simply apply all possible elementary column reduction moves from left to right and elementary row reductions from bottom to top. These moves preserve the southwest rank of the matrix and, since M is invertible, will eventually terminate with a single nonzero entry in each row and column. Finally, rescale each entry to be 1 to obtain the associated permutation matrix. Bruhat order on the symmetric group S_{n} is the partial order given by v\leq w if and only if \operatorname{rank}_{M(v)}(i,j)\leq\operatorname{rank}_{M(w)}(i,j) for all 1\leq i,j\leq n , where M(v),M(w) are the permutation matrices corresponding to v,w . Bruhat order also determines the partial order on permutations given by containment of Schubert varieties in the flag manifold [ Ful97 , Ch. 9] . One observes from the Hasse diagram of S_{3} that Bruhat order is not a lattice, as a partial order. In general, the Dedekind–MacNeille completion of a finite poset is a lattice which contains the poset and is isomorphic to some subposet of any other lattice containing it. Lascoux and Schützenberger proved that the Dedekind–MacNeille completion of Bruhat order to a lattice is given by a natural partial order on square alternating sign matrices (ASMs) [ LS96 , Las08 ] . The (square) alternating sign matrices were defined by Mills, Robbins and Rumsey to be the n\times n matrices with entries from the set \{-1,0,1\} such that the nonzero entries in each row and each column alternate between 1 and -1 and must both start and end with 1 [ MRR83 , RR86 ] . They arise in the process of computing a determinant using Dodgson condensation. By definition, permutation matrices are examples of ASMs. The partial order on n\times n ASMs generalizing Bruhat order is given by A=(a_{ij})\leq B=(b_{ij}) if and only if the corresponding entries in the southwest corner sum matrices (CSMs) are increasing, (1.1) \sum_{i\leq i^{\prime}\leq n,1\leq j^{\prime}\leq j}a_{i^{\prime}j^{\prime}}\leq\sum_{i\leq i^{\prime}\leq n,1\leq j^{\prime}\leq j}b_{i^{\prime}j^{\prime}}\quad\mbox{for all }1\leq i,j\leq n. One can show that the ASM poset is a lattice with meet and join given by taking the entry-wise min and max in the corresponding corner sum matrices, and every such matrix does indeed correspond to an ASM. See Section 2 for more details. Since the corner sum matrix of a permutation matrix is exactly its southwest rank table, Bruhat order on S_{n} embeds into the ASM lattice. There are exactly \prod_{j=0}^{n-1}(3j+1)!/(n+j)! alternating sign matrices of size n\times n . This result was conjectured by Mills, Robbins and Rumsey and proved first by Zeilberger [ Zei96 ] , and further established independently by Kuperberg and Fischer [ Kup96 , Fis07 ] . It was notoriously difficult to prove the enumeration formula for square ASMs, and no simple formula for the number of rectangular ASMs is known. In this paper, we define new objects, quilts of alternating sign matrices , corresponding to two ranked partially ordered sets with greatest and least elements. They are a generalization of rectangular alternating sign matrices and their corner sum matrices. For example, the southwest rank table of a matrix in GL_{n} corresponds to a quilt on two copies of the chain C_{n} . Also, if B_{n} is the Boolean lattice of subsets of [n] ordered by inclusion and M is a k\times n matrix of full rank (i.e., the rank is \min\{k,n\} ), the function f_{M}:B_{k}\times B_{n}\longrightarrow\mathbb{N} given by setting f_{M}(I,J) to be the rank of the submatrix of M in rows I and columns J is a quilt of type (B_{k},B_{n}) . See Example 3.11 . Given the complexity of enumerating rectangular ASMs, it is surprising that we are still able to say quite a bit about the enumeration of quilts, especially when one of the two posets is an antichain (see Theorem 6.1 ) or a chain. One of our main results is the following theorem, more precisely stated as Theorem 7.1 . Here S(P) is the set of standard quilts, defined in Section 7 . Theorem 1.1 . The number of quilts of type (P,C_{n}) for n\geq\operatorname{rank}P is a polynomial of degree b(P)=\sum_{x\in P}\operatorname{rank}x . Furthermore, the leading coefficient is \frac{|S(P)|}{b(P)!} . The following is an easy consequence of the theorem and the hook-length formula for shifted standard tableaux. To the best of our knowledge, this is a new observation for rectangular ASMs. Corollary 1.2 . The number of rectangular ASMs of size k\times n , for n\geq k , is a polynomial in n of degree {\binom{k+1}{2}} with leading coefficient \prod_{i=0}^{k-1}\frac{(2i)!}{(k+i)!} . In general, it is rare to find exact formulas for quilt enumeration. We show the problem of counting quilts on two arbitrary posets is #P-complete by a reduction to the enumeration of antichains, see Theorem 3.18 . The quilts form a distributive lattice with a number of beautiful properties, see Sections 3 and 5 . They generalize the notions of matroids and flag matroids, as we will show in Section 5 . As

Read the complete text