Let us consider the matrix $A$ with its rows and columns enumerated by the elements of $S_n$ with $A_{\sigma\tau}=x^{c(\sigma\tau^{1})}$ where $c()$ is the number of cycles in a permutation's decomposition. I'm interested in $A$. More specifically I aim to prove that all of its roots as of a polynomial in $x$ are integers between $n+1$ and $n1$ but the roots' multiplicities would also be nice to know.

5$\begingroup$ Something that might work: Your determinant is a particular case of a group determinant (a.k.a. generalized circulant, a.k.a. Frobenius determinant; see math.uconn.edu/~kconrad/articles/groupdet.pdf for details), and thus equals $\prod\limits_{\chi\text{ is an irreducible character of }S_n} \left(\sum\limits_{g\in S_n} \chi\left(g\right) x^{c\left(g\right)} \right)^{\deg\chi}$. The sum $\sum\limits_{g\in S_n} \chi\left(g\right) x^{c\left(g\right)}$ looks like something we get out of SchurWeyl duality, but I don't see how exactly to get it. $\endgroup$ – darij grinberg Feb 14 '12 at 5:00

1$\begingroup$ Apparently the map $g\mapsto x^{c\left(g\right)}$ is called the Polya character of $S_n$ (adjoined to $x$ or something like that). $\endgroup$ – darij grinberg Feb 14 '12 at 5:11

2$\begingroup$ See also theorem 110 here qspace.library.queensu.ca/bitstream/1974/5235/1/… $\endgroup$ – Gjergji Zaimi Feb 14 '12 at 5:18

4$\begingroup$ Anyway, let me correct myself: $\sum\limits_{g\in S_n} \chi\left(g\right)x^{c\left(g\right)}$ is not "the trace of the sum of all $g\in S_n$ acting on $V^{\otimes n}_{\chi}$" but the inner product of the character $\chi$ with the character of the $S_n$module $V^{\otimes n}$. In other words, it is the number of $\chi$'s in $V^{\otimes n}$. This is (by SchurWeyl duality) the dimension of the Schur functor corresponding to the partition corresponding to $\chi$, evaluated at the vector space $V$. Now use the Weyl character formula to obtain a polynomial formula for this. $\endgroup$ – darij grinberg Feb 14 '12 at 5:29

3$\begingroup$ The polynomial $\sum_{g\in S_n} \chi(g)x^{c(g)}$ is evaluated in Exercise 7.50 of Enumerative Combinatorics, vol. 2 (solution on page 515). $\endgroup$ – Richard Stanley Feb 14 '12 at 16:43
This determinant came up, and was evaluated, in the comments of the Secret Blogging Seminar. The motivation there was that it vanishes if and only if $V^{\otimes n}$ has neglible endomorphisms in Deligne's category of "$GL_x$ representations for noninteger $x$". Here $V$ is the "$x$dimensional representation of $GL_x$". See that post for more.

$\begingroup$ This reminds me of my own motivation: this polynomial vanishes for some $n$ iff a certain representation of $\mathfrak{gl}(a+b)$ is reducible. Namely, if $\mathfrak{gl}(a+b)=\mathfrak{gl}(a)+\mathfrak{gl}(b)+\mathfrak{x}+\mathfrak{y}$ where $\mathfrak{x}$ and $\mathfrak{y}$ are correspondingly the subalgebras of upper diagonal and lower diagonal matrices not included in $\mathfrak{gl}(a)+\mathfrak{gl}(b)$, then we consider the generalized Verma module induced from the one dimensional represenation of $\mathfrak{gl}(a)+\mathfrak{gl}(b)+\mathfrak{y}$ defined by $(A+B+Y)v=k\mathrm{Tr}(B)v$. $\endgroup$ – imakhlin Feb 14 '12 at 16:45

