TITLE: Number of equivalence classes of matrices under switching rows and columns
QUESTION [6 upvotes]: I have been thinking about this problem:
Suppose we have all $R$ by $C$ matrices, where the values are integers in $[1,n]$. Two matrices are equivalent under interchanging rows and columns. For example, 
1 5    
0 0    

would be equal to itself and to
0 0
1 5

and would be equal to
0 0 
5 1

and would be equal to 
5 1
0 0

How many unique such matrices are there?
Any ideas how to go about it?
Any help much appreciated!

REPLY [1 votes]: Burnside's Lemma is probably the right way to approach this problem in general. The idea is to define a group $G$ which corresponds to your combined actions on the set of matrices $M$ of swapping columns or rows; then to think of the equivalence classes of matrices as being orbits, which Burnsides Lemma allows us to count by counting, for each $g \in G$, the number of elements of $M$ which are left unchanged by $g$.
The $2\times 2$ case is simple enough to look at by cases. First, let's think about what the group $G$ looks like in this situation. Let $c \in G$ be the action of swapping columns, and $r \in G$ be the action of swapping rows. Taking $e$ to be 'the action of doing nothing', it's clear that $c^2 = r^2 = e$. Let's call $d = rc$ (i.e., swap rows then columns, which swaps both the diagonal elements). It should be clear that $d = cr$ and $d^2 = e$ as well.
So $G$ has $4$ elements: $\{e, c, r, d\}$ (this is also known as the Klein Group).
You want to count the distinct equivalence classes (a.k.a 'orbits') where $m_1 \sim m_2$ iff $\exists g \in G$ s.t. $g(m_1) = m_2$.
To use Burnside's Lemma, we want to first define, for $g \in G$, $M^g = \{m \in M : g(m) = m\}$; which is to say that $M^g$ is the set of elements of $M$ which are not changed by the element $g$.
It's pretty easy to see that:
$$M^e = M$$
$$M^r = \{m \in M : m_{1,1} = m_{2,1};  m_{1,2} = m_{2,2}\}$$
$$M^c = \{m \in M : m_{1,1} = m_{1,2};  m_{2,1} = m_{2,2}\}$$
$$M^d = \{m \in M : m_{1,1} = m_{2,2};  m_{1,2} = m_{2,1}\}$$
Burnside's Lemma says, where $|M/G|$ is the number of orbits:
$$|M/G| = \frac{1}{|G|}\sum_{g \in G}|M^g|$$
We can see that in your $2\times 2$ example:
$$|M^e| = n^4$$
$$|M^r| = |M^c| = |M^d| = n^2$$
so we get 
$$|M/G| = \frac{n^2(n^2+3)}{4}$$
{"set_name": "stack_exchange", "score": 6, "question_id": 1941503}