Namespaces
Variants
Actions

Coherent algebra

From Encyclopedia of Mathematics
Jump to: navigation, search

Algebras introduced by D.G. Higman, first in relational language under the name coherent configuration [a4] and later in terms of matrices [a6]. The slightly different axiomatics of cellular algebras were independently suggested by B.Yu. Weisfeiler and A.A. Leman (cf. also Cellular algebra).

Like association schemes and Bose–Mesner algebras, coherent algebras provide a wide and solid foundation for investigations in various areas of algebraic combinatorics.

A coherent algebra of order n and rank r is a matrix subalgebra of the full matrix algebra of ( n \times n )-matrices over \mathbf{C} such that:

W is closed with respect to the Hermitian adjoint, which is defined by A ^ { * } = ( a _ { i , j } ) ^ { * } = ( \overline { a _ { j , i } } ) for A = ( a _ { i ,\, j } ) \in W;

I \in W, where I is the unit matrix;

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

W is closed with respect to Schur–Hadamard multiplication \circ , where A \circ B = ( a _ { i , j} b _ { i , j} ) for A = ( a_{i ,\, j} ), B = ( b _ { i , j} ), A , B \in W.

Each coherent algebra W has a unique basis of zero-one matrices \{ A _ { 1 } , \dots , A _ { r } \} such that:

1) \sum _ { i = 1 } ^ { r } A _ { i } = J;

2) \forall 1 \leq i \leq r \exists 1 \leq j \leq r : A _ { i } ^ { T } = A _ { j }, where A _ { i } ^ { T } is the matrix transposed to A_i;

3) A _ { i }\, A _ { j } = \sum _ { k = 1 } ^ { r } p _ { i ,\, j } ^ { k } \,A _ { k }.

Property 1) implies that the basis \{ A _ { 1 } , \dots , A _ { r } \} consists of mutually orthogonal idempotents with respect to the Schur–Hadamard product. This basis is called the standard basis of W. The non-negative integer structure constants p _ { i,j } ^ { k } are important numerical invariants of W. The notation W = \langle A _ { 1 } , \dots , A _ { r } \rangle indicates that W is a coherent algebra with standard basis \{ A _ { 1 } , \dots , A _ { r } \}.

Let X = \{ 1 , \dots , n \} and denote by R_l = \{ ( i , j ) : a _ { i , j } = 1 \} a binary relation over X. R_l is called the support of the zero-one matrix A_{l} = ( a _ { i,j }) (or, in other words, A _ { l } is the adjacency matrix of the graph \Gamma _ { l } = ( X , R _ { l } ) with vertex set X and set R_l of directed edges). The system of relations \mathfrak { M } = ( X , \{ R _ { i } \} _ { 1 \leq i \leq r } ) obtained in this way from a coherent algebra W is called a coherent configuration.

The structure constants p _ { i,j } ^ { k } of W are sometimes called the intersection numbers of \mathfrak{M}. They have the following combinatorial interpretation:

\begin{equation*} \forall ( x , y ) \in R _ { k }: \end{equation*}

\begin{equation*} p _ { i ,\, j } ^ { k } = | \{ z \in X : ( x , z ) \in R _{i}\, \& ( z , y ) \in R _ { j } \} |. \end{equation*}

A coherent configuration \mathfrak{M} is called homogeneous if one of its basic relations, say R _ { 1 }, coincides with the diagonal relation \Delta = \{ ( x , x ) : x \in X \}. In terms of matrices, a coherent algebra W = \langle A _ { 1 } , \dots , A _ { r } \rangle is called a Bose–Mesner algebra (briefly BM-algebra) if A _ { 1 } = I. Note that according to E. Bannai and T. Ito [a1], a homogeneous coherent configuration is also called an association scheme (not necessarily commutative; cf. also Association scheme).

Let \mathfrak { M } = ( X , \{ R _ { i } \} _ { 1 \leq i \leq r } ) be a coherent configuration. A subset \emptyset \neq M \subseteq X is called a fibre of \mathfrak{M} if

\begin{equation} \tag{a1} \forall 1 \leq i \leq r : R _ { i } \subseteq M ^ { 2 } \vee R _ { i } \bigcap M ^ { 2 } = \emptyset \end{equation}

and M is a minimal (with respect to inclusion) subset satisfying condition (a1). The coherent algebras with one fibre are exactly the BM-algebras. Coherent algebras with few fibres may be used for a unified presentation and investigation of various combinatorial objects, see, for example, [a3], [a7], [a9].

An important class of coherent algebras consists of the centralizer algebras of permutation groups (not necessarily transitive) [a2], [a10] (cf. also Permutation group; Centralizer). This leads to many important applications of coherent algebras.

It was Higman [a5], [a8] who developed the foundations of the representation theory of coherent algebras as a generalization of the representation theory of finite permutation groups (cf. also Finite group, representation of a).

References

[a1] E. Bannai, T. Ito, "Algebraic combinatorics" , I , Benjamin/Cummings (1984)
[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] W.H. Haemers, D.G. Higman, "Strongly regular graphs with strongly regular decomposition" Linear Alg. & Its Appl. , 114/115 (1989) pp. 379–398
[a4] D.G. Higman, "Coherent configurations I" Rend. Sem. Mat. Univ. Padova , 44 (1970) pp. 1–25
[a5] D.G. Higman, "Coherent configurations, Part I: Ordinary representation theory" Geom. Dedicata , 4 (1975) pp. 1–32
[a6] D.G. Higman, "Coherent algebras" Linear Alg. & Its Appl. , 93 (1987) pp. 209–239
[a7] D.G. Higman, "Strongly regular designs and coherent configurations of type \left( \begin{array} { l l } { 3 } & { 2 } \\ { 2 } & { 3 } \end{array} \right)" Europ. J. Combin. , 9 (1988) pp. 411–422
[a8] D.G. Higman, "Computations related to coherent configurations" Congr. Numer. , 75 (1990) pp. 9–20
[a9] M.E. Muzychuk, M. Klin, "On graphs with three eigenvalues" Discr. Math. , 189 (1998) pp. 191–207
[a10] H. Wielandt, "Finite permutation groups" , Acad. Press (1964)
How to Cite This Entry:
Coherent algebra. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Coherent_algebra&oldid=50680
This article was adapted from an original article by Mikhail Klin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article