1
$\begingroup$

I have an $n \times m$ matrix, and fill it with numbers of $1 \dots k$.

If a matrix can be turned into another matrix by exchanging its lines and exchanging its columns, the two matrices are considered to be the same.

I know that I can easily computed the numbers of the different matrices out in $O((n\times m)^k)$ time, but is there any better algorithms for this problems?

Also, I am wondering whether $\texttt{Burnside's lemma}$ or $\texttt{Polya's Theorem}$ work here. I am having no ideas with them.

$\endgroup$
  • $\begingroup$ Are you asking number of symmetric matrices having element in range 1 to K? If it's so, then you just need to calculate $k^{n(n+1)/2}$. $\endgroup$ – Mr. Sigma. Nov 24 '18 at 4:43
  • $\begingroup$ In order to use Burnside's lemma, you should consider every permutation of the rows and the columns ($n!\times n!$) and find the number of matrices that are unchanged under this permutation. Since they are two permutations are intertwined, a super fast solution is not straightforward. $\endgroup$ – Mohemnist Nov 24 '18 at 7:02

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.