I have a $n\times n$ square matrix $M$, and a set of $n$ natural numbers, where the rows of $M$ contain different permutations of such $n$ elements (with repeated rows allowed). I want to find a relabeling of the matrix (e.g., permutation of rows and columns such that, the same permutations applied to rows must be applied to columns), that sorts the rows lexicographically, in the following sense.
Definition: If $a$ and $b$ are vectors (e.g., rows), $a$ is lexicographically $\leq b$ if $a=b$, or, if $a\neq b$ and $i$ is the lowest index where $a_i\neq b_i$, then $a_i\lt b_i$.
For example, consider the $3 \times 3$ matrix
$$M = \begin{pmatrix} 3 & 2 & 1\\ 1 & 3 & 2\\ 2 & 3 & 1\\ \end{pmatrix}$$
Applying the relabeling $(3 1 2)$ to $M$ gives the matrix
$$M' = \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2\\ 2 & 1 & 3\\ \end{pmatrix}$$
which is lexicographically sorted row-wise, in the sense that the first row is lexicographically $\leq$ than the second row, and the second row is lexicographically $\leq$ than the third row, and there's no other possible relabeling of $M$ that gives a matrix that is better sorted than that.
Is there any polynomial-time algorithm for this problem? I know that, in general, this kind of "normalization" of matrices and everything that can be use for isomorphism testing are NP-problems or related, but I wonder if, in this case, the restrictions that all rows are permutations of each other (and thus all rows are guaranteed to have all different elements from $1$ to $n$) helps somehow.
Just to expand the example, here I provide all the relabelings of the first matrix of the list. The first matrix of the list is the lexicographically best sorted matrix of its group ($M'$ indeed), and, given any matrix, I want to find the relabeling that transform it into the first matrix of its group.
$$ \begin{array}{cccccc} (1\ 2\ 3) & (1\ 3\ 2) & (2\ 1\ 3) & (2\ 3\ 1) & (3\ 1\ 2) & (3\ 2\ 1)\\ \hline \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2\\ 2 & 1 & 3\\ \end{pmatrix} & \begin{pmatrix} 1 & 3 & 2\\ 2 & 3 & 1\\ 1 & 2 & 3\\ \end{pmatrix} & \begin{pmatrix} 3 & 1 & 2\\ 2 & 1 & 3\\ 1 & 2 & 3\\ \end{pmatrix} & \begin{pmatrix} 3 & 2 & 1\\ 1 & 3 & 2\\ 2 & 3 & 1\\ \end{pmatrix} & \begin{pmatrix} 3 & 2 & 1\\ 3 & 1 & 2\\ 2 & 1 & 3\\ \end{pmatrix} & \begin{pmatrix} 3 & 1 & 2\\ 2 & 3 & 1\\ 3 & 2 & 1\\ \end{pmatrix} & \end{array} $$