# Path tableaux and combinatorial interpretations of immanants for class functions on $S_n$

Sam Clearman, Brittany Shelton, Mark Skandera

► To cite this version:

Sam Clearman, Brittany Shelton, Mark Skandera. Path tableaux and combinatorial interpretations of immanants for class functions on $S_n$. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.233-244, 10.46298/dmtcs.2906. hal-01215097

HAL Id: hal-01215097

https://inria.hal.science/hal-01215097

Submitted on 13 Oct 2015

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
# Path tableaux and combinatorial interpretations of immanants for class functions on $S_n$

Sam Clearman, Brittany Shelton and Mark Skandera

Department of Mathematics, Lehigh University, Bethlehem, PA, USA

**Abstract.** Let $\chi^\lambda$ be the irreducible $S_n$-character corresponding to the partition $\lambda$ of $n$, equivalently, the preimage of the Schur function $s_\lambda$ under the Frobenius characteristic map. Let $\phi^\lambda$ be the function $S_n \to \mathbb{C}$ which is the preimage of the monomial symmetric function $m_\lambda$ under the Frobenius characteristic map. The irreducible character immanant $\mathrm{Imm}_\lambda(x) = \sum_{w \in S_n} \chi^\lambda(w)x_{1,w_1} \cdots x_{n,w_n}$ evaluates nonnegatively on each totally nonnegative matrix $A$. We provide a combinatorial interpretation for the value $\mathrm{Imm}_\lambda(A)$ in the case that $\lambda$ is a hook partition. The monomial immanant $\mathrm{Imm}_{\phi^\lambda}(x) = \sum_{w \in S_n} \phi^\lambda(w)x_{1,w_1} \cdots x_{n,w_n}$ is conjectured to evaluate nonnegatively on each totally nonnegative matrix $A$. We confirm this conjecture in the case that $\lambda$ is a two-column partition by providing a combinatorial interpretation for the value $\mathrm{Imm}_{\phi^\lambda}(A)$.

**Résumé.** Soit $\chi^\lambda$ le caractère irréductible de $S_n$ qui correspond à la partition $\lambda$ de l'entier $n$, ou de manière équivalente, la préimage de la fonction de Schur $s_\lambda$ par l'application caractéristique de Frobenius. Soit $\phi^\lambda$ la fonction $S_n \to \mathbb{C}$ qui est la préimage de la fonction symétrique monomiale $m_\lambda$. La valeur du caractère irréductible immanent $\mathrm{Imm}_\lambda(x) = \sum_{w \in S_n} \chi^\lambda(w)x_{1,w_1} \cdots x_{n,w_n}$ est non négative pour chaque matrice totalement non négative. Nous donnons une interprétation combinatoire de la valeur $\mathrm{Imm}_\lambda(A)$ lorsque $\lambda$ est une partition en équerre. Stembridge a conjecturé que la valeur de l'immanent monomial $\mathrm{Imm}_{\phi^\lambda}(x) = \sum_{w \in S_n} \phi^\lambda(w)x_{1,w_1} \cdots x_{n,w_n}$ de $\phi^\lambda$ est elle aussi non négative pour chaque matrice totalement non négative. Nous confirmons cette conjecture quand $\lambda$ satisfait $\lambda_1 \le 2$, et nous donnons une interprétation combinatoire de $\mathrm{Imm}_{\phi^\lambda}(A)$ dans ce cas.

**Keywords:** total nonnegativity, Schur nonnegativity, planar network, symmetric group, class function, character

## 1 Introduction

A real matrix is called *totally nonnegative* (TNN) if the determinant of each of its square submatrices is nonnegative. Such matrices appear in many areas of mathematics and the concept of total nonnegativity has been generalized to apply not only to matrices, but also to other mathematical objects. (See e.g. [Lus08] and references there.) In particular, for an $n \times n$ matrix $x = (x_{i,j})$ of variables, a polynomial $p(x)$ in $\mathbb{C}[x]_\text{def} = \mathbb{C}[x_{1,1}, \dots, x_{n,n}]$ is called *totally nonnegative* (TNN) if it satisfies

$$p(A) \underset{\text{def}}{=} p(a_{1,1}, \dots, a_{n,n}) \ge 0 \qquad (1)$$
for every $n \times n$ TNN matrix $A = (a_{i,j})$. Obvious examples are the $n \times n$ determinant $\det(x)$, and each minor $\det(x_{I,J})$ of $x$, i.e., the determinant of a square submatrix

$$x_{I,J} = \underset{\text{def}}{(x_{i,j})_{i \in I, j \in J}}, \quad I, J \subseteq [n] = \{1, \dots, n\} \qquad (2)$$

of $x$. Graph-theoretic interpretations of the nonnegativity of the numbers $\det(A_{I,J})$ for A TNN were given by Karlin and MacGregor [KM59] and Lindström [Lin73].

