4
$\begingroup$

This question already has an answer here:

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!

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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. $\endgroup$ – 6005 Sep 26 '16 at 1:46
5
$\begingroup$

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

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

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.