# Cellular algebra

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

(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 $W$ of order $n$ and rank $r$ is a matrix subalgebra of the full matrix algebra $\mathbf{C}^{n \times n}$ of $( n \times n )$-matrices over $\mathbf{C}$ such that:

$W$ is closed with respect to the Hermitian adjoint;

$J \in W$, where $J$ is the all-one matrix;

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

Like coherent algebras, a cellular algebra $W$ has a unique standard basis of zero-one matrices $\{ A _ { 1 } , \dots , A _ { r } \}$, consisting of mutually orthogonal Schur–Hadamard idempotents. The notation $W = \langle A _ { 1 } , \dots , A _ { r } \rangle$ indicates that $W$ has the standard basis $\{ A _ { 1 } , \dots , A _ { r } \}$.

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

The relational analogue of cellular algebras with the unit matrix $I$ 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 $I$ (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 $n$ it is possible to determine a minimal cellular algebra containing this set. In particular, if $\Gamma$ is an $n$-vertex graph and $A = A ( \Gamma )$ is its adjacency matrix, then $\langle \langle A \rangle \rangle$ denotes the smallest cellular algebra containing $A$. It is called the cellular closure (or Weisfeiler–Leman closure) of $W$.

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

For each cellular algebra $W = \langle A _ { 1 } , \dots , A _ { r } \rangle$ one can introduce its automorphism group

\begin{equation*} \operatorname { Aut } ( W ) = \cap _ { i = 1 } ^ { r } \operatorname { Aut } ( A _ { i } ). \end{equation*}

Here, $\operatorname { Aut} ( A _ { i } )$ is the automorphism group of the graph $\Gamma_{i}$ with adjacency matrix $A _ { i } = A ( \Gamma _ { i } )$. For each permutation group $( G , \Omega )$, its centralizer algebra $\mathfrak { V } ( G , \Omega )$ is a cellular algebra with matrix $I$. Thus, the functors $\operatorname { Aut}$ and $\mathfrak V$ introduce a Galois correspondence between cellular (coherent) algebras and permutation groups. Some properties and applications of this correspondence are considered in [a2], [a5].

How to Cite This Entry:
Cellular algebra. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Cellular_algebra&oldid=51332
This article was adapted from an original article by Mikhail Klin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article