Permutation equivalence and the Hermite invariant (Q1355232)

This paper introduces a new invariant -- the Hermite invariant -- for testing permutation equivalence, along with a method for computing it and an assessment of its complexity. Under a restricted definition, the complexity of the invariant becomes polynomial in the dimensions of the input matrices. The sufficiency of the invariant is discussed, and experimental results are given. These results suggest that the Hermite invariant is particularly good at distinguishing nonpermutation equivalent matrices with constant row and column sums. Permutation equivalence and permutation congruence are special cases of matrix equivalence and similarity. Many normal or canonical forms have been developed to identify matrices belonging to the same equivalence or similarity classes. The situation is quite different when attempting to determine the permutation equivalence or permutation congruence of given matrices. The paper contains 6 sections: 1. Introduction, 2. The Hermite invariant, 3. Complexity and computation of the Hermite invariant, 4. The Hermite invariants of the direct sum, 5. Sufficiency of the Hermite invariant, 6. Results determined through use of the Hermite invariant. Experimental results demonstrate the value of the Hermite invariant. Section 6 discusses the determination of non-permutation-equivalence of seven sets of matrices whose status could not be determined using conventional techniques.