2
$\begingroup$

Recall that there are $$\frac{n!}{\prod^n_{i = 1}i^{k_i}k_i!}$$ permutations in $S_n$ which have cycle structure $(k_1, \dots, k_n)$, that is to say they have exactly $k_1$ 1-cycles, $k_2$ 2-cycles, ... and $k_n$ n-cycles. The cycle index of $S_m \times S_n$ acting on the set $\{1, \dots, n\} \times \{1, \dots, n\}$ of indices of entries of an $m \times n$ matrices by row permutations and column permutations can be written as

$$Z(S_m \times S_n; s_1, \dots, s_x) := \frac{1}{m!n!} \cdot \sum_{k_1 + 2k_2 + .. mk_m = m \\ l_1 + 2l_2 + .. nl_n=n} \frac{m!n!}{\prod^m_{i = 1}i^{k_i}k_i! \cdot \prod^n_{j = 1}j^{l_j}l_j! } \cdot \prod_{i = 1}^m \prod_{j = 1}^n s_{\mathrm{lcm}(i,j)}^{\gcd(i,j) \cdot k_i \cdot l_j}$$

In the square case, does anyone know how to calculate the cycle index of the extension $(S_n \times S_n) \rtimes C_2$ where $C_2$ acts by transposing? I.e. extending by the permutation which sends $(i,j)$ to $(j,i)$ for all $1 \leq i,j \leq n$.

Equivalently, if $\sigma \in S_n$ has cycle structure $(k_1, \dots, k_n)$ and $\rho$ has cycle structure $(l_1, \dots, l_n)$ then $(\sigma, \rho, 1)$ has cycle index $$z((\sigma, \rho, 1)) := \prod_{i = 1}^n \prod_{j = 1}^n s_{\mathrm{lcm}(i,j)}^{\gcd(i,j) \cdot k_i \cdot l_j}$$ but if $c$ is the generator of the $C_2$ factor then what is the cycle index of $(\sigma, \rho, c)$?

$\endgroup$
6
  • 1
    $\begingroup$ For the extension with $C_2$, do you want an action on the union of the sets of $m \times n$ binary matrices and $n \times m$ binary matrices? In the formula, is $x \ge mn$? Can't we just take $x = mn$, or $\mathrm{lcm}(m,n)$ if preferred? $\endgroup$ Sep 11, 2018 at 11:49
  • $\begingroup$ Oh my apologies, I actually just want to work with the square case when considering this extension and I miswrote my question. I want to consider the action on $n \times n$ binary matrices. $\endgroup$ Sep 11, 2018 at 11:51
  • 1
    $\begingroup$ I am still confused: take $\sigma = \rho = \mathrm{id}_{S_n}$. Then $k_1 = l_1 = n$, so your formula says $z (\mathrm{id}_{S_n}, \mathrm{id}_{S_n}, 1) = s_1^{n^2}$. This is the cycle type of the identity permutation on a set of size $n^2$. But there are $2^{n^2}$ binary $n \times n$ matrices. $\endgroup$ Sep 11, 2018 at 12:07
  • 1
    $\begingroup$ The way the question is worded might suggest that the cycle index of $(\sigma,\rho,c)$ depends only on the cycle-types of $\sigma$ and $\rho$. This is not the case: for example, working with transpositions, $((12),(34),c)$ is conjugate to $(\mathrm{id}_{S_4},1,c)$, and not conjugate to $((12),(12),c)$, which is in the class with representative $(\mathrm{id}_{S_4},\mathrm{id}_{S_4},c)$. $\endgroup$ Sep 11, 2018 at 14:16
  • 1
    $\begingroup$ I see, the second question of mine is not a good one. Thank you for pointing this out. I am thinking I should have asked a different question. What I want this for is to calculate the number of binary matrices up to row permutations, column permutations and transposition. Perhaps I should just ask if any knows how to do that. $\endgroup$ Sep 11, 2018 at 14:28

2 Answers 2

2
$\begingroup$

The question is about cycle types of elements of the wreath product $G = (S_n \times S_n) \ltimes C_2 \cong S_n \wr C_2$ in its product action on $\{1,\ldots, n\} \times \{1,\ldots, n\}$.

The permutation $(\sigma, \rho, c) \in G$ is conjugate, by $(\rho^{-1},\mathrm{id}_{S_n},1)$, to $g = (\rho\sigma, \mathrm{id}_{S_n}, c)$. Suppose

$$\rho\sigma = (x_1,\ldots, x_a)(y_1,\ldots, y_b) \ldots .$$

Let $X = \{x_1,\ldots, x_a\}$ and $Y = \{y_1,\ldots, y_b\}$. Take all $x$ indices modulo $a$ and all $y$ indices modulo $b$. With this convention, $(x_i,y_j)g = (y_j,x_{i+1})$ and $(y_j,x_i)g = (x_i,y_{j+1})$. Hence

$$(x_i,y_j)g^2 = (x_{i+1},y_{j+1})$$

and so $(x_1,y_1)$ is in a cycle of $g^2$ of length $\mathrm{lcm}(a,b)$. Since $g$ swaps the disjoint sets $X \times Y$ and $Y \times X$, the cycle of $g$ containing $(x_1,y_1)$ has length $2\mathrm{lcm}(a,b)$. Therefore $g$ acts on $X \times Y \cup Y \times X$ with cycle type

$$\bigl((2\mathrm{lcm}(a,b))^{ab/\mathrm{lcm}(a,b)}\bigr).$$

For the action on $X \times X$ things are slightly fiddlier: if $a$ is even then there are $a/2$ cycles each of length $2a$; if $a$ is odd then the cycle type is

$$\bigl( (2a)^{(a-1)/2}, a \bigr).$$

Putting these together determines the cycle type of $g$ and hence the cycle index of $G$.

$\endgroup$
2
  • $\begingroup$ I am not sure if I understand the final part. Does this mean that the cycle type of $((1,2,3,4,5), 1_{S_5}, c)$ acting on $\{1, \dots , 5\} \times \{1, \dots, 5\}$ should be $(100, 5)$, which is too many points because the lengths of the cycles should add up to $25$. $\endgroup$ Sep 11, 2018 at 15:42
  • 1
    $\begingroup$ @ChrisRussell He means there are $(a-1)/2$ $2a$-cycles and $1$ $a$-cycle. $\endgroup$
    – MTyson
    Sep 11, 2018 at 15:44
4
$\begingroup$

More generally, the analogue with any number of factors is studied in E.M. Palmer, R.W. Robinson, Enumeration under two representations of the wreath product, Acta Math. 131 (1973) 123–143. A species approach to this problem can be found in Ji Li, Prime graphs and exponential composition of species, Journal of Combinatorial Theory, Series A, 115 (2008), 1374–1401.

$\endgroup$

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.