See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/319201120

LCD codes from adjacency matrices of graphs

Article in Applicable Algebra in Engineering Communication and Computing · June 2018

DOI: 10.1007/s00200-017-0339-6

CITATIONS READS

21 392

2 authors:

Jennifer D. Key Bernardo Rodrigues

Clemson University University of Pretoria
125 PUBLICATIONS 2,262 CITATIONS 82 PUBLICATIONS 573 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Jennifer D. Key on 05 September 2017.

The user has requested enhancement of the downloaded file.

 LCD codes from adjacency matrices of graphs
J.D. Key∗
Institute of Mathematics, Physics and Computer Science
Aberystwyth University, Aberystwyth SY23 3BZ, U.K.
B.G. Rodrigues†
School of Mathematics, Statistics and Computer Science
University of KwaZulu-Natal
Durban 4000, South Africa

August 4, 2017

Abstract
It is shown how LCD codes with a particularly useful feature can be found from row spans
over finite fields of adjacency matrices of graphs by considering these together with the codes
from the associated reflexive graphs and complementary graphs. Application is made to some
particular classes, including uniform subset graphs and strongly regular graphs where, if a p-
ary code from a graph has this special LCD feature, the dimension can be found from the
multiplicities modulo p of the eigenvalues of an adjacency matrix and, bounds on the minimum
weight of the code and the dual code follow from the valency of the graph.

Keywords: LCD codes; uniform subset graphs; strongly regular graphs

Mathematics Subject Classifications: 05C50, 94B05

1 Introduction
In [28] Massey defines an LCD code (linear code with complementary dual) as a code for which
the hull is zero, i.e. if C is a linear code, C is LCD if Hull(C) = C ∩ C ⊥ = {0}. Thus C ⊥ is also
LCD, and if C is of length n over a field F , then F n = C ⊕ C ⊥ .
It is shown in [28] that for an LCD code C to correct errors by nearest neighbour decoding,
one needs only to find the nearest word to the received word in the code C ⊥ . This reduces the
computation of error correction. In order to achieve this, one first needs to be able to say exactly
how any vector w ∈ F n can be written as its unique sum of vectors in C and C ⊥ . In this work here
we show how consideration of codes from the adjacency matrix of undirected graphs, together with
their reflexive associates, and their complementary graphs, leads to a simple way to achieve this
representation. Furthermore, in this event, since C and C ⊥ are the codes from graphs or reflexive
graphs, respectively, information regarding the codes can be obtained from properties of the graph,
including that the minimum weight of C is at most the valency ν, and that of C ⊥ at most ν + 1.
For some classes of graphs there is already information to be found in the literature regarding the
properties of the codes from adjacency matrices of graphs and their reflexive associates.
∗
Email:[email protected]
†
Email:[email protected]

1
2 BACKGROUND AND DEFINITIONS 2

We show, in Proposition 1 (in Section 3), how, for these LCD codes C, the representation of
any vector as a unique sum of vectors in C and C ⊥ can be achieved for the codes from adjacency
matrices of graphs that satisfy certain properties, and in Proposition 2 we show some graph theoretic
properties that will suffice to establish this. In Sections 4 and 5 we show how this can be done
explicitly for uniform subset graphs (Proposition 3), and for strongly regular graphs (Proposition 4).
Section 2 gives some terminology and background.

2 Background and definitions

The notation for codes and codes from incidence structures and graphs is as in [2]. For an incidence
structure D = (P, B, J ), with point set P, block set B and incidence J , the code CF (D) = Cq (D)
of D over the finite field F = Fq is the space spanned by the incidence vectors of the blocks over
F . If Q is any subset of P, then we will denote the incidence vector of Q by v Q , and if Q = {x}
where x ∈ P, then we will write v x . Thus CF (D) = v B | B ∈ B , and is a subspace of F P , the full
vector space of functions from P to F . For any w ∈ F P and P ∈ P, w(P ) denotes the value of w
at P .
All the codes here are linear codes, and the notation [n, k, d]q will be used for a q-ary code C of
length n, dimension k, and minimum weight d, where the weight wt(v) of a vector v is the number
of non-zero coordinate entries. Vectors in a code are also called words. The support, Supp(v), of
a vector v is the set of coordinate positions where the entry in v is non-zero. So |Supp(v)| = wt(v).
A generator matrix for C is a k × n matrix made up of a basis for C, and the dual code C ⊥ is
the orthogonal under the standard inner product (, ), i.e. C ⊥ = {v ∈ F n | (v, c) = 0 for all c ∈ C}.
The hull, Hull(C), of a code C is the self-orthogonal code Hull(C) = C ∩ C ⊥ . A check matrix
for C is a generator matrix for C ⊥ . The all-one vector will be denoted by , and is the vector
with all entries equal to 1. If we need to specify the length m of the all-one vector, we write m . A
constant vector is a non-zero vector in which all the non-zero entries are the same. We call two
linear codes isomorphic (or permutation isomorphic) if they can be obtained from one another by
permuting the coordinate positions. An automorphism of a code C is an isomorphism from C to
C. The automorphism group will be denoted by Aut(C), also called the permutation group of C,
and denoted by PAut(C) in [20].
The graphs, Γ = (V, E) with vertex set V and edge set E, discussed here are undirected with
no loops, apart from the case where all loops are included, in which case the graph is called the
reflexive associate of Γ, denoted by RΓ. If x, y ∈ V and x and y are adjacent, we write x ∼ y, and
xy for the edge in E that they define. We also consider the complementary graph, Γ = (V, E)
where for x, y ∈ V , x 6= y, x ∼ y in Γ if and only if x 6∼ y in Γ. The set of neighbours of x ∈ V
is denoted by N (x), and the valency of x is |N (x)|. Γ is regular if all the vertices have the same
valency.
An adjacency matrix A = [ax,y ] for Γ is a |V | × |V | matrix with rows and columns labelled by
the vertices x, y ∈ V , and with ax,y = 1 if x ∼ y in Γ, and ax,y = 0 otherwise. Then RA = A + I is
an adjacency matrix for RΓ, and A = J − I − A one for Γ, where I = I|V | and J is the |V | × |V |
all-ones matrix. The row corresponding to x ∈ V in A will be denoted by rx , that in RA by sx ,
and that in A by cx .
The code over a field F of Γ will be the row span of an adjacency matrix A for Γ, and written
as CF (A), CF (Γ), or Cp (A), Cp (Γ), respectively, if F = Fp .
The background on LCD codes from [28] is described below.
3 SPECIAL LCD CODES FROM GRAPHS 3

Definition 1 A linear code C over any field is a linear code with complementary dual (LCD)
code if Hull(C) = C ∩ C ⊥ = {0}.

If C is an LCD code of length n over a field F , then F n = C ⊕ C ⊥ . Thus the orthogonal

projector map ΠC from F n to C can be defined as follows: for v ∈ F n ,

v if v ∈ C,
vΠC = , (1)
0 if v ∈ C ⊥

and ΠC is defined to be linear. 1 This map is only defined if C (and hence also C ⊥ ) is an LCD
code. Similarly then ΠC ⊥ is defined.
Note that for all v ∈ F n ,
v = vΠC + vΠC ⊥ . (2)
We will use [28, Proposition 4]:

Result 1 (Massey) Let C be an LCD code of length n over the field F and let ϕ be a map
ϕ : C ⊥ 7→ C such that u ∈ C ⊥ maps to one of the closest codewords v to it in C. Then the map
ϕ̃ : F n 7→ C such that
ϕ̃(r) = rΠC + ϕ(rΠC ⊥ )
maps each r ∈ F n to one of it closest neighbours in C. 2

