Sminaire Lotharingien de Combinatoire 46 (2001), Article B46c

2–ENUMERATIONS OF HALVED ALTERNATING SIGN MATRICES

THERESIA EISENKÖLBL

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.

                      E-mail: Theresia.Eisenkoelbl@univie.ac.at

Abstract. We compute 2–enumerations of certain halved alternating sign matrices. In one case the enumeration equals the number of perfect matchings of a halved Aztec diamond. In the other case the enumeration equals the number of perfect matchings of a halved fortress graph. Our results prove three conjectures by Jim Propp.

An alternating sign matrix is a square matrix with entries 0, 1, −1 where the entries 1 and −1 alternate in each row and column and the sum of entries in each row and column is equal to 1. An example of an alternating sign matrix of order 6 is

(\begin{matrix}0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & −1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & −1 & 1 \\ 0 & 1 & −1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{matrix}) .

Given a k × k alternating sign matrix with entries a_{ij}, 1 ≤ i, j ≤ k, we form the corresponding height matrix h with h_{ij} = i + j − 2 ∑_{l=1}^{i} ∑_{r=1}^{j} a_{lr}, 0 ≤ i, j ≤ k.

The height matrix for the above alternating sign matrix looks as follows:

h = (\begin{matrix}0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 2 & 3 & 4 & 5 \\ 2 & 1 & 2 & 3 & 4 & 3 & 4 \\ 3 & 2 & 3 & 2 & 3 & 4 & 3 \\ 4 & 3 & 2 & 3 & 2 & 3 & 2 \\ 5 & 4 & 3 & 4 & 3 & 2 & 1 \\ 6 & 5 & 4 & 3 & 2 & 1 & 0 \end{matrix}) .

A height matrix has first row and column (0, 1, …, k), last row and column (k, …, 1, 0) and adjacent entries differing by one.

Now we look at halved alternating sign matrices of order 2n, i.e., n × 2n–rectangles with entries 0, 1, −1 where the non–zero entries alternate in each row and column, the row sums equal 1 and the first non–zero entry in each column is 1 if there is any. There is a corresponding (n+1)×(2n+1)–rectangle of heights. In this article we only consider halved alternating sign matrices corresponding to height matrices of the form

2000 Mathematics Subject Classification. Primary 05A15 ; Secondary 05C70.

(\begin{matrix}0 & 1 & 2 & 3 & 4 & … & 2n − 2 & 2n − 1 & 2n \\ 1 & ? & ? & ? & ? & … & ? & ? & 2n − 1 \\ 2 & ? & ? & ? & ? & … & ? & ? & 2n − 2 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & … & ⋮ & ⋮ & ⋮ \\ n − 2 & ? & ? & ? & ? & … & ? & ? & n + 2 \\ n − 1 & ? & ? & ? & ? & … & ? & ? & n + 1 \\ n & c_{1} & n & c_{2} & n & … & n & c_{n} & n \end{matrix}) .  (1)

In [4], Propp states conjectures regarding weighted enumerations of halved alternating sign matrices with height matrices of the form (1). We prove some of these conjectures in the following theorems. Theorem 1. The weighted enumeration with weight 2^{N_{−}(A)} of halved alternating sign matrices A of order 2n with height matrix of the form (1) is 2^{n^{2}}, where N_{−}(A) is the number of (−1)’s in the halved alternating sign matrix A. Remark. The halved alternating sign matrices corresponding to height matrices of the form (1) are exactly the alternating sign matrices with U–turn boundary (UASM’s) defined in Greg Kuperberg’s paper [3]. Therefore, Theorem 1 is in fact a direct consequence of [3, Theorems 3 and 4]. Theorem 1 has also been independently proved by Robin Chapman (private communication), using again a different approach. Theorem 2. The weighted enumeration with weight 2^{N_{−}(A, even)+N_{+}(A, odd)} of halved alternating sign matrices A of order 2n with height matrix of the form (1) is 3^{n}5^{\binom{n}{2}}, where N_{−}(A, even) is the number of (−1)’s in the halved alternating sign matrix A in even position (i.e., the sum of the row index and the column index is even) and N_{+}(A, odd) is the number of 1’s in odd position. Remark. If we use the weight 2^{N_{−}(A, odd)+N_{+}(A, even)}, we get the same result because reflecting a halved alternating sign matrix corresponding to a height matrix of the form (1) with respect to a vertical symmetry axis gives a matrix of the same form and interchanges even and odd positions of entries. Remark. The weighted enumeration of all alternating sign matrices A of order n with weight 2^{N_{−}(A)} gives 2^{\binom{n}{2}}, the number of perfect matchings of an Aztec diamond of order n − 1, see [2].

