### Cayley graph construction

Here's an example.

Let be a finite group of order generated by . Let denote the Cayley graph of and let be the incidence matrix of . Then the matrix is the parity check matrix of a LDPC code, provided is ``small'' with respect to . 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