# Enumeration of alternating sign matrices of even size (quasi)-invariant under a quarter-turn rotation

Jean-Christophe Aval and Philippe Duchon†

LaBRI, Université Bordeaux 1, CNRS
351 cours de la Libération, 33405 Talence cedex, FRANCE

**Abstract.** The aim of this work is to enumerate alternating sign matrices (ASM) that are quasi-invariant under a quarter-turn. The enumeration formula (conjectured by Duchon) involves, as a product of three terms, the number of unrestrited ASm's and the number of half-turn symmetric ASM's.

**Résumé.** L'objet de ce travail est d'énumérer les matrices à signes alternants (ASM) quasi-invariantes par rotation d'un quart-de-tour. La formule d'énumération, conjecturée par Duchon, fait apparaître trois facteurs, comprenant le nombre d'ASM quelconques et le nombre d'ASM invariantes par demi-tour.

## 1 Introduction

An alternating sign matrix is a square matrix with entries in $\{-1, 0, 1\}$ and such that in any row and column: the non-zero entries alternate in sign, and their sum is equal to 1. Their enumeration formula was conjectured by Mills, Robbins and Rumsey (5), and proved by Zeilberger (9), and almost simultaneously by Kuperberg (3). Kuperberg used a bijection between the ASM's and the states of the statistical square-ice model, for which he studied and computed the partition function. He also used this method in (4) to obtain many enumeration or equinumeration results for various classes of symmetries of ASM's, most of them having been conjectured by Robbins (7). Among these results can be found the following remarkable one.

**Theorem 1** (Kupeberg). The number $A_{QT}(4N)$ of ASM's of size $4N$ invariant under a quarter-turn (QTASM's) is related to the number $A(N)$ of (unrestricted) ASM's of size $N$ and to the number $A_{HT}(2N)$ of ASM's of size $2N$ invariant under a half-turn by the formula:

$$A_{QT}(4N) = A_{HT}(2N)A(N)^2. \qquad (1)$$

More recently, Razumov and Stroganov (6) applied Kuperberg's strategy to settle the following result, also conjectured by Robbins (7) and relative to QTASM's of odd size.

**Theorem 2** (Razumov, Stroganov). The numbers of QTASM's of odd size are given by the following formulas, where $A_{HT}(2N + 1)$ is the number of HTASM's of size $2N + 1$:

$$A_{QT}(4N - 1) = A_{HT}(2N - 1)A(N)^2 \qquad (2)$$

$$A_{QT}(4N + 1) = A_{HT}(2N + 1)A(N)^2. \qquad (3)$$

It is easy to observe (and will be proved in Section 2) that the set of QTASM's of size $4N + 2$ is empty. But, by slightly relaxing the symmetry condition at the center of the matrix, Duchon introduced in (2) the notion of ASM's quasi-invariant under a quarter turn (the definition will be given in Section 2) whose class is non-empty in size $4N + 2$. Moreover, he conjectured for these qQTASM's an enumeration formula that perfectly completes the three previous enumeration results on QTASM. This is the aim of this paper to establish this formula.

<footnote>†This work has been supported by the ANR project MARS (BLAN06-2_0193)</footnote>
**Theorem 3** The number $A_{QT}(4N + 2)$ of $qQTASM$ of size $4N + 2$ is given by:

$$A_{QT}(4N + 2) = A_{HT}(2N + 1)A(N)A(N + 1). \quad (4)$$

This paper is organized as follows: in Section 2, we define $qQTASM$'s; in Section 3, we recall the definitions of square ice models, precise the parameters and the partition functions that we shall study, and give the formula corresponding to equation (4) at the level of partition functions; the Section 4 is devoted to the proofs.

## 2 ASM's quasi-invariant under a quarter-turn

The class of ASM's invariant under a rotation by a quarter-turn (QTASM) is non-empty in size $4N - 1$, $4N$, and $4N + 1$. But this is not the case in size $4N + 2$.

**Lemma 4** There is no $QTASM$ of size $4N + 2$.