The weighted enumeration of all alternating sign matrices of order 2n with weight 2^{N_{−}(A, even)+N_{+}(A, odd)} gives 5^{n^{2}}, the number of perfect matchings in a 2n × 2n fortress graph, see [6, Ch.3]. Theorem 3. The weighted enumeration with weight 2^{N_{−}(A, even)+N_{+}(A, odd)} of halved alternating sign matrices A of order 2n with height matrix of the form (1) with the additional constraint that c_{i} = n + 1 for all i equals 5^{\binom{n}{2}} for even n and 2^{n}5^{\binom{n}{2}} for odd n. If c_{i} = n − 1 for all i, it equals 2^{n}5^{\binom{n}{2}} for even n and 5^{\binom{n}{2}} for odd n.

Below we give a proof of Theorem 1 which is not based on Kuperberg’s results in [3]. Our proof of Theorem 2 starts on page 4. Finally, we sketch a proof of Theorem 3 on page 11.

Proof of Theorem 1. Since adjacent entries in the height matrix differ by one, each c_{i} is either n − 1 or n + 1.

Figure 1. A 2 × 3 Aztec rectangle with no vertices missing.

0  0  1  0  0  0 1  0  −1  0  1  0 0  0  1  0  −1  1

Figure 2. The set of perfect matchings corresponding to a halved alternating sign matrix.

= + Figure 3.

There is a well–known 1 to 2^{N_{−}(A)} correspondence between (halved) alternating sign matrices and perfect matchings of (halved) Aztec diamonds (cf. [1]). An m × k Aztec rectangle is a graph composed of m×k squares (see Figure 1). A halved Aztec diamond is an Aztec rectangle with the shape of half a square, with some vertices in the two bottom rows missing (see Figure 4). A perfect matching (1–factor) of a graph is a set of edges such that every vertex of the graph lies on exactly one of these edges. In the remainder of this paper we will use the term matching instead of perfect matching.

We write the entries of the halved alternating sign matrix in the squares of the halved Aztec diamond as shown in Figure 2. The corresponding 2^{N_{−}(A)} matchings can be found by demanding that a square surrounding a −1, 0 or 1 contains exactly 2, 1 or 0 edges of the matching, respectively. The edges in the squares containing a 0 can be found by joining the two vertices lying in the direction of the next 1’s in the same row and column (if there is no 1 in the column we take the bottom vertex). There are two choices for the squares containing −1 as shown in Figure 3. This accounts for the weight 2^{N_{−}(A)}.

Close inspection of the correspondence reveals that the condition on the last row of the height matrix determines which of the vertices of the halved Aztec diamond are missing. The halved Aztec diamond is an n × (2n − 1) Aztec rectangle with missing last row of vertices and missing vertices in the next row in positions a_{1}, …, a_{n}, say. It is easy to see that we have either a_{i} = 2i − 1 or a_{i} = 2i corresponding to c_{i} = n − 1 or n + 1, respectively. Therefore, we have to sum over 2^{n} different boundary conditions.

Figure 4.

Fortunately, we can add pairs of vertices in the last two rows as shown in Figure 2 and just count all matchings of the emerging new region (see Figure 4). The vertices in the bottom row can be matched either to the northeast or to the northwest. This corresponds to the possible choices for the a_{i}.

Now we can apply the following lemma (cf. [2, p.18]).

Lemma 4. The number of perfect matchings of an m × k Aztec rectangle, where all the vertices in the bottom row have been removed except for the x_{1}st, the x_{2}nd, …, and the x_{m}th vertex equals

\frac{2^{\binom{m+1}{2}}}{∏_{i=1}^{m}(i − 1)!} ∏_{1≤i<j≤m}(x_{j} − x_{i}).

To apply the lemma to our case, we have to set k = 2n − 1, m = n and x_{i} = 2i − 1. We obtain that our 2–enumeration of halved alternating sign matrices equals

\frac{2^{\binom{n+1}{2}}}{∏_{i=1}^{n}(i − 1)!} ∏_{1≤i<j≤n}(2j − 2i) = 2^{\binom{n+1}{2}}2^{\binom{n}{2}} = 2^{n^{2}},

as desired. □

Proof of Theorem 2. Now we have the weight 2^{N_{−}(A, even)+N_{+}(A, odd)}. We will illustrate all steps of the proof by the example of halved alternating sign matrices of order 6 (cf. Figure 5). From there it will be clear what happens in the general case.

The first step is another well–known bijection between alternating sign matrices and a family of graphs called fortresses. These are squares arranged in a rectangular shape separated by single edges. On the right, the left and the upper side of the rectangle edges are appended to every other square (see Figure 5 for a 3 × 6 fortress graph with some extra edges appended to the squares in the bottom row). We have the following replacement rules:

• 1’s in even places and −1’s in odd places translate to

0  0  1  0  0  0 1  0  −1  0  1  0 0  0  1  0  −1  1

