Namespaces
Variants
Actions

Difference between revisions of "Coherent algebra"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (Automatically changed introduction)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct and if all png images have been replaced by TeX code, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 60 formulas, 59 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|part}}
 
Algebras introduced by D.G. Higman, first in relational language under the name coherent configuration [[#References|[a4]]] and later in terms of matrices [[#References|[a6]]]. The slightly different axiomatics of cellular algebras were independently suggested by B.Yu. Weisfeiler and A.A. Leman (cf. also [[Cellular algebra|Cellular algebra]]).
 
Algebras introduced by D.G. Higman, first in relational language under the name coherent configuration [[#References|[a4]]] and later in terms of matrices [[#References|[a6]]]. The slightly different axiomatics of cellular algebras were independently suggested by B.Yu. Weisfeiler and A.A. Leman (cf. also [[Cellular algebra|Cellular algebra]]).
  
Like association schemes (cf. also [[Association scheme|Association scheme]]) and Bose–Mesner algebras, coherent algebras provide a wide and solid foundation for investigations in various areas of algebraic combinatorics.
+
Like [[association scheme]]s and Bose–Mesner algebras, coherent algebras provide a wide and solid foundation for investigations in various areas of algebraic combinatorics.
 +
 
 +
A coherent algebra $W$ of order $n$ and rank $r$ is a matrix subalgebra of the full matrix algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c1301404.png"/> 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$;
  
A coherent algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c1301401.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c1301402.png" /> and rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c1301403.png" /> is a matrix subalgebra of the full matrix algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c1301404.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c1301405.png" />-matrices over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c1301406.png" /> such that:
+
$I \in W$, where $I$ is the unit matrix;
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c1301407.png" /> is closed with respect to the Hermitian adjoint, which is defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c1301408.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c1301409.png" />;
+
$J \in W$, where $J$ is the all-one matrix;
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014010.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014011.png" /> is the unit 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$.  
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014012.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014013.png" /> is the all-one matrix;
+
Each coherent algebra $W$ has a unique basis of zero-one matrices $\{ A _ { 1 } , \dots , A _ { r } \}$ such that:
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014014.png" /> is closed with respect to Schur–Hadamard multiplication <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014015.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014016.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014019.png" />. Each coherent algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014020.png" /> has a unique basis of zero-one matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014021.png" /> such that:
+
1) $\sum _ { i = 1 } ^ { r } A _ { i } = J$;
  
1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014022.png" />;
+
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$;
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014023.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014024.png" /> is the matrix transposed to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014025.png" />;
+
3) $A _ { i }\, A _ { j } = \sum _ { k = 1 } ^ { r } p _ { i ,\, j } ^ { k } \,A _ { k }$.  
  
3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014026.png" />. Property 1) implies that the basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014027.png" /> consists of mutually orthogonal idempotents with respect to the Schur–Hadamard product. This basis is called the standard basis of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014028.png" />. The non-negative integer structure constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014029.png" /> are important numerical invariants of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014030.png" />. The notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014031.png" /> indicates that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014032.png" /> is a coherent algebra with standard basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014033.png" />.
+
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 constant]]s $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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014034.png" /> and denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014035.png" /> a binary relation over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014036.png" />. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014037.png" /> is called the support of the zero-one matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014038.png" /> (or, in other words, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014039.png" /> is the [[adjacency matrix]] of the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014040.png" /> with vertex set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014041.png" /> and set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014042.png" /> of directed edges). The system of relations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014043.png" /> obtained in this way from a coherent algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014044.png" /> is called a coherent configuration.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014045.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014046.png" /> are sometimes called the intersection numbers of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014047.png" />. They have the following combinatorial interpretation:
+
The structure constants $p _ { i,j } ^ { k }$ of $W$ are sometimes called the intersection numbers of $\mathfrak{M}$. They have the following combinatorial interpretation:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014048.png" /></td> </tr></table>
+
\begin{equation*} \forall ( x , y ) \in R _ { k }: \end{equation*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014049.png" /></td> </tr></table>
+
\begin{equation*} p _ { i ,\, j } ^ { k } = | \{ z \in X : ( x , z ) \in R _{i}\, \&amp; ( z , y ) \in R _ { j } \} |. \end{equation*}
  
A coherent configuration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014050.png" /> is called homogeneous if one of its basic relations, say <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014051.png" />, coincides with the diagonal relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014052.png" />. In terms of matrices, a coherent algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014053.png" /> is called a Bose–Mesner algebra (briefly BM-algebra) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014054.png" />. Note that according to E. Bannai and T. Ito [[#References|[a1]]], a homogeneous coherent configuration is also called an association scheme (not necessarily commutative; cf. also [[Association scheme|Association scheme]]).
+
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 [[#References|[a1]]], a homogeneous coherent configuration is also called an association scheme (not necessarily commutative; cf. also [[Association scheme|Association scheme]]).
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014055.png" /> be a coherent configuration. A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014056.png" /> is called a fibre of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014057.png" /> if
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014058.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014059.png" /> 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, [[#References|[a3]]], [[#References|[a7]]], [[#References|[a9]]].
+
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, [[#References|[a3]]], [[#References|[a7]]], [[#References|[a9]]].
  
An important class of coherent algebras consists of the centralizer algebras of permutation groups (not necessarily transitive) [[#References|[a2]]], [[#References|[a10]]] (cf. also [[Permutation group|Permutation group]]; [[Centralizer|Centralizer]]). This leads to many important applications of coherent algebras.
+
An important class of coherent algebras consists of the centralizer algebras of permutation groups (not necessarily transitive) [[#References|[a2]]], [[#References|[a10]]] (cf. also [[Permutation group]]; [[Centralizer]]). This leads to many important applications of coherent algebras.
  
 
It was Higman [[#References|[a5]]], [[#References|[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|Finite group, representation of a]]).
 
It was Higman [[#References|[a5]]], [[#References|[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|Finite group, representation of a]]).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  E. Bannai,  T. Ito,  "Algebraic combinatorics" , '''I''' , Benjamin/Cummings  (1984)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  W.H. Haemers,  D.G. Higman,  "Strongly regular graphs with strongly regular decomposition"  ''Linear Alg. &amp; Its Appl.'' , '''114/115'''  (1989)  pp. 379–398</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D.G. Higman,  "Coherent configurations I"  ''Rend. Sem. Mat. Univ. Padova'' , '''44'''  (1970)  pp. 1–25</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D.G. Higman,  "Coherent configurations, Part I: Ordinary representation theory"  ''Geom. Dedicata'' , '''4'''  (1975)  pp. 1–32</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  D.G. Higman,  "Coherent algebras"  ''Linear Alg. &amp; Its Appl.'' , '''93'''  (1987)  pp. 209–239</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  D.G. Higman,  "Strongly regular designs and coherent configurations of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130140/c13014060.png" />"  ''Europ. J. Combin.'' , '''9'''  (1988)  pp. 411–422</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  D.G. Higman,  "Computations related to coherent configurations"  ''Congr. Numer.'' , '''75'''  (1990)  pp. 9–20</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  M.E. Muzychuk,  M. Klin,  "On graphs with three eigenvalues"  ''Discr. Math.'' , '''189'''  (1998)  pp. 191–207</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  H. Wielandt,  "Finite permutation groups" , Acad. Press  (1964)</TD></TR></table>
+
<table>
 +
<tr><td valign="top">[a1]</td> <td valign="top">  E. Bannai,  T. Ito,  "Algebraic combinatorics" , '''I''' , Benjamin/Cummings  (1984)</td></tr>
 +
<tr><td valign="top">[a2]</td> <td valign="top">  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</td></tr>
 +
<tr><td valign="top">[a3]</td> <td valign="top">  W.H. Haemers,  D.G. Higman,  "Strongly regular graphs with strongly regular decomposition"  ''Linear Alg. &amp; Its Appl.'' , '''114/115'''  (1989)  pp. 379–398</td></tr>
 +
<tr><td valign="top">[a4]</td> <td valign="top">  D.G. Higman,  "Coherent configurations I"  ''Rend. Sem. Mat. Univ. Padova'' , '''44'''  (1970)  pp. 1–25</td></tr>
 +
<tr><td valign="top">[a5]</td> <td valign="top">  D.G. Higman,  "Coherent configurations, Part I: Ordinary representation theory"  ''Geom. Dedicata'' , '''4'''  (1975)  pp. 1–32</td></tr>
 +
<tr><td valign="top">[a6]</td> <td valign="top">  D.G. Higman,  "Coherent algebras"  ''Linear Alg. &amp; Its Appl.'' , '''93'''  (1987)  pp. 209–239</td></tr>
 +
<tr><td valign="top">[a7]</td> <td valign="top">  D.G. Higman,  "Strongly regular designs and coherent configurations of type $\left( \begin{array} { l l } { 3 } &amp; { 2 } \\ { 2 } &amp; { 3 } \end{array} \right)$"  ''Europ. J. Combin.'' , '''9'''  (1988)  pp. 411–422</td></tr>
 +
<tr><td valign="top">[a8]</td> <td valign="top">  D.G. Higman,  "Computations related to coherent configurations"  ''Congr. Numer.'' , '''75'''  (1990)  pp. 9–20</td></tr>
 +
<tr><td valign="top">[a9]</td> <td valign="top">  M.E. Muzychuk,  M. Klin,  "On graphs with three eigenvalues"  ''Discr. Math.'' , '''189'''  (1998)  pp. 191–207</td></tr>
 +
<tr><td valign="top">[a10]</td> <td valign="top">  H. Wielandt,  "Finite permutation groups" , Acad. Press  (1964)</td></tr>
 +
</table>

Latest revision as of 17:44, 1 July 2020

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 $W$ 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=35934
This article was adapted from an original article by Mikhail Klin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article