Coherent algebras and the graph isomorphism problem.

*(English)*Zbl 0704.05023Let \(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 D. G. Higman [Linear Algebra Appl. 93, 209-239 (1987; Zbl 0618.05014)] and B. Weisfeiler [On construction and identification of graphs (1976; Zbl 0336.05019)].

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 D. G. Higman [Linear Algebra Appl. 93, 209-239 (1987; Zbl 0618.05014)] and B. Weisfeiler [On construction and identification of graphs (1976; Zbl 0336.05019)].

Reviewer: K.R.Parthasarathy

##### MSC:

05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |

05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |

05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |

##### Keywords:

coherent algebra; simple spectrum; isomorphism; strong isomorphism problem; homogeneous algebras
PDF
BibTeX
XML
Cite

\textit{S. Friedland}, Discrete Appl. Math. 25, No. 1--2, 73--98 (1989; Zbl 0704.05023)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Babai, L.; Grigoryev, D.Yu.; Mount, D.M., Isomorphism of graphs with bounded eigenvalue multiplicities, (), 310-324 |

[2] | Bannai, E.; Ito, T., Algebraic combinatorics I: association schemes, (1984), Benjamin/Cummings Menlo Park, CA · Zbl 0555.05019 |

[3] | Cvetković, D.M.; Doob, M.; Sachs, H., Spectra of graphs, (1979), Academic Press New York |

[4] | Delsarte, P., An algebraic approach to the association schemes of coding theory, Philips res. repts., Suppl. 10, (1973) · Zbl 1075.05606 |

[5] | Ferguson, P.A.; Turull, A., Algebraic decompositions of commutative association schemes, J. algebra, 96, 211-229, (1985) · Zbl 0573.20051 |

[6] | Friedland, S., Extremal eigenvalue problems, Bol. soc. brasil. mat., 9, 13-40, (1978) · Zbl 0441.47024 |

[7] | Geramita, A.; Seberry, J., Orthogonal designs, (1979), Dekker New York |

[8] | Higman, D.G., Coherent configurations I, ordinary representation theory, Geom. dedicata, 4, 1-32, (1975) · Zbl 0333.05010 |

[9] | Higman, D.G., Coherent algebras, Linear algebra appl., 93, 209-239, (1987) · Zbl 0618.05014 |

[10] | Kato, T., A short introduction to perturbation theory for linear operators, () · Zbl 0493.47008 |

[11] | Wallis, W.D.; Street, A.P.; Wallis, J.S., Combinatorics: room squares, sum-free sets, Hadamard matrices, () · Zbl 1317.05003 |

[12] | () |

[13] | Weisfeiler, B.; Lehman, A.A., A reduction of a graph to canonical form and an algebra arising during this construction, Naučn-tech. informacija ser. 2, 9, 12-16, (1968) |

[14] | Wielandt, H., Permutation groups through the invariant relations and invariant functions, () |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.