9
$\begingroup$

Let $A_n$ be the adjacency matrix of the Cayley graph $\text{Cay}(S_n,C_n)$ where $C_n \subseteq S_n$ is the conjugacy class of $n$-cycles of the symmetric group $S_n$. Since the generating set of this Cayley graph is a conjugacy class, it is not too difficult to use the representation theory of $S_n$ to elegantly count the number of nonzero eigenvalues of $A$:

$$ \text{rank}(A_n) = \binom{n-1}{0}^2 + \binom{n-1}{1}^2 + \cdots + \binom{n-1}{n-1}^2 = \binom{2(n-1)}{n-1}.$$

I am interested in the rank of $A_n$ modulo $p$ where $p$ is an odd prime for all $n$. One way to determine this would be to compute the Smith Normal Form of $A_n$ (over $\mathbb{Z}$). Let $D_n = \text{diag}(s_1,s_2,\cdots,s_r,0,\cdots,0)$ such that $s_i | s_{i+1}$ for all $1 \leq i < r := \text{rank}(A)$ be the Smith Normal Form of $A_n$. Computations for small $n$ show that the nonzero $s_i$'s are all powers of 2, which might suggest that $\text{rank}_p(A_n) = \text{rank}(A_n)$ for all $n$ and odd primes $p$.

It seems unlikely that one can divine unimodular matrices $U_n,V_n$ such that $D_n = U_nA_nV_n$ for all $n$, so I would like to think of $A_n$ as an endomorphism of the group algebra $\mathbb{F}_p[S_n]$ and perhaps use $p$-modular representation theory of $S_n$ to say something about the image of $A_n$. (Here, we are assuming $p$ is small, i.e., $p \mid n!$, so $\mathbb{F}_p[S_n]$ is not semisimple.)

Generally speaking, working with modular representations of $S_n$ is also difficult; however, the image of $A_n$ (in the characteristic 0 case) is the direct sum of the hook-shaped Specht modules, which are pretty well-understood, even in the modular case. In particular, Peel (1971) showed for odd primes $p$ that the hook-shaped Specht modules $S^{(n-k,1^k)}_{\mathbb{F}_p}$ are simple when $p \not \mid n$ and determined their composition series when $p \mid n$.

Experimentally, if one picks $b \in S^{(n-k,1^k)}_{\mathbb{F}_p}$ to be a $(n-k,1^k)$-standard polytabloid (which is a $\{0,\pm1 \}$-valued vector well-defined for any Specht module over any field), then $A_nx = b$ indeed has a solution over $\mathbb{F}_p$ for small $k$, odd primes $p$, and $n$. In the case that $p \not \mid n$, because $A_nx = b$ has a solution, it follows that $A_nx = b'$ for any $b' \in S^{(n-k,1^k)}_{\mathbb{F}_p}$, as $S^{(n-k,1^k)}_{\mathbb{F}_p}$ is irreducible by Peel's result. Here, we are "using the modular representation theory of $S_n$", but the problem is that showing a solution $x$ for $A_nx = b$ exists over $\mathbb{F}_p$ for all $0 \leq k < n$ and odd primes $p$ seems to involve similar row-operation-type calculations as putting $A_n$ into Smith Normal Form.

My (open-ended) question is whether there is a more clever way to leverage such information about the modular representation theory of $S_n$ that would circumvent row and column operations to say something about the Smith Normal Form of $A_n$ or $\text{rank}_p(A)$ for odd primes $p$.

EDIT Here's the SNF for small $n$ (thanks Dima for verifying these):

$n = 2$ the SNF is $1^2$

$n = 3$ the SNF is $1^42^2$

$n = 4$ the SNF is $1^{8}2^{12}$

$n = 5$ the SNF is $1^{16}2^{52}8^2$

$n = 6$ the SNF is $1^{32}2^{200}8^{20}$

$n = 7$ the SNF is $1^{64}2^{728}4^{2}8^{128}16^2$

(I have not gone beyond $n=7$, as this would take some time.)

