# The polytope of Tesler matrices

Karola Mészáros, Alejandro H. Morales, Brendon Rhoades

► To cite this version:

Karola Mészáros, Alejandro H. Morales, Brendon Rhoades. The polytope of Tesler matrices. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.205-216, 10.46298/dmtcs.2475 . hal-01337826

HAL Id: hal-01337826

https://hal.science/hal-01337826

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# The polytope of Tesler matrices
(extended abstract)

Karola Mészáros$^{1†}$ and Alejandro H. Morales$^{2‡}$ and Brendon Rhoades$^{3§}$

**Abstract.** We introduce the Tesler polytope $Tes_n(a)$, whose integer points are the Tesler matrices of size $n$ with hook sums $a_1, a_2, \dots, a_n \in \mathbb{Z}_{\ge 0}$. We show that $Tes_n(a)$ is a flow polytope and therefore the number of Tesler matrices is given by the type $A_n$ Kostant partition function evaluated at $(a_1, a_2, \dots, a_n, -\sum_{i=1}^n a_i)$. We describe the faces of this polytope in terms of "Tesler tableaux" and characterize when the polytope is simple. We prove that the $h$-vector of $Tes_n(a)$ when all $a_i > 0$ is given by the Mahonian numbers and calculate the volume of $Tes_n(1, 1, \dots, 1)$ to be a product of consecutive Catalan numbers multiplied by the number of standard Young tableaux of staircase shape.

**Résumé.** On présente le polytope de Tesler $Tes_n(a)$, dont les points réticulaires sont les matrices de Tesler de taille $n$ avec des sommes des équerres $a_1, a_2, \dots, a_n \in \mathbb{Z}_{\ge 0}$. On montre que $Tes_n(a)$ est un polytope de flux. Donc le nombre de matrices de Tesler est donné par la fonction de Kostant de type $A_n$ évaluée à $(a_1, a_2, \dots, a_n, -\sum_{i=1}^n a_i)$. On décrit les faces de ce polytope en termes de "tableaux de Tesler" et on caractérise quand le polytope est simple. On montre que l'h-vecteur de $Tes_n(a)$, quand tous les $a_i > 0$, est donnée par le nombre de permutations avec un nombre donné d'inversions et on calcule le volume de $Tes_n(1, 1, \dots, 1)$ comme un produit de nombres de Catalan consécutives multiplié par le nombre de tableaux standard de Young en forme d'escalier.

**Keywords:** Tesler matrices, flow polytopes, Kostant partition function

# 1 Introduction

Tesler matrices have played a major role in the works [1][8][9] in the context of diagonal harmonics. We examine them from a different perspective in this paper: we study the polytope, which we call the Tesler polytope, consisting of upper triangular matrices with nonnegative real entries with the same restriction as Tesler matrices.

Let $U_n(\mathbb{R}_{\ge 0})$ be the set of $n \times n$ upper triangular matrices with nonnegative real entries. The $k^{\text{th}}$ **hook sum** of a matrix $(x_{i,j})$ in $U_n(\mathbb{R}_{\ge 0})$ is the sum of all the elements of the $k^{\text{th}}$ row minus the sum of the elements in the $k^{\text{th}}$ column excluding the term in the diagonal: $x_{k,k} + \sum_{j=k+1}^n x_{k,j} - \sum_{i=1}^{k-1} x_{i,k}$. Given

<footnote>$^{1}$Department of Mathematics, Cornell University, Ithaca NY</footnote>

<footnote>$^{2}$Department of Mathematics, University of California, Los Angeles, Los Angeles CA</footnote>

<footnote>$^{3}$Department of Mathematics, University of California, San Diego, La Jolla CA</footnote>

<footnote>†karola@math.cornell.edu Partially supported by an NSF Postdoctoral Research Fellowship DMS-1103933.</footnote>

<footnote>‡ahmorales@math.ucla.edu Was supported by a postdoctoral fellowship from CRM-ISM and LaCIM.</footnote>

<footnote>§bprhoades@math.ucsd.edu Partially supported by NSF grant DMS-1068861.</footnote>
<figure><img src="image_2.png" /><figcaption>**Fig. 1:** The seven 3 × 3 Tesler matrices with hook sums (1, 1, 1). Six of them are vertices of the graph (depicted in gray) of the Tesler polytope $Tes_n(1, 1, 1)$.</figcaption></figure>

a length $n$ vector $\mathbf{a} = (a_1, a_2, \dots, a_n) \in (\mathbb{Z}_{\ge 0})^n$ of nonnegative integers, the **Tesler polytope** $Tes_n(\mathbf{a})$ with hook sums $\mathbf{a}$ is the set of matrices in $U_n(\mathbb{R}_{\ge 0})$ where the $k^{\text{th}}$ hook sum equals $a_k$, for $k = 1, \dots, n$:

$$ Tes_n(\mathbf{a}) = \{(x_{i,j}) \in U_n(\mathbb{R}_{\ge 0}) \mid x_{k,k} + \sum_{j=k+1}^{n} x_{k,j} - \sum_{i=1}^{k-1} x_{i,k} = a_k, 1 \le k \le n \}. $$

