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.

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. 


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.$$ 


Hello, 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 Matsumo called "JucysMurphy elements and unitary matrix integrals." 


Here 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. 

