Quadratic forms and the graph isomorphism problem (Q810529)

The isomorphism of two simple n-vertex graphs G and H can be defined through their adjacency matrics A and B (which are symmetric 0-1 matrices with zero diagonal): \(G\simeq H\) if there exists a \(P\in \pi_ n\) (the group of \(n\times n\) permutation matrices) such that \(B=P^ TAP\). We then say that A and B are permutationally equivalent and write \(A\approx B\). The graph isomorphism problem (GI) of determining whether two graphs are isomorphic is not known to be NP-complete; nor is a polynomial algorithm known. It is natural to study the problem in the context of matrix equivalence (or quadratic form equivalence) of more general set- ups. This is precisely the aim of this paper. Let P be an integral domain and \(M_ n(\Gamma)\), \(S_ n(\Gamma)\), \(U_ n(\Gamma)\) denote respectively, the ring of \(n\times n\) matrices, the set of \(n\times n\) symmetric matrices and the graph of \(n\times n\) invertible matrices with entries in \(\Gamma\). Then A and \(B\in S_ n(\Gamma)\) are said to be \(\Gamma\)-equivalent (A\(\sim^{\Gamma}B)\) if there is a \(T\in U_ n(\Gamma)\) such that \(B=T^ TAT\). Several candidates like the reals R, the rational Q, the q-adic numbers \(Q_ p\), the integers Z etc. are considered for \(\Gamma\). A good deal of the paper is taken up by a comprehensive survey of the known literatures on quadratic forms (matrices) over these algebraic structures. The main result shows that the graph isomorphism problem is a special case of the equivalence of special positive definite integer quadratic forms. To state this, let \(O_ n(Z)\) denote the orthogonal group of \(n\times n\) matrices over the integers and \(A\sim^{O(z)}B\) denote the existence of a \(T\in O_ n(Z)\) such that \(B=T^ TAT\). The result is: Let \(A,B\in S_ n(Z)\) have the same characteristic polynomial and let \(O<\lambda_ 1(A)<\lambda_ n(A)\), where \(\lambda_ l\) and \(\lambda_ n\) are the largest and smallest eigenvalues. Then \(A\sim^{Z}B\) implies \(A\sim^{O(Z)}B\). If the nonzero diagonal elements of A and B have the same sign, then \(A\approx B.\) This naturally leads to a discussion of the splitting of the characteristic polynomial over the integers. A brief mention is made of a \(\theta\)-function associated with a positive definite symmetric integer matrix A: \[ \theta (t,A)=\sum_{x\in Z^ n}e^{\pi itx^ TAx}. \] Some conjectures and open problems are mentioned, one of which could possibly lead to an alternative proof of the polynomial complexity of the graph isomorphism problem for graphs with bounded valency.