Coherent algebras and the graph isomorphism problem (Q916672)

Let \(M_ n\) be the algebra of \(n\times n\) complex-valued matrices, o denote the Hadamard (element-wise) product of two matrices in \(M_ n\), * denote complex conjugate and I be the identity matrix and J the all-one matrix in \(M_ n\). A subalgebra \({\mathcal A}\) of \(M_ n\) is called a coherent algebra if it is closed under o and * and I and J belong to it. By definition it is semisimple. If \({\mathcal A}\) contains I as a basis element, then it is called homogeneous. A matrix \(A\in {\mathcal A}\) is called generic if its eigenvalues have smallest multiplicity. \({\mathcal A}\) is said to have a simple spectrum if it has a generic matrix A with simple eigenvalues. \({\mathcal A}\) is said to have multiplicity at most k if it has a generic matrix A, every eigenvalue of which has multiplicity at most k. An isomorphism of coherent algebras \({\mathcal A}\), \({\mathcal B}\) is an algebra isomorphism i which preserves o, commutes with * and preserves the matrix J. Such an isomorphism i is said to be strong if for every \(A\in {\mathcal A}\) there is an \(n\times n\) permutation matrix P such that \(i(A)=PAP^*.\) After reviewing the basic properties of coherent algebras, the author proves that the strong isomorphism problem for two isomorphic coherent algebras is equivalent to the isomorphism problem for two regular multigraphs having the same degrees, thus bringing out the importance of the former. The main contribution of the author to the solution of the former is the proof that every isomorphism between two coherent algebras with simple spectra is a strong isomorphism. The homogeneous algebras are used as an important reduction tool. The nonsimple case has been studied by embedding the given algebras in bigger ones (of higher dimension) but less multiplicity. The investigation is inconclusive and a plausible conjecture is proposed. The author makes contact with earlier works by \textit{D. G. Higman} [Linear Algebra Appl. 93, 209-239 (1987; Zbl 0618.05014)] and \textit{B. Weisfeiler} [On construction and identification of graphs (1976; Zbl 0336.05019)].