7
$\begingroup$

Consider an $m$ by $n$ matrix filled with integers in $\left[0, b\right[$.

There would be $b^{mn}$ possible matrices.

Two matrices would be considered equivalent (in this system) iff you can switch some rows and columns in the matrix and they are the same (So the order doesn't matter). For example:

$$ \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} $$

How can you get the number of unique matrices?

For $n=m=b=2$, the number of unique matrices is $7$:

$$\text{(The above example)}\tag1$$$$ \begin{bmatrix}0&0\\0&0\end{bmatrix}\tag2$$$$ \begin{bmatrix}1&0\\0&0\end{bmatrix}=\begin{bmatrix}0&1\\0&0\end{bmatrix}=\begin{bmatrix}0&0\\0&1\end{bmatrix}=\begin{bmatrix}0&0\\1&0\end{bmatrix}\tag3$$$$ \begin{bmatrix}1&1\\0&0\end{bmatrix}=\begin{bmatrix}0&0\\1&1\end{bmatrix}\tag4$$$$ \begin{bmatrix}1&0\\1&0\end{bmatrix}=\begin{bmatrix}0&1\\0&1\end{bmatrix}\tag5$$$$ \begin{bmatrix}1&0\\0&1\end{bmatrix}=\begin{bmatrix}0&1\\1&0\end{bmatrix}\tag6$$$$ \begin{bmatrix}1&1\\1&1\end{bmatrix}\tag7$$

For $n=2; m=3; b=4$, the answer is $430$.

How would I go about calculating this?

Progress

(Using $n=2; m=3; b=4$ as an example)

You can create a set of possible rows $N$. This would have $b^m$ items and start:

{(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 1, 0), (0, 1, 1), ...}

Which will be written:

{N_0, N_1, N_2, N_3, N_4, ...}

Then, matrices can be defined as of $n$ items in $N$, being rows. Since the order of the rows do not matter, it can be a multiset. So, the first few matrices would be:

{{N_0, N_0}, {N_0, N_1}, {N_0, N_2}, ...}

Before removing duplicates, there would be $\left(b^m\right)^n=b^{mn}$ of these. After removing duplicates there would be $\begin{pmatrix}n+b^m-1\\n\end{pmatrix}$ (Choose $n$ rows from $b^m$ possible with repeats) matrices with unique rows.

Some of these would have more than one unique matrix defined by the same rows but with different columns. So, for each one, I would have to look at the number of unique ways to define them as columns. I don't know how I would go about this in a timely manner.

I then found out about Burnside's Lemma, which I got that that

$$|X/G|=\frac1{|G|}\sum_{g\in G}|X^g|$$

Where $|X/G|$ is the number of oribits (Or unique matrices), $X$ is the set of all possible matrices (So $|X|=b^{mn}$), $G$ is a group of "the actions", like swapping some rows and / or columns, and $X^g$ is the set of the matrices in $X$ where applying the action $g$ leaves the matrix unchanged, but I could not figure out how to calculate the group of possible actions.

$\endgroup$
  • 1
    $\begingroup$ This appeared at the following MSE link if I am interpreting the question correctly. There is a worked example at this MSE link II. $\endgroup$ – Marko Riedel Mar 12 '17 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.