| Matrices play an important role in many areas of both pure and applied mathematics in that numerous objects and concepts are represented by matrices. However, in virtually all applications, many isomorphic matrices may represent a single object. Hence, questions of existence and enumeration often hinge upon determining whether sets of matrices are isomorphic. Deciding two isomorphisms, permutation equivalence and permutation congruence, is not merely a theoretical exercise, rather, it is precisely what is needed to settle the isomorphism of designs and of graphs.; One could simply try all possible permutations of the rows and columns to determine whether two given matrices were permutation equivalent or permutation congruent. However, this is not practicable, as the testing of the number of allowable permutations of even relatively small matrices exceeds computational resources. Alternative strategies fall into two general categories, employing invariants and/or related matrices. Related matrices are those that must meet the desired isomorphism whenever the original matrices do. Both invariants and related matrices may be used to construct negative tests, i.e. tests that may only definitively show matrices to be nonisomorphic.; A new invariant, called the Hermite invariant, reveals the nonisomorphism of many matrices about which other invariants fail to give any information. In particular, use of the Hermite invariant leads to results that were previously unobtainable in the area of statistical designs. The Hermite invariant also shows much promise when focused on the problem of graph isomorphism. The Hermite invariant may be used to investigate not only adjacency matrices, but also incidence matrices, thus yielding potentially more information. In practice, the Hermite invariant seems to be most useful in distinguishing graphs that fail simpler tests. The Hermite invariant is shown to be a superior graph invariant through a more theoretical measure as well.; Graph isomorphism is not only of practical interest but plays an important part in terms of its structure as a problem. The related problems of graph and design isomorphism may help answer questions that arise in Complexity Theory. Conversely, results in Complexity Theory are useful in focusing attention on appropriate details concerning permutation equivalence and permutation congruence. |