Close cousins of TNN matrices are the *Jacobi-Trudi* matrices indexed by pairs of partitions $(\lambda, \mu)$ and defined by $H_{\lambda/\mu} = (h_{\lambda_i - \mu_j + j - i})_{i,j=1}^r$ where $h_k$ is the $k$th complete homogeneous symmetric function, and where we set $h_k = 0$ for $k < 0$. We declare a polynomial $p(x) \in \mathbb{C}[x]$ to be *monomial nonnegative* (MNN) or *Schur nonnegative* (SNN), if for each $n \times n$ Jacobi-Trudi matrix $H_{\lambda/\mu}$, the symmetric function $p(H_{\lambda/\mu})$ is MNN or SNN, respectively. Clearly, every SNN polynomial is MNN. Well-known examples of SNN polynomials are the $n \times n$ determinant $\det(x)$ and all minors $\det(x_{I,J})$. Graph-theoretic interpretations of the monomial nonnegativity of the symmetric functions $\det(H_{\lambda/\mu})$ were given by Gessel and Viennot [GV89]. No such interpretation of Schur nonnegativity is known.

Some recent interest in TNN, MNN, and SNN polynomials concerns the so-called *dual canonical basis* of $\mathbb{C}[x]$, which arose in the study of canonical bases of quantum groups. (See, e.g., [BZ93], [Du92], [Lus93, Sec. 29.5].) While the dual canonical basis has no elementary description, it includes the determinant $\det(x)$, all matrix minors $\det(x_{I,J})$, and by a result of Lusztig [Lus94], exclusively TNN polynomials. In [Du92], [Ska08], dual canonical basis elements were expressed in terms of functions $f: S_n \to \mathbb{C}$ and their generating functions

$$\mathrm{Imm}_f(x) = \sum_{\mathrm{def}} \sum_{v \in S_n} f(v)x_{1,v_1} \cdots x_{n,v_n} \qquad (3)$$

in the complex span of $\{x_{1,v_1} \cdots x_{n,v_n} | v \in S_n\}$. Such generating functions had been named *immanants* in [Sta00], after Littlewood's term [Lit40] for the special cases in which $f$ is one of the irreducible $S_n$-characters $\{\chi^\lambda | \lambda \vdash n\}$. This immanant formulation and results of Haiman [Hai93], showed that dual canonical basis elements are also SNN [RS06]. In general, given a TNN matrix $A$, Jacobi-Trudi matrix $H_{\lambda/\mu}$, and dual canonical basis element $\mathrm{Imm}_f(x)$, there is no known graph-theoretic interpretation for the nonnegative number $\mathrm{Imm}_f(A)$ or the MNN symmetric function $\mathrm{Imm}_f(H_{\lambda/\mu})$. On the other hand, Rhoades and the third author provided such interpretations for special dual canonical basis elements which they called *Temperley-Lieb immanants* in [RS05]. This led to the resolution in [LPP07] of several conjectures concerning Littlewood-Richardson coefficients.

Other interest in TNN, MNN, and SNN polynomials concerns immanants for class functions $f: S_n \to \mathbb{C}$ such as $S_n$-characters. Littlewood [Lit40], and Merris and Watkins [MW85] expressed immanants for induced sign characters $\{\epsilon^\lambda | \lambda \vdash n\}$ as sums of products of matrix minors, making clear that these immanants are TNN and SNN. Goulden and Jackson [GJ92] conjectured irreducible character immanants to be MNN, leading Stembridge [Ste92] to conjecture the immanants to be TNN and SNN as well. The three conjectures were proved by Greene [Gre92], Stembridge [Ste91], and Haiman [Hai93]. (See also [Kos95].) Haiman, Stanley, and Stembridge formulated several stronger conjectures [Hai93], [SS93], [Ste92], including the total nonnegativity and Schur nonnegativity of immanants for class functions $\{\phi^\lambda | \lambda \vdash n\}$ called *monomial virtual characters*. Irreducible character immanants are nonnegative linear combinations [Ste92] of these. On the other hand, these conjectures have no graph-theoretic interpretation analogous to the results of Karlin-MacGregor, Lindström, and Gessel-Viennot.
In Section 2 we recall definitions and results relating total nonnegativity, planar networks, and immanants. We introduce *path tableaux*, a new generalization of Young tableaux, whose entries are paths in planar networks. In Section 3 we review facts about Temperley-Lieb immanants. In Section 4 we consider elementary immanants, known to be TNN and SNN. We use path tableaux to give new graph-theoretic interpretations of the nonnegative number $Imm_{\epsilon^{\lambda}}(A)$ when $A$ is TNN, and for the MNN symmetric function $Imm_{\epsilon^{\lambda}}(H_{\mu/\nu})$ when $H_{\mu/\nu}$ is a Jacobi-Trudi matrix. In the special case $\lambda = (\lambda_1, \lambda_2)$, we state a new combinatorial interpretation of the coordinates of the elementary immanant $Imm_{\epsilon^{\lambda}}(x)$ with respect to the Temperley-Lieb subset of the dual canonical basis. In Section 5, we consider monomial immanants, in general not known to be TNN, MNN, or SNN. We show that for $\lambda_1 \le 2$, the monomial immanant $Imm_{\phi^{\lambda}}(x)$ is TNN and SNN. This proves special cases of [Ste92, Conj. 2.1, Conj. 4.1]. For $\lambda_1 \le 2$, we use path tableaux to provide new graph-theoretic interpretations of the nonnegative number $Imm_{\phi^{\lambda}}(A)$ and of the MNN symmetric function $Imm_{\phi^{\lambda}}(H_{\mu/\nu})$. Again we state a new combinatorial interpretation of the coordinates of $Imm_{\phi^{\lambda}}(x)$ with respect to the Temperley-Lieb immanants. In Section 6, we consider irreducible character immanants, known to be TNN and SNN. For $\lambda$ a hook shape, we use path tableaux to provide combinatorial interpretations of the nonnegative number $Imm_{\chi^{\lambda}}(A)$ and of the MNN symmetric function $Imm_{\chi^{\lambda}}(H_{\mu/\nu})$.