The lattice points of $Tes_n(\mathbf{a})$ are called **Tesler matrices** with hook sums $\mathbf{a}$. These are $n \times n$ up-per triangular matrices $B = (b_{i,j})$ with nonnegative integer entries such that for $k = 1, \dots, n$, $b_{k,k} + \sum_{j=k+1}^{n} b_{k,j} - \sum_{i=1}^{k-1} b_{i,k} = a_k$. The set and number of such matrices are denoted by $T_n(\mathbf{a})$ and $T_n(\mathbf{a})$ respectively. See Figure 1 for an example of the seven Tesler matrices in $T_3(1, 1, 1)$ and [14, A008608] for the sequence $\{T_n(1, 1, \dots, 1)\}$ added by Glenn Tesler in the late 1990s.

Tesler matrices reappeared recently in Haglund's study of diagonal harmonics [9] and their combinatorics and further properties were explored in [1][8][12]. The flavor of the results obtained for Tesler matrices in connection with diagonal harmonics is illustrated by the following example. For the definitions regarding the polynomial in $\mathbb{N}[q, t]$ in the left hand side of (1.1) we refer the reader to [9].

**Example 1.1** When $\mathbf{a} = \mathbf{1} := (1, 1, \dots, 1) \in \mathbb{Z}^n$, Haglund [9] showed that

$$ \partial_{p_1}^n \nabla e_n = \frac{(-1)^n}{(1-t)^n (1-q)^n} \sum_{A \in \mathcal{T}_n(1,1,\dots,1)} \prod_{i,j} wt(a_{ij}), \quad (1.1) $$

$$ \text{where } wt(b) = -(1-t)(1-q)^{\frac{q^b-t^b}{q-t}} \text{ if } b > 0 \text{ and } wt(0) = 1. $$

The starting point for our investigation is the observation stated in the next lemma.

**Lemma 1.2** The Tesler polytope $Tes_n(\mathbf{a})$ is a flow polytope $Flow_n(\mathbf{a})$,

$$ Tes_n(\mathbf{a}) \cong Flow_n(\mathbf{a}). \quad (1.2) $$

We now define flow polytopes to make Lemma 1.2 clear. For an illustration of the correspondence of polytopes in Lemma 1.2 see Figure 2.

Given $\mathbf{a} = (a_1, a_2, \dots, a_n)$, let $Flow_n(\mathbf{a})$ be the **flow polytope** of the complete graph $k_{n+1}$ with netflow $a_i$ on vertex $i$ for $i = 1, \dots, n$ and the netflow on vertex $n+1$ is $-\sum_{i=1}^n a_i$. This polytope is the set of functions $f: E \to \mathbb{R}_{\ge 0}$, called flows, from the edge set $E = \{(i, j) \mid 1 \le i < j \le n+1\}$ of $k_{n+1}$
<figure><img src="image_3.png" /><figcaption>**Fig. 2:** Correspondence between a 3 × 3 Tesler matrix with hook sums (1, 1, 1), an integer flow in the complete graph $k_4$ and a vector partition of (1, 1, 1, -3) into $e_i - e_j$ $1 \le i < j \le 4$.</figcaption></figure>

to the set of nonnegative real numbers such that for $k = 1, \dots, n$, $\sum_{j>s} f(k, j) - \sum_{i<k} f(i, k) = a_k$. This forces $\sum_{i=1}^n f(i, n+1) = \sum_{i=1}^n a_i$.