**Proof:** Let us suppose that $M$ is a $QTASM$ of even size $2L$. Now we use the fact that the size of an ASM is given by the sum of its entries, and the symmetry of $M$ to write:

$$2L = \sum_{1 \le i,j \le 2L} M_{i,j} = 4 \times \sum_{1 \le i,j \le L} M_{i,j} \quad (5)$$

which implies that the size of $M$ has to be a multiple of 4. □

Duchon introduced in (2) a notion of ASM's quasi-invariant under a quarter-turn, by slightly relaxing the symmetry condition at the center of the matrix. The definition is more simple when considering the height matrix associated to the ASM, but can also been given directly.

**Definition 5** An ASM $M$ of size $4N + 2$ is said to be quasi-invariant under a quarter-turn ($qQTASM$) if its entries satisfy the quarter-turn symmetry

$$M_{4N+2-j+1,4N+2-i+1} = M_{i,j} \quad (6)$$

except for the four central entries ($M_{2N,2N}$, $M_{2N,2N+1}$, $M_{2N+1,2N}$, $M_{2N+1,2N+1}$) that have to be either $(0, -1, -1, 0)$ or $(1, 0, 0, 1)$.

We give below two examples of $qQTASM$'s of size 6, with the two possible patterns at the center.

$$\left(\begin{array}{cccccc}
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & -1 & 1 & 0 \\
0 & 1 & -1 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0
\end{array}\right)$$

$$\left(\begin{array}{cccccc}
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & -1 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & -1 & 1 \\
1 & -1 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & -1 & 1 & 0 \\
0 & 0 & 0 & 1 & 0 & 0
\end{array}\right)$$

In the next section, we associate square ice models to ASM's with various types of symmetry.

## 3 Square ice models and partition functions

### 3.1 Notations

Using Kuperberg's method we introduce square ice models associated to ASM, HTASM and QTASM. We recall here the main definitions and refer to (4) for details and many examples.

Let $a \in \mathbb{C}$ be a global parameter. For $x$ any complex number different from zero, we denote $\bar{x} = 1/x$, and we define:

$$\sigma(x) = x - \bar{x}. \quad (7)$$
<figure><img src="image_1.png" /><figcaption>Fig. 3: Partition functions for HTASM's</figcaption></figure>

<figure><img src="image_2.png" /><figcaption>Fig. 4: Partition functions for (q)QTASM of even size</figcaption></figure>
**Theorem 6** When $a = \omega_6 = \exp(i\pi/3)$, one has for $N \ge 1$:

$$Z_{QT}(4N; X_{2N-1}, x, y) = \sigma(a)^{-1} Z_{HT}(2N; X_{2N-1}, x, y) Z(N; X_{2N-1}, x) Z(N; X_{2N-1}, y) \quad (8)$$

and

$$Z_{QT}(4N + 2; X_{2N}, x, y) = \sigma(a)^{-1} Z_{HT}(2N + 1; X_{2N}, x, y) Z(N; X_{2N}) Z(N + 1; X_{2N}, x, y). \quad (9)$$

Equation (9) is new; equation (8) is due to Kuperberg (4) for the case $x = y$. To see that Theorem 6 implies Theorem 3, we just have to observe that when $a = \omega_6$ and all the variables equal to 1, then the weights at each vertex is $\sigma(a) = \sigma(a^2)$ thus the partition function reduces (up to multiplication by $\sigma(a)^{\text{number of vertices}}$) to the number of states.

# 4 Proofs

In this extended abstract, we shall only give the main ideas of the proofs. Most of them are greatly inspired from (4). To prove Theorem 6, the method is to identify both sides of equations (8) and (9) as Laurent polynomials, and to produce as many specializations of the variables that verify the equalities, as needed to imply these equations in full generality.

## 4.1 Laurent polynomials

