An algebraic approach to the association schemes of coding theory. (English) Zbl 1075.05606
Philips Research Reports. Supplements 10. Ann Arbor, MI: Historical Jrl. vi, 97 p. (1973).
This report examines algebraic and combinatorial properties of codes from the point of view of association schemes in which the relations are not necessarily symmetric. For an association scheme with \(n\) classes on the set \(X\), the matrices \(D_i\), \(i=0,\dots,n\), denote the adjacency matrices of the \(n\) relations together with \(D_0=I\). If \(P_{ik}\) is the \(i\)th eigenvalue of \(D_k\) then the eigenmatrices of the scheme are defined as \(P=(P_{ik})\) and \(Q=|X|P^{-1}\). These two matrices turn out to be of great importance to the theory.
Two schemes in particular play prominent roles, namely, the Hamming and Johnson schemes. Let \(F\) be a finite set, \(|F|=q\geq 2\) and \(X=F^n\) its \(n\)-fold Cartesian product. Two points \(x\) and \(y\) are said to be \(i\)th related if the Hamming distance between them, \(d_H(x,y)\), is \(i\). This defines the Hamming scheme \(H(n,q)\) of length \(n\) over \(F\). The Johnson scheme \(J(n,v)\) is defined as follows. Let \(1\leq n\leq v/2\), \(F=\{0,1\}\) and let \(X\) be the set of binary \(v\)-tuples of Hamming weight \(n\). Two points \(x\) and \(y\) of \(X\) are \(i\)th associates in \(J(n,v)\) if \(d_H(x,y)/2=i\). \(J(n,v)\) is a symmetric scheme with \(n\) classes. Concepts of duality and extensions of association schemes are also considered.
Distance distributions of subsets of the set \(X\) on which an association scheme is defined are studied, and these considerations lead to interesting linear programming problems involving the eigenmatrices \(P\) and \(Q\). The notion of a \(T\)-design on a subset \(Y\) of \(X\) is defined and, for sets of the form \(T=\langle 1,2,\dots,\tau\rangle\) and a Hamming scheme defined on \(X\), these are simply orthogonal arrays of strength \(\tau\). For Johnson schemes they are the usual \(t\)-designs. For both Hamming and Johnson schemes, explicit forms for \(P\) and \(Q\) are obtained and, in the case of Hamming schemes, the simple connection between \(P\) and the MacWilliams weight enumeration formula is given. Some classical coding inequalities follow directly from the linear programming bound applied to these two schemes.
In Chapter five, polynomial schemes are introduced and an important analog to Lloyd’s theorem on perfect codes in \(P\)-polynomial schemes is proven. The duality between \(P\)-polynomial and \(Q\)-polynomial schemes is considered. Inequalities of Rao (for orthogonal arrays in \(H(n,q)\)) and Wilson and Ray-Chaudhuri (for \(t\)-designs in \(J(n,v)\)) are extended to \(t\)-designs in any \(Q\)-polynomial scheme. The final chapter treats additive codes that are subgroups of \(F^n\), the \(n\)-fold direct product of the abelian group \(F\). The duality among subgroups is studied using group characters. A criterion for deciding when an additive code is a subscheme of a Hamming scheme is given and the result is applied to the Golay code.
This report, which forms the author’s thesis at the Université Catholique de Louvain, demonstrates the utility of association schemes in coding and is one of the most important and innovative works in this area in recent years.
Two schemes in particular play prominent roles, namely, the Hamming and Johnson schemes. Let \(F\) be a finite set, \(|F|=q\geq 2\) and \(X=F^n\) its \(n\)-fold Cartesian product. Two points \(x\) and \(y\) are said to be \(i\)th related if the Hamming distance between them, \(d_H(x,y)\), is \(i\). This defines the Hamming scheme \(H(n,q)\) of length \(n\) over \(F\). The Johnson scheme \(J(n,v)\) is defined as follows. Let \(1\leq n\leq v/2\), \(F=\{0,1\}\) and let \(X\) be the set of binary \(v\)-tuples of Hamming weight \(n\). Two points \(x\) and \(y\) of \(X\) are \(i\)th associates in \(J(n,v)\) if \(d_H(x,y)/2=i\). \(J(n,v)\) is a symmetric scheme with \(n\) classes. Concepts of duality and extensions of association schemes are also considered.
Distance distributions of subsets of the set \(X\) on which an association scheme is defined are studied, and these considerations lead to interesting linear programming problems involving the eigenmatrices \(P\) and \(Q\). The notion of a \(T\)-design on a subset \(Y\) of \(X\) is defined and, for sets of the form \(T=\langle 1,2,\dots,\tau\rangle\) and a Hamming scheme defined on \(X\), these are simply orthogonal arrays of strength \(\tau\). For Johnson schemes they are the usual \(t\)-designs. For both Hamming and Johnson schemes, explicit forms for \(P\) and \(Q\) are obtained and, in the case of Hamming schemes, the simple connection between \(P\) and the MacWilliams weight enumeration formula is given. Some classical coding inequalities follow directly from the linear programming bound applied to these two schemes.
In Chapter five, polynomial schemes are introduced and an important analog to Lloyd’s theorem on perfect codes in \(P\)-polynomial schemes is proven. The duality between \(P\)-polynomial and \(Q\)-polynomial schemes is considered. Inequalities of Rao (for orthogonal arrays in \(H(n,q)\)) and Wilson and Ray-Chaudhuri (for \(t\)-designs in \(J(n,v)\)) are extended to \(t\)-designs in any \(Q\)-polynomial scheme. The final chapter treats additive codes that are subgroups of \(F^n\), the \(n\)-fold direct product of the abelian group \(F\). The duality among subgroups is studied using group characters. A criterion for deciding when an additive code is a subscheme of a Hamming scheme is given and the result is applied to the Golay code.
This report, which forms the author’s thesis at the Université Catholique de Louvain, demonstrates the utility of association schemes in coding and is one of the most important and innovative works in this area in recent years.
Reviewer: Ian Blake (MR 52#5187)