The type $A_n$ **Kostant partition function** $K_{A_n}(\mathbf{a}')$ is the number of ways of writing $\mathbf{a}' := (\mathbf{a}, -\sum_{i=1}^n a_i)$ as an $\mathbb{N}$-combination of the type $A_n$ positive roots $e_i - e_j$, $1 \le i < j \le n+1$ without regard to order. Kostant partition functions are useful in representation theory to calculate tensor product and weight multiplicities. The value $K_{A_n}(\mathbf{a}')$ is also the number of lattice points of the polytope $\text{Flow}_n(\mathbf{a})$. Thus the following lemma is immediate from Lemma 1.2.

**Lemma 1.3** The number $T_n(\mathbf{a})$ of Tesler matrices with hook sums $(a_1, a_2, \dots, a_n)$ is given by the value $K_{A_n}(\mathbf{a}')$ of the Kostant partition function at $(a_1, \dots, a_n, -\sum_{i=1}^n a_i)$,

$$T_n(\mathbf{a}) = K_{A_n}(\mathbf{a}'). \qquad (1.3)$$

In the next example we include a brief discussion of another flow polytope of the complete graph, namely, $\text{Flow}_n(1, 0, \dots, 0)$.

**Example 1.4** The polytope $\text{Flow}_n(1, 0, \dots, 0)$ is known as the **Chan-Robbins-Yuen polytope** [6, 7]. It has dimension $\binom{n}{2}$ and $2^{n-1}$ vertices. Stanley-Postnikov (unpublished), and Baldoni-Vergne [3, 4] proved that the normalized volume of this polytope is given by a value of the Kostant partition function (see (3.2)). Then Zeilberger [16] used a variant of the Morris constant term identity [13] to compute this Kostant partition function as the product of the first $n-2$ Catalan numbers.

$$\text{vol} \, \text{Flow}_n(1, 0, \dots, 0) = K_{A_{n-1}}(0, 1, 2, \dots, n-2, -\binom{n-1}{2}) = \prod_{i=0}^{n-2} \frac{1}{i+1} \binom{2i}{i}. \qquad (1.4)$$

**The study of $\text{Tes}_n(\mathbf{a})$:** Examples 1.1 and 1.4 served as our inspiration for studying the Tesler polytope $\text{Tes}_n(\mathbf{a}) \cong \text{Flow}_n(\mathbf{a})$. In Section 2 we prove that for any vector $\mathbf{a} \in (\mathbb{Z}_{\ge 0})^n$ of nonnegative integers, the polytope $\text{Tes}_n(\mathbf{a})$ has dimension $\binom{n}{2}$ and at most $n!$ vertices, all of which are integral. When $\mathbf{a} \in (\mathbb{Z}_{>0})^n$ consists entirely of positive entries, we prove that $\text{Tes}_n(\mathbf{a})$ has exactly $n!$ vertices. In this case, these vertices are the **permutation Tesler matrices** of order $n$, which are the $n \times n$ Tesler matrices with at most one nonzero entry in each row.

Recall that if $P$ is a $d$-dimensional polytope, the $f$-vector $f(P) = (f_0, f_1, \dots, f_d)$ of $P$ is given by letting $f_i$ equal the number of faces of $P$ of dimension $i$. The $f$-polynomial of $P$ is the corresponding generating function $\sum_{i=0}^d f_i x^i$. A polytope $P$ is simple if each of its vertices is incident to $\dim(P)$ edges. If $P$ is a simple polytope, the $h$-polynomial of $P$ is the polynomial $\sum_{i=0}^d h_i x^i$ which is related
to the f-polynomial of P by the equation $\sum_{i=0}^{d} f_i(x-1)^i = \sum_{i=0}^{d} h_i x^i$. The coefficient sequence $(h_0, h_1, \dots, h_d)$ of the h-polynomial of P is called the h-vector of P.

In Section 2 we characterize the vectors $\mathbf{a} \in (\mathbb{Z}_{>0})^n$ for which the Tesler polytope $\text{Tes}_n(\mathbf{a})$ is simple (Theorem 2.7). In particular, we show that $\text{Tes}_n(\mathbf{a})$ is simple whenever $\mathbf{a} \in (\mathbb{Z}_{>0})^n$. In this case, the sum of its h-vector entries is given by $\sum_{i=0}^{\binom{n}{2}} h_i = f_0$. Since $\text{Tes}_n(\mathbf{a})$ for $\mathbf{a} \in (\mathbb{Z}_{>0})^n$ has $n!$ vertices, this implies that $\sum_{i=0}^{\binom{n}{2}} h_i = n!$. One might expect that the h-polynomial $\sum_{i=0}^{\binom{n}{2}} h_i x^i$ of $\text{Tes}_n(\mathbf{a})$ is the generating function of some interesting statistic on permutations. Indeed, we show in Section 2 that the h-polynomial of the Tesler polytope is the generating function for Coxeter length.

**Theorem 1.5** (Theorem 2.7, Corollary 2.9) Let $\mathbf{a} \in (\mathbb{Z}_{>0})^n$ be a vector of positive integers. The polytope $\text{Tes}_n(\mathbf{a})$ is a simple polytope and its h-vector is given by the Mahonian numbers, that is, $h_i$ is the number of permutations of $\{1, 2, \dots, n\}$ with $i$ inversions. We have

$$ \sum_{i=0}^{\binom{n}{2}} f_i(x-1)^i = \sum_{i=0}^{\binom{n}{2}} h_i x^i = [n]!_x, $$

where $[n]!_x = \prod_{i=1}^{n} (1 + x + x^2 + \dots + x^{i-1})$ and the $f_i$ are the f-vector entries of $\text{Tes}_n(\mathbf{1})$.

Just as the Chan-Robbins-Yuen polytope $\text{Tes}_n(1, 0, \dots, 0) \cong \text{Flow}_n(1, 0, \dots, 0)$ has a product formula for its normalized volume involving Catalan numbers, so does the Tesler polytope $\text{Tes}_n(\mathbf{1}) := \text{Tes}_n(1, 1, \dots, 1)$.

**Theorem 1.6** (Corollary 3.5) The normalized volume of the Tesler polytope $\text{Tes}_n(\mathbf{1})$, or equivalently of the flow polytope $\text{Flow}_n(1, 1, \dots, 1)$ equals

$$ \begin{aligned} \text{vol } \text{Tes}_n(\mathbf{1}) &= \text{vol } \text{Flow}_n(1, 1, \dots, 1) = \frac{\binom{n}{2}! \cdot 2^{\binom{n}{2}}}{\prod_{i=1}^{n} i!} \\ &= |SYT_{(n-1,n-2,\dots,1)}| \cdot \prod_{i=0}^{n-1} \text{Cat}(i), \end{aligned} \quad (1.5) $$

where $\text{Cat}(i) = \frac{1}{i+1} \binom{2i}{i}$ is the $i$th Catalan number and $|SYT_{(n-1,n-2,\dots,1)}|$ is the number of Standard Young Tableaux of staircase shape $(n-1, n-2, \dots, 1)$.

The proof of this result is sketched in Section 3. The proof uses the following new iterated constant term identity similar to the Morris constant term identity [13].

**Lemma 3.4.1** For $n \ge 2$ and nonnegative integers $a, c$ we have that

$$ \begin{aligned} \text{CT}_{x_n} \cdots \text{CT}_{x_1} (x_1 + x_2 + \cdots + x_n)^{(a-1)n+c\binom{n}{2}} & \prod_{i=1}^{n} x_i^{-a+1} \prod_{1 \le i < j \le n} (x_i - x_j)^{-c} \\ ={}& \Gamma(1 + (a-1)n + c\binom{n}{2}) \prod_{i=0}^{n-1} \frac{\Gamma(1 + c/2)}{\Gamma(1 + (i+1)c/2)\Gamma(a + ic/2)}, \end{aligned} $$

where $\text{CT}_y f(y)$ means the constant term in $y$ of $f(y)$ and $\Gamma(\cdot)$ is the Gamma function. In particular, the value at $a = c = 1$ yields (1.5).
For details on the proofs please see the complete version [11] of this paper.

## 2 The face structure of $Tes_n(a)$

Let $a \in (\mathbb{R}_{\ge 0})^n$. The aim of this section is to describe the face poset of $Tes_n(a)$. It will turn out that the combinatorial isomorphism type of $Tes_n(a)$ only depends on the positions of the zeros in the integer vector $a$.

Let $rstc_n$ denote the reverse staircase of size $n$; the Ferrers diagram of $rstc_4$ is shown below.

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

We use the “matrix coordinates” $\{(i,j) \mid 1 \le i \le j \le n\}$ to describe the cells of $rstc_n$. An **a-Tesler tableau** $T$ is a 0, 1-filling of $rstc_n$ which satisfies the following three conditions:

1. for $1 \le i \le n$, if $a_i > 0$, there is at least one 1 in row $i$ of $T$,

2. for $1 \le i < j \le n$, if $T(i, j) = 1$, then there is at least one 1 in row $j$ of $T$, and

3. for $1 \le j \le n$, if $a_j = 0$ and $T(i, j) = 0$ for all $1 \le i < j$, then $T(j, k) = 0$ for all $j \le k \le n$.

For example, if $n = 4$ and $a = (7, 0, 3, 0)$, then three **a-Tesler tableaux** are shown below. We write the entries of $a$ in a column to the left of a given **a-Tesler tableau**.

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

The **dimension** $\dim(T)$ of an **a-Tesler tableau** $T$ is $\sum_{i=1}^n (r_i - 1)$, where

$$r_i = \begin{cases} \text{the number of 1's in row } i \text{ of } T & \text{if row } i \text{ of } T \text{ is nonzero,} \\ 1 & \text{if row } i \text{ of } T \text{ is zero.} \end{cases}$$

From left to right, the dimensions of the tableaux shown above are 3, 1, and 3.

Given two **a-Tesler tableaux** $T_1$ and $T_2$, we write $T_1 \le T_2$ to mean that for all $1 \le i \le j \le n$ we have $T_1(i, j) \le T_2(i, j)$. Moreover, we define a 0, 1-filling $\max(T_1, T_2)$ of $rstc_n$ by $\max(T_1, T_2)(i, j) = \max(T_1(i, j), T_2(i, j))$.

We start with two lemmas on **a-Tesler tableaux**. Our first lemma states that any two zero-dimensional **a-Tesler tableaux** are componentwise incomparable.

**Lemma 2.1** Let $a \in (\mathbb{R}_{\ge 0})^n$ and let $T_1$ and $T_2$ be two **a-Tesler tableaux** with $\dim(T_1) = \dim(T_2) = 0$. If $T_1 \le T_2$, then $T_1 = T_2$.

Our next lemma states that the operation of componentwise maximum preserves the property of being an **a-Tesler tableau**.
**Corollary 2.9** Let $\mathbf{a} \in (\mathbb{R}_{>0})^n$ be a vector of positive integers. The h-polynomial of the Tesler polytope $\text{Tes}_n(\mathbf{a})$ is the Mahonian distribution

$$ \sum_{i=0}^{\binom{n}{2}} h_i x^i = [n]!_x = (1+x)(1+x+x^2)\cdots(1+x+x^2+\cdots+x^{n-1}). $$

Corollaries 2.8 and 2.9 are also true for Tesler polytopes $\text{Tes}_n(\mathbf{a})$, where $\epsilon(\mathbf{a}) = +^{n-1}0$. In light of Theorem 2.7, it is natural to ask for an analog to these results when $\epsilon(\mathbf{a})$ is of the form $+0+^{n-2}$ or $+0+^{n-3}0$. Such an analog is provided by the following corollary.

**Corollary 2.10** Let $\mathbf{a} \in (\mathbb{R}_{\ge 0})^n$ and assume that $\epsilon(\mathbf{a})$ has one of the forms $+0+^{n-2}$ or $+0+^{n-3}0$. Let $P$ be the quotient polytope $(\Delta_{n-2} \times \Delta_{n-1})/\sim$, where we declare $(p, q) \sim (p', q)$ whenever $q \in \Delta_{n-1}$ belongs to the facet of $\Delta_{n-1}$ defined by $x_2 = 0$ and $p, p' \in \Delta_{n-2}$.

The face poset of the polytope $\text{Tes}_n(\mathbf{a})$ is isomorphic to the face poset of the Cartesian product $\Delta_1 \times \Delta_2 \times \cdots \Delta_{n-3} \times P$. Moreover, we have that $\text{Tes}_n(\mathbf{a})$ has $2(n-1)!$ vertices and h-polynomial $(1+x^{n-1})[n-1]!_x$.

**Remark 2.11** When $\mathbf{a} \in (\mathbb{R}_{>0})^n$ is a vector of positive integers, Theorem 2.5 can be deduced from results of Hille [10]. In particular, if $Q$ denotes the quiver on the vertex set $Q_0 = [n+1]$ with arrows $i \to j$ for all $1 \le i < j \le n+1$ and if $\theta: Q_0 \to \mathbb{R}$ denotes the weight function defined by $\theta(i) = a_i$ for $1 \le i \le n$ and $\theta(n+1) = -a_1 - \cdots - a_n$, then the Tesler polytope $\text{Tes}_n(\mathbf{a})$ is precisely the polytope $\Delta(\theta)$ considered in [10, Theorem 2.2]. By the argument in the last paragraph of [10, Theorem 2.2] and [10, Proposition 2.3], the genericity condition on $\theta$ in the hypotheses of [10, Theorem 2.2] is equivalent to every entry of $\mathbf{a}$ being positive. The conclusion of [10, Theorem 2.2] is essentially the same as the special case of Theorem 2.5 when $\mathbf{a} \in (\mathbb{R}_{>0})^n$. When some entries of $\mathbf{a}$ are zero, in the terminology of [10] the weight function $\theta$ lies on a wall, and the results of [10] do not apply to $\text{Tes}_n(\mathbf{a})$.

**Remark 2.12** When $\mathbf{a} \in (\mathbb{R}_{>0})^n$ is a vector of positive integers, the simplicity of $\text{Tes}_n(\mathbf{a})$ guaranteed by Theorem 2.7 had been observed previously in the context of flow polytopes. The condition that every entry in $\mathbf{a}$ is positive is equivalent to $\mathbf{a}$ lying in the “nice chamber” defined by Baldoni and Vergne in [3, p. 458]. In [5, p. 798], Brion and Vergne observe that this condition on $\mathbf{a}$ implies the simplicity of $\text{Tes}_n(\mathbf{a})$. The simplicity of $\text{Tes}_n(\mathbf{a})$ in this case can also be derived from Hille’s characterization of the face poset [10] using exactly the same argument as in the proof of Theorem 2.7.

## 3 Volume of the Tesler polytope $\text{Tes}_n(1)$

The aim of this section is to sketch the proof of Theorem 1.6 through a sequence of results. For ease of reading the section is broken down into several subsections. We start by previous results on volumes and Ehrhart polynomials of flow polytopes and then prove specific lemmas regarding $\text{Tes}_n(1)$.

In this section we work in the field of iterated formal Laurent series with $m$ variables as discussed by Haglund, Garsia and Xin in [8, §4]. We choose a total order of the variables: $x_1, x_2, \dots, x_m$ to extract iteratively coefficients, constant coefficients, and residues of an element $f(\mathbf{x})$ in this field. We denote these respectively by

$$ \mathrm{CT}_{x_m} \cdots \mathrm{CT}_{x_1} f, \quad [\mathbf{x}^\mathbf{a}] := [x_m^{a_m} \cdots x_1^{a_1}] f, \quad \mathrm{Res}_{x_m} \cdots \mathrm{Res}_{x_1} f. $$

For more on these iterative coefficient extractions see [15, §2].
## 3.1 Generating function of $K_{A_n}(\mathbf{a}')$ and the Lidskii formulas

Recall that by Lemmas 1.2 and 1.3 we have that the normalized volume vol Tes$_n(\mathbf{a})$ equals the normalized volume vol Flow$_n(\mathbf{a})$ and that the number $T_n(\mathbf{a})$ of Tesler matrices is given by the Kostant partition function $K_{A_n}(\mathbf{a}')$. By definition, the latter is given by the following iterated coefficient extraction.

$$ K_{A_n}(\mathbf{a}') = [\mathbf{x}^{\mathbf{a}'}] \prod_{1 \le i < j \le n+1} (1 - x_i x_j^{-1})^{-1}. \quad (3.1) $$

Assume that $\mathbf{a} = (a_1, a_2, \dots, a_n)$ satisfies $a_i \ge 0$ for $i = 1, \dots, n$. Then the Lidskii formulas [3, Proposition 34, Theorem 37] state that

$$ \mathrm{vol} \, \mathrm{Flow}_n(\mathbf{a}) = \sum_i \binom{\binom{n}{2}}{i_1, i_2, \dots, i_n} a_1^{i_1} \cdots a_n^{i_n} \cdot K_{A_{n-1}}(i_1 - n + 1, i_2 - n + 2, \dots, i_n), \quad (3.2) $$

and

$$ K_{A_n}(\mathbf{a}') = \sum_i \binom{a_1 + n - 1}{i_1} \binom{a_2 + n - 2}{i_2} \cdots \binom{a_n}{i_n} \cdot K_{A_{n-1}}(i_1 - n + 1, i_2 - n + 2, \dots, i_n), \quad (3.3) $$

where both sums are over weak compositions $\mathbf{i} = (i_1, i_2, \dots, i_n)$ of $\binom{n}{2}$ with $n$ parts which we denote as $\mathbf{i} \models \binom{n}{2}$, $\ell(\mathbf{i}) = n$.

**Example 3.1** The Tesler polytope $\mathrm{Tes}_3(1, 1, 1) \cong \mathrm{Flow}_3(1, 1, 1)$ has normalized volume 4 since by (3.2)

$$ \mathrm{vol} \, \mathrm{Flow}_3(1, 1, 1) = \binom{3}{3, 0, 0} K_{A_2}(1, -1, 0) + \binom{3}{2, 1, 0} K_{A_2}(0, 0, 0) + 0 = 1 \cdot 1 + 3 \cdot 1 = 4. $$

And this polytope has $T_3(1, 1, 1) = K_{A_3}(1, 1, 1, -3) = 7$ lattice points (the seven $3 \times 3$ Tesler matrices with hook sums $(1, 1, 1)$; see Figure 1). Indeed by (3.3)

$$ K_{A_3}(1, 1, 1, -3) = \binom{1+2}{3} \binom{1+1}{0} K_{A_2}(1, -1, 0) + \binom{1+2}{2} \binom{1+1}{1} K_{A_2}(0, 0, 0) = 7. $$

**Example 3.2** [3] If one uses (3.2) on the Chan-Robbins-Yuen polytope $\mathrm{Tes}_n(e_1)$ one obtains

$$ \mathrm{vol} \, \mathrm{Tes}_n(1, 0, \dots, 0) = K_{A_{n-1}}(-\binom{n-1}{2}, -n+2, \dots, -1, 0), $$

since the only composition $\mathbf{i}$ that does not vanish is $i_1 = \binom{n}{2}$, $i_2 = 0, \dots, i_n = 0$. This is equivalent to the first identity in Example 1.4.

Next, we use (3.2) and the generating series (3.1) of Kostant partition functions to write the volume of $\mathrm{Tes}_n(1)$ as an iterated constant term of a formal Laurent series.

**Lemma 3.3**

$$ \mathrm{vol} \, \mathrm{Tes}_n(1) = \mathrm{CT}_{x_n} \cdots \mathrm{CT}_{x_1} (x_1 + \cdots + x_n)^{\binom{n}{2}} \prod_{1 \le i < j \le n} (x_j - x_i)^{-1}, \quad (3.4) $$

where $\mathrm{CT}_{x_n} \cdots \mathrm{CT}_{x_1} f$ denotes the iterated constant term of $f$.
## 3.2 A Morris-type constant term identity

Let $e_k = e_k(x_1, x_2, \dots, x_n)$ denote the $k$th elementary symmetric polynomial. In particular $e_1 = x_1 + x_2 + \dots + x_n$. For $n \ge 2$ and nonnegative integers $a, c$ we define $L_n(a, c)$ to be the following iterated constant term:

$$L_n(a, c) := \mathrm{CT}_{x_n} \cdots \mathrm{CT}_{x_1} e_1^{(a-1)n+c\binom{n}{2}} \prod_{i=1}^{n} x_i^{-a+1} \prod_{1 \le i < j \le n} (x_i - x_j)^{-c}. \quad (3.5)$$

Note that by Lemma 3.3 we have that

$$\mathrm{vol} \, \mathrm{Tes}_n(\mathbf{1}) = L_n(1, 1). \quad (3.6)$$

Next we give a product formula for $L_n(a, c)$ that for $a = c = 1$ yields (1.5). We postpone the proof to the next section.

**Lemma 3.4** For $n \ge 2$ and nonnegative integers $a, c$ we have that

$$L_n(a, c) := \mathrm{CT}_{x_n} \cdots \mathrm{CT}_{x_1} e_1^{(a-1)n+c\binom{n}{2}} \prod_{i=1}^{n} x_i^{-a+1} \prod_{1 \le i < j \le n} (x_i - x_j)^{-c}$$

equals

$$L_n(a, c) = \Gamma(1 + (a-1)n + c\binom{n}{2}) \prod_{i=0}^{n-1} \frac{\Gamma(1+c/2)}{\Gamma(1+(i+1)c/2)\Gamma(a+ic/2)}, \quad (3.7)$$

where $\Gamma(\cdot)$ is the Gamma function.

**Corollary 3.5**

$$L_n(1, c) = \Gamma(1 + c\binom{n}{2}) \prod_{i=0}^{n-1} \frac{\Gamma(1 + c/2)}{\Gamma(1 + c(i+1)/2)\Gamma(1 + ic/2)} = (c\binom{n}{2})! \frac{2^{c\binom{n}{2}+n-cn}(2c-1)!!^n}{\prod_{i=0}^{n-1} (ci+1)!}$$

and in particular

$$L_n(1, 1) = \frac{\binom{n}{2}! \cdot 2^{\binom{n}{2}}}{\prod_{i=1}^{n} i!} = |SYT_{(n-1,n-2,\dots,1)}| \cdot \prod_{i=1}^{n-1} \mathrm{Cat}(i).$$

where $|SYT_{(n-1,n-2,\dots,1)}|$ denotes the number of Standard Young Tableaux of staircase shape $(n-1, n-2, \dots, 1)$.

The following remarks give an alternate constant term description for $L_n(a, c)$ which resembles a known constant term identity.

**Remark 3.6** Consider the constant term of $(1 - e_1)^{-1} \prod_{i=1}^{n} x_i^{-a+1} \prod_{1 \le i < j \le n} (x_i - x_j)^{-c}$. Since $(1 - e_1)^{-1} = \sum_{k \ge 0} e_1^k$ then by linearity of $\mathrm{CT}_{x_n} \cdots \mathrm{CT}_{x_1}$ and degree considerations it follows that

$$L_n(a, c) = \mathrm{CT}_{x_n} \cdots \mathrm{CT}_{x_1} (1 - e_1)^{-1} \prod_{i=1}^{n} x_i^{-a+1} \prod_{1 \le i < j \le n} (x_i - x_j)^{-c}. \quad (3.8)$$
**Remark 3.7** A similar iterated constant term identity to (3.7) is Zeilberger's version of the Morris constant term identity [16] used to prove (1.4): for $n \ge 2$ and nonnegative integers $a, b, c$ let

$$M_n(a, b, c) := \mathrm{CT}_{x_n} \cdots \mathrm{CT}_{x_1} \prod_{i=1}^{n} x_i^{-a+1} (1-x_i)^{-b} \prod_{1 \le i < j \le n} (x_i - x_j)^{-c} \quad (3.9)$$

$$\text{then } M_n(a, b, c) = \prod_{j=0}^{n-1} \frac{\Gamma(1+c/2)\Gamma(a+b-1+(n+j-1)c/2)}{\Gamma(1+(j+1)c/2)\Gamma(a+jc/2)\Gamma(b+jc/2)}.$$

### 3.3 Sketch of proof of Lemma 3.4 via Baldoni-Vergne recurrence approach

To prove Lemma 3.4 we follow Xin's [15, §3.5] simplified recursion approach of the proof by Baldoni-Vergne [4] of the Morris identity (3.9).

**Outline of the proof:** First, for nonnegative integers $n \ge 2, a, c$ and $\ell = 0, \dots, n$ we introduce the constants

$$C_n(\ell, a, c) := \mathrm{CT}_{x_n} \cdots \mathrm{CT}_{x_1} \frac{P_\ell \cdot e_1(x_1, \dots, x_n)^{(a-1)n+c(\binom{n}{2})-\ell}}{\prod_{i=1}^n x_i^{a-1} \prod_{i=1}^n (x_i - x_j)^c},$$

where $P_\ell = \ell!(n-\ell)!e_\ell(x_1, \dots, x_n)$. Note that $C_n(0, a, c) = n!L_n(a, c)$. Second, we show that $C_n(\ell, a, c)$ satisfy certain linear relations (Proposition 3.8). Third, we show that these relations uniquely determine the constants $C_n(\ell, a, c)$ (Proposition 3.9). Lastly, in Proposition 3.10 we define $C'_n(\ell, a, c)$ as certain products of Gamma functions such that $C'_n(0, a, c)/n!$ coincides with the expression on the right-hand-side of (3.7). We then show that $C'_n(\ell, a, c)$ satisfy the same relations as $C_n(\ell, a, c)$ and since these relations determine uniquely the constants then $C'_n(\ell, a, c) = C_n(\ell, a, c)$. This completes the proof of the Lemma.

The $C_n(\ell, a, c)$ satisfy the following relations.

**Proposition 3.8** Let $C_n(\ell, a, c)$ be defined as above then for $1 \le \ell \le n$ we have:

$$\frac{C_n(\ell, a, c)}{C_n(\ell - 1, a, c)} = \frac{a - 1 + c(n - \ell)/2}{(a - 1)n + c(\binom{n}{2}) - \ell + 1}, \quad (3.10)$$

$$C_n(n, a, c) = C_n(0, a - 1, c), \quad (3.11)$$

$$C_n(n-1, 1, c) = C_{n-1}(0, c, c), \quad (\text{if } n > 1) \quad (3.12)$$

$$C_n(0, 1, 0) = n!, \quad (3.13)$$

$$C_n(\ell, 0, c) = 0. \quad (3.14)$$

**Proof Sketch:** The relations (3.11)-(3.14) follow from the same proof as in [15, Theorem 3.5.2].

To prove (3.10), we let $U_\ell = e_1^{(a-1)n+c(\binom{n}{2})-\ell}/(\prod_{i=1}^n x_i^a \prod_{i=1}^n (x_i-x_j)^c)$, since $\mathrm{CT}_y g(y) = \mathrm{Res}_y yg(y)$ then $C_n(\ell, a, c) = \mathrm{Res}_{x_n} \cdots \mathrm{Res}_{x_1} P_\ell U_\ell$.

Then we show that

$$\sum_{w \in \mathfrak{S}_n} (\pm 1)^{sgn(w)} w \cdot \left( \frac{\partial}{\partial x_1} e_1 x_1 x_2 \cdots x_\ell U_\ell \right) = \quad (3.15)$$

$$((a-1)n + c(\binom{n}{2}) - \ell + 1) P_{\ell} U_{\ell} - (a - 1 + c(n - \ell)/2) P_{\ell-1} U_{\ell-1},$$
where $\pm$ depends on the parity of $c$. Finally, we take the iterated residue $\text{Res}_{x_n} \cdots \text{Res}_{x_1}$ of (3.15). Since the left-hand-side of this equation consists of sums of derivatives with respect to $x_1, \dots, x_n$, then its iterated residue $\text{Res}_x$ is zero [4, Remark 3(c), p. 15]. This yields

$$0 = ((a-1)n + c\binom{n}{2} - l + 1) C_n(l, a, c) - (a-1 + c(n-l)/2)C_n(l-1, a, c),$$

which proves (3.10).

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

We now show that the recurrences (3.10)-(3.14) determine entirely the constants $C_n(l, a, c)$ (same algorithm as in [4, p. 10]).

**Proposition 3.9** [4, p. 10] The recurrences (3.10)-(3.14) determine uniquely the constants $C_n(l, a, c)$.

Next we give an explicit product formula for $C_n(l, a, c)$. This is proved by showing that the formula satisfies relations (3.10)-(3.14) which by Proposition 3.9 determine uniquely $C_n(l, a, c)$.

**Proposition 3.10** If $c > 0$ or if $a > 1$ then for $1 \le l \le n$ then

$$C_n(l, a, c) = \prod_{j=1}^{l} \frac{a-1+c(n-j)/2}{(a-1)n+c\binom{n}{2}-j+1} C_n(0, a, c) \quad (3.16)$$

if $a \ge 1$ then

$$C_n(0, a, c) = n! \cdot \Gamma(1 + (a-1)n + c\binom{n}{2}) \prod_{i=0}^{n-1} \frac{\Gamma(1 + c/2)}{\Gamma(1 + (i+1)c/2)\Gamma(a + ic/2)}. \quad (3.17)$$

To conclude, since $C_n(0, a, c) = n! \cdot L_n(a, c)$ then Lemma 3.4 follows from (3.17) in Proposition 3.10. By Corollary 3.5 $L_n(1, 1)$ yields the desired formula for the volume of $\text{Tes}_n(1)$ which completes the proof of Theorem 1.6.

**Acknowledgements:** We thank Drew Armstrong for many inspiring conversations throughout this project. We thank François Bergeron for suggesting that flow polytopes were related to Tesler matrices, and Ole Warnaar for showing us simplifications that led to the compact expression on the right-hand-side of (3.7) from a more complicated precursor.

## References

[1] D. Armstrong, A. Garsia, J. Haglund, B. Rhoades, and B. Sagan. Combinatorics of Tesler matrices in the theory of parking functions and diagonal harmonics. *J. Comb.*, 3 (3): 451–494, 2012.

[2] W. Baldoni-Silva, M. Beck, C. Cochet, and M. Vergne. Volume computation for polytopes and partition functions for classical root systems. *Discrete Comput. Geom.*, 35(4):551–595, 2006. Maple worksheets: http://www.math.jussieu.fr/~vergne/work/IntegralPoints.html.

[3] W. Baldoni and M. Vergne. Kostant partitions functions and flow polytopes. *Transform. Groups*, 13(3-4):447–469, 2008.
[4] W. Baldoni and M. Vergne. Morris identities and the total residue for a system of type $A_r$. *Noncommutative Harmonic Analysis*, Progress in Mathematics 220, 1–19, 2004.

[5] M. Brion and M. Vergne. Residue formulae, vector partition functions and lattice points in rational polytopes. *J. Amer. Math. Soc.*, 10, 797–833, 1997.

[6] C.S. Chan, D.P. Robbins. On the volume of the polytope of doubly stochastic matrices, *Experiment. Math.* 8(3):291–300, 1999.

[7] C.S. Chan, D.P. Robbins, and D.S. Yuen. On the volume of a certain polytope, *Experiment. Math.*, 9(1):91-99, 2000.

[8] A.M. Garsia, J. Haglund, and G. Xin. Constant Term methods in the theory of Tesler matrices and Macdonald polynomial operators, *Ann. Comb.* 18 (2014) 83-109.

[9] J. Haglund. A polynomial expression for the Hilbert series of the quotient ring of diagonal coinvariants, *Adv. Math.* 227 (2011), 2092-2106.

[10] L. Hille. Quivers, Cones and Polytopes, *Linear Algebra and its Applications* 365 (2003), 215-237.

[11] K. Mészáros, A.H. Morales, B. Rhoades. The Tesler Polytope, ArXiv:1409.8566, 2014.

[12] P. Levande. Special Cases of the Parking Functions Conjecture and Upper-Triangular Matrices In *DMTCS Proceedings, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)*, 635-644

[13] W.G. Morris. *Constant Term Identities for Finite and Affine Root Systems: Conjectures and Theorems*. PhD thesis, University of Wisconsin-Madison, 1982.

[14] Neil J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. http://oeis.org/.

[15] G. Xin. *The Ring of Malcev-Neumann Series and the Residue Theorem*. PhD thesis, Brandeis University, 2004.

[16] D. Zeilberger. Proof of conjecture of Chan, Robbins, and Yuen *Electron. Trans. Numer. Anal.* 9:147-148, 1999.

[17] G. Ziegler, *Lectures on polytopes*, Graduate Texts in Mathematics **152**, Springer-Verlag, New York, 1995.