The problem Counting cycles after permuting within rows and columns reminds me of the following unpublished conjecture of mine. Let $D$ be any finite planar diagram (in the sense of Young diagram, which is a special case), say with $n$ squares. Put the numbers $1,2,\dots,n$ into the squares of the diagram. Let $R_D$ be the subgroup of the symmetric group $S_n$ permuting elements within each row, and similarly $C_D$ for the columns. Let $\chi$ and $\psi$ be any characters of $S_n$. Define $$ u_D=\sum_{\substack{u\in R_D\\ v\in C_D}} \chi(u)\psi(v)p_{\rho(uv)}, $$ where $p_{\rho(uv)}$ is the power sum symmetric function indexed by the cycle type of $uv$. Then (conjecturally) $u_D$ is Schur-positive.

This conjecture is open even for diagrams of partitions when $\chi$ and $\psi$ are the trivial character. (In this case, one can show for hook shapes that $u_D$ is even $h$-positive, but $h$-positivity fails in most other cases.) When $D$ is the diagram of a partition $\lambda$, and where $\chi$ is the trivial character and $\psi$ the sign character, we have $u_D= H_\lambda s_\lambda$, where $H_\lambda$ is the product of the hook lengths of $\lambda$. See the slides of Valentin Féray at http://fpsac.combinatorics.kr/program.

  • $\begingroup$ This conjecture is in a bit similar flavor as Lemma 3.6 in my paper with Valentin, arxiv.org/pdf/1608.02447v1.pdf Perhaps there is a connection? $\endgroup$ Nov 16, 2016 at 2:23
  • $\begingroup$ Also, is there any reason not to extend this conjecture to say a subset of integer $n$ lattice points in $\mathbb{Z}^3$ and consider subgroups that preserve two of the three coordinates? Then one has to pick three characters, and take the type of the triple product as index of the power sum... Some initial experiments suggests that this might also be Schur-positive. $\endgroup$ Nov 16, 2016 at 3:33
  • 2
    $\begingroup$ Let $S_1=\{1,2\}$, $S_2=\{1,3\}$, $S_3=\{1,4\}$, and $y=\sum_{w_1,w_2,w_3} p_{\rho(w_1w_2w_3)}$, where $w_i$ ranges over all permutations of $S_i$. Then $y=8s_4+5s_{31}-s_{22}+s_{211}$. Thus one must be careful in trying to generalize the conjecture. $\endgroup$ Nov 16, 2016 at 15:34
  • $\begingroup$ Right, that doesn't work... $\endgroup$ Nov 16, 2016 at 16:44

1 Answer 1


I heard about this conjecture from Sara Billey at FPSAC, and I think I've got an argument. Let $F : \mathbb{C}[S_n] \to \mathbb{Z}[x_1, \ldots, x_N]^{S_N}$ be the linear map sending $w \mapsto p_{\rho(w)}(x_1, \ldots, x_N)$, and $V$ a complex vector space with $\dim V = N \geq n$.

Lemma: If $\alpha \in \mathbb{C}[S_n]$ acts on $V^{\otimes n}$ (on the right) with nonnegative eigenvalues, then $F(\alpha)$ is Schur-positive.

Proof: By a density argument we can assume $\alpha$ acts diagonalizably: say $V^{\otimes n} = \bigoplus_{\omega} U_{\omega}$ where $U_{\omega}$ is the $\omega$-eigenspace of $\alpha$. Each $U_{\omega}$ is a left $\operatorname{GL}(V)$-module since the left $\operatorname{GL}(V)$-action commutes with $\alpha$. Let $X \in \operatorname{GL}(V)$ have eigenvalues $x_1, \ldots, x_n$. The trace of $X \times \alpha$ on $V^{\otimes n}$ (i.e. of the map $z \mapsto Xz\alpha$) is, on the one hand, $\sum_{\omega} \omega \operatorname{tr}(X|_{V_\omega})$. Since $V_\omega$ is a $\operatorname{GL}(V)$-module, $\operatorname{tr}(X|_{V_\omega})$ is a Schur-positive polynomial in $x_1, \ldots, x_N$. On the other hand, $\operatorname{tr}(X \times \alpha) = F(\alpha)$.

Since $\mathbb{C}[S_n]$ acts faithfully on $V^{\otimes d}$, the eigenvalues of $\alpha$ acting on $\mathbb{C}[S_n]$ or on $V^{\otimes d}$ are the same, ignoring multiplicity (maybe the lemma can be modified to work directly on $\mathbb{C}[S_n]$?). Up to constant factors, $\sum_{u \in R_D} \chi(u)u \sum_{v \in C_D} \psi(v)v$ is the product of two idempotents, which are both Hermitian with respect to the inner product on $\mathbb{C}[S_n]$ for which permutations form an orthonormal basis. The product of two positive semidefinite matrices has nonnegative eigenvalues, so $F(\sum_{u \in R_D} \chi(u)u \sum_{v \in C_D} \psi(v)v)$ is Schur-positive by the lemma.

  • $\begingroup$ This looks correct to me. It is a great argument! The groups $R_D$ and $C_D$ can be generalized to $S_\pi$ and $S_\sigma$, where $\pi$ and $\sigma$ are partitions of the set $\{1,\dots,n\}$, and $S_\tau$ denotes the subgroup of $S_n$ fixing each block of the partition $\tau$. $\endgroup$ Nov 20, 2016 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.