Improve this question
$\endgroup$
9
  • $\begingroup$ Does it suffice to show that the lowest (in the sense of degree) nonzero coefficient of the minimal polynomial of $A_n $ (or of some polynomial over $\mathbb Z $ that vanishes on $A_n $) is a power of $2$ ? My intuition suggests that this should somehow force the nonzero invariant factors to be powers of $2$ as well. $\endgroup$
    – darij grinberg
    Commented Jun 28, 2019 at 6:27
  • $\begingroup$ @darijgrinberg by analogy with "sandpile groups" this looks plausable. There the order of the corresponding abelian group is computed by determinant of a maximal nonzero minor, which is indeed the coefficient of the lowest degree monomial in the char. poly. $\endgroup$
    – Dima Pasechnik
    Commented Jun 28, 2019 at 6:40
  • $\begingroup$ Okay, let me be more precise. Let $A $ be a symmetric integer matrix (such as your $A_n $) and $p $ be an integer polynomial such that $p\left (A\right) = 0$ and such that the lowest (in the sense of degree) nonzero coefficient of $p $ is a power of $2$. Then, over $\mathbb Z \left [1/2\right] $, the homomorphism represented by $A $ decomposes as a direct sum of an invertible homomorphism with a zero map. That is, it has a Smith normal form over $\mathbb Z \left [1/2\right] $ in which the diagonal entries are $0$s and $1$s. Thus, its rank does not change when modding out an odd prime. $\endgroup$
    – darij grinberg
    Commented Jun 28, 2019 at 6:43
  • $\begingroup$ Now of course we need to find such a $p $. But the eigenvalues of $A_n $ are known, so this should not be hard. You just need to prove that the product of all nonzero eigenvalues is a power of $2$. $\endgroup$
    – darij grinberg
    Commented Jun 28, 2019 at 6:44
  • $\begingroup$ I checked the case n=5 and there the minimal polynomial of A is $x_1^4-22x_1^3-72x_1^2+576x_1$, so you get 3 as a divisor, as well. $\endgroup$
    – Dima Pasechnik
    Commented Jun 28, 2019 at 6:45

1 Answer 1

Reset to default
1
$\begingroup$

I would think of $A_n$ as an element of the commutative algebra spanned by the conjugacy class sums of $S_n$. It is known that the multiplication coefficients of such an algebra are determined by the character table of the underlying group, see e.g. the documentation on the GAP system function ClassMultiplicationCoefficient.

An advantage of working in this algebra is that its dimension equals the number of conjugacy classes rather than the order of the group (i.e. the multiplicies of eigenvalues of $A_n$ will be taken care of once you pass to the image of $A_n$ in this algebra via the natural algebra isomorphism). You'd need to keep track of the eigenvalue multiplicites, but this is all well-understood, e.g. in terms of the underlying association scheme (an object in algberaic combinatorics that generalises this sort of setting).

This does not seem to give one a direct (or any?) way to compute the SNF of $A_n$, but as you are interested in the $p$-rank of $A_n$ rather than its SNF, this looks reasonable.

Improve this answer
$\endgroup$
12
  • $\begingroup$ I am well-aware that one can view $A_n$ as the $(n)$-associate of the conjugacy-class association scheme of $S_n$, but I do not see why this allows one to say anything about the $p$-rank for all odd primes $p$. Naively, one could look at the eigenvalues of $A_n$ modulo $p$ to get some sort of estimate; however, they are highly composite (for small $p$ they are 0 mod $p$). $\endgroup$
    – Nathan Lindzey
    Commented Jun 27, 2019 at 16:50
  • $\begingroup$ you might know that old paper for the case of strongly regular graphs: link.springer.com/content/pdf/10.1023%2FA%3A1022438616684.pdf It suggests that eigenvalues might help... $\endgroup$
    – Dima Pasechnik
    Commented Jun 27, 2019 at 18:38
  • $\begingroup$ Thanks for reminding me of this paper. I had skimmed it quite some time ago, but I'll give it a more thorough read. $\endgroup$
    – Nathan Lindzey
    Commented Jun 27, 2019 at 19:34
  • $\begingroup$ Can you post more details of your computation, i.e., the actual SNF for small values of $n$? $\endgroup$
    – Richard Stanley
    Commented Jun 27, 2019 at 21:23
  • 1
    $\begingroup$ I'm using GAP since 1993, you know, give me a credit :-) $\endgroup$
    – Dima Pasechnik
    Commented Jun 27, 2019 at 22:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .