{'fraction_non_alphanumeric': 0.03861044260751282, 'fraction_numerical': 0.009940357852882704, 'mean_word_length': 4.100320170757738, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Three alternating sign matrix identities in search of bijective proofs

This paper highlights three known identities, each of which involves sums over alternating sign matrices. While proofs of all three are known, the only known derivations are as corollaries of difficult results. The simplicity and natural combinatorial interpretation of these identities, however, suggest that there should be direct, bijective proofs.


Introduction
Alternating sign matrices (ASMs) are square matrices of 0s, 1s, and −1s with row and column-sums equal to 1 and with the restriction that the non-zero entries alternate signs across each row and down each column. An example is These are rich combinatorial objects with connections to many problems in algebraic combinatorics (see [2], [3], [12]). They also have many different representations. The representation that was used in Kuperberg's proof of the counting function for alternating sign matrices [9] and Zeilberger's proof of the refined alternating sign matrix conjecture [14] is the six-vertex model of statistical mechanics. These are directed graphs in which each vertex has in-degree two and out-degree two, and boundary conditions that the vertical arrows along the top and bottom are directed out, horizontal arrows along the left and right are directed in, as in the following directed graph.
To actually make this a directed graph on 25 vertices, we can identify the ith up-arrow along the top row with the ith right arrow along the left edge, and similarly identify bottom and right arrows. This is called a six-vertex model because there are six possible configurations at each vertex. We shall describe a vertex as horizontal if both in-edges are horizontal, vertical if both in-edges are vertical, and otherwise southwest, northwest, northeast, or southeast, according to the direction of the sum of the four vectors represented by the four adjacent edges.
It should be noted that the sum of all vertical vectors is zero, as is the sum of all horizontal vectors. It follows that there will always be an equal number of southwest and northeast vertices, and an equal number of southeast and northwest vertices.
Our example of a six-vertex model corresponds to our example of an alternating sign matrix. Each 1 in the ASM corresponds to a horizontal vertex, each −1 to a vertical vertex, and the 0s to the other vertices. This is a bijection because once the positions of the horizontal and vertical vertices are known, all other vertices are uniquely determined.
The six-vertex model is not the only insightful representation, but it is very suggestive, especially because there is also a natural connection between ASMs and complete directed graphs or tournaments. It would be very useful to have a direct bijective connection between ASMs and tournaments. In explaining the bijection that we seek, we shall also present two other related identities that cry out for bijective proofs.

The λ-determinant
The first two identities that I wish to present arise from the λ-determinant of Robbins and Rumsey [13]. This is based on the Desnanot-Jacobi adjoint matrix theorem [4], [7] that was used by Dodgson [5] to create his algorithm for evaluating determinants. Given a square matrix M , we let M i j denote M with row i and column j deleted. We then have that If we define the determinant of an empty matrix (0 × 0) to be 1 and the determinant of the 1 × 1 matrix (a) to be a, then equation (1) can be used as a recursive definition of the determinant. A natural one-parameter generalization of the determinant arises if we use the same initial conditions and replace the minus sign in the numerator of the recursive step by +λ: The following generalization of the Vandermonde determinant evaluation follows by induction.
If we expand a few λ-determinants, an interesting pattern emerges: The monomials in roman letters that correspond to permutation matrices are each multiplied by λ raised to the inversion number of the permutation. The other monomials in roman letters that appear, such as cf g −1 hij −1 kn, correspond to alternating sign matrices, in this case Each of these monomials is multiplied by a power of λ and a power of 1 + λ. Let A n be the set of n × n ASMs. Given A = (a ij ) ∈ A n , we define its inversion number, I(A), to be We define N (A) to be the number of −1s in A. The following characterization of the λ-determinant was published by Robbins and Rumsey in 1986 [13].
Zeilberger [15] has given a bijective proof of equation (1). It would be desirable to have a direct proof of Proposition 2 by finding a similar proof of equation (2) when the λ-determinant is defined by the right side of Proposition 2.
Problem 1 Find a direct, bijective proof of the following identity. Within each summation, the range of indices for the alternating sign matrices B and C is specified by the product term.

Directed Graphs
If we combine Propositions 1 and 2, we get that It is worth noting that analogs of this identity for other root systems have been found by Okada [11].
The left side of equation (5) can be interpreted as a sum over the set of tournaments on n vertices, calT n . Each binomial x i + λx j corresponds to the edge between vertices i and j. If the edge is directed from i to j, we choose x i . If it is directed from j to i, we choose λx j . Each tournament corresponds to a monomial in which the power of x i is ω(i), the out-degree of vertex i, and the power of λ is U (T ), the number of upsets in the tournament: j > i and j → i: We shall use the six-vertex model to interpret the right side of equation (5). We begin with the following observations which are explained below. The number of vertical vertices is immediate from the bijection, and there most be one more 1 than −1 in each row. A southwest vertex corresponds to a 0 of the ASM for which there is a 1 above it in its column (due north) with no other non-zero entries in between, and a 1 to its left in its row (due west) with no other non-zero entries in between.  (5) can be written as This suggests a natural bijection between tournaments on n vertices and sixvertex models on n 2 vertices in which we have chosen a direction (left or right) at each vertical vertex. Each vertex in the six-vertex model that has an in-edge from the north will define an out-edge of the tournament. Call this vertex of the six-vertex model an initiating vertex. If an initiating vertex is southwest, there is an out-edge to the left, and the corresponding edge in the tournament will contribute to the upset number. If the initiating vertex is southeast, there is an out-edge to the right, and the corresponding edge in the tournament will not contribute to the upset number. If the initiating vertex is vertical, we have a choice of taking either the left or right out-edge. The left choice contributes one to the upset number of the tournament; the right choice contributes nothing.
Problem 2 Find a bijective proof of equation (6).

The Izergin-Korepin Determinant Evaluation
Kuperberg's proof of the alternating sign matrix conjecture and Zeilberger's proof of the refined conjecture rest on the following determinant evaluation of Izergin [6], described in Korepin, Bogoliubov, and Izergin's Quantum Inverse Scattering Method [8].
Proposition 4 Given A ∈ A n , let (i, j) be the vertex in row i, column j of the corresponding six-vertex model, and let H, V, SE, SW, N E, N W be, respectively, the sets of horizontal, vertical, southeast, southwest, northeast, and northwest vertices. For indeterminants a, x 1 , . . . , x n , and y 1 , . . . , y n , we have that As Lascoux has pointed out [10], the right way to understand this identity is as an extension of Cauchy's This is true by inspection. The determinant times the product over i, j is an alternating polynomial in the x i and in the y j . Since any alternating polynomial is divisible by the Vandermonde product, the left side of this equality is a symmetric polynomial in the x i , and it is a symmetric polynomial in the y j . The degree in x 1 of this polynomial is zero, and the constant can be checked by induction.
Applying this same reasoning to the left side of equation (7), we see that it is a symmetric polynomial in the x i and in the y j . Its degree in x 1 is n − 1. On the right, we also have a polynomial in x 1 of degree n − 1. We need only check that these two sides agree for n values of x 1 . By induction, they agree at x 1 = −y 1 /a. If we can show that the right side is symmetric in the y j , then the identity is proven.
Symmetry follows from Baxter's triangle-to-triangle relation which was used by Izergin to prove that is symmetric in the x i , and it is symmetric in the y j .
We can set a = ω := e 2πi/3 , x j = −ωq j , and y j = q 1−j , evaluate the determinant, and then take the limit as q → 1 to get the number of ASMs of a given size: If we set a = −1, then the matrix for which we take the determinant is (1/(x 2 i − y 2 j )), which can be evaluated using Cauchy's formula, equation (8). The left side of equation (7) simplifies to (−1) n(n−1)/2 1≤i<j≤n (x i + x j )(y i + y j ).
From equation (6), each of these Vandermonde-type products can be written as a sum over alternating sign matrices. We let Ein i (A) be the number of vertices in row i with an in-edge from the left, Nin j (A) be the number of vertices in column j with an in-edge from below. Replacing y j by −y j and multiplying each side by x 1 · · · x n , the case a = −1 is equivalent to the identity Problem 3 Find a bijective proof of equation (11).