Cellular algebra

(in algebraic combinatorics)

Algebras introduced by B.Yu. Weisfeiler and A.A. Leman [a9] and initially studied by representatives of the Soviet school of algebraic combinatorics. The first stage of this development was summarized in [a8]. Important particular examples of cellular algebras are the coherent algebras (cf. also Coherent algebra).

A cellular algebra of order and rank is a matrix subalgebra of the full matrix algebra of -matrices over such that:

is closed with respect to the Hermitian adjoint;

, where is the all-one matrix;

is closed with respect to Schur–Hadamard multiplication (cf. also Coherent algebra). A coherent algebra is a cellular algebra that contains the unit matrix .

Like coherent algebras, a cellular algebra has a unique standard basis of zero-one matrices , consisting of mutually orthogonal Schur–Hadamard idempotents. The notation indicates that has the standard basis .

A cellular algebra is called a cell if the all unit matrix belongs to its centre (cf. also Centre of a ring). Cells containing the unit matrix are equivalent to Bose–Mesner algebras. If the entries of the matrices in are restricted to the ring , then the corresponding ring of matrices is called a cellular ring.

The relational analogue of cellular algebras with the unit matrix was introduced by D.G. Higman in [a3] under the name coherent configuration. For a long time the theories of cellular algebras and coherent configurations were developed relatively independently. After the appearance of Higman's paper [a4], where the terminology of coherent algebras was coined, most researchers switched to the terminology of coherent algebras.

As a rule, only cellular algebras containing (that is, coherent algebras) were investigated. Situations where cellular algebras are required properly appear rarely, see for example [a7], where a particular kind of such algebras are treated as pseudo-Schur rings.

The initial motivation for the introduction of cellular algebras was the graph isomorphism problem (cf. also Graph isomorphism).

The intersection of cellular algebras is again a cellular algebra. For each set of matrices of the same order it is possible to determine a minimal cellular algebra containing this set. In particular, if is an -vertex graph and is its adjacency matrix, then denotes the smallest cellular algebra containing . It is called the cellular closure (or Weisfeiler–Leman closure) of .

In [a9] and [a8], Weisfeiler and Leman described an algorithm of stabilization which has an input and returns in polynomial time, depending on . Isomorphic graphs have isomorphic cellular closures, and this fact has important applications, see [a6]. In general, does not coincide with the centralizer algebra of the automorphism group of the graph ; however, they do coincide for many classes of graphs, for example for the algebraic forests introduced in [a1].

For each cellular algebra one can introduce its automorphism group

Here, is the automorphism group of the graph with adjacency matrix . For each permutation group , its centralizer algebra is a cellular algebra with matrix . Thus, the functors and introduce a Galois correspondence between cellular (coherent) algebras and permutation groups. Some properties and applications of this correspondence are considered in [a2], [a5].

References

[a1]	S. Evdokimov, I. Ponomarenko, G. Tinhofer, "Forestal algebras and algebraic forests (on a new class of weakly compact graphs)" Discr. Math. , 225 (2000) pp. 149–172
[a2]	I.A. Faradžev, M.H. Klin, M.E. Muzichuk, "Cellular rings and groups of automorphisms of graphs." I.A. Faradžev (ed.) et al. (ed.) , Investigations in Algebraic Theory of Combinatorial Objects , Kluwer Acad. Publ. (1994) pp. 1–152
[a3]	D.G. Higman, "Coherent configurations I" Rend. Sem. Mat. Univ. Padova , 44 (1970) pp. 1–25
[a4]	D.G. Higman, "Coherent algebras." Linear Alg. & Its Appl. , 93 (1987) pp. 209–239
[a5]	A.A. Ivanov, I.A. Faradžev, M.H. Klin, "Galois correspondence between permutation groups and cellular rings (association schemes)" Graphs and Combinatorics , 6 (1990) pp. 303–332
[a6]	M. Klin, C. Rücker, G. Rücker, G. Tinhofer, "Algebraic combinatorics in mathematical chemistry. Methods and algorithms. I. Permutation groups and coherent (cellular) algebras" MATCH , 40 (1999) pp. 7–138
[a7]	M.E. Muzychuk, "The structure of rational Schur rings over cyclic groups" Europ. J. Combin. , 14 (1993) pp. 479–490
[a8]	"On construction and identification of graphs" B. Weisfeiler (ed.) , Lecture Notes in Math. , 558 , Springer (1976)
[a9]	B.Yu. Weisfeiler, A.A. Leman, "A reduction of a graph to a canonical form and an algebra arising during this reduction" Nauchno-Techn. Inform. Ser. 2 , 9 (1968) pp. 12–16 (In Russian)