# Cycle index of $(S_n \times S_n) \rtimes C_2$ acting on matrix indices by row/column permutation and transposition

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)$?

• 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? – Mark Wildon Sep 11 '18 at 11:49
• 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. – Chris Russell Sep 11 '18 at 11:51
• 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. – Mark Wildon Sep 11 '18 at 12:07
• 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)$. – Mark Wildon Sep 11 '18 at 14:16
• 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. – Chris Russell Sep 11 '18 at 14:28

## 2 Answers

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

• 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$. – Chris Russell Sep 11 '18 at 15:42
• @ChrisRussell He means there are $(a-1)/2$ $2a$-cycles and $1$ $a$-cycle. – MTyson Sep 11 '18 at 15:44

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.