We make the following observation which will be of use in the next section:

Lemma 1 If C is a q-ary code of length n such that C + C ⊥ = Fnq then C is LCD.

Proof: Since (C + C ⊥ )⊥ = C ⊥ ∩ C = (Fnq )⊥ = {0} = Hull(C), C (and C ⊥ ) are LCD. 

3 Special LCD codes from graphs

We note first that we are considering a particular class of LCD codes from adjacency matrices of
undirected graphs. There are indeed many cases of LCD codes from adjacency, and also incidence,
matrices of graphs in the literature: for example, refer to [21, 23, 18, 17, 14, 29]. However in this
paper we are only looking at a particular type of LCD code from a graph, as we will describe
below.
If Γ = (V, E) is a graph, A an adjacency matrix for Γ and p a prime, let C = Cp (A), RC =
Cp (RA) and C = Cp (A), using the notation as defined in Section 2, i.e. RA = A + I, and A =
J − I − A.
For any x ∈ V , with rx , sx , cx as defined in Section 2, we have,

sx = v x + rx , cx =  − v x − rx =  − sx . (3)

Proposition 1 Let Γ = (V, E) be a graph, A an adjacency matrix, RΓ its associated reflexive

graph, Γ its complementary graph. Let p be any prime, and C = Cp (A), RC = Cp (RA), C = Cp (A).
Then:
1
Note typographical error on p.338, l.-11, in [28]
2
Note typographical error on p.341, l.-7, in [28]
3 SPECIAL LCD CODES FROM GRAPHS 4

1. If C = RC ⊥ , then C and RC are LCD codes. Further, if v ∈ FVp , and v = v(x)v x ,

P
x∈V
then X X X
v= v(x)v x = − v(x)rx + v(x)sx = vΠC + vΠC ⊥ ,
x∈V x∈V x∈V
P P
where vΠC = − x∈V v(x)r
P x and vΠC ⊥ = x∈V v(x)sx . In particular, if p = 2 and P if v ∈ C,
T = Supp(v) then v = x∈T rx , and similarly if v ∈ C ⊥ , R = Supp(v) then v = x∈R sx .
⊥
2. If Γ is regular of valency ν, and C = C , then C and C are LCD codes. Further, if v ∈ FVp ,
and v = x∈V v(x)v x , then
P

X X X X
v= v(x)v x = ( v(x)) − v(x)rx − v(x)cx = vΠC + vΠC ⊥
x∈V x∈V x∈V x∈V
P P P
where vΠC = ( x∈V v(x)) − x∈V v(x)rx if p 6 |ν, and vΠC = − x∈V v(x)rx if p|ν.

Proof: (1): Since v x = sx − rx implies that FVp = C + RC, that C and RC are LCD follows from
Lemma 1.
Since for any x ∈ V , sx = v x + rx , for any v ∈ FVp , v = x∈V v(x)v x = x∈V v(x)(sx − rx ), we
P P

have vΠC = − x∈V v(x)rx and vΠC ⊥ = x∈V v(x)sx . If p = 2 then v = v S =

P P P P
x∈S sx P x∈S rx ,
+
T
P
where S = Supp(v).
P P In particular, if v ∈ C, and Supp(v) = T , then v = v = x∈T rx + x∈T sx =
⊥ = {0}.
x∈T rx , since x∈T sx = 0 because C ∩ C
⊥
(2): Suppose C = C . Since ν = x∈V rx , if p 6 |ν then  ∈ C; if p|ν then  ∈ C ⊥ = C. Thus,
P
since for any x ∈ V , v x =  − rx − cx , we have in either case that FVp = C + C ⊥ and thus C and C
are LCD by Lemma 1.P
For v ∈ FVp , v = x∈V v(x)v x = ( x∈V v(x)) − x∈V v(x)rx − x∈V v(x)cx . Since ν =
P P P
⊥
P P P
Px∈V rx , if p 6 |ν then vΠC = ( x∈V v(x)) − x∈V v(x)rx ; if p|ν then  ∈ C = C, so vΠC =
− x∈V v(x)rx . 
Because the conditions on the relations amongst the code of a graph and its reflexive and
complementary graphs lead to LCD codes with a given split of any vector into its parts in the
disjoint components, for convenience, for the purposes of this paper, we give these conditions
special names.
With notation as defined above:

Definition 2 Let Γ = (V, E) be a graph with adjacency matrix A. Let p be any prime, C = Cp (A),
RC = Cp (RA) (for the reflexive graph), and C = Cp (A). Then

• if C = RC ⊥ , then we call C a reflexive LCD code, and write RLCD for such a code;
⊥
• if Γ is regular and C = C , then we call C a complementary LCD code, and write CLCD
for such a code.

Note: If Γ is regular and Cp (Γ) is both RLCD and CLCD, then Cp (RΓ) = Cp (Γ).
In [26] it was noted that the triangular graph T (n) for n ≡ 1 (mod 4) has binary code that is
CLCD, and the question was raised as to the existence of other graphs with such a property. The
authors of that paper did find some more codes acted on by subgroups of the McLaughlin group:
see [26, Theorem 1].
We will find more infinite classes of graphs with RLCD or CLCD codes in what follows.
3 SPECIAL LCD CODES FROM GRAPHS 5

Note: If we know the eigenvalues of A, and if they are integral, we can use them to get information
regarding the possible dimension of the codes C, RC and C. Since if λ is an eigenvalue for a matrix
M then λ + 1 is an eigenvalue for M + I, this will also give information about RC. If M is a
v × v integral matrix with integral eigenvalues, then modulo p these will still be eigenvalues, but
not necessarily all distinct. If none or at most one reduce to 0 modulo p then the p-rank of M will
be v or v − mj , respectively, where mj is the multiplicity of the eigenvalue that is zero. In any case,
the dimension of the zero eigenspace over Fp of the matrix A or A + I is at most the sum m of the
multiplicities of the eigenvalues that reduce to 0 modulo p, and thus the p-rank of A or A + I is at
least v − m.
Likewise, for Γ regular of valency ν, the spectrum for A = J − I − A can be obtained from that
of Γ as being |V | − 1 − ν and −1 − θ, where the θ is an eigenvalue of A with eigenvector w such
that wT = 0, i.e. w is orthogonal to . So these are also all integral if the θ are.
We note the following result from [19], which is given there for p = 2 but it holds for all primes
p, so we state it for all p:

Result 2 (Proposition 2.2 [19]) If A is a symmetric integral matrix, and CA , CA+I denote the
⊥ ⊆ C
row span over Fp , where p is a prime, of A, A + I respectively, then CA A+I with equality if
and only if A(A + I) ≡ 0 (mod p).

Lemma 2 If Γ = (V, E) is regular of valency ν, |V | = n, p is a prime, and A is an adjacency

matrix for Γ, then both Cp (Γ) and Cp (Γ) can be RLCD if and only if n − 2ν − 1 ≡ 0 (mod p).

Proof: With the usual notation, A(A + I) = (J − I − A)(J − A) = J 2 − 2AJ − J + A(A + I) =

(n − 2ν − 1)J + A(A + I), so the assertion follows. 

Proposition 2 Let Γ = (V, E) be a graph with adjacency matrix A, |V | = n. Let C = Cp (A),

RC = Cp (RA) and C = Cp (A). Then

1. if C ⊆ RC ⊥ , then C = RC ⊥ and C is RLCD;

⊥ ⊥
2. if Γ is regular of valency ν, A has integral eigenvalues, and C ⊆ C , then C = C and C is
⊥
CLCD, except, possibly, if p|ν and p|(|V | − 1). In any case, dim C ≤ dim(C ) ≤ dim(C) + 1.