Since the weight of any vertex is a Laurent polynomial in the variables $x_i$, $x$ and $y$, the partition functions are Laurent polynomials in these variables. Moreover they are centered Laurent polynomials, i.e. their lowest degree is the negative of their highest degree (called the half-width of the polynomial). In order to divide by two the number of required specializations in $x$, we shall deal with Laurent polynomials of given parity in this variable. To do so, we group together the states with a given orientation (indicated as subscripts in the following notations) at the edge where the parameters $x$ and $y$ meet.

So let us consider the partition functions $Z_{QT}^{\leftarrow}(4N, X_{2N-1}, x, y)$ and $Z_{QT}^{\rightarrow}(4N, X_{2N-1}, x, y)$, respectively odd and even parts of $Z_{QT}(4N; X_{2N-1}, x, y)$ in $x$; $Z_{QT}^{\leftarrow}(4N + 2; X_{2N}, x, y)$ and $Z_{QT}^{\rightarrow}(4N + 2; X_{2N}, x, y)$, respectively odd and even parts of $Z_{QT}(4N + 2; X_{2N}, x, y)$ in $x$; $Z_{HT}^{\leftarrow}(2N; X_{2N-1}, x, y)$ and $Z_{HT}^{\rightarrow}(4N; X_{2N-1}, x, y)$, respectively parts with the parity of $N$ and of $N-1$ of $Z_{HT}(4N; X_{2N-1}, x, y)$ in $x$; and $Z_{HT}^{\leftarrow}(2N + 1; X_{2N}, x, y)$ and $Z_{HT}^{\rightarrow}(2N + 1; X_{2N}, x, y)$, respectively parts with the parity of $N-1$ and of $N$ of $Z_{HT}(2N + 1; X_{2N}, x, y)$ in $x$.

With these notations, the equations (8) et (9) are equivalent to the following:

$$\sigma(a) Z_{QT}^{\leftarrow}(4N; X_{2N-1}, x, y) = Z_{HT}^{\leftarrow}(2N; X_{2N-1}, x, y) Z(N; X_{2N-1}, x) Z(N; X_{2N-1}, y) \quad (10)$$

$$\sigma(a) Z_{QT}^{\rightarrow}(4N; X_{2N-1}, x, y) = Z_{HT}^{\rightarrow}(2N; X_{2N-1}, x, y) Z(N; X_{2N-1}, x) Z(N; X_{2N-1}, y) \quad (11)$$

$$\sigma(a) Z_{QT}^{\leftarrow}(4N + 2; X_{2N}, x, y) = Z_{HT}^{\leftarrow}(2N + 1; X_{2N}, x, y) Z(N + 1; X_{2N}, x, y) Z(N; X_{2N}) \quad (12)$$

$$\sigma(a) Z_{QT}^{\rightarrow}(4N + 2; X_{2N}, x, y) = Z_{HT}^{\rightarrow}(2N + 1; X_{2N}, x, y) Z(N + 1; X_{2N}, x, y) Z(N; X_{2N}) \quad (13)$$

**Lemma 7** Both left-hand side and right-hand side of equations (10-13) are centered Laurent polynomials in the variable $x$, odd or even, of respective half-widths $2N-1, 2N-2, 2N$, and $2N-1$. Thus to prove each of these identities we have to exhibit specializations of $x$ for which the equality is true, and in number strictly exceeding the half-width.

**Proof:** To compute the half-width of these partition functions, just count the number of vertices in the ice models, and take care that non-zero entries of the ASM (i.e. the first two orientations of Figure 1) give constant weight $\sigma(a^2)$. $\square$
<figure><img src="image_3.png" /></figure>

□

**Lemma 15** [specialization of $Z_{HT}$] If we denote

$$A_H^1(x_1, X_{2N}\setminus x_1) = \prod_{1\le k \le N} \sigma(a^2 x_1 \bar{x}_k) \prod_{N+1\le k \le 2N} \sigma(ax_k \bar{x}_1)$$

$$\bar{A}_H^1(x_1, X_{2N}\setminus x_1) = \prod_{1\le k \le N} \sigma(a^2 x_k \bar{x}_1) \prod_{N+1\le k \le 2N} \sigma(ax_1 \bar{x}_k)$$