Figure 5. The corresponding matchings of the fortress graph.

a  d c b A C B  D 1 1 11  a′ d′ c′ b′ A C B  D →

Figure 6. Urban Renewal, a′ = \frac{c}{ac+bd}, b′ = \frac{d}{ac+bd}, c′ = \frac{a}{ac+bd}, d′ = \frac{b}{ac+bd}.

• −1’s in even places and 1’s in odd places translate to

=  +

• 0’s translate to

or the rotations of this graph.

The edges of the squares corresponding to ±1 determine uniquely which of the four possibilities should be chosen for each 0. An example of the correspondence is shown in Figure 5. The reader should note that there are two choices of edges for −1’s in even places and for 1’s in odd places. This accounts for the weight.

It is not difficult to see that the restriction on the last row of the height matrix corresponds to a condition on the extra pending edges at the bottom row of the resulting graph. Either both edges in the positions 2i and 2i − 1 are contained in the graph or neither.

In the following we will repeatedly use a well–known local modification of a graph called urban renewal, which changes the enumeration of perfect matchings only by a global factor (see [5]). The modification is shown in Figure 6. Before we can explain this modification, we have to make a few definitions. Let G be a graph with weights assigned to its edges. Then the weight of a matching is the product of the weights of the edges it contains. The weighted enumeration of matchings M(G) is now defined as the sum of the weights of all possible matchings of the graph G.

Urban renewal can now be described as follows. We start with a graph G which looks locally like the left–hand–side of Figure 6. Then we contract the four edges of weight 1 and change the weights a, b, c, d to a′, b′, c′, d′. We obtain a graph G′ which looks locally like the right–hand–side of Figure 6 and like G everywhere else. The new edge weights a′, b′, c′, d′ of the resulting G′ are defined by a′ = \frac{c}{ac+bd}, b′ = \frac{d}{ac+bd}, c′ = \frac{a}{ac+bd}, d′ = \frac{b}{ac+bd}, whereas all other weights stay the same.

The weighted enumerations of matchings M(G) and M(G′) of the two graphs are related in the following way:

Lemma 5. Let G be a graph which looks locally like the left–hand–side of Figure 6 and let G′ be the graph which looks locally like the right–hand–side and like G elsewhere. Then the weighted enumeration of matchings of the new graph G′ equals the weighted enumeration of matchings of the graph G multiplied by ac + bd, i.e.,

M(G) = M(G′)(ac + bd).

We want to apply urban renewal to all squares in even position in the graph in Figure 5. First, we append two vertical edges to squares in the last row in even position which have no downward–pointing edge appended. In the example in Figure 5, this happens to the fifth square in the bottom row, resulting in the upper graph in Figure 7 (at this point, the dotted circles should be ignored). This does not change the enumeration of perfect matchings since there is only one possibility for the new vertices to be paired. We obtain an n × 2n fortress with some edges appended. Now, we can apply urban renewal to every square in even position (the circled squares in Figure 7). There are n^{2} of these squares with ac + bd = 2, which yields a factor of 2^{n^{2}}. The resulting graph is an n × 2n Aztec rectangle where every other square has edges of weight \frac{1}{2} (see the dotted lines in the bottom graph in Figure 7) and some downward–pointing edges appended to the last row of squares. It is easy to see that the original restriction on the last row of the height matrix now translates to the restriction that for each i there is exactly one edge in the position 2i − 1 or 2i. Similar to the proof of Theorem 1, we can interpret the sum of the corresponding 2^{n} terms as the number of matchings of the weighted halved Aztec diamond G_{n} in Figure 8 because every vertex in its last row can be either matched to the left or to the right.

Therefore, we have to determine 2^{n^{2}} × M(G_{n}).

We will use urban renewal repeatedly to reduce the graph G_{n} to the graph G_{n−1}. The first step consists of replacing every vertex of G_{n} by a line of three vertices so that the weighted enumeration of matchings remains unchanged. The resulting graph in our example is shown in Figure 9. Now we are in the position to apply urban renewal to all squares in the graph. The factor ac + bd equals \frac{1}{2} · \frac{1}{2} + \frac{1}{2} · \frac{1}{2} = \frac{1}{2} for half of the squares and 1 · 1 + 1 · 1 = 2 for the other half. Thus, the factors resulting from urban renewal

↓ 2^{n^{2}}

Figure 7. The dotted lines have weight \frac{1}{2}.

Figure 8. G_{n} for n = 3.

Figure 9. Each vertex is split into three.

Figure 10. The graph obtained by applying urban renewal to all squares in Figure 9.

cancel each other. Square edges of weight 1 become edges of weight \frac{1}{2} and vice versa and in our example we obtain the graph shown in Figure 10.