## 2 Planar networks, immanants, and path tableaux

Given a commutative $\mathbb{C}$-algebra $R$, we define an $R$-weighted planar network of order $n$ to be an acyclic planar directed multigraph $G = (V, E, \omega)$, in which $2n$ distinguished boundary vertices are labeled clockwise as source 1, ..., source $n$, sink $n$, ..., sink 1, and the function $\omega: E \to R$ associates a weight to each edge. For each multiset $F = e_1^{k_1} \cdots e_m^{k_m}$ we define the weight of $F$ to be $\omega(F) = \omega(e_1)^{k_1} \cdots \omega(e_m)^{k_m}$. We draw planar networks with sources on the left, sinks on the right, and all edges understood to be oriented from left to right. Unlabeled edges are understood to have weight 1. We assume that all sources and sinks have indegree 0 and outdegree 0, respectively.

Given a planar network $G$ of order $n$, we define the *path matrix* $A = A(G) = (a_{i,j})$ of $G$ by letting $a_{i,j}$ be the sum

$$a_{i,j} = \sum_{(e_1, \dots, e_m)} \omega(e_1) \cdots \omega(e_m)$$

of weights of all paths $(e_1, \dots, e_m)$ from source $i$ to sink $j$. It is easy to show that given planar networks $G, H$ of order $n$, the concatenation $G \circ H$, constructed by identifying sinks of $G$ with sources of $H$, satisfies $A(G \circ H) = A(G)A(H)$. It follows that every complex $n \times n$ matrix is the path matrix of some complex weighted planar network of order $n$. (See, e.g., [RS05, Obs. 2.2].) For example, one planar network of order 4 and its path matrix are

$$ \begin{tikzpicture}[baseline=(current bounding box.center)]
\node (1) at (0,0) {$4$};
\node (2) at (1,0) {$3$};
\node (3) at (2,0) {$2$};
\node (4) at (3,0) {$1$};
\draw[->] (1) -- (2);
\draw[->] (2) -- (3);
\draw[->] (3) -- (4);
\node at (0.5,0) {$4$};
\node at (1.5,0) {$3$};
\node at (2.5,0) {$2$};
\node at (3.5,0) {$1$};
\end{tikzpicture} \quad \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix} \quad (4) $$

We call a sequence $\pi = (\pi_1, \dots, \pi_k)$ of paths in $G$ a *path family* if its component paths connect $k$ distinct sources of $G$ to $k$ distinct sinks. We call the path family *bijjective* if $k = n$, and for a permutation $w = w_1 \cdots w_n \in S_n$, we say that the path family has *type* $w$ if path $\pi_i$ originates at source $i$ and terminates
at sink $w_i$ for $i = 1, \dots, n$. If $w$ is the identity permutation, we will say that $\pi$ has type 1. We define the weight of a path family $\pi$ to be the weight of the multiset of edges contained in its component paths,

$$ \omega(\pi_1, \dots, \pi_k) = \omega(\pi_1) \cdots \omega(\pi_k). $$

Following Stembridge, we will call this multiset of edges the skeleton of $\pi$. Conversely, we call a multiset $F$ of edges of $G$ a bijective skeleton if it is a multiset union of $n$ source-to-sink paths. Sometimes it will be convenient to consider the endpoints of these edges to be part of the skeleton so that we may refer to the indegree or outdegree of a vertex in the skeleton as the cardinality of edges (including repetition) in the skeleton which originate or terminate at that vertex. We will refer to a planar network $G = (V, E)$ as a bijective network if $E$ is the set of edges in some bijective skeleton. For example, the planar network in (4) is a bijective network.

Recall that Lindström's Lemma interprets the determinant of $A = A(G)$ as

$$ \det(A) = \sum_{\pi} \omega(\pi), \qquad (5) $$

where the sum is over all path families $\pi$ of type 1 in which no two paths share a vertex [KM59], [Lin73]. Recall also that $A$ is TNN if and only if we can choose the planar network $G$ above to have nonnegative edge weights [ASW52], [Bre95], [Cry76], [Loe55]. Thus for each TNN matrix $A$, Lindström's Lemma provides a graph-theoretic interpretation of the nonnegative number $\det(A)$, indeed of the numbers $\det(A_{I,J})$ for $|I| = |J|$, since each submatrix of a TNN matrix is again TNN. Other families of immanants $\mathrm{Imm}_f(x)$ are known to be TNN, but only in few cases do the nonnegative numbers $\mathrm{Imm}_f(A)$ have graph-theoretic interpretations of the form