$$A_H^0(x_N, X_{2N-1}\setminus x_N) = \prod_{1\le k \le N-1} \sigma(ax_k \bar{x}_N) \prod_{N\le k \le 2N-1} \sigma(a^2 x_N \bar{x}_k)$$

$$\bar{A}_H^0(x_N, X_{2N-1}\setminus x_N) = \prod_{1\le k \le N-1} \sigma(ax_N \bar{x}_k) \prod_{N\le k \le 2N-1} \sigma(a^2 x_k \bar{x}_N),$$

then for $\star = \nearrow, \searrow, \searrow$ and $\Box = \searrow, \nearrow, \searrow, \nearrow$ respectively, we have

$$Z_{HT}^*(2N+1; X_{2N}, x, \mathbf{ax}_1) = A_H^1(x_1, X_{2N}\setminus x_1) Z_{HT}^*(2N; X_{2N}\setminus x_1, x_1, x_1) \quad (26)$$

$$Z_{HT}^{\square}(2N+1; X_{2N}, x, \bar{\mathbf{ax}}_1) = \bar{A}_H^1(x_1, X_{2N}\setminus x_1) Z_{HT}^*(2N; X_{2N}\setminus x_1, x_1, x_1) \quad (27)$$

$$Z_{HT}^*(2N; X_{2N-1}, x, \mathbf{ax}_N) = \sigma(ax\bar{x}_N)A_H^0(x_N, X_{2N-1}\setminus x_N)Z_{HT}^*(2N-1; X_{2N-1}\setminus x_N, x_N, x_N) \quad (28)$$

$$Z_{HT}^{\square}(2N; X_{2N-1}, \bar{\mathbf{ax}}_N, y) = \sigma(ax_N \bar{y}) \bar{A}_H^0(x_N, X_{2N-1}\setminus x_N) Z_{HT}^*(2N-1; X_{2N-1}\setminus x_N, y, x_N) \quad (29)$$

**Proof:**

The proof is similar to the previous one, with the difference that before looking at fixed edges, we need to multiply the partition function by a given factor; we interpret this operation by a modification of the graph of the ice model and apply Lemma 14. It turns out that in each case, the additional factors are exactly cancelled by the weights of fixed vertices.

To prove (26), we multiply the left-hand side by

$$\prod_{N+1\le k \le 2N} \sigma(a^2 x_k \bar{y}),$$

which is equivalent to adding to the line of parameter $y$ a new line $\bar{ay}$ just below the grid; the Lemma 14 transforms the graph of Figure 6(a) into the graph of Figure 6(b). When we put $y = ax_1$, we get the indicated fixed edges, which gives as partition function

$$\prod_{N+1\le k \le 2N} \sigma^2(ax_k \bar{x}_1) \prod_{1\le k \le N} \sigma(a^2 x_1 \bar{x}_k) Z_{HT}(2N; X_{2N}\setminus x_1, x_1, x_1).$$

Since $a^2 x_k \bar{y} = ax_k \bar{x}_1$, the equation simplifies. Ton conclude, we observe that if we start with an edge going out from the crossing $x/x_{2N}$ (function $Z_{HT}^{\nwarrow}$) we get at the end the same orientation (function $Z_{HT}^{\nearrow}$). □
<figure><img src="image_4.png" /><figcaption>Fig. 6: Proof of (26)</figcaption></figure>

**Lemma 16** [specialization of $Z_{QT}$] If we denote

$$ \bar{A}_Q(x_1, X_{m-1}\backslash x_1) = \prod_{1 \le k \le m-1} \sigma(a^2 x_k \bar{x}_1) \sigma(ax_1 \bar{x}_k), $$

$$ A_Q(x_1; X_{m-1}\backslash x_1) = \prod_{1 \le k \le m-1} \sigma(a^2 x_1 \bar{x}_k) \sigma(ax_k \bar{x}_1), $$

then for $\star = \downarrow, \uparrow, \leftarrow$ and $\Box = \uparrow, \leftarrow, \rightarrow$ respectively, we have:

