Number of equivalence classes of matrices under switching rows and columns 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!
 A: Here goes an idea (it is not a complete answer but it is too long to go in the comments box): Note that if $K=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ and $M$ is any $2\times2$ matrix then $KM$ correspond to interchange two rows and $MK$ correspond to interchange two columns. Also note that $K^2=I_2$, so the only possible matrices equivalent to $M$ are $M, KM, MK$ and $KMK$. Let $E(M)=\{M,KM,MK,KMK\}$ be the set of matrices equivalent to $M$. 
For any $M$ we have two possible options, $KM=MK$ or $KM\neq MK$. In the first case we have $E(M)=\{M,KM\}$ (check that $KMK=M$) and if $M=\begin{pmatrix}a&b\\c&d\end{pmatrix}$, neccesarily $a=d$ and $b=c$, i.e., if $KM=MK$ then $M=\begin{pmatrix}a&b\\b&a\end{pmatrix}$. We have then $n^2$ matrices distributed in sets of 2 elements, so we have $n^2/2$ unique matrices (up to equivalence). 
If $KM\neq MK$ we have 3 options (1 and 2 are easy to check but 3 is a little bit problematic)


*

*$E(M)=\{M,KM\}\iff M=\begin{pmatrix}a&a\\b&b\end{pmatrix}$ with $a\neq b$ (so we have $n(n-1)/2$ unique matrices)

*$E(M)=\{M,MK\}\iff M=\begin{pmatrix}a&b\\a&b\end{pmatrix}$ with $a\neq b$ (so we have again $n(n-1)/2$ unique matrices)

*$E(M)=\{M,KM,KM,KMK\}\iff M=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ with $\cdots$ (if you find a characterization of such matrices, and you find out that there are $N$ of them, then the total number of unique matrices would be $n^2+n(n-1)+N/4$). 


This approaching comes from someone with zero experience in combinatorics, so probably there are some mistakes, or better methods to compute such things.
A: NOTE: In this answer, I give an explanation of how Burnside's Lemma can solve the question, but I do not arrive at any simplification. Hence, it may not be an ideal answer right now, but I expect some simplification is possible and maybe someone else can see where to go next. Anyway, I do the example of $2 \times 2$ matrices at the end.

We may apply Burnside's Lemma.
Let $G = S_R \times S_C$, where $S_k$ is the symmetric group.
$G$ acts on the set $X$ of $R \times C$ integer matrices where the entries are between $1$ and $n$, where $S_R$ permutes the rows and $S_C$ permutes the columns.
The number of non-equivalent matrices (equivalence classes of matrices, rather) is equal to the number of distinct orbits of this group action.
Burnside's Lemma gives us that this equals
\begin{align*}
\frac{1}{|G|}
\sum_{g \in G} |X^g| 
&= \frac{1}{R! C!} \sum_{\sigma \in S_R}\sum_{\tau \in S_C} |X^{(\sigma, \tau)}|.
\end{align*}
What is $|X^{(\sigma, \tau)}|$? It is the number of matrices which are unchanged under applying permutation $\sigma$ to the rows and permutation $\tau$ to the columns.
Let's say $\sigma$ groups $1, 2, 3, \ldots, R$ into cycles of size $c_1, c_2, \ldots c_l$, with $c_1 + c_2 + \cdots + c_l = R$, and similarly $\tau$ groups $1, 2, 3, \ldots, C$ into cycles of size $d_1, d_2, \ldots, d_m$ with $d_1 + d_2 + \cdots + d_m = C$.
Now the set of entries $R \times C$ splits into $lm$ blocks, where each block $(i,j)$ is the entries of cycle $c_i$ cross the entries of cycle $d_j$. This block $(i,j)$ has $c_i d_j$ elements, and in the combined group action of $(\sigma, \tau)$ that block splits into $\gcd(c_i, d_j)$ distinct cycles. All the elements of one of these cycles must be the same in the matrix. In total we have that
$$
|X^{(\sigma, \tau)}| = \prod_{i, j} n^{\gcd(c_i, d_j)}.
$$
I suspect it can be further simplified, but I don't know how right now.

Example: $\boldsymbol{2 \times 2}$ matrices
To check, let's do the example of $2 \times 2$ matrices. $S_2$ has only two elements, which we call $e$ and $\rho$ ($\rho$ switches the two rows or columns, $e$ leaves them the same.)
We have
\begin{align*}
X^{(e,e)} &= \prod_{i=1}^2 \prod_{j=1}^2 n^{\gcd(1,1)} = n^4 \\
X^{(e,\rho)} &= \prod_{i=1}^2 n^{\gcd(1,2)} = n^2 \\
X^{(\rho,e)} &= \prod_{j=1}^2 n^{\gcd(2,1)} = n^2 \\
X^{(\rho,\rho)} &= n^{\gcd(2,2)} = n^2
\end{align*}
So our answer is
$$
\frac{1}{4} (n^4 + n^2 + n^2 + n^2)
= \frac{n^4 + 3n^2}{4}.
$$
For example, if $n = 1$ there is only one matrix, $\begin{bmatrix}1&1\\1&1\end{bmatrix}$.
For $n = 2$, the above formula gives
$\frac{16 + 12}{4} = 7$, so there are $7$ matrices. Indeed, these are
$$
\begin{bmatrix}1&1\\1&1\end{bmatrix},
\begin{bmatrix}2&1\\1&1\end{bmatrix},
\begin{bmatrix}2&2\\1&1\end{bmatrix},
\begin{bmatrix}2&1\\2&1\end{bmatrix},
\begin{bmatrix}2&1\\1&2\end{bmatrix},
\begin{bmatrix}2&2\\2&1\end{bmatrix},
\begin{bmatrix}2&2\\2&2\end{bmatrix}.
$$
A: 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}$$