$$ \mathrm{Imm}_f(A) = \sum_{\pi \in S} \omega(\pi) \qquad (6) $$

where $S$ is a set of path families in $G$ having a certain property. By the Gessel-Viennot method [GV89], such an interpretation implies that $\mathrm{Imm}_f(x)$ is MNN, but not necessarily that it is SNN.

In order to prove that certain immanants $\mathrm{Imm}_f(x)$ are TNN and to state graph-theoretic interpretations of the nonnegative numbers $\mathrm{Imm}_f(A)$ for $A$ TNN, it will be convenient to associate elements of the group algebra $\mathbb{C}[S_n]$ of $S_n$ to planar networks and to bijective skeletons. We refer the reader to [Sag01] for standard information about $\mathbb{C}[S_n]$. Observing that any two path families $\pi, \pi'$ satisfying $\mathrm{skel}(\pi) = \mathrm{skel}(\pi')$ must also satisfy $\omega(\pi) = \omega(\pi')$, we introduce the notation $\gamma(F, w)$ for the number of path families $\pi$ of type $w$ with skeleton $F$, and the $\mathbb{Z}[S_n]$-generating function

$$ \beta(F) = \sum_{w \in S_n} \gamma(F, w)w \qquad (7) $$

for these numbers. The importance of this generating function was stated by Goulden and Jackson [GJ92] and Greene [Gre92] as follows.

**Observation 2.1** Let $R$ be a $\mathbb{C}$-algebra, and let $G$ be an $R$-weighted planar network of order $n$ having path matrix $A$. Then for any function $f: S_n \to \mathbb{C}$, we have

$$ \mathrm{Imm}_f(A) = \sum_{F \subseteq G} \omega(F)f(\beta(F)), \qquad (8) $$
where the sum is over all bijective multisets $F$ of edges in $G$. In particular, if we have $f(\beta(F)) \ge 0$ for all possible bijective networks $F$, then $\mathrm{Imm}_f(x)$ is TNN and MNN.

To see immediate consequences of Observation 2.1, suppose that $p_0$ is a property which applies to path families $\pi = (\pi_1, \dots, \pi_n)$, let $G$ be a planar network of order $n$, and define the sets

$$ S(G, p_0) = \{\pi \mid \pi \text{ bijective in } G, \pi \text{ has property } p_0\}, \\ T(G, p_0) = \{\pi \in S(G, p_0) \mid \pi \text{ covers } G\}. \tag{9} $$

Then we have the following.

**Corollary 2.2** Given a function $f: S_n \to \mathbb{C}$, and a property $p_0$, the following are equivalent:

1. For each planar network $G$ of order $n$ whose edges are weighted by distinct indeterminates, the path matrix $A = (a_{i,j})$ of $G$ satisfies

$$ \mathrm{Imm}_f(A) = \sum_{\pi \in S(G, p_0)} \omega(\pi). \tag{10} $$

2. For each bijective planar network $G$ of order $n$, we have $f(\beta(G)) = |T(G, p_0)|$.

**Proof:** Omitted. $\square$

To facilitate the description of more TNN polynomials $p(x)$ and their evaluations at TNN matrices, we recall some standard terminology associated to integer partitions. For $\lambda = (\lambda_1, \dots, \lambda_r) \vdash n$, the (French) Young diagram of $\lambda$ is the left-justified array of boxes with $\lambda_i$ boxes in row $i$, and with rows numbered from bottom to top. We let $\lambda^\top$, the transpose or conjugate of $\lambda$, denote the partition of $n$ whose $i$th part is equal to the number of boxes in column $i$ of the Young diagram of $\lambda$. Filling the boxes of a Young diagram with any mathematical objects, we obtain a tableau $T$ and we let $T(i, j)$ denote the object in row $i$ and column $j$ of $T$. We call a tableau containing nonnegative integers a Young tableau, and further classify it as column-strict, row-semistrict, or semistandard if its entries strictly increase upward in each column, weakly increase to the right in each row, or satisfy both of these conditions, respectively. If the multiset of entries of Young tableau $T$ is $1^{\alpha_1} 2^{\alpha_2} \dots$, we say that $T$ has content $\alpha$. We call a tableau containing elements of a poset $P$ a $P$-tableau, and further classify it as column-strict, row-semistrict, or semistandard if its entries satisfy $T(1, j) <_P T(2, j) <_P \dots$ in each column $j$, $T(i, 1) \not\le_P T(i, 2) \not\le_P \dots$ in each row $i$, or both of these conditions, respectively.

Now observe that for any planar network $G$ of order $n$, we may partially order the set $P(G)$ of paths $F$ from source $i$ to sink $i$ in $G$, $i = 1, \dots, n$, by declaring $F <_{P(G)} F'$ if $F$ lies entirely below $F'$ in $G$, i.e., if $F$ and $F'$ are disjoint paths connecting sources $i < j$ to sinks $i < j$, respectively. This definition leads to a set of $P(G)$-tableaux for each planar network $G$. Imposing one more condition on this set of tableaux, we declare a $P(G)$-tableau of shape $\lambda \vdash n$ to be a $G$-tableau if the paths in its $n$ boxes form a bijective path family $\pi = (\pi_1, \dots, \pi_n)$ such that $\pi_i$ connects source and sink $i$, for $i = 1, \dots, n$. Given a $G$-tableau $T$, we define its weight $\omega(T)$ to be the weight of the path family it contains. Thus we may restate Lindström's Lemma for a planar network $G$ and its path matrix $A = A(G)$ as $\det(A) = \sum_T \omega(T)$, where the sum is over all column-strict $G$-tableaux of shape $1^n$.

For example, let $G$ be the planar network in (4), and let $F$ be the multiset of its edges in which the upper central edge has multiplicity two and all other edges have multiplicity one. Then there is exactly
and represents multiplication by concatenating diagrams and replacing each resulting cycle by a factor of 2. For instance, the fourteen basis elements of $T_n(2)$ are

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

and the identity $t_3t_2t_3t_1 = 2t_1t_3$ in $T_4(2)$ is represented by

$$ \mathcal{C} = 2 \mathcal{C}. \qquad (16) $$

For each natural basis element $\tau$ of $T_n(2)$, we define the function $f_{\tau} : \mathbb{C}[S_n] \to \mathbb{C}$ by

$$ f_{\tau} : w \mapsto \text{coefficient of } \tau \text{ in } \theta(w), \qquad (17) $$

and the corresponding immanant $\text{Imm}_{\tau}(x)$ by

$$ \text{Imm}_{\tau}(x) \underset{\text{def}}{=} \text{Imm}_{f_{\tau}}(x) = \sum_{w \in S_n} f_{\tau}(w)x_{1,w_1} \cdots x_{n,w_n}. \qquad (18) $$

Observe that for a bijective skeleton $F$ satisfying $\theta(\beta(F)) = 2^k\tau$, the definition (17) implies the formula

$$ f_{\sigma}(\beta(F)) = \delta_{\sigma, \tau} 2^k. \qquad (19) $$

# 4 Elementary immanants

For $\lambda \vdash n$, let $\epsilon^\lambda$ be the $S_n$-character induced from the sign character of a Young subgroup of type $\lambda$. Equivalently, $\epsilon^\lambda$ is the $S_n$-class function which corresponds by the Frobenius characteristic map to the elementary symmetric function $e_\lambda$,

$$ e_{\lambda} = \frac{1}{n!} \sum_{w \in S_n} \epsilon^{\lambda}(w) p_{\rho(w)}, $$

where $\rho(w)$ is the cycle type of $w$. (See [Sag01].) We call the corresponding immanant $\text{Imm}_{\epsilon^\lambda}(x)$ an *elementary immanant*. Since $\{\epsilon^\lambda | \lambda \vdash n\}$ is a basis of the space of $S_n$-class functions, the elementary immanants $\{\text{Imm}_{\epsilon^\lambda}(x) | \lambda \vdash n\}$ are a basis of the space of class immanants. The Littlewood-Merris-Watkins identity [Lit40], [MW85] for elementary immanants provides a short proof that these immanants are TNN and SNN.

**Proposition 4.1** For $\mu = (\mu_1, \dots, \mu_r) \vdash n$, we have

$$ \text{Imm}_{\epsilon^{\mu}}(x) = \sum_{Q} \det(x_{Q_1, Q_1}) \cdots \det(x_{Q_r, Q_r}), \qquad (20) $$

where the sum is over all sequences $Q = (Q_1, \dots, Q_r)$ of disjoint subsets of $[n]$ satisfying $|Q_i| = \mu_i$ for $i = 1, \dots, r$.

Combining this identity with Lindström's Lemma, we obtain the following combinatorial interpretation of elementary character immanants.
**Corollary 4.2** Let R be a $\mathbb{C}$-algebra, let G be an R-weighted planar network of order n with path matrix A, and let $\lambda$ be a partition of n. Then we have

$$ \mathrm{Imm}_{\epsilon^{\lambda}}(A) = \sum_{T} \omega(T), \qquad (21) $$

where the sum is over all column-strict G-tableaux T of shape $\lambda^T$.

Now let us closely examine the special cases of induced sign characters $\epsilon^\lambda$ indexed by partitions $\lambda$ having at most two parts. The corresponding immanant $\mathrm{Imm}_{\epsilon^\lambda}(x)$ clearly belongs to the Temperley-Lieb subspace (12) of $\mathbb{C}[x]$. Expanding elementary immanants indexed by $\lambda = (\lambda_1, \lambda_2)$ in terms of the dual canonical basis, we have

$$ \mathrm{Imm}_{\epsilon^{\lambda}}(x) = \sum_{\tau} b_{\lambda, \tau} \mathrm{Imm}_{\tau}(x), \qquad (22) $$

with coefficients $b_{\lambda, \tau} \in \mathbb{N}$, by Proposition 4.1 and [RS05, Thm. 4.5]. We now reprove this result and interpret the coefficients in terms of colorings of natural basis elements of $T_n(2)$. We adjoin vertices to the $2n$ endpoints of the curves of the Kauffman diagram of a basis element $\tau$, labeling these source 1, ..., source $n$, sink $n$, ..., sink 1, as in a planar network. We define a 2-coloring of $\tau$ to be an assignment of colors $\{1, 2\}$ to these vertices such that source $i$ and sink $i$ have equal colors for all $i$, and connected vertices have equal colors if and only if one is a source and one is a sink. More specifically, we call a 2-coloring a $(2, \lambda)$-coloring for $\lambda = (\lambda_1, \lambda_2) \vdash n$ if $\lambda_1$ sources have color 1 and $\lambda_2$ sources have color 2. For example, the basis element $t_2t_1$ of $T_4(2)$ has one $(2, 31)$-coloring and two $(2, 22)$-colorings:

$$ \overline{\mathcal{K}}, \overline{\mathcal{K}}, \overline{\mathcal{K}} \qquad (23) $$

Now we may interpret the coordinates of elementary immanants with respect to the dual canonical basis as follows.

**Proposition 4.3** For $\lambda = (\lambda_1, \lambda_2) \vdash n$ and $\tau$ a standard basis element of $T_n(2)$, the coefficient $b_{\lambda, \tau}$ appearing in the expansion (22) is equal to the number of $(2, \lambda)$-colorings of $\tau$.

**Proof:** Omitted. $\square$

# 5 Monomial immanants

For $\lambda \vdash n$, let $\phi^\lambda$ be the $S_n$-class function which corresponds by the Frobenius characteristic map to the monomial symmetric function $m_\lambda$,

$$ m_{\lambda} = \frac{1}{n!} \sum_{w \in S_n} \phi^{\lambda}(w) p_{\rho(w)}. \qquad (24) $$

Following [Ste92], we call $\phi^\lambda$ a monomial virtual character of $S_n$, and we call the corresponding immanant $\mathrm{Imm}_{\phi^\lambda}(x)$ a monomial immanant. ($\phi^\lambda$ is not an $S_n$-character.) Like induced sign characters and elementary immanants, monomial virtual characters and monomial immanants form bases of the space of $S_n$-class functions and the space of class immanants, respectively. While no simple formula analogous to (20) is known for monomial immanants, Stembridge has conjectured that they are TNN and SNN [Ste92].
**Conjecture 5.1** For $\lambda \vdash n$, the monomial immanant $\mathrm{Imm}_{\phi^{\lambda}}(x)$ is TNN and SNN.

It is straightforward to show Stembridge's TNN conjecture to be the strongest possible for TNN class immanants, i.e., that a class immanant $\mathrm{Imm}_f(x)$ is TNN only if it is equal to a nonnegative linear combination of monomial immanants. For instance, one may deduce this from the following result.

**Proposition 5.2** For $\mu \vdash n$, let $A(\mu)$ be the $n \times n$ block-diagonal matrix whose $i$th diagonal block is a $\mu_i \times \mu_i$ matrix of ones. Then we have $\mathrm{Imm}_{\phi^{\lambda}}(A(\mu)) = \delta_{\lambda,\mu}$.

**Proof:** Omitted. $\square$

To prove the TNN and MNN cases of Conjecture 5.1, it would suffice to give an analog of Corollary 4.2 for monomial immanants.

**Problem 5.3** For $\lambda \vdash n$, find a graph-theoretic interpretation of $\mathrm{Imm}_{\phi^{\lambda}}(A)$ which holds for path matrices $A$ of arbitrary $R$-weighted planar networks of order $n$.

In Theorem 5.6, we prove the special case of Stembridge's conjectures for $\lambda$ satisfying $\lambda_1 \le 2$. In particular, we express each such monomial immanant $\mathrm{Imm}_{\phi^{\lambda}}(x)$ as a nonnegative linear combination of Temperley-Lieb immanants, with coefficients counting special 2-colorings of natural basis elements of $T_n(2)$. For each natural basis element $\tau$ and each index $j \le \lfloor \frac{n}{2} \rfloor$, define $\mathcal{A}(\tau, j)$ to be the set of all $(2, 2^j 1^{n-2j})$-colorings of $\tau$, define $\iota(\tau)$ to be the minimum $i$ for which $\mathcal{A}(\tau, i) \ne \emptyset$, and define $\mathcal{B}(\tau) = \mathcal{A}(\tau, \iota(\tau))$. Let $M_{\lambda,\mu}$ denote the number of column-strict Young tableaux of shape $\lambda$ and content $\mu$. The cardinalities of these sets are related as follows.

**Lemma 5.4** For each natural basis element $\tau$ of $T_n(2)$, and each index $j \le \lfloor \frac{n}{2} \rfloor$, we have $|\mathcal{A}(\tau, j)| = M_{2^j 1^{n-2^j}, 2^i(\tau) 1^{n-2^i}(\tau)} |\mathcal{B}(\tau)|$.

**Proof:** Omitted. $\square$

**Proposition 5.5** For each bijective skeleton $F$ of order $n$, and each index $j \le \lfloor \frac{n}{2} \rfloor$, we have
$\phi^{2^i 1^{n-2^i}}(\beta(F)) = \delta_{i, \iota(\tau)} |\mathcal{B}(\tau)|$, where $k, \tau$ are defined by $\theta(\beta(F)) = 2^k \tau$.

**Proof:** Choose a reduced expression $s_{i_1} \cdots s_{i_\ell}$ for each $w \in S_n$ and define a corresponding element $D_w = (1 + s_{i_1}) \cdots (1 + s_{i_\ell})$ of $\mathbb{C}[S_n]$. (These elements depend upon the chosen reduced expressions, but we suppress this from the notation.) It is straightforward to show that there exist planar networks $\{F_w \mid w \in S_n\}$ satisfying $D_w = \beta(F_w)$, and that for each $w$, one may define the integer $k_w$ and natural basis element $\sigma_w$ of $T_n(2)$ by the equation $\theta(\beta(F_w)) = 2^{k_w} \sigma_w$. For $i = 0, \dots, \lfloor \frac{n}{2} \rfloor$, define the functions $f_i : \mathbb{C}[S_n] \to \mathbb{C}$ by the conditions

$$f_i(D_w) = \delta_{i, \iota(\sigma_w)} 2^{k_w} |\mathcal{B}(\sigma_w)| \quad \text{for all } w \in S_n, \qquad (25)$$

and by linearly extending to all of $\mathbb{C}[S_n]$. Lemma 5.4 then implies that for each permutation $w$ we have

$$\begin{align}
\epsilon^{n-j, j}(D_w) &= |\mathcal{A}(\sigma_w, j)| &= M_{2^j 1^{n-2^j}, 2^i(\sigma_w) 1^{n-2^i}(\sigma_w)} 2^{k_w} |\mathcal{B}(\sigma_w)| \nonumber \\
&= \sum_{i=0}^{j} M_{2^j 1^{n-2^j}, 2^i 1^{n-2^i}} f_i(D_w). \tag{26}
\end{align}$$
On the other hand, induced sign characters and monomial virtual characters are related by the (unitriangular) system of equations

$$ \epsilon^{\mu} = \sum_{\lambda \subseteq \mu} M_{\mu, \lambda} \phi^{\lambda}. \qquad (27) $$

Comparing this expression to (26) and using unitriangularity, we see that $f_i$ and $\phi^{2^i 1^{n-2^i}}$ agree on the basis $\{D_w | w \in S_n\}$ and therefore on all of $\mathbb{C}[S_n]$. $\square$

**Theorem 5.6** For $j \le \lfloor \frac{n}{2} \rfloor$ and $\lambda = 2^j 1^{n-2^j}$, we have

$$ \mathrm{Imm}_{\phi^{\lambda}}(x) = \sum_{\substack{\tau \\ \iota(\tau)=j}} |\mathcal{B}(\tau)| \mathrm{Imm}_{\tau}(x). \qquad (28) $$

**Proof:** Omitted. $\square$

Now we solve the special case of Problem 5.3 for $\lambda$ satisfying $\lambda_1 \le 2$.

**Theorem 5.7** Let $R$ be a $\mathbb{C}$-algebra, let $G$ be an $R$-weighted planar network of order $n$ with path matrix $A$, and fix $\lambda \vdash n$ with $\lambda_1 \le 2$. Then we have

$$ \mathrm{Imm}_{\phi^{\lambda}}(A) = \sum_{T} \omega(T), \qquad (29) $$

where the sum is over all column-strict $G$-tableaux $T$ of shape $\lambda$, such that no column-strict $G$-tableau $S$ of shape $\mu < \lambda$ satisfies $\mathrm{skel}(S) = \mathrm{skel}(T)$.

**Proof:** Omitted. $\square$

# 6 Irreducible character immanants

For $\lambda \vdash n$, let $\chi^{\lambda}$ be the irreducible $S_n$-character traditionally indexed by $\lambda$. (See, e.g., [Sag01].) Equivalently, $\chi^{\lambda}$ is the $S_n$-class function which corresponds by the Frobenius characteristic map to the Schur function $s_{\lambda}$,

$$ s_{\lambda} = \frac{1}{n!} \sum_{w \in S_n} \chi^{\lambda}(w) p_{\rho(w)}. \qquad (30) $$

Let $\mathrm{Imm}_{\lambda}(x) = \mathrm{Imm}_{\chi^{\lambda}}(x)$ denote the corresponding irreducible character immanant. While no simple formula analogous to (20) is known for irreducible character immanants, Goulden and Jackson [GJ92] conjectured that they are MNN [Ste92], Stembridge conjectured that they are TNN and SNN, and these three conjectures were proved by Greene [Gre92], Stembridge [Ste91] and Haiman [Hai93]. In spite of these results, no analog of Corollary 4.2 is known for irreducible character immanants.

**Problem 6.1** For $\lambda \vdash n$, find a graph theoretic interpretation of $\mathrm{Imm}_{\lambda}(A)$ when $A$ is the path matrix of an $R$-weighted planar network of order $n$.

In Theorem 6.2 we solve the special case of Problem 6.1 for $\lambda$ a hook partition, i.e., $\lambda = r 1^{n-r}$. We will do so by expressing irreducible character immanants in terms of elementary immanants and by using combinatorial objects called *special ribbon diagrams* in [BRW96].
**Theorem 6.2.** Let $\mathcal{R}$ be a $\mathbb{C}$-algebra, let $\mathcal{G}$ be an $\mathbb{R}$-weighted planar network of order $n$ with path matrix $A$, and let $\mu$ be the hook partition $r1^{n-r}$ of $n$. Then we have

$$ \mathrm{Imm}_{\mu}(A) = \sum_{T} \omega(T), \qquad (31) $$

where the sum is over all semistandard $\mathcal{G}$-tableaux $T$ of shape $\mu$.

**Proof:** Omitted. $\square$

For example, when the planar network $\mathcal{G}$ and its path matrix $A$ are as shown in (4), we have $\mathrm{Imm}_{31}(A) = 4$, counting the semistandard $\mathcal{G}$-tableau in (11).

## References

[ASW52] M. Aissen, I. J. Schoenberg, and A. Whitney. On generating functions of totally positive sequences. *J. Anal. Math.*, 2:93–103, 1952.

[Bre95] Francesco Brenti. Combinatorics and total positivity. *J. Combin. Theory Ser. A*, 71(2):175–218, 1995.

[BRW96] D. Beck, J. Remmel, and T. Whitehead. The combinatorics of transition matrices between the bases of the symmetric functions and the $b_n$ analogues. *Discrete Math.*, 153:3–27, 1996.

[BZ93] A. Berenstein and A. Zelevinsky. String bases for quantum groups of type $A_r$. *Adv. Sov. Math.*, 16(1):51–89, 1993.

[Cry76] C. W. Cryer. Some properties of totally positive matrices. *Linear Algebra Appl.*, 15:1–25, 1976.

[Du92] Jie Du. Canonical bases for irreducible representations of quantum $GL_n$. *Bull. London Math. Soc.*, 24(4):325–334, 1992.

[GJ92] I. P. Goulden and D. M. Jackson. Immanants of combinatorial matrices. *J. Algebra*, 148:305–324, 1992.

[Gre92] C. Greene. Proof of a conjecture on immanants of the Jacobi-Trudi matrix. *Linear Algebra Appl.*, 171:65–79, 1992.

[GV89] I. Gessel and G. Viennot. Determinants and plane partitions. Preprint, 1989.

[Hai93] M. Haiman. Hecke algebra characters and immanant conjectures. *J. Amer. Math. Soc.*, 6(3):569–595, 1993.

[Kau87] L. Kauffman. State models and the Jones polynomial. *Topology*, 26(3):395–407, 1987.

[KM59] S. Karlin and G. McGregor. Coincidence probabilities. *Pacific J. Math.*, 9:1141–1164, 1959.

[Kos95] Bertram Kostant. Immanant inequalities and 0-weight spaces. *J. Amer. Math. Soc.*, 8(1):181–186, 1995.
[Lin73] B. Lindström. On the vector representations of induced matroids. *Bull. London Math. Soc.*, 5:85–90, 1973.

[Lit40] Dudley E. Littlewood. *The Theory of Group Characters and Matrix Representations of Groups*. Oxford University Press, New York, 1940.

[Loe55] C. Loewner. On totally positive matrices. *Math. Z.*, 63:338–340, 1955.

[LPP07] Thomas Lam, Alexander Postnikov, and Pavlo Pylyavskyy. Schur positivity and Schur log-concavity. *Amer. J. Math.*, 129(6):1611–1622, 2007.

[Lus93] George Lusztig. *Introduction to Quantum Groups*, volume 110 of *Progress in Mathematics*. Birkhäuser Boston Inc., Boston, MA, 1993.

[Lus94] G. Lusztig. Total positivity in reductive groups. In *Lie Theory and Geometry: in Honor of Bertram Kostant*, volume 123 of *Progress in Mathematics*, pages 531–568. Birkhäuser, Boston, 1994.

[Lus08] G. Lusztig. A survey of total positivity. *Milan J. Math.*, 76:125–134, 2008.

[MW85] Russell Merris and William Watkins. Inequalities and identities for generalized matrix functions. *Linear Algebra Appl.*, 64:223–242, 1985.

[RS05] Brendon Rhoades and Mark Skandera. Temperley-Lieb immanants. *Ann. Comb.*, 9(4):451–494, 2005.

[RS06] B. Rhoades and M. Skandera. Kazhdan-Lusztig immanants and products of matrix minors. *J. Algebra*, 304(2):793–811, 2006.

[Sag01] B. Sagan. *The Symmetric Group*. Springer, New York, 2001.

[Ska08] M. Skandera. On the dual canonical and Kazhdan-Lusztig bases and 3412, 4231-avoiding permutations. *J. Pure Appl. Algebra*, 212, 2008.

[SS93] R. Stanley and J. R. Stembridge. On immanants of Jacobi-Trudi matrices and permutations with restricted positions. *J. Combin. Theory Ser. A*, 62:261–279, 1993.

[Sta00] R. Stanley. Positivity problems and conjectures. In V. Arnold, M. Atiyah, P. Lax, and B. Mazur, editors, *Mathematics: Frontiers and Perspectives*, pages 295–319. American Mathematical Society, Providence, RI, 2000.

[Ste91] John Stembridge. Immanants of totally positive matrices are nonnegative. *Bull. London Math. Soc.*, 23:422–428, 1991.

[Ste92] John Stembridge. Some conjectures for immanants. *Can. J. Math.*, 44(5):1079–1099, 1992.