$$ Z_{\mathbb{Q}T}^*(2m; X_{m-1}, \bar{\mathbf{ax}}_1, y) = \sigma(ax_1 \bar{y}) \bar{A}_Q(x_1, X_{m-1}) Z_{\mathbb{Q}T}^*(2m-2; X_{m-1}\backslash x_1, y, x_1) \quad (30) $$

$$ Z_{\mathbb{Q}T}^{\square}(2m; X_{m-1}, x, \mathbf{ax}_1) = \sigma(ax\bar{x}_1) A_Q(x_1; X_{m-1}\backslash x_1) Z_{\mathbb{Q}T}^{\star}(2m-2; X_{m-1}\backslash x_1, x_1, x) \quad (31) $$

**Proof:** Similar to the proof of Lemma 15. $\square$

**Remark 17** By using the (pseudo-)symmetry in $(x, y)$, we may transform any specialization of the variable $y$ into a specialization of the variable $x$. Moreover, by using Lemma 11 and (when $a = \omega_6$) Lemma 12, we obtain for $Z$, $Z_{HT}$ and $Z_{QT}Z_{2N}$ specialization now have to compare them.

## 4.4 Special value of the parameter $a$; conclusion

When $a = \omega_6 = \exp(i\pi/3)$, two new ingredients may be used. The first one is Lemma 12, as mentioned in Remark 17. The second one is that with this special value of $a$:

$$ \sigma(a) = \sigma(a^2) \qquad \sigma(a^2 x) = -\sigma(\bar{a}x) = \sigma(a\bar{x}). \qquad (32) $$

which implies that the products appearing in Lemmas 13, 15 and 16 may be written in a more compact way:

$$ A(x_{N+1}, X_{2N}\backslash\{x_1, x_{N+1}\}) = \sigma(a) \prod_{k \ne 1, N+1} \sigma(ax_k \bar{x}_{N+1}), $$

$$ \bar{A}(x_{N+1}, X_{2N}\backslash\{x_1, x_{N+1}\}) = \sigma(a) \prod_{k \ne 1, N+1} \sigma(ax_{N+1} \bar{x}_k), $$

$$ A_H^1(x_1, X_{2N}\backslash x_1) = \prod_{1 \le k \le 2N} \sigma(ax_k \bar{x}_1), $$
$$ \overline{A}_H^1(x_1, X_{2N}\setminus x_1) = \prod_{1 \le k \le 2N} \sigma(ax_1 \overline{x}_k), $$

$$ A_H^0(x_N, X_{2N-1}\setminus x_N) = \prod_{1 \le k \le 2N-1} \sigma(ax_k \overline{x}_N) $$

$$ \overline{A}_H^0(x_N, X_{2N-1}\setminus x_N) = \prod_{1 \le k \le 2N-1} \sigma(ax_N \overline{x}_k), $$

$$ \overline{A}_Q(x_1, X_{m-1}\setminus x_1) = \prod_{1 \le k \le m-1} \sigma^2(ax_1 \overline{x}_k), $$

$$ A_Q(x_1, X_{m-1}\setminus x_1) = \prod_{1 \le k \le m-1} \sigma^2(ax_k \overline{x}_1). $$

Thus we get by comparing:

$$ A(x_i, X_{2N}\setminus x_i, x) A_H^1(x_i, X_{2N}\setminus x_i) = \sigma(ax \overline{x}_i) A_Q(x_i, X_{2N}\setminus x_i) $$

$$ \overline{A}(x_i, X_{2N}\setminus x_i, x) \overline{A}_H^1(x_i, X_{2N}\setminus x_i) = \sigma(ax_i \overline{x}) \overline{A}_Q(x_i, X_{2N}\setminus x_i), $$

whence (10) and (11) imply that (12) and (13) are true (in size $4N + 2$) for the $2N$ specializations $y = a^{(+,-)} x_i$ ($1 \le i \le N$). It is enough to prove (13) (Laurent polynomials of half-width $2N - 1$), but we still need one specialization to get (12) (half-width $2N$).