Proof: (1): This is clear by Result 2.

⊥
(2) Suppose C ⊆ C . Denote the eigenvalues for A by {ei | 1 ≤ i ≤ r} with multiplicity mi , and
suppose that in Fp , e1 , . . . , es ≡ 0 (mod p), and ei 6≡ 0 (mod p) for i ≥ s + 1. If ν 6∈ {e1 , . . . , es },
then the corresponding eigenvalues for A are −1 − e1 , . . . , −1 P − es and are 6≡ 0 (mod p). From
Ps the
s
argument regardingPs the eigenvalues above, dim(N ull(C))
Pr ≤ m
i=1 i , so dim(C) ≥ n
Pr− i=1 mi ,
⊥
and dim(C ) ≤ i=1 mi . Now dim(N ull(C)) ≤ i=s+1 mi , so dim(C) ≥ n − i=s+1 mi =
Ps ⊥
i=1 mi , and we have C = C .
Now suppose that ν ∈ {e1 , . . . , es }, i.e. that p|ν. The corresponding eigenvalue of A is n − 1 − ν
and if this is not ≡ 0 (mod p) then the argument goes through as above. If however n − 1 −
⊥
ν ≡ 0 (mod p), i.e. p|(n − 1), then we cannot deduce equality, although we do have dim(C ) ≤
dim(C) + 1. 
When we have a graph Γ with integral eigenvalues for which Cp (Γ) is RLCD, we can say exactly
what the dimension is from the values of the eigenvalues modulo p:
4 UNIFORM SUBSET GRAPHS 6

Lemma 3 Let Γ = (V, E) be a graph with adjacency matrix A that has integral eigenvalues and
suppose p is a prime for which Cp (Γ) is RLCD. Then dim(Cp (Γ)) is the sum of the multiplicities
of the eigenvalues that are non-zero modulo p.

Proof: Let C = Cp (A), RC = Cp (RA) = Cp (A + I). We have C ⊥ = RC. Suppose the eigen-
values for A are {ei | 1 ≤ i ≤ r} with multiplicity mi . Suppose that e1 , . . . , es ≡ 0 (mod p), and
ei 6≡ 0 (mod p) for i ≥ s+1. Thus the eigenvalues e1 +1, . . . , es +1
Psof A+I are 6≡ 0 (mod P p). From
the argument regarding
Ps the eigenvalues above, dim(NP ull(C)) ≤ i=1 mi , so dim(C) ≥P v− si=1 mi ,
and dim(C ) ≤ i=1 mi . Now dim(N ull(RC)) ≤ i=s+1 mi , so dim(RC) ≥ v − ri=s+1 mi =
⊥ r
Ps ⊥
Ps Ps Pr
i=1 mi . Thus dim(RC) = dim(C ) = i=1 mi , and dim(C) = v − i=1 mi = i=s+1 mi . 

4 Uniform subset graphs

The uniform subset graph Γ(n, k, r) (also called a Johnson graph J(n, k, r) in the literature)
has for vertices V = Ω{k} , the set of all subsets of size k of a set of size n,
with
two k-subsets x
k n−k
and y defined to be adjacent if |x ∩ y| = r. The valency of Γ(n, k, r) is r k−r . The symmetric
group Sn always acts on Γ(n, k, r), transitively on vertices and edges. Similarly for RΓ(n, k, r), the
corresponding reflexive graph, and Γ, the complementary graph.
Let Akr , RAkr = Akr + I, Akr = J − I − Akr be adjacency matrices for Γ(n, k, r), RΓ(n, k, r) and
Γ, respectively, where 0 ≤ r ≤ k − 1. For any fixed prime p, and fixed n, k, let Cr , RCr , Cr denote
the row span over Fp of Akr , RAkr , Akr , respectively.
Rows of Akr , RAkr , Akr for r = 0, 1, . . . , k − 1 are denoted by rxr , srx , crx respectively, for x ∈ V ,
where we assume a fixed value of k ≥ 2. Thus, from Equation (3),

srx = rxr + v x , crx =  − v x − rxr .

We will simply write A, rx , and so on, instead of Akr , rxr , and so on, when speaking generally of a
fixed k and r in Γ(n, k, r).
The codes Wi for 1 ≤ i ≤ k − 1 are defined in [11]: for 1 ≤ s ≤ n let Ω{s} denote the set of
s-subsets of Ω. For Λ ∈ Ω{s} and 0 ≤ s ≤ k, define
X
wΛ = v Λ∪Λ1 , Ws = hwΛ | Λi ∈ Ω{s} i, E(Ws ) = hwΛ1 − wΛ2 | Λi ∈ Ω{s} i. (4)
Λ1 ∈Ω{k−s}
Λ∩Λ1 =∅

A further code WΠ is obtained by taking the partitions of subsets of size 2k of Ω. Let such
a partition π of the 2k-set Λ = {a1 , a2 , b1 , b2 , . . . , k1 , k2 } be [[a1 , a2 ], [b1 , b2 ], . . . , [k1 , k2 ]]. The word
wπ , of weight 2k is given by X
wπ = ±v {ai1 ,bi2 ,...,kik }
where all the subsets of Λ of k-sets of the form {ai1 , bi2 , . . . , kik }, where ij ∈ {1, 2}, are present,
with the sign being determined by giving x = {a1 , b1 , . . . , k1 } the sign “+”, and then demanding
that any other k-set in the support with intersection of size k − 1 with x will have sign “−”, and
then applying this in general to get the signs on all the 2k vertices. Then

WΠ = hwπ | π partition of Λ ⊂ Ω, |Λ| = 2k i. (5)

Note that WΠ ⊆ Ws⊥ for all p, n, k, r, 0 ≤ s ≤ k − 1.

4 UNIFORM SUBSET GRAPHS 7

We mention these codes as they show themselves in the codes from uniform subset graphs, as
demonstrated in [11] (but see also [22, 21, 23, 17, 14] for k = 2, 3): what was found for k = 2, 3,
all p, and for other values of k (for example for Johnson and odd graphs for all k and p = 2, from
Fish [16]) was that the codes of Γ(n, k, r) and RΓ(n, k, r) were all some combination of the codes
C, where C is Ws , E(Ws ), WΠ , hi, FVp , along with their duals and hulls.
In particular, from [22, 21, 23, 17, 14, 11, 16], we have the following RLCD candidates from
the codes from adjacency matrices of uniform subset graphs.

Result 3 For n ≥ 7, k = 3, Ci , RCi for i = 0, 1, 2 as defined, Ci⊥ = RCi in the following cases:

5, n
≡ 5 (mod p), C0⊥ = RC0 = W2 , and RC0 is a [ n3 , n2 , n − 2]p code, C0 is a

1. For
p ≥
[ n3 , n3 − n2 , δ]p code, where δ ≤ 8.

n ≡
1 (mod 4), C0⊥ = RC0 = W1 + W2 , and RC0 is a [ n3 , n2 , n − 2]2 code, C0 is

2. For p
= 2,
a [ n3 , n3 − n2 , 8]2 code.

9), C0⊥ = RC0 = W2 + hi, and RC0 is a [ n3 , n2 + 1, n − 2]3 code,

