# Matrix permutation-similarity invariants

https://en.wikipedia.org/wiki/Matrix_similarity

https://en.wikipedia.org/wiki/Permutation_matrix

The determinant and trace (and characteristic polynomial coefficients) are well-known similarity invariants of a matrix. There are more if we only allow permutation similarities (swapping a pair of rows, and swapping the corresponding pair of columns). How many independent invariants does an $n \times n$ matrix have? I assume it would be $n^2$. How many invariants (polynomials of the matrix's elements) must be known to determine the matrix up to permutation-similarity? I don't know if it's too much to ask for a general formula for all the polynomials.

(This is related to graph isomorphism, by the adjacency matrix.)

A $2 \times 2$ matrix has only one other matrix that is permutation-similar:

$$\begin{bmatrix} a & b \\ c & d \end{bmatrix} \sim \begin{bmatrix} d & c \\ b & a \end{bmatrix}$$

The following quantities are invariant with respect to this similarity:

$$p_1 = a + d$$ $$p_2 = ad$$ $$q_1 = b + c$$ $$q_2 = bc$$ $$r_2 = (a-d)(b-c)$$

Knowing the $p$'s and $q$'s almost determines the matrix; it's either one of the two shown above, or one of their transposes. The transposes are eliminated if we are also given $r_2$. There are 5 equations here, but only 4 unknowns, so the system is over-determined. It has a solution (in Complex Numbers) if and only if

$$(p_1^2 - 4p_2)(q_1^2 - 4q_2) = r_2^2$$ (If the system is restricted to Real Numbers, we also need $(p_1^2 - 4p_2) \ge 0$, and $(q_1^2 - 4q_2) \ge 0$ .)

This equation cannot be used, in general, to reduce the system to 4 equations, because of the possibility that one factor on the left is zero, putting the other factor out of reach. (This is similar to the equation of a line, $Ax + By = C$; there are 3 parameters, but only 2 degrees of freedom. This is fixed by $x \cos\alpha + y \sin\alpha = D$, but I don't want to use trig functions in the matrix context.) So all 5 invariants are necessary to determine the matrix.

For a $3 \times 3$ matrix $A$, I've found at least a dozen invariants, such as

$$p_3 = A_{11}A_{22}A_{33}$$ $$q_3 = A_{12}A_{23}A_{31} + A_{13}A_{21}A_{32}$$ $$r_3 = A_{11}A_{23}A_{32} + A_{12}A_{21}A_{33} + A_{13}A_{22}A_{31}$$ $$p_5 = (A_{12}A_{13}A_{21}A_{23}A_{31} + A_{12}A_{13}A_{21}A_{23}A_{32} + A_{12}A_{13}A_{21}A_{31}A_{32} + A_{12}A_{13}A_{23}A_{31}A_{32} + A_{12}A_{21}A_{23}A_{31}A_{32} + A_{13}A_{21}A_{23}A_{31}A_{32})$$

In the $n \times n$ case, $n$ invariants will be the elementary symmetric polynomials of the matrix's diagonal elements, others will depend only on the off-diagonal elements, and others will be mixed. This is one way of classifying the invariants. We could refine this classification by specifying the number of on-diagonal and off-diagonal factors in each term.

So, what invariants will guarantee that two matrices are permutation-similar? (There may be a better type of invariant to tell whether they're similar, such as a canonical/normal form of the matrix. But that's not what this question is about.)