For (10) and (11), we observe the same kind of simplification

$$ A(x_i, X_{2N-1}\setminus x_i) \sigma(ax \overline{x}_i) A_H^0(x_i, X_{2N-1}\setminus x_i) = \sigma(ax \overline{x}_i) A_Q(x_i, X_{2N-1}\setminus x_i), $$

whence (13) and (12) for the size $4N - 2$ imply that (10) and (11) are true for the $N$ specializations $x = ax_i$, $N \le i \le 2N - 1$. We obtain in the same way the coincidence for the $N$ specializations $x = \overline{ax}_i$, $N \le i \le 2N - 1$. Thus we have $2N$ specializations of $x$: it is enough both for (10) (half-width $2N - 1$), and for (11) (half-width $2N - 2$).

At this point, we have almost proved

$$ ((10) \text{ and } (11), \text{ size } 4N) \implies (((12) \text{ and } (13), \text{ size } 4N + 2) \implies ((10) \text{ and } (11), \text{ size } 4N + 4); $$

almost, because we still need one specialization for (12).

We get this missing speciazation, not directly for $Z_{\overrightarrow{QT}}$, $Z_{\overleftarrow{QT}}$, $Z_{\overrightarrow{HT}}$ and $Z_{\overleftarrow{HT}}$, but for the original series $Z_{\overrightarrow{QT}}(4N + 2; X_{2N}, x, y)$ and $Z_{\overrightarrow{HT}}(2N + 1; X_{2N}, x, y)$: indeed if we set $x = ay$ we may apply Lemma 14.

<figure><img src="image_5.png" /></figure>

$$ Z_{\overrightarrow{QT}}(4N + 2; X_{2N}, ay, y) = \sigma(a) \prod_{1 \le k \le 2N} \sigma(ax_k \overline{y}) \sigma(a^2 y \overline{x}_k) Z_{\overrightarrow{QT}}(4N; X_{2N} \setminus x_{2N}, x_{2N}, x_{2N}) $$
<figure><img src="image_6.png" /></figure>

$$Z_{HT}(2N + 1; X_{2N}, ay, y) = \left( \prod_{1 \le k \le N} \sigma(ax_k \bar{y}) \prod_{N+1 \le k \le 2N} \sigma(a^2 y \bar{x}_k) \right) Z_{HT}(2N; X_{2N} \setminus x_N, x_N, x_N)$$

This way, we get another point where (9) is true, and thus, because we already have (13), by difference we obtain that (12) holds for $y = \bar{a}x$.

This completes the proof of Theorem 6.

## References

[1] J.-C. AVAL, *On the symmetry of the partition function of some square ice models*, to appear in Theor. Math. Phys, arXiv:0903.0777.

[2] P. DUCHON, *On the link pattern distribution of quarter-turn symmetric FPL configurations*, FPSAC 2008, Valparaiso (Chile), DMTCS proceedings, 331–342.

[3] G. KUPERBERG, *Another proof of the alternating sign matrices conjecture*, Internat. Math. Research Not., **1996** (1996), 139–150.

[4] G. KUPERBERG, *Symmetry classes of alternating sign matrices under one roof*, Ann. Math. **156** (2002) 835–866.

[5] W. MILLS, D. ROBBINS, H. RUMSEY, *Alternating sign matrices and descending plane partitions*, J. Combin. Th. Ser. A **34** (1983), 340–359.

[6] A. V. RAZUMOV, Y. G. STROGANOV, *Enumeration of quarter-turn symmetric alternating sign matrices of odd order*, Theoret. Math. Phys. **149** (2006) 1639–1650.

[7] D. ROBBINS, *Symmetry classes of alternating sign matrices*, arXiv:math.CO/0008045.

[8] Y. G. STROGANOV, *A new way to deal with Izergin-Korepin determinant at root of unity*, arXiv:math-ph/0204042.

[9] D. ZEILBERGER, *Proof of the alternating sign matrix conjecture*, Electronic J. Combinatorics **3**, No. 2 (1996), R13, 1–84.