1
$\begingroup$

I was trying to solve the following problem using Burnside's lemma, but when testing the solution for a $12\times 12$ matrix involving $20$ possibilities for each matrix element, it had an awful run time.

Does this problem have a better solution than the Burnside's lemma, so it can give the result with a better time complexity?

The problem:

Suppose that a matrix is equivalent to another one if it can be obtained by swapping the rows and/or columns of the other one. The goal is to find the number of inequivalent $h\times w$ matrices with each of its elements having $s$ possible choices.

For example,

1 5    
0 0    

would be equivalent to itself and to:

0 0
1 5

and would also be equivalent to:

0 0 
5 1

and to:

5 1
0 0
$\endgroup$
  • $\begingroup$ what does swapping rows and columns mean? $\endgroup$ – Jorge Fernández Hidalgo Jan 7 '17 at 20:27
  • $\begingroup$ It might be useful to consider that this swapping preserves the row sums and column sums. $\endgroup$ – Mark Jan 7 '17 at 20:27
  • $\begingroup$ This question recently appeared at this MSE link. $\endgroup$ – Marko Riedel Jan 7 '17 at 20:33

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.