Cayley graph construction

Here's an example.

Let $ G$ be a finite group of order $ n$ generated by $ S=\{s_1,...,s_d\}$. Let $ \Gamma$ denote the Cayley graph of $ (G,S)$ and let $ H$ be the incidence matrix of $ \Gamma$. Then the matrix $ H=(P_{ij})$ is the parity check matrix of a LDPC code, provided $ d$ is ``small'' with respect to $ n$. See [LR] and the references cited there for more details on such constructions.

Here's a small example using MAGMA. (Note that MAGMA does not have the ability to create a code from its parity check matrix, so we must treat the parity check matrix as the generator matrix of the dual code.)

> S3:=PermutationGroup< 3 | (1,2),(1,2,3)>;  
> Gamma:=CayleyGraph(S3);
> Gamma;
Digraph
Vertex  Neighbours

1       3 4 ;
2       3 4 ;
3       1 6 ;
4       2 5 ;
5       1 6 ;
6       2 5 ;

> I:=IncidenceMatrix(Gamma);
> I;
[ 1  1  0  0 -1  0  0  0 -1  0  0  0]
[ 0  0  1  1  0  0 -1  0  0  0 -1  0]
[-1  0 -1  0  1  1  0  0  0  0  0  0]
[ 0 -1  0 -1  0  0  1  1  0  0  0  0]
[ 0  0  0  0  0  0  0 -1  1  1  0 -1]
[ 0  0  0  0  0 -1  0  0  0 -1  1  1]
> NumberOfColumns(I);
12
> NumberOfRows(I);   
6
> M := KMatrixSpace(FiniteField(2), 6,12);  
> G:=M!I;
> C1:=LinearCode(G);
> C:=Dual(C1);    
> Dimension(C);
7
> MinimumDistance(C);
2
> C;
[12, 7, 2] Linear Code over GF(2)
Generator matrix:
[1 0 0 0 0 1 0 0 1 0 0 1]
[0 1 0 0 0 0 0 1 1 0 0 0]
[0 0 1 0 0 1 0 0 0 0 1 0]
[0 0 0 1 0 0 0 1 0 0 1 1]
[0 0 0 0 1 1 0 0 1 0 0 1]
[0 0 0 0 0 0 1 1 0 0 1 1]
[0 0 0 0 0 0 0 0 0 1 0 1]


David Joyner 2007-09-03