$\begingroup$ ...this polynomial vanishes in $k$ for some $n$ iff... $\endgroup$ – imakhlin Feb 14 '12 at 16:50
I might as well write an answer with the proof I referenced to above (found as theorem 110 here). Hopefully Darij will write a more detailed answer tomorrow.
The first thing to observe is that your matrix $A$ is the image of the element $$\omega=\sum_{\sigma\in S_n} x^{\pi}\pi$$ in the regular representation of the group algebra $\mathbb C[S(n)]$. Next notice that this element factors as $$\omega=(x+J_1)(x+J_2)\cdots(x+J_n)$$ where $J_k$ are the JucysMurphy elements defined as $J_k=\sum_{ s < k} (s,k)$.
Let's denote $\Xi_n=\lbrace J_1,J_2,\dots,J_n,0,0,\dots\rbrace$. It is a theorem that for any symmetric function $f\in \Lambda$, the mapping $f\to f(\Xi_n)$ sends symmetric polynomials onto elements of the class algebra $\mathcal Z(n)$.
Now since $f(\Xi_n)\in \mathcal Z(n)$, by Schur's lemma it acts as a scalar on any irreducible representation $V^{\lambda}$ of $\mathbb C[S(n)]$. Jucys theorem says that the central character of $f(\Xi_n)$ acting on $V^{\lambda}$ can be obtained by simply substituting the alphabet $\Xi_n$ with the content alphabet $$A_{\lambda}=\lbrace c(\square): \square\in \lambda\rbrace.$$ These two facts are proved in Jucys' article, "Symmetric polynomials and the center of the symmetric group ring".
So, in particular, the central character of $\omega$ is $$\prod_{\square\in \lambda}(x+c(\square)),$$ and, putting things together, from the decomposition $\mathbb C[S(n)]=\bigoplus_{\lambda \vdash n} (\dim \lambda)V^{\lambda}$, we obtain $$\det(A)=\prod_{k=1}^{n1}(x^2k^2)^{r_k},$$ where $$r_k=\sum_{\lambda\vdash n, k\in A_{\lambda}} \dim \lambda.$$

$\begingroup$ I'd love to see all these Jucys theorems proven somewhere... but I guess I'm just too lazy to go in the library. $\endgroup$ – darij grinberg Feb 14 '12 at 14:33

1$\begingroup$ I gave a link to the original paper with the theorems. $\endgroup$ – Gjergji Zaimi Feb 14 '12 at 16:01

$\begingroup$ ... $\omega=(x+J_1)(x+J_2)\cdots(x+J_n)$ ... Am I talking nonsense, or this means that our polynomial is (up to the sign of $x$) the product of the JM's characteristic polynomials (as of operators on $\mathbb{C}[S_n]$) which are known to be polynomials of the needed type (mathoverflow.net/questions/83150/…)? $\endgroup$ – imakhlin Feb 14 '12 at 17:09

$\begingroup$ You are correct. So another way of saying this is that our polynomial is (up to sign of x) the product of JM's characteristic polynomials, and the spectrum of $J_k$ in $V^{\lambda}$ is $\lbrace c_T(k): T\in SYT(\lambda)\rbrace$, by OkounkovVershik. $\endgroup$ – Gjergji Zaimi Feb 14 '12 at 17:21

$\begingroup$ Where $c_T(k)$ is the content of the cell labelled $k$ in $T$. $\endgroup$ – Gjergji Zaimi Feb 14 '12 at 17:22
Here (Darij Grinberg, A representationtheoretical solution to MathOverflow question #88399) is the proof that I hinted at in the comments section in more details. Repeated mistakes absorbed most of the time I spent writing it, which is why it took four days; let me apologize for this.
I really think it helps to think about the entries of this matrix does $q^{d(\sigma,\tau)}$ where d denotes the distance between two permutations on the Cayley graph of the symmetric group generated by the set of all transpositions. In this light you can compare the determinant you're interested in with the one computed by Don Zagier in his article "realizability of a model in infinite statistics." In that paper, Zagier computes the analogous determinant corresponding to the Cayley graph of the symmetric group generated by adjacent transpositions (i.e. the Coxeter generators). This is a very different geometry on permutations but Zagier finds a similar factorization showing that the determinant has roots on the unit circle. Zagier's result is based on a clever factorization in the group algebra, just like the factorization into JM elements discussed above.
Another point of view on Zagier's result, relating it to hyperplane arrangements, is explained in Stanley and Hanlon's article "a qdeformation of a trivial symmetric group action." Also, if you want to see similar results in the context of the Brauer algebra, you should look up Paul ZinnJustin's paper "JucysMurphy elements and Weingarten matrices." I saw that a user above posted a link to my Phd thesis  I was young and foolish then and more polished versions of those results have since appeared in a paper written jointly with Sho Matsumoto called "JucysMurphy elements and unitary matrix integrals."

2$\begingroup$ Welcome to Mathoverflow! I added links to the arxiv versions of the papers in your answer. $\endgroup$ – Gjergji Zaimi Feb 14 '12 at 19:20