For a known matrix of zeros and ones $A\in\{0,1\}^{m\times n}$, what pairs of column and row permutations leave it invariant when applied together? We can assume every row and column has a one in it if it helps.

For example, if the matrix is all ones, every pair of row and column permutations leaves it unchanged. For an identity matrix, permuting the columns by the inverse of the row permutation appears to put it back the way it started, implying all pairs of the form $(p,p^{-1})$ as solutions. For other matrices it's more complicated.

Is there a name for this problem or any area of study likely to pertain to it? (I've poked around a few references on group theory but could certainly have missed something.) I would also like to generalize it to higher dimensional arrays if possible.


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.