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.)


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.