3. For p = 3,
n ≡
5 (mod
C0 is a [ n3 , n3 − n2 − 1, 8]3 code.

⊥ = RC = W and RC is a [ n , n, n−1 ] code, C is a

4. For
p = 2, n ≡ 0 (mod 4), C 1 1 1 1 3 2 2 1
[ n3 , n3 − n, 4]2 code.

5. For
p =
2, n
≡ 1, 3 (mod 4), C2⊥ = RC2 = W2 and RC2 is a [ n3 , n2 , n − 2]2 code, C2 is a

[ n3 , n3 − n2 , 4]2 code.

For n ≥ 5, k = 2, p = 2,

1. For n
≡ 3
(mod 4) then C0⊥ = RC0 = W1 + hi and RC0
is a [ n2 , n, n − 1]2 code, C0 is

a [
n2 ,
n2 − n, 4]2 code; C1 = W1 = RC1⊥ and C1 is a [ n2 , n − 1, n − 1]2 code, RC1 is a

[ n2 , n2 − n, 3]2 code.

2. For n ≡ 1 (mod 4), C1 = W1 = RC1⊥ and C1 is a [ n2 , n − 1, n − 1]2 code, RC1 is a [ n2 , n2 −

n, 3]2 code; C0 = E(W1 )⊥ is LCD.

Since the paper [11] concerns the relationship of the codes from the Γ(n, k, r) and the W codes (see
Equations (4) and (5)) as defined above, we mention a couple of results from [11] concerning these
codes, since they occur frequently amongst the RLCD and CLCD codes for this class of graphs.

Result 4 For all n, dim(W1 ) = n if p 6 | k and dim(W1 ) = n − 1 if p|k.

For p = 2, k ≥ 2, n ≥ 7, the non-zero words of W1 have weight nr for 1 ≤ r ≤ bn/2c where
b(k−1)/2c   
X r n−r
nr =
2i + 1 k − (2i + 1)
i=0

n n



and also of weight k − nr if k is odd. There are r of weight nr .
For k = 3 the minimum weight is n−1


2 .

Result 5 For n ≥ 2k + 1, any k ≥ 2, p prime, Wk−1 has minimum weight n − k + 1. For

n > 2k + 1, the minimum words are the scalar multiples of the wΛ for Λ ⊂ Ω with |Λ| = k − 1.
Further, dim(Wk−1 ) ≥ n−1


k−1 for all p, with equality when p = 2.
4 UNIFORM SUBSET GRAPHS 8

The fact that for uniform subset graphs where C = Ci and C ⊥ = RCi or Ci (or vice versa) and
thus LCD, it is immediate how to split any v ∈ FVp into its orthogonal parts, should be a help in
correcting errors.
Example 1 Consider Γ(n, 3, 1) for n ≡ 0 (mod 4) > 7. Then from Result

3, for p = 2, let C⊥ =
⊥ ⊥ n n−1


RC1
= W
1 , and then C = C1 = W1 . From Result 4, C is a [ 3 , n, 2 ]2 LCD code, and C is
a [ n3 , n3 − n, 4]2 code.
r is the received vector. If S =PSupp(r) then r = v S = x∈S s1x + x∈S rx1 =
P P
To decode, supposeP
1 1 ⊥
u1 + u2 where
P u1 1= x∈S sx = rΠC ∈ C, u2 = x∈S rx = rΠC ⊥ ∈ C . We can also write
T
u2 = v = x∈T rx where T = Supp(u2 ). Thus |T | = wt(u2 ).
Now we wish to find first m = min{wt(w
− u2 ) | w ∈ C}, and then {w|w ∈ C|wt(w − u2 ) = m}.
If the number of errors is less than 12 n−1
2 then there will be a unique member of this set. Thus we
look for a coset leader c of C − u2 = W1 − u2 , and decode as u1 + (c + u2 ) = r + c. Since C = W1
is a small code, it seems that this is quite speedily done by computer, although a real formula or
algorithm for this would be desirable. 

Computational findings
Using Magma [7, 3] some further RLCD and CLCD codes were found:

• k = 4, p = 2:
n = 9, C1⊥ = RC1 = C1 , C3⊥ = RC3 = C3 ; n = 11, C0⊥ = C0 , C3⊥ = RC3 = C3 ; n = 13,
C1⊥ = RC1 , C3⊥ = RC3 ; n = 15, C0⊥ = RC0 , C3⊥ = RC3 ; n = 17, C1⊥ = RC1 = C1 ,
C3⊥ = RC3 = C3 ;

• k = 4, p = 3: n = 15, C1⊥ = RC1 = C1 ;

• k = 5, p = 2
n = 11, C4⊥ = RC4 = C4 ; n = 12, C3⊥ = RC3 = C3 ; n = 13, C2⊥ = RC2 , C4⊥ = RC4 ; n = 15,
C4⊥ = RC4 .
All these computational findings are justified below in the lemmas and propositions to follow.
Uniform subset graphs of particular interest and that have been especially studied are those
with r = 0 and r = k − 1: Γ(n, k, 0) is the Kneser graph KGn,k , with eigenvalues for j = 0 to k:
 
j n−k−j
λj = (−1) (6)
k−j

with multiplicity mj = nj − j−1 n

for j > 0 and 1 for j = 0. Here KG2k+1,k = Ok , is the odd
graph of valency k + 1.
Further, the graph Γ(n, k, k − 1) is the Johnson graph J(n, k),with eigenvalues for j = 0 to k:

θj = k(n − k) − j(n + 1 − j) (7)

with multiplicity mj as above.

For the general case Γ(n, k, r), the eigenvalues are found from the Eberlein polynomials in [25,
Theorem 5.1] (see also [9, 1, 5, 8] and [5, Theorem 4.6]) for j = 0 to k:
M in{j,k−r}    
X
i j k−j n−k−j
εj = (−1) (8)
i k−r−i k−r−i
i=M ax{0,j−r}
4 UNIFORM SUBSET GRAPHS 9

with multiplicity mj as given above.

k

n−k
k−r k


Note that in all cases ε0 = k−r k−r , the valency of Γ(n, k, r), and εk = (−1) k−r .
For r = 1, i.e. Γ(n, k, 1), this can be written more simply, for j = 0 to k:
   
j−1 n−k−j j n−k−j
εj = (−1) j + (−1) (k − j) . (9)
k−j k−j−1
Since the eigenvalues of all the uniform subset graphs are integral we can use Proposition 2 to
determine for what p and for what values of n, k they have RLCD or CLCD codes, and also to
determine the dimnsion of the code in the RLCD case, using Lemma 3. We need to determine
when the inner product (sx , ry ) or (cx , ry ) is zero for all choices of x, y. This value depends on
|x ∩ y|.
Note: For Γ = Γ(n, k, r), Γ is not a uniform subset graph unless k = 2. The eigenvalues of
RA = J − A are also integral and given by |V | − ν, and −θ, where ν is the valency of Γ and the
θ are the eigenvalues of A with eigenvectors w orthogonal to , as discussed earlier for A. If we
denote the rows of RA by dx for x ∈ V , then dx =  − rx = v x + cx .

Proposition 3 Let Γ = Γ(n, k, r) = (V, E) of valency ν = kr n−k

k−r , where 0 ≤ r ≤ k − 1, p
any prime, and A an adjacency matrix for Γ. Let C = Cp (Γ), RC = Cp (RΓ), C = Cp (Γ), and
ν = |V | − 1 − ν, the valency of Γ.
For j = 0, . . . , k, let ij = (rx , ry ) for |x ∩ y| = j. Then (sx , ry ) = ij for j 6= r, (sx , ry ) = 1 + ir
for |x ∩ y| = r, ik = ν, and
j 
k−j 2 j
   
X n − (2k − j)
ij = .
r−i i k − (2r − i)
i=0

Further:
1. C ⊆ RC ⊥ if and only if ij ≡ 0 (mod p) for 0 ≤ j ≤ k, j 6= r, and i∗r = ir + 1 ≡ 0 (mod p),
in which case C = RC ⊥ .
⊥
2. C ⊆ C if and only if for 0 ≤ j ≤ k, j =
6 r, `j = ik − ij ≡ 0 (mod p), and `r = ik − ir − 1 =
∗ ⊥
ik − ir ≡ 0 (mod p). Further, C = C unless, possibly, p|ν and p|(|V | − 1).
⊥ ⊥
3. C = RC if and only if tj = ν − `j ≡ 0 (mod p) for 0 ≤ j ≤ k. Then C ⊆ C , and if p|ν
⊥
then C = RC ⊥ , or if p 6 |ν, then C = C = RC.

Proof: (1) The value for ij is a direct count of vertices adjacent to both x and y, and then the
requirement that the inner product must be 0 for any pair of rows of A and A+I, so that C ⊆ RC ⊥ .
That C = RC ⊥ follows from Proposition 2 and the above statement regarding the eigenvalues of
Γ.
(2) Since cx =  − v x − rx , for any y ∈ V , (cx , ry ) = ik − (v x , ry ) − (rx , ry ). Thus (cx , rx ) = `k = 0,
(cx , ry ) = ik − ij if j 6= r, and (cx , ry ) = ik − ir − 1. Similarly, Proposition 2 can be used for the
equality.
(3) dx =  − rx , so (dx , cy ) = ( − rx ,  − v y − ry ) = ν + (rx , v y ) + (rx , ry ) − ik . Thus (dx , cy ) =
ν + (ij − ik ) = ν − `j = tj for j 6= r, and (dx , cy ) = ν + (i∗r − ik ) = ν − `r = tr for |x ∩ y| = r. If
⊥ ⊥
all these are zero modulo p then we will have C = RC and C ⊆ C . If p|ν then C = RC ⊥ , and
⊥
if p 6 |ν then C = C . 
4 UNIFORM SUBSET GRAPHS 10

Example 2 Special cases:

• For Γ = J(n, k) = Γ(n, k, k − 1),

ij = 0 for 0 ≤ j ≤ k − 3, ik−2 = 4, i∗k−1 = n − 1, ik = k(n − k);
`j = k(n − k) for 0 ≤ j ≤ k − 3, `k−2 = k(n − k) − 4, `k−1 = k(n − k) − (n − 1), `k = 0;

• For Γ = KGn,k = Γ(n, k, 0), for 0 ≤ j ≤ k,

ij = n−(2k−j) , i0 = 1 + n−2k

∗

k
k ;
`0 = k − 1 − k , `j = k − n−(2k−j)
n−k n−2k n−k




k for 1 ≤ j ≤ k.

• For Γ(n, k, 1), for 0 ≤ j ≤ k,

   
n − (2k − j) 2 n − (2k − j)
ij = j + (k − j) ,
k−1 k−2
n−(2k−1)
n−(2k−1)

and i∗1 = 1 + k−1 + (k − 1)2 k−2 .

Corollary 1 1. For C = Cp (J(n, k)), C is RLCD if and only if p =
2 and n is odd. C is

CLCD (and C = RC), only for p = 2 and n odd, unless, possibly, nk is odd.

2. If C = Cp (KG2k+1,k ) = Cp (Ok ), then C is neither RLCD nor CLCD for any p or k.

3. if C = Cp (Γ(n, k, r)) and C ⊆ RC ⊥ then C ⊆ (C)⊥ and RC = C ⊥ . Conversely, C ⊆ (C)⊥ 6⇒

C = RC ⊥ .

Proof: (1): Clearly since ik−2 = 4, we must have p = 2, and then for ik−1 = n − 1 to be even we
need n odd. Then ik = k(n − k) is
even for any k. Similarly for CLCD.
(2) For the odd graph i∗0 = 1 + k1 = 1, so this is never zero. Similarly for CLCD.
(3)The first statement is clear, and as a counterexample to illustrate the second, take Γ = Γ(13, 3, 1),
p = 2. Here C1 = C = (C)⊥ 6= RC ⊥ 
Note: For any regular graph Γ of valency ν, with the same notation for rx , sx , cx , C, RC, C as above,
since (cx , ry ) = ν − (sx , ry ), it follows that C ⊆ RC ⊥ ⇒ C ⊆ (C)⊥ , but the converse implication
only holds if p|ν.
For J(n, k) the following result, giving C = C2 (J(n, k)) in terms of the code Wk , is from [11, 16]:

Result 6 For k ≥ 3, n ≥ 2k + 1, p = 2, Γ = J(n, k), let C = C2 (Γ), RC = C2 (RΓ). Then

⊥ , RC = W
1. for n, k odd, C = Wk−1 k−1 , Hull(C) = {0};

⊥ , Hull(C) = {0};
2. for n odd, k even, C = Wk−1 , RC = Wk−1

3. for n, k even, C ⊆ Hull(Wk−1 ), RC = FV2 ;

4. for n even, k odd, C = FV2 , RC ⊆ Hull(Wk−1 ).

From Example 2, putting the ij ≡ 0 (mod p) (respectively `j ≡ 0 (mod p)) for j 6= r, and
i∗r ≡ 0 (mod p) (respectively `r ≡ 0 (mod p)), we can deduce the following:

• for C = Cp (Γ) for Γ = KGn,k = Γ(n, k, 0):

5 STRONGLY REGULAR GRAPHS 11

– For k = 2, C is RLCD precisely when p = 2 and n ≡ 3 (mod 4). (Since Γ(n, 2, 0) is

strongly regular, this also follows from Corollary 2 (1).) C is CLCD when p = 2 and
n ≡ 1 (mod 4).
– For k = 3, C is RLCD precisely when p = 2 and n ≡ 1 (mod 4), and C is also CLCD; C
is RLCD for p = 3 and n ≡ 5 (mod 9), and C is CLCD for p = 3 and n ≡ 2, 8 (mod 9);
C is RLCD for p ≥ 5 only for n ≡ 5 (mod p), and likewise C is CLCD only in this case.
– For k = 4, C is RLCD precisely when p = 2 and n ≡ 7 (mod 8); C is CLCD precisely
when p = 2 and n ≡ 3 (mod 8).

• for C = Cp (Γ) for Γ = Γ(n, k, 1):

– For k = 3, C is RLCD precisely when p = 2 and n ≡ 0 (mod 4); C is CLCD precisely

when p = 2 and n ≡ 0, 1 (mod 4).
– For k = 4, for p = 2 C is RLCD precisely when n ≡ 1 (mod 4) and C is CLCD for
p = 2 when n ≡ 1 (mod 8); for p = 3 C is RLCD precisely when n ≡ 6 (mod 9), and
likewise C is CLCD; for p ≥ 5, C is neither RLCD nor CLCD.

Using the formula for the eigenvalues as given in Equation (8), we can get the precise dimension
in the cases above when the code is RLCD, from Lemma 3.

Example 3 1. From the above observations we have

n−3

C2 (Γ(n,
n−4

1)) is RLCD if n ≡ 0 (mod 4).
3,
From Equation (9) the eigenvalues are ε0 = 3 2 , ε1 = 2 −2(n−4), ε2 = −2n+11, ε3 = 3.
Only ε2 and ε3 are non-zero modulo 2, so dim(C2 (Γ(n, 3, 1)) = m2 + m3 = n3 − n. This

agrees with [21] where the dimensions of the binary codes were found by other methods.

2. For Γ(n, 4, 1), the eigenvalues are ε0 = 4 n−4 n−5

− 3 n−5




3 , ε1 = 3 2 , ε2 = −(n − 6)(n − 9),
ε3 = 3n − 22, ε4 = −4. Thus for p = 2 and n ≡ 1 (mod 4), from the observations
n
above,
C2 (Γ(n, 4, 1)) is RLCD, and since only ε3 6≡ 0 (mod 2), C2 (Γ(n, 4, 1)) is a [ 4 , 3 − n2 , d]2
n

code, where d ≤ 4 n−4

3 .

3. For C3 (Γ(n, 4, 1)) and n ≡ 6 (mod 9), from the expressions for

εi in (2) above, only ε3
and
ε4 are non-zero modulo 3, so C3 (Γ(n, 4, 1)) is a [ n4 , n4 − n2 , d]3 code, where d ≤ 4 n−4



3 .

5 Strongly regular graphs

A graph Γ = (V, E), neither complete nor null, is strongly regular graph of type (n, k, λ, µ) if it
is regular on n = |V | vertices, has valency k, and is such that any two adjacent vertices are together
adjacent to λ vertices and any two non-adjacent vertices are together adjacent to µ vertices. The
complement Γ of the graph Γ is also strongly regular of type (n, n − k − 1, n − 2k + µ − 2, n − 2k + λ).
Let Γ be a strongly regular graph with parameters (n, k, λ, µ) and A an adjacency matrix for Γ.
From [6, Chapter 2], the eigenvalues for A are λi for 0 ≤ i ≤ 2 with multiplicities mi respectively,
those for RΓ are λ∗i = λi + 1 with multiplicities mi for 0 ≤ i ≤ 2, and those for Γ are λ0 = n − 1 − k,
λi = −λi − 1 for i = 1, 2, where where

• λ0 = k, λ∗0 = k + 1, λ0 = n − 1 − k, m0 = 1;

• λ1 = 12 (λ−µ+ (λ − µ)2 + 4(k − µ)), λ∗1 = 12 (λ−µ+2+ (λ − µ)2 + 4(k − µ)), λ1 = −λ2 −1,
p p

m1 = 12 (n − 1 + √(n−1)(µ−λ)−2k
2
);
(µ−λ) +4(k−µ)
5 STRONGLY REGULAR GRAPHS 12

• λ2 = 12 (λ−µ− (λ − µ)2 + 4(k − µ)), λ∗2 = 12 (λ−µ+2− (λ − µ)2 + 4(k − µ)), λ2 = −λ1 −1,
p p

m2 = 12 (n − 1 − √(n−1)(µ−λ)−2k
2
).
(µ−λ) +4(k−µ)

Note that λ1 + λ2 = λ − µ.
Strongly regular graphs are of two types: Type I where (n − 1)(µ − λ) = 2k, in which case
it follows that λ = µ − 1, k = 2µ, n = 4µ + 1, and n is the sum of two integer squares (see [6,
(2.18)Theorem]). Or, of Type II, where (µ − λ)2 + 4(k − µ) is the square of an integer, and in this
case it follows that the eigenvalues are all integral.

Examples 1 1.
Triangular graph T (m) = Γ(n, 2, 1):

(n, k, λ, µ) = ( m
2 , 2(m − 2), m − 2, 4) so λ − µ = m − 6, k − µ = 2m − 8.

• λ0 = 2m − 4, λ∗0 = 2m − 3, λ0 = m−2


2 , m0 = 1;

• λ1 = m − 4, λ∗1 = m − 3, λ1 = −3, m1 = m − 1;

• λ2 = −2, λ∗2 = −1, λ2 = −m + 4, m2 = 12 m(m − 3);

2. Paley graph P (q) = P (q), where q ≡ 1 (mod 4):

(n, k, λ, µ) = (q, 12 (q − 1), 41 (q − 5), 14 (q − 1)) so λ − µ = −1, k − µ = 14 (q − 1).

• λ0 = 12 (q − 1), λ∗0 = 12 (q + 1), m0 = 1;

√ √
• λ1 = 21 (−1 + q), λ∗1 = 12 (1 + q), m1 = 12 (q − 1);
√ √
• λ2 = 12 (−1 − q), λ∗2 = 12 (1 − q), m2 = 12 (q − 1).

Note: The eigenvalues of P (q) are integral if q is a square prime power.

For x ∈ V , as before, let rx denote the row for x in A, sx the row in A + I, cx the row for x in
A = J − I − A.
With this notation:

Proposition 4 Let Γ be a strongly regular graph with parameters (n, k, λ, µ) and A an adjacency
matrix for Γ. Let p be any prime, C = Cp (A), RC = Cp (A + I), C = Cp (A). Then,

1. C ⊆ RC ⊥ if and only if k ≡ 0 (mod p), λ ≡ −1 (mod p), and µ ≡ 0 (mod p). If this is the
case then C = RC ⊥ and if the eigenvalues of A are integral, then dim(C) = m1 or m2 , i.e.
1
2 (n − 1 ±
√(n−1)(µ−λ)−2k
2
).
(µ−λ) −4(k−µ)

⊥
2. C ⊆ C if and only if k − 1 − λ ≡ 0 (mod p) and k − µ ≡ 0 (mod p). Further, if all the
⊥
eigenvalues of A are integral, C = C , unless, possibly, k ≡ 0 (mod p) and n−1 ≡ 0 (mod p).
⊥
In any case, dim C ≤ dim(C ) ≤ dim(C) + 1.

Proof: (1): (rx , sx ) = k; if x ∼ y then (rx , sy ) = 1 + λ; if x 6∼ y then (rx , sy ) = µ. Thus C ⊆ RC ⊥ if

and only if k ≡ 0 (mod p), λ ≡ −1 (mod p), and µ ≡ 0 (mod p). If this is the case then C = RC ⊥ ,
by Proposition 2.
We have λ0 = k ≡ 0 (mod p), λ ≡ −1 (mod p), and µ ≡ 0 (mod p), so λ − µ ≡ −1 (mod p),
and λ1 + λ2 ≡ −1 (mod p). If both λ1 and λ2 are non-zero modulo p, then dim(C) = n − 1, and
dim(RC) ≤ 1, which is impossible. So one of λ1 , λ2 is 0 modulo p, and suppose λi ≡ 0 (mod p).
5 STRONGLY REGULAR GRAPHS 13

It follows that dim(C) ≥ n − (1 + mi ) = mj . Since λ∗i ≡ 1 (mod p) and λ∗0 ≡ 1 (mod p), we must
have λ∗j ≡ 0 (mod p), since RC 6= Fnp , and thus dim(RC) = 1 + mi ≤ dim(C ⊥ ) ≤ n − mj = 1 + mi ,
proving equality.
(2): (rx , cy ) = (rx , ) − (rx , v y ) − (rx , ry ), so (rx , rx ) = 0; if x ∼ y then (rx , cy ) = k − 1 − λ; if x 6∼ y,
⊥
then (rx , sy ) = k − µ. Thus C ⊆ C if and only if k − 1 − λ ≡ 0 (mod p) and k − µ ≡ 0 (mod p).
However, if all the eigenvalues of A are integral, in the case where λ0 = k ≡ 0 (mod p) and λ0 =
n − k − 1 ≡ 0 (mod p), we cannot use the dimension argument as in the RLCD case, so we might
⊥ ⊥
have C ⊂ C , in which case, following Proposition 2, dim(C ) = dim(C) + 1. 
⊥
Note: 1: Γ = T (m), p = 2, and m ≡ 3 (mod 4) has m


2 ≡ 1 (mod 4), and C ⊂ C , so the excluded
case mentioned in (2) above does occur.
2: See [4, 19] for the p-ranks of strongly regular graph when the eigenvalues are not necessarily
⊥
integral, in which case we only have C ⊆ C , so other arguments must be used to obtain equality.

1. If Γ = T (m) = Γ(m, 2, 1), the triangular graph with parameters ( m

Corollary 2 2 , 2(m −
2), m − 2, 4), then if m is odd and p = 2, C = C2 (Γ) is RLCD, and dim(C) = m − 1. Further,
T (m) is CLCD for p = 2 and m ≡ 1 (mod 4).
The complement T (m) = Γ(m, 2, 0), is a ( m

m−2
m−4
m−3

2 , 2 , 2 , 2 ) strongly regular graph.
Here C = Cp (T (m)) is RLDC only for p = 2 and m ≡ 3 (mod 4).

2. If Γ = L2 (m), the square lattice graph, the parameters are (m2 , 2(m − 1), m − 2, 2). For p = 2
and m odd C = C2 (Γ) is RLCD with dim(C) = m1 = 2m − 2.
Γ is (m2 , (m − 1)2 , (m − 2)2 , (m − 1)(m − 2)) and is RLCD if p = 2 and m is odd. Then
dim(C) = m1 = (m − 1)2 .

3. If Γ = P (q) = P (q), the Paley graph with parameters (q, 12 (q − 1), 14 (q − 5), 14 (q − 1)), where
q ≡ 1 (mod 4), then for any prime p, Cp (Γ) is RLCD of dimension 21 (q − 1) if p = 2 and
q ≡ 1 (mod 8) or p is odd and q ≡ 1 (mod p).

4. Γ is the graph #12 of [4, p. 342] with parameters (81, 20, 1, 6) is RLCD if p = 2, and
dim(C) = 20.

Proof: (1): Referring to Proposition 4 for T (m), since µ = 4 this can only be 0 modulo p if p = 2.
Then we need m to be odd for λ + 1 ≡ 0 (mod 2). Since λ1 ≡ 0 (mod 2), from the proposition
dim(C) = m1 = m − 1. For T (m), the parameters follow from [6, Chapter 2]. The conclusions also
follow from Result 3.
(2),(3),(4): Similarly clear from the parameters. 
Note: 1. Since the Petersen graph is T (5), i.e. also the odd graph Γ(5, 2, 0) = O(2), its p-ary code
is not RLCD for any p.
2. If Γ = Sp2m (q), the symplectic graph with point set the projective points of P G2m−1 (q), then Γ
is strongly regular with parameters

q 2m − 1 q 2m−1 − 1 q 2m−2 − 1 q 2m−2 − 1

n= ,k = − 1, λ = − 2, µ =
q−1 q−1 q−1 q−1

with spectrum k 1 , (q m−1 −1)f , (−q m−1 −1)g , where f = 21 (µ−1+q m ) and g = 21 (µ−1−q m ): see, for
example, [4]. Thus the eigenvalues are all integral and both parts of Proposition 4 can be applied.
6 OTHER LCD CODES FROM GRAPHS 14

Also, Γ has λ = µ. Since µ = λ + 2, we cannot have µ ≡ 0 (mod p) and λ ≡ −1 (mod p), so Γ

is never RLCD, and neither is Γ. Similarly, it cannot be CLCD for any of the parameters, since
k − 1 − λ ≡ 0 (mod p) implies that k − µ + 1 ≡ 0 (mod p), so we cannot have k − µ ≡ 0 (mod p),
i.e. the conditions of Proposition 4 are not satisfied in any case.

5.1 Generalized Paley graphs

It was found computationally in [27], using Magma, that some of the generalized Paley graphs,
GP (q, k) are strongly regular with q odd, and the parameters tell us that those found are RLCD.
A generalized Paley graph GP (q, k) (see also [30]) is defined as follows: q is a prime power,
k|(q − 1), k ≥ 2 and either q or q−1 × q−1
k is even. S is the subgroup of Fq of order s = k . Then
GP (q, k) = (V, E) where V = Fq and, for x, y ∈ V , x ∼ y if x − y ∈ S. The conditions imply that
GP (q, k) is an undirected graph, and for q odd, s = |S| = q−1k even. If k = 2 then q is odd, and
GP (q, 2) = P (q), the Paley graph.
The computational results (excluding k = 2, so that the graphs are of Type II) from [27] for
GP (q, k) to be strongly regular are given in Table 1, using also our Proposition 4 to show where
the codes are RLCD, since all the eigenvalues are integral. In the table the columns are headed
by GP (q, k), the parameters of the strongly regular graph, the code parameters, and the nature of
the minimum words, if found computationally, respectively. None of these are CLCD.

(q, k) p type Cp (Γ) min wds C RCp (Γ)

(25, 3) 2 (25, 8, 3, 2) [25, 8, 8]2 rows of A [25, 17, 4]2
(49, 4) 2 (49, 12, 5, 2) [49, 12, 12]2 rows of A [49, 37, 4]2
(81, 4) 2 (81, 201, 1, 6) [81, 20, 20]2 rows of A [81, 61, 6]2
(81, 5) 2 (81, 16, 7, 2) [81, 16, 16]2 rows of A [81, 65, 4]2
(121, 3) 2 (121, 40, 15, 12) [121, 40, 20]2 [121, 81, 8]2
(121, 4) 2 (121, 30, 11, 6) [121, 90, 6]2 [121, 31, 11]2
(121, 4) 3 (121, 30, 11, 6) [121, 30, 20]3 [121, 91, 6]3
(121, 6) 2 (121, 20, 9, 2) [121, 20, 20]2 rows of A [121, 101, 4]2
(35 , 11) 2 (243, 22, 1, 2) [243, 110, d]2 d ≤ 22 [243, 133, δ ≤ 23]2
(36 , 4) 2 (729, 182, 55, 42) [729, 546, d]2 d ≤ 182 [729, 183, δ ≤ 183]2
(36 , 7) 2 (729, 104, 31, 12) [729, 104, d]2 d ≤ 104 [729, 625, δ ≤ 105]2
(36 , 14) 2 (729, 52, 25, 2) [729, 52, d]2 d ≤ 52 [729, 677, δ ≤ 53]2

Table 1: Strongly regular generalized Paley graphs

It is shown in [30, Corollary 1] that the number of common neighbours to two adjacent vertices
in GP (q, k) is |N (1) ∩ S|, so λ is a constant for all these graphs. In [27] it is shown that λ − µ is
odd if GP (q, k) is strongly regular, and k > 2.

6 Other LCD codes from graphs

Some of the papers mentioned here concerning codes from adjacency matrices from graphs have
cases where the hull is zero, but the code is not RLCD nor CLCD. However, in some of these
papers the proofs that the hull was zero did involve expressing a weight-1 vector as a sum of vectors
in C and C ⊥ , so this would facilitate the expression of w ∈ FVp as a sum of vectors in C and C ⊥ .
7 CONCLUSION 15

For example, in [21], where binary codes from the graphs Γ(n, 3, r) are studied, for C =
C2 (Γ(n, 3, 2)) and n odd, in Proposition 1 it is shown that C ⊥ = W2 , and that Hull(C) = {0}, by
showing that for x = {a, b, c},
v x = rx2 + wa,b + wa,c + wb,c ,
where rxi denotes the row corresponding to x in an adjacency matrix for Γ(n, 3, i). (Note that there
are typographical errors in that paper: on page 175, line -18, v {a,b,x} should read v {a,b,c} , four times,
at the end of the display.)
In [23], where ternary codes from the graphs Γ(n, 3, r) are studied, in Proposition 18, looking
at C = C3 (Γ(n, 3, 0)) when n ≡ 1 (mod 3), the set of equations at the end of the proof give, for
x = {a, b, c},
v x =  − rx0 + rx1 + wa + wb + wc ,
where  ∈ C or C ⊥ , wi ∈ C ⊥ , and rx1 ∈ C.
P|V |
However, the expression for w = i=1 αi v xi = (α1 , . . . , α|V | ), where V = [x1 , . . . , x|V | ], as the
sum of a vector in C and C ⊥ is not as neatly expressed as in the case of RLCD and CLCD. Thus,
P|V |
for this last expression, we have, for w = i=1 αi v xi ,

|V | |V | |V | |V |
X X X X X
w= αi  − αi rx0i + αi rx1i + αi wa .
i=1 i=1 i=1 i=1 a∈xi

Further, in [10], a similar formula for v x is established in Lemma 3.8 of that paper for the binary
code C for the odd graph Ok = Γ(2k + 1, k, 0), where it is shown that Hull(C) = {0} for all k. The
formula for v x is
k−2 X
X X X X
vx = v A∪Y ∪{a} + ry + k,
i=1 A⊂x Y ⊂Ω\x a6∈A∪Y y⊂Ω\x
|A|=i |Y |=k−1−i

where  ∈ C for k even, and  ∈ C ⊥ for k odd. Here the first term on the right-hand side is in C ⊥ .

7 Conclusion
Many other classes of graphs are likely to have codes that are RLCD or CLCD: we found, by
computation, some from the Hamming graphs H k (n, m) (see [13, 12, 24] for the notation) where
H 1 (n, 2) = H(n, 2) = Qn , the n-cube. For example, for n = 6, 8, 10, Γ = H 1 (n, 2), C2 (Γ) = C2 (Γ)⊥ ;
for n = 6, 9, Γ = H 2 (n, 2), C3 (Γ) = C3 (RΓ)⊥ ; for k = 1, 2, Γ = H k (6, 3), C2 (Γ) = C2 (RΓ)⊥ . Also,
in [26] codes acted on by subgroups of the McLaughlin group are found to have this property.
The codes from the Hamming graphs H k (n, m) are examined with respect to these properties
in [15] and many classes of these graphs are found to satisfy them.

References
[1] José Araujo and Tim Bratten, On the spectrum of the Johnson graphs J(n, k, r), Proceedings
of the XXIIrd “Dr. Antonio A. R. Monteiro” Congress, 2016, Univ. Nac. Sur Dep. Mat. Inst.
Mat., Baha Blanca, 2015, pp. 57–62.
REFERENCES 16

[2] E. F. Assmus, Jr and J. D. Key, Designs and their codes, Cambridge: Cambridge University
Press, 1992, Cambridge Tracts in Mathematics, Vol. 103 (Second printing with corrections,
1993).

[3] W. Bosma, J. Cannon, and C. Playoust, The Magma algebra system I: The user language, J.
Symbolic Comput. 24, 3/4 (1997), 235–265.

[4] A. E. Brouwer and C. J. van Eijl, On the p-rank of the adjacency matrices of strongly regular
graphs, J. Algebraic Combin. 1 (1992), 329–346.

[5] A.E. Brouwer and W.H. Haemers, Association schemes, Handbook of Combinatorics (R.L.
Graham, M. Grötschel, and L. Lovász, eds.), Elsevier; MIT, Cambridge,MA, 1995, Chapter 15,
Vol. 1, pp. 749–771.

[6] P. J. Cameron and J. H. van Lint, Designs, graphs, codes and their links, Cambridge: Cam-
bridge University Press, 1991, London Mathematical Society Student Texts 22.

[7] J. Cannon, A. Steel, and G. White, Linear codes over finite fields, Handbook of Magma
Functions (J. Cannon and W. Bosma, eds.), Computational Algebra Group, Department of
Mathematics, University of Sydney, 2006, V2.13, http://magma.maths.usyd.edu.au/magma,
pp. 3951–4023.

[8] P. Delsarte, An algebraic approach to the association schemes of coding theory, Tech. report,
Philips Research Laboratorie, 1973, Philips Research Reports, Supplement No. 10.

[9] Philippe Delsarte and Vladimir I. Levenshtein, Association schemes and coding theory, IEEE
Trans. Inform. Theory 44 (1998), 2477–2504.

[10] W. Fish, R. Fray, and E. Mwambene, Binary codes and partial permutation decoding sets from
the odd graphs, Cent. Eur. J. Math. 12 (9) (2014), 1362 –1371.

[11] W. Fish, J. D. Key, and E. Mwambene, Codes from adjacency matrices of uniform subset
graphs, (Submitted).

[12] , Codes, designs and groups from the Hamming graphs, J. Combin. Inform. System Sci.
34 (2009), 169–182, No.1 – 4.

[13] , Graphs, designs and codes related to the n-cube, Discrete Math. 309 (2009), 3255–
3269.

[14] , Ternary codes from reflexive graphs on 3-sets, Appl. Algebra Engrg. Comm. Comput.
25 (2014), 363–382.

[15] W. Fish, J. D. Key, E. Mwambene, and B.G. Rodrigues, Hamming graphs and LCD codes, (In
preparation).

[16] Washiela Fish, Codes from uniform subset graphs and cycle products, Ph.D. thesis, University
of the Western Cape, 2007.

[17] Washiela Fish, Jennifer D. Key, and Eric Mwambene, Binary codes from reflexive graphs on
3-sets, Adv. Math. Commun. 9 (2015), 211–232.
 REFERENCES 17

[18] D. Ghinelli, J. D. Key, and T. P. McDonough, Hulls of codes from inci-

dence matrices of connected regular graphs, Des. Codes Cryptogr. 70 (2014), 35–54,
http://dx.doi.org/10.1007/s10623-012-9635-0.

[19] Willem H. Haemers, René Peeters, and Jeroen M. van Rijckevorsel, Binary codes of strongly
regular graphs, Des. Codes Cryptogr. 17 (1999), 187–209.

[20] W. Cary Huffman, Codes and groups, Handbook of Coding Theory (V. S. Pless and W. C.
Huffman, eds.), Amsterdam: Elsevier, 1998, Volume 2, Part 2, Chapter 17, pp. 1345–1440.

[21] J. D. Key, J. Moori, and B. G. Rodrigues, Binary codes from graphs on triples, Discrete Math.
282/1-3 (2004), 171–182.

[22] , Permutation decoding for binary codes from triangular graphs, European J. Combin.
25 (2004), 113–123.

[23] , Ternary codes from graphs on triples, Discrete Math. 309 (2009), 4663–4681.

[24] Jennifer D. Key, Washiela Fish, and Eric Mwambene, Codes from the incidence matrices and
line graphs of Hamming graphs H k (n, 2) for k ≥ 2, Adv. Math. Commun. 5 (2011), 373–394.

[25] M. Krebs and A. Shaheen, On the spectra of Johnson graphs, Electron. J. Linear Algebra 17
(2008), 154–167.

[26] D. Leemans and B. G. Rodrigues, Linear codes with complementary duals from some strongly
regular subgraphs of the McLaughlin graph, Math. Commun. 21 (2) (2016), 239–249.

[27] J. Limbupasiriporn and P. Limbupasiriporn, Codes from adjacency matrices of generalized

Paley graphs, In preparation.

[28] James L. Massey, Linear codes with complementary duals, Discrete Math. 106/107 (1992),
337–342.

[29] B. G. Rodrigues, Linear codes with complementary duals related to the complement of the
Higman-Sims graph, To appear: Bull. Iranian Math. Soc.

[30] P. Seneviratne and J. Limbupasiriporn, Permutation decoding of codes from generalized Paley
graphs, Appl. Algebra Eng. Commun. Comput. 24 (2013), 225–236.

View publication stats