The pending edges along the border of the graph have to be in every perfect matching and can be removed together with the two endpoints without changing the enumeration of perfect matchings. For the same reason, we can fill the “dents” in the bottom row by adding some edges which have to be in every perfect matching. The resulting graph is shown in Figure 11.

Now we (almost) repeat the last two steps. We replace each vertex by three vertices to obtain the graph in Figure 12. Note that the squares in the bottom row contain only one edge of weight \frac{1}{2} each.

The next step is to apply urban renewal to all squares. The product of the factors ac + bd is easily seen to be (\frac{5}{4})^{(n−1)(2n−1)} (\frac{3}{2})^{2n−1}. The new edge weights are \frac{2}{3}, \frac{1}{3}, \frac{2}{5} and

Figure 11. Remove and add some forced edges of weight 1.

Figure 12. The graph obtained by replacing all vertices in Figure 11 by three vertices.

\frac{4}{5} (only the forced appended edges have still weight 1). The resulting graph is shown in Figure 13.

Now we mark every other vertex in the bottommost row with a dotted circle starting with the second vertex (see Figure 13). Similarly, we mark all vertices immediately above and to the left of the dotted circles with an unbroken circle. We divide the weight of the edges incident to one of the n − 1 points marked by an unbroken circle by two and multiply the weight of the edges incident to the n − 1 points marked by a dotted circle by two. This does not change the weighted enumeration of matchings.

Then we strip off all the forced edges (i.e., edges that must be contained in every perfect matching) and obtain the graph shown in Figure 14. It is easy to see that every matching contains exactly 2n − 2 of the edges with weight \frac{1}{3} or \frac{2}{3} (the double edges and dotted double edges) and exactly 2(n − 1)^{2} edges with weight \frac{2}{5} or \frac{4}{5}. If we now divide the weights of all double edges and dotted double edges by \frac{2}{3} and the weights of all the Figure 13. The double edges have weight \frac{2}{3}, the dotted double edges have weight \frac{1}{3}, the dotted edges have weight \frac{2}{5}, the pending edges have weight 1 and the remaining edges have weight \frac{4}{5}.

Figure 14. The double edges have weight \frac{2}{3}, the dotted double edges have weight \frac{1}{3}, the dotted edges have weight \frac{2}{5} and the remaining edges have weight \frac{4}{5}.

Figure 15. The dotted edges have weight \frac{1}{2}, the other edges have weight 1.

other edges by \frac{4}{5}, we obtain a graph with edges of weight 1 and \frac{1}{2} only. This changes the weighted enumeration by a factor of (\frac{2}{3})^{2n−2} (\frac{4}{5})^{2(n−1)^{2}}.

The resulting graph is shown in Figure 15. It is clearly the mirror image of G_{n−1} (compare Figure 8).

Therefore, we obtain for the weighted enumeration of matchings of G_{n}:

Figure 16.

M(G_{n}) = (\frac{5}{4})^{(n−1)(2n−1)} (\frac{3}{2})^{2n−1} (\frac{2}{3})^{2n−2} (\frac{4}{5})^{2(n−1)^{2}} M(G_{n−1}) = \frac{3 · 5^{n−1}}{2^{2n−1}} M(G_{n−1}).

Since M(G_{1}) is easily seen to be \frac{3}{2}, we get for our weighted enumeration of halved alternating sign matrices

2^{n^{2}}M(G_{n}) = 2^{n^{2}} \frac{3^{n}5^{\binom{n}{2}}}{2^{n^{2}}} = 3^{n}5^{\binom{n}{2}}.

□

Sketch of the proof of Theorem 3. The proof is analogous to the proof of Theorem 2. For example, in the case c_{i} = n − 1 for all i, we use the bijection to fortress graphs and apply urban renewal to all the squares. We obtain a weighted halved Aztec diamond of order 2n (see Figure 16 for the case n = 3). Imitating the steps in the proof of Theorem 2, we can reduce it to the weighted halved Aztec diamond of order 2n − 2. In this way, we again obtain a simple recursion which gives the results stated in Theorem 3.

□

References

[1] Mihai Ciucu, Perfect matchings of cellular graphs, J. Alg. Combin. 5 (1996), 87–103.

[2] M. Elkies, G. Kuperberg, M. Larsen and J. Propp, Alternating sign matrices and domino tilings (Part 1), J. Alg. Combin. 1 (1992), 111–132.

[3] G. Kuperberg, Symmetry classes of alternating-sign matrices under one roof, arXiv:math.CO/0008184.

[4] J. Propp, The Many Faces of Alternating–Sign Matrices, preprint.

[5] J. Propp, Generalized Domino–Shuffling, preprint.

[6] B.–Y. Yang, Two Enumeration Problems about the Aztec Diamonds, Ph.D. thesis, Mass. Inst. Tech., 1991.