I need to judge whether two $N\times N$ matrices $A$ and $B$ are permutation-similar or not; if we have $A_{ij}=B_{\sigma(i)\sigma(j)}$ where $\sigma(i)$ denote a permutation, we say $A\sim B$. Here $\sim$ denotes the permutation-similarity.
For simplicity, let us assume $A$ has eigenvalues which are not degenerated. Apparently, the eigenvalues of $A$ and those of $B$ should be the same if $A$~$B$.
Let us consider a set of matrices $\{\tilde{A}^m |m=1,2...N\}$, where $\tilde{A}^m$ are $A$ but skipping $m$-th column and $m$-th row. Thus the dimension of $\tilde{A}^m$ is $(N-1)\times(N-1)$. We can calculate $(N-1)$ eigenvalues of $\tilde{A}^m$. The eigenvalues should be the same as the eigenvalues of $\tilde{B}^{m'}$ if $A\sim B$. Combine all eigenvalues of $\{\tilde{A}^m\}$ together, we have the total number of $N \times (N-1)$ eigenvalues. Adding $N$ eigenvalues of $A$, we have total of $N^2$ eigenvalues. All these eigenvalues of $A$ and of $B$ are the same if $A\sim B$.
The degree of freedom of the total number of eigenvalues $N^2$ are the same as the degree of freedom of the matrix elements $N^2$. Thus it should be impossible to make continuous changing of matrix elements of $A$ with keeping the $N^2$ eigenvalues. I think that this implies $A$~$B$ is judged by these $N^2$ eigenvalues.
Am I correct? I guess I have something wrong. My purpose is characterizing matrices for finding (or screening) $B$ for given $A$, among a large set of candidates $B$.