Combinatorics and symmetry in matrices under row and column swaps

Question

Suppose we have a $m\times n$ matrix and a sequence of numbers with which to fill the matrix, $\{c_1,c_2 \dots c_k \}$. I like to think of the numbers as colors, hence the notation. How many unique configurations can we produce if we are given that matrices are equivalent when one matrix can be transformed to another via one or more row or column swaps?

As a concrete example consider the case for a $2\times 2$ matrix with the list of numbers $\{ 1, 3\}$. Notice that the numbers must sum to the product of the dimensions of the matrix. Let us say $c_1$ is denoted by $1$ and $c_2$ by $0$. Then we need to fill the matrix with one $1$ and three $0's$

There are four possible configurations:

$$ \left( \begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array} \right) % \left( \begin{array}{cc} 0 & 1 \\ 0 & 0 \end{array} \right) % \left( \begin{array}{cc} 0 & 0 \\ 1 & 0 \end{array} \right) % \left( \begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array} \right) $$

It is clear that all four of these matrices are equivalent, since any one can be transformed to another via one or more row or column swaps. Hence for the problem of a $2\times 2$ matrix with the list of numbers $\{ 1, 3\}$, there is ONE unique configuration we can produce.

As another example consider the case of $2\times 2$ with the list of numbers $\{ 2, 2\}$, again we denote $c_1$ by $1$ and $c_2$ by $0$.

There are six configurations:

$$ \left( \begin{array}{cc} 1 & 1 \\ 0 & 0 \end{array} \right) % \left( \begin{array}{cc} 0 & 0 \\ 1 & 1 \end{array} \right) % \left( \begin{array}{cc} 1 & 0 \\ 1 & 0 \end{array} \right) % \left( \begin{array}{cc} 0 & 1 \\ 0 & 1 \end{array} \right) \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right) $$

Now, the first can be transformed to the second by $R_1 \leftrightarrow R_2$. The third can be transformed to the fourth via $C_1 \leftrightarrow C_2$ and the fifth can become the sixth either via $R_1 \leftrightarrow R_2$ or $C_1 \leftrightarrow C_2$. What we are left with are THREE unique configurations under row and column swaps.

I hope the reader will get the idea of how the problem is presented, but I will be happy to clarify if needed.

I know that for a given $m$, $n$ and $\{ c_1, c_2 \dots, c_k \}$ the total number of possible configurations is:

$$\frac{(m \cdot n)!}{c_1!\cdot c_2! \cdot \dots c_k!}$$

I am however unable to incorporate the the swapping of rows and columns. Any help or advice would be greatly appreciated.

Answer 1

Let me elaborate on the use of Pólya enumeration for this problem.

Let $G\simeq S_m \times S_n$ act on $X=\{x_{i,j}\colon 1\leq i \leq m, 1\leq j \leq n\}$ via $(\sigma,\pi)\cdot x_{i,j} = x_{\sigma(i),\pi(j)}$, and via this action view $G\subseteq S_{mn}$. For $g\in G$ let $c_i(g)$ be the number of $i$-cycles of $g$ (in this embedding into $S_{mn}$), and form the corresponding cycle index $$ Z_{G}(t_1,t_2,\ldots) = \frac{1}{\#G}\sum_{g\in G} t_1^{c_1(g)}t_2^{c_2(g)}\cdots.$$ Then by the Pólya-Redfield enumeration theorem, the number of $m \times n$ matrices, with $\alpha_1$ $1$'s, $\alpha_2$ $2$'s, ..., $\alpha_k$ $k$'S considered up to permutation of rows and columns, is $$ [y_1^{\alpha_1}y_2^{\alpha_2}\cdots y_k^{\alpha_k}] Z_{G}(y_1+y_2+\cdots+y_k,y_1^2+y_2^2+\cdots+y_k^2,y_1^3+y_2^3+\cdots+y_k^3,\ldots).$$ (Here $[\mathbf{y}^{\alpha}]$ denotes coefficient extraction, and I switched from your notation of $\{c_1,\ldots,c_k\}$ to $\{\alpha_1,\ldots,\alpha_k\}$ to not get confused with the common notation in the definition of the cycle index.)

For example, consider the case $m=n=2$. Then $$G= \{(x_{11})(x_{12})(x_{21})(x_{22}),(x_{11},x_{21})(x_{12}x_{22}),(x_{11},x_{12})(x_{21}x_{22}),(x_{11},x_{22})(x_{12}x_{21}) \}$$ so $$ Z_{G}(t_1,t_2,\ldots) = \frac{1}{4}\left( t_1^4 + 3\cdot t_2^2 \right).$$ Thus, the number of $2\times 2$ matrices with $2$ 0's and $2$ 1's, up to permutation of rows and columns, is $$ [y_0^2y_1^2]Z_{G}(y_0+y_1,y_0^2+y_1^2,\ldots) = [y_0^2y_1^2] \frac{1}{4}( (y_0+y_1)^4 + 3(y_0^2+y_1^2)^2) \\ = [y_0^2y_1^2](y_0^4 + y_0^3y_1 + 3y_0^2y_1^2 + y_0y_1^3+y_1^4)=3,$$ as you demonstrated above.

So to address the case of general $m$ and $n$, we need to understand $Z_G$ precisely. In other words, for a pair $\sigma \in S_m$ and $\pi \in S_n$, we need to understand the cycle structure of the corresponding element $g=(\sigma,\pi)\in G \subseteq S_{mn}$.

Note that in this last example we saw that if $\sigma$ is a $2$-cycle and $\pi$ is a $2$-cycle, then $g=(\sigma,\pi)$ will consist of $2$ $2$-cycles. But for instance if $\sigma$ is a $2$-cycle and $\pi$ is a $3$-cycle, then $g=(\sigma,\pi)$ will be one $6$-cycle. In general, if $\sigma$ is an $m$-cycle and $\pi$ is a $n$-cycle, then $g=(\sigma,\pi)$ will consist of $\mathrm{gcd}(m,n)$ $\mathrm{lcm}(m,n)$-cycles. And then of course we can figure out the cycle structure of $g=(\sigma,\pi)$ for arbitrary $\sigma$ and $\pi$ by comparing pairwise the cycles of $\sigma$ and $\pi$.

Recall that for a partition $\lambda=(1^{m_1},2^{m_2},\cdots) \vdash n$, the number of permutations in $S_n$ of cycle type $\lambda$ is $z_{\lambda} = \frac{n!}{1^{m_1}m_1!2^{m_2}m_2!\cdots}$. Thus, the rule from the previous paragraph in principle allows you to easily compute $Z_G$ for any fixed $m,n$; but it introduces some nontrivial arithmetic which makes me doubt there will be any truly simple formula one can write down.

EDIT: Okay, so from the above we can write in general that $$ Z_G(t_1,t_2,\ldots) =\sum_{\substack{\lambda=(1^{m_1},2^{m_2},\cdots)\vdash m, \\ \mu=(1^{m'_1},2^{m'_2},\cdots)\vdash n}} \frac{\prod_{i,j\geq 1}t_{\mathrm{lcm}(i,j)}^{\mathrm{gcd}(i,j) \cdot m_i \cdot m'_j}}{1^{m_1} m_1! 2^{m_2} m_2!\cdots 1^{m'_1} m'_1! 2^{m'_2} m'_2! \cdots} .$$ For any fixed $m$, $n$ this formula should be able to be quickly evaluated with a computer.

EDIT 2: Here is some SageMath code for this problem:

m=3
n=3
k=2
R = PolynomialRing(QQ, ['t%s'%i for i in range(1,m*n+1)])
S = PolynomialRing(QQ, 'y', k)
z = 0
for p in Partitions(m):
    for q in Partitions(n):
        g=1
        for i in range(1,len(p.to_exp())+1):
            for j in range(1,len(q.to_exp())+1):
               g = g * R.gens()[lcm(i,j)-1]^(gcd(i,j)*p.to_exp()[i-1]*q.to_exp()[j-1])
        for i in range(1,len(p.to_exp())+1):
            g = g * 1/(factorial(p.to_exp()[i-1])*i^(p.to_exp()[i-1]))
        for j in range(1,len(q.to_exp())+1):
            g = g * 1/(factorial(q.to_exp()[j-1])*j^(q.to_exp()[j-1]))
        z = z + g
print("Cycle index: " + str(z))
f = z.subs({R.gens()[i-1]:sum([S.gens()[j]^i for j in range(k)]) for i in range(1,m*n+1)})
print("Colorings generating function: " + str(f))

which produces the output

Cycle index: 1/36*t1^9 + 1/6*t1^3*t2^3 + 1/4*t1*t2^4 + 2/9*t3^3 + 1/3*t3*t6
Colorings generating function: y0^9 + y0^8*y1 + 3*y0^7*y1^2 + 6*y0^6*y1^3 + 7*y0^5*y1^4 + 7*y0^4*y1^5 + 6*y0^3*y1^6 + 3*y0^2*y1^7 + y0*y1^8 + y1^9

This tells us, for example, that there are 7 $3\times 3$ matrices of 5 $0$'s and 4 $1$'s up to permutation of rows and columns.