# Counting on a matrix

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.

• 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}$. – Mr. Sigma. Nov 24 '18 at 4:43
• 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. – Mohemnist Nov 24 '18 at 7:02