# Number of equivalence classes of matrices under switching rows and columns [duplicate]

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!

## marked as duplicate by Hans Engler, Shailesh, Claude Leibovici, JonMark Perry, VladJun 20 '17 at 6:46

• Burnside's theorem gives us a summation formula. It gets quite messy though when we start trying to compute $X^g$, the number of matrices fixed by some permutation $g$ of the rows and columns. – 6005 Sep 26 '16 at 1:46

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

• I think it is $d_m$ and not $d_l$ – Ajay Aug 14 '17 at 5:06
• @RattusRattus Yes, thanks for the correction. – 6005 Aug 14 '17 at 17:25

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)

1. $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)
2. $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)
3. $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.

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