. 1
( 3)



>>

Polynomial aspects of codes,
matroids and permutation groups

Peter J. Cameron
School of Mathematical Sciences
Queen Mary, University of London
Mile End Road
London E1 4NS
UK
p.j.cameron@qmul.ac.uk
Contents



1 Codes 1
1.1 Encoding and decoding . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Weights and weight enumerator . . . . . . . . . . . . . . . . . . 3
1.3 MacWilliams™ Theorem . . . . . . . . . . . . . . . . . . . . . . . 5

2 Codes over Z4 9
2.1 The Gray map . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Chains of binary codes . . . . . . . . . . . . . . . . . . . . . . . 11

3 Matroids 15
3.1 The basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Deletion and contraction . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Rank polynomial and Tutte polynomial . . . . . . . . . . . . . . 18
3.4 Perfect matroid designs . . . . . . . . . . . . . . . . . . . . . . . 21

4 Matroids and codes 27
4.1 The correspondence . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Greene™s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 Is there a Z4 version? . . . . . . . . . . . . . . . . . . . . . . . . 30

5 Permutation groups 33
5.1 Orbits and stabiliser . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2 The Orbit-Counting Lemma . . . . . . . . . . . . . . . . . . . . 36
5.3 Bases and strong generating sets . . . . . . . . . . . . . . . . . . 38
5.4 Primitivity and multiple transitivity . . . . . . . . . . . . . . . . . 40
5.5 Modern permutation group theory . . . . . . . . . . . . . . . . . 41

iii
iv Contents

6 Cycle index 47
6.1 De¬nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.2 The cycle index theorem . . . . . . . . . . . . . . . . . . . . . . 48
6.3 Some other counting results . . . . . . . . . . . . . . . . . . . . . 50
6.4 The Shift Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 51

7 Codes and permutation groups 55
7.1 In¬‚ating a matroid . . . . . . . . . . . . . . . . . . . . . . . . . . 55
7.2 The connection . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
7.3 More generally . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

8 IBIS groups 59
8.1 Matroids and IBIS families . . . . . . . . . . . . . . . . . . . . . 59
8.2 IBIS groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
8.3 Groups from codes . . . . . . . . . . . . . . . . . . . . . . . . . 63
8.4 Flat actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
8.5 Base-transitive groups . . . . . . . . . . . . . . . . . . . . . . . . 66
8.6 Some examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
8.7 The Tutte cycle index . . . . . . . . . . . . . . . . . . . . . . . . 68

Index 74
Preface



The three subjects of the title (codes, matroids, and permutation groups) have
many interconnections. In particular, in each case, there is a polynomial which
captures a lot of information about the structure: we have the weight enumerator
of a code, the Tutte polynomial (or rank polynomial) of a matroid, and the cycle
index of a permutation group.
With any code is associated a matroid in a natural way. A celebrated theorem
of Curtis Greene asserts that the weight enumerator of the code is a specialisation
of the Tutte polynomial of the matroid. It is less well known that with any code
is associated a permutation group, and the weight enumerator of the code is the
same (up to normalisation) as the cycle index of the permutation group.
There is a class of permutation groups, the so-called IBIS groups, which are
closely associated with matroids. More precisely, the IBIS groups are those for
which the irredundant bases (in the sense of computational group theory) are the
bases of a matroid. The permutation group associated with a code is an IBIS
group, and the matroid associated to the group differs only inessentially from the
matroid obtained directly from the code.
For some IBIS groups, the cycle index can be extracted from the Tutte poly-
nomial of the matroid but not vice versa; for others, the Tutte polynomial can be
obtained from the cycle index but not vice versa. This leads us to wonder whether
there is a more general polynomial for IBIS groups which “includes” both the
Tutte polynomial and the cycle index. Such a polynomial (the Tutte cycle index)
is given in the last chapter of these notes (an expanded version of [5]).
Whether or not there is a more general concept extending both matroids and
arbitrary permutation groups, and giving rise to a polynomial extending both the
Tutte polynomial and the cycle index, I do not know; I cannot even speculate what
such a concept might be.

v
vi Contents

The other theme of these notes is codes over Z4 , the integers mod 4, where
there have been some important recent developments. These codes ¬t naturally
into the framework of permutation groups, but not so easily into the matroid
framework. Carrie Rutherford has shown in her Ph.D. thesis [27] that we need
a pair of matroids to describe such a code, and even then the correspondence is
not exact; no natural matroid polynomial generalises the Lee weight enumerator.
Moreover, the permutation group is not an IBIS group.
The remainder of the notes is concerned with developing the basics of codes,
matroids and permutation groups, and their associated polynomials. For fur-
ther background, see MacWilliams and Sloane [22] for codes, Oxley [25] or
Welsh [30] for matroids, Cameron [4] or Dixon and Mortimer [13] for permu-
tation groups, and Harary and Palmer [18] for the use of the cycle index in com-
binatorial enumeration. Another book by Welsh [31] gives further insights on
polynomial aspects of codes and matroids. I refer to the Classi¬cation of Finite
Simple Groups, but detailed knowledge of this is not required; see Gorenstein [15]
for an overview.
These notes accompany a short course of lectures given at the Universitat Po-
litecnica de Catalunya in Barcelona in March 2002. I have included a few ex-
ercises at the end of each chapter. I am grateful to the course participants for
comments which have led to some improvements in the notes.

Peter J. Cameron
London, March 2002
CHAPTER 1




Codes

This chapter provides a very brief introduction to the theory of error-correcting
codes. The highlight is the theorem of MacWilliams, asserting that the weight
enumerator of a linear code determines that of its dual. The standard proof is
algebraic, but we will see a combinatorial proof in Chapter 4.


1.1 Encoding and decoding
We begin with an example.
Suppose that we are transmitting information, in the form of a long string of
binary digits, over a channel. There is a small probability, say 1 in 106 , that a bit
error occurs, that is, the received bit is not the same as the transmitted bit; errors in
different bits are independent. In the course of sending, say, 1000 bits, the chance
3
of an error is 1 ’ (1 ’ 10’6 )10 , or about 1 in 1000, which may be unacceptably
high.
Suppose that instead we adopt the following scheme. Break the data into
blocks of four. Now for each 4-tuple a = (a1 , a2 , a3 , a4 ), we encode it by multi-
plying by the matrix
« 
1000011
¬0 1 0 0 1 0 1·
G=¬ 0 0 1 0 1 1 0.
·

0001111

(Arithmetic is performed in the binary ¬eld GF(2) = Z2 .) The ¬rst four bits of
c = aG are just the bits of a; the purpose of the other three bits is error correction.

1
2 Chapter 1. Codes

We transmit the string c.
We calculate s = bH, where
Suppose that a 7-tuple b is received.
« 
0 01
¬0 1 0·
¬ ·
¬0 1 1·
¬ ·
H = ¬1 0 0·.
¬ ·
¬1 0 1·
¬ ·
1 1 0
1 11
If s = 0, we assume that b is the transmitted codeword. Otherwise, s is the base 2
representation of an integer i in the range 1, . . . , 7; we assume that there was a
single bit error in position i, that is, we complement the ith entry of b. Then we
read the ¬rst four bits of b and assume that these were the bits transmitted.
We will see shortly that our assumptions are correct provided that at most one
error occurs to the bits of b. So the probability that the assumptions are wrong
is 1 ’ (1 ’ 10’6 )7 ’ 7 — 10’6 (1 ’ 10’6 )6 , which is about 2.1 — 10’11 . Now we
have to send 250 blocks, so the error probability is about 1 in 190 000 000, much
smaller than before!
It remains to justify our claims. First, by listing all the 7-tuples of the form aG,
we ¬nd that each of them except 0 has at least three 1s. Moreover, since this set C
is just the row space of G, it is closed under subtraction; so any two elements of
C differ in at least three positions.This means that, if at most one error occurs, the
resulting vector b is either in C (if no error occurs) or can be uniquely expressed
in the form c + ei , where c ∈ C and ei is the vector with 1 in position i and zero
elsewhere. In the latter case, c was the sequence transmitted.
Now we can also check that cH = 0 for all c ∈ C. (For this, it is enough to
show that GH = 0, since vectors in C have the form aG.) Then
(c + ei )H = ei H = ith row of H,
and H has the property that its ith row is the base 2 representation of i. So our
claims about the correctness of the decoding procedure (assuming at most one
error) are justi¬ed.
The price we pay for the much improved error correction capability of this
scheme is slower transmission rate: instead of 1000 bits, we have to send 1750
bits through the channel. We say that the rate of the code is 4/7.
To summarise: we encode the information (in blocks of four bits) as elements
of the set C, and transmit these. The properties of C permit error correction. We
call the set C a code, and its elements codewords.
The code C is an example of a Hamming code. The decoding method we
described is called syndrome decoding.
1.2. Weights and weight enumerator 3

1.2 Weights and weight enumerator
Let F be a set called the alphabet and n a positive integer. A word of length n
over F is simply an n-tuple of elements of F; sometimes we write a1 a2 · · · an
instead of (a1 , a2 , . . . , an ). In the most important case here, F is a ¬eld; in this
chapter, this is always assumed to be the case. A code is just a set of words, that
is, a subset of F n . We always require a code to have at least two words, since
a code with one word would convey no information (since we would know for
certain what message was sent). The words in a code are called codewords.
The code C is linear over the ¬eld F if it is a subspace of F n . A linear code of
length n and dimension k is referred to as an [n, k] code.
From an algebraic point of view, a linear [n, k] code is a k-dimensional sub-
space of an n-dimensional vector space with a ¬xed basis. It is this basis which
makes coding theory richer than the elementary theory of a subspace of a vector
space.
Let C be a [n, k] code. We can describe C by a generator matrix G, a k — n
matrix G whose rows form a basis for C, so that

C = {aG : a ∈ F k }.

We can also describe C by a parity check matrix H, a (n ’ k) — n matrix such that
C is the null space of H , that is,

C = {c ∈ F n : cH = 0}.

(This is the transpose of the matrix H of the preceding section.) The generator
and parity check matrices for a given code are of course not unique.
The dual code C⊥ of C is the set

C⊥ = {x ∈ F n : x · c = 0 for all c ∈ C},

where · denotes the standard inner product on F n : that is,

a · b = a1 b1 + a2 b2 + · · · + an bn .

Proposition 1.1 A generator matrix for C is a parity check matrix for C⊥ , and
vice versa.

The Hamming distance d(a, b) between words a and b is the number of coor-
dinates where they differ:

d(a, b) = |{i : 1 ¤ i ¤ n, ai = bi }|.
4 Chapter 1. Codes

Let e be a positive integer. The code C is e-error-correcting if, for any word
v, there is at most one codeword c ∈ C for which d(v, c) ¤ e. Thus, if C is used
for transmitting information, and up to e errors occur during the transmission of a
codeword, then the correct codeword can be recovered uniquely.
The minimum distance of C is the smallest distance between two different
codewords. By the Triangle Inequality, if the minimum distance is at least 2e + 1,
then C is e-error-correcting: for, if d(v, c1 ) ¤ e and d(v, c2 ) ¤ e, then d(c1 , c2 ) ¤
2e. Conversely, if the minimum distance is 2e or smaller, it is easy to ¬nd a word
lying at distance e or smaller from two different codewords. So we have:

Proposition 1.2 A code is e-error-correcting if and only if its minimum distance
is at least 2e + 1.

The weight wt(c) is the number of non-zero coordinates of c, that is, wt(c) =
d(c, 0), where 0 is the all-zero word. The minimum weight of C is the smallest
weight of a non-zero codeword.

Proposition 1.3 If C is linear, then its minimum distance is equal to its minimum
weight.

Proof Since wt(c) = d(c, 0), every weight is a distance. Conversely, d(c1 , c2 ) =
wt(c1 ’ c2 ); and, since C is linear, c1 ’ c2 ∈ C; so every distance is a weight.

Thus, the minimum weight is one of the most signi¬cant parameters of a linear
code. Indeed, if an [n, k] code has minimum weight d, we sometimes describe it
as an [n, k, d] code.
If F is ¬nite, the weight enumerator WC (X,Y ) of the code C is the homoge-
neous polynomial
n
‘X = ‘ Ai X n’iY i ,
n’wt(c) wt(c)
WC (X,Y ) = Y
i=0
c∈C

where Ai is the number of words of weight i in C.
Two codes C,C of length n over F are monomial equivalent if C can be
obtained from C by permuting the coordinates and multiplying coordinates by
non-zero scalars. This is the natural equivalence relation on linear codes, and pre-
serves dimension, weight enumerator, and most signi¬cant properties (including
minimum weight).
What can be said about generator matrices of the same, or equivalent, codes?
Elementary row operations on a matrix do not change its row space, and so leave
the code unaltered. Column permutations, and multiplying columns by non-zero
scalars, replace the code by an equivalent code. (The third type of elementary
1.3. MacWilliams™ Theorem 5

column operation, adding a multiple of one column to another, does not preserve
the structure of the code.) Thus equivalence classes of codes correspond to equiv-
alence classes of matrices under these operations (i.e. arbitrary row operations,
column permutations and scalar multiplications).
A simple example of a code is the binary repetition code of length n, consisting
of the two words (0, 0, . . . , 0) and (1, 1, . . . , 1); its minimum weight is clearly n.
Its dual is the binary even-weight code consisting of all words of even weight; its
minimum weight is 2.
The Hamming code of the previous section is a [7, 4] binary linear code. If
a = 1100, then aG = 1100110, a word of weight 4. Repeating for all 4-tuples a,
we ¬nd that the code contains seven words of weight 3 and seven of weight 4, as
well as the all-0 and all-1 words (with weight 0 and 7 respectively). So the weight
enumerator is
X 7 + 7X 4Y 3 + 7X 3Y 4 +Y 7 ,
the minimum weight is 3, the minimum distance is also 3, and the code is 1-error-
correcting (which should come as no surprise given the decoding procedure for
it).
Further calculation shows that the dual code C⊥ consists of the zero word and
the seven words of weight 4 in C; its weight enumerator is X 7 + 7X 3Y 4 , and its
minimum weight is 4.
No brief account of codes would be complete without mention of the cele-
brated binary Golay code. This is a [24, 12, 8] code with weight enumerator

X 24 + 759X 16Y 8 + 2576X 12Y 12 + 759X 8Y 16 +Y 24 .

This code is self-dual, that is, it is equal to its dual. Its automorphism group is the
Mathieu group M24 .

1.3 MacWilliams™ Theorem
From the weight enumerator of a code C, we can calculate the weight enumer-
ator of the dual code C⊥ , using the theorem of MacWilliams:

Theorem 1.4 Let C be an [n, k] code over GF(q). Then the weight enumerators
WC and WC⊥ of C and its dual are related by

1
WC (X + (q ’ 1)Y, X ’Y ).
WC⊥ (X,Y ) =
|C|
6 Chapter 1. Codes

Proof We give here the classical proof, which is algebraic in nature. In Chapter 4,
we will see a different, combinatorial proof.
We let χ be any non-trivial character of the additive group of GF(q) (that is,
homomorphism from this group to the multiplicative group of complex numbers).
If q = p is prime, so that GF(q) = Z p , then we can take χ(k) = e2πik/p . It is easily
veri¬ed that
‘ χ(x) = 0.
x∈GF(q)

Now let f (v) = X n’wt(v)Y wt(v) for v ∈ GF(q)n (a term in the sum for the weight
enumerator), and
g(u) = ‘ χ(u · v) f (v)
v∈GF(q)n

for u ∈ GF(q)n . Then we have

‘ g(u) = ‘ f (v) ‘ χ(u · v).
v∈GF(q)n
u∈C u∈C

We evaluate this sum in two ways. First, note that the inner sum on the right
is equal to |C| if v ∈ C⊥ , since χ(0) = 1; and, for v ∈ C⊥ , χ(u · v) takes each value
/
in GF(q) equally often, so the sum is zero. So the whole expression is |C| times
the sum of the terms f (v) over v ∈ C⊥ , that is,

‘ g(v) = |C|WC⊥ (X,Y ).
v∈C

On the other hand, if we put

if x = 0,
0
δ(x) =
if x = 0,
1

for x ∈ GF(q), then, with u = (u1 , . . . , un ), we have
n
‘ ∏ X 1’δ(vi)Y δ(vi)χ(u1v1 + · · · + unvn)
g(u) =
v1 ,...,vn ∈GF(q) i=1
n
∏‘ 1’δ(v) δ(v)
χ(ui v).
= X Y
i=1 v∈GF(q)

Now the inner sum here is equal to X + (q ’ 1)Y if ui = 0, and to X ’Y if ui = 0.
So
g(u) = (X + (q ’ 1)Y )n’wt(u) (X ’Y )wt(u) ,
and ‘u∈C g(u) = WC ((X + (q ’ 1)Y, X ’Y ). So we are done.
1.3. MacWilliams™ Theorem 7

We saw that the weight enumerator of the Hamming code is X 7 + 7X 4Y 3 +
7X 3Y 4 +Y 7 . So the weight enumerator of the dual code is
1
((X +Y )7 +7(X +Y )4 (X ’Y )3 +7(X +Y )3 (X ’Y )4 +(X ’Y )7 = X 7 +7X 3Y 4 ,
16
as we showed earlier.


Exercises
1.1. Let H be the d — 2d ’ 1 matrix whose columns are the base 2 representa-
tions of the integers 1, . . . , 2d ’ 1. Show that the [2d ’ 1, 2d ’ d ’ 1] binary code
with parity check matrix H is 1-error-correcting, and devise a syndrome decoding
method for it.
1.2. You are given 12 coins, one of which is known to be either lighter or heavier
than all the others; you are also given a beam balance. Devise a scheme of three
weighings which will identify the odd coin and determine if it is light or heavy; the
coins weighed at each step should not depend on the results of previous weighings.
What is the connection between this problem and error-correcting codes over Z3 =
{0, +1, ’1}?
1.3. The direct sum C1 •C2 of two codes C1 and C2 is obtained by concatenating
each word of C1 with each word of C2 . Show that if Ci is a [ni , ki , di ] code for
i = 1, 2, then C1 • C2 is a [n1 + n2 , k1 + k2 , min{d1 , d2 }] code. Show also that
WC1 •C2 (X,Y ) = WC1 (X,Y )WC2 (X,Y ). Show also how to construct

(a) a [n1 + n2 , min{k1 , k2 }, d1 + d2 ] code;

(b) a [n1 n2 , k2 k2 , d1 d2 ] code.

Why is there no general construction of a [n1 + n2 , k1 + k2 , d1 + d2 ] code?
1.4. A code (not necessarily linear) is said to be systematic in a given set of k
coordinate positions if every k-tuple of symbols from the alphabet occurs in these
positions in exactly one codeword. (Such a code contains qk codewords, where k
is the size of the alphabet.)

(a) Prove that a linear code is systematic in some set of coordinate positions.

(b) Prove that a code of length n which is systematic in every set of k coordinate
positions has minimum distance d = n ’ k + 1.

(A code with the property of (b) is called a maximum distance separable code, or
MDS code.)
8 Chapter 1. Codes

1.5. Let A be the binary code spanned by the word 01101001 and all words
obtained by cyclic shifts of the ¬rst seven positions (¬xing the last position). Show
that A is a [8, 4, 4] code. (This is an extended Hamming code.)
Let X be obtained from A by reversing the ¬rst seven positions (¬xing the last
position). Show that A © X contains only the all-0 and all-1 words. Hence show
that
G = {(a + x, b + x, a + b + x) : a, b ∈ A, x ∈ X}
is a [24, 12, 8] code. (This is the (extended) Golay code.)
1.6. An octad in the Golay code is a set of eight coordinate positions supporting
a codeword of weight 8. For any codeword c ∈ G, let π(c) be the restriction of
c to the positions of an octad. Prove that {π(c) : c ∈ G} is the even-weight code
E8 of length 8. Now, for any subset X of E8 , let π← (X) be the restriction to the
complement of the octad of the set {c ∈ C : π(c) ∈ X}. Show that

(a) π← ({0}) is a [16, 5, 8] code;

(b) π← (E8 ) is a [16, 11, 4] code (each word occurring from two different code-
words differing at all positions of the octad);

(c) If X = {00000000, 11000000, 10100000, 01100000}, then π← (X) is a [16, 7, 6]
code;

(d) If X = {00000000, 11000000, 10100000, 10010000, 10001000, 10000100,
10000010, 10000001}, then π← (X) is a nonlinear code consisting of 256
words of length 16 with minimum distance 6.

1.7. Prove that the Golay code, and the each of the codes constructed in (a),
(b) and (d) of the preceding exercise, is of maximum possible cardinality for a
binary code of its length and minimum distance. (Hint: Look up the Hamming
and Plotkin bounds. Part (d) is more dif¬cult!)
CHAPTER 2




Codes over Z4

The largest binary linear code with length 16 and minimum weight 6 has dimen-
sion 7, and thus has 128 codewords. However, this is beaten by a non-linear code,
the Nordstrom“Robinson code, which has minimum distance 6 and has 256 code-
words. (Both of these codes were constructed in Exercise 1.3.)
This code C has an additional property: for any codeword c and integer i with
0 ¤ i ¤ n, the number of codewords c satisfying d(c, c ) = i depends only on i and
not on the chosen codeword c ∈ C. A code with this property is called distance-
invariant. Another way of stating this property is as follows: for all c ∈ C, the
weight enumerator of the code C ’ c (the code c translated by ’c) is the same.
Any linear code C is distance-invariant, but it is rare for a non-linear code to have
this property.
In the case of the Nordstrom“Robinson code, the weight enumerator is
X 16 + 112X 10Y 6 + 30X 8Y 8 + 112X 6Y 10 +Y 16 .
This has an even more remarkable property. If there were a linear code C with this
weight enumerator, then the MacWilliams theorem would show that WC⊥ = WC .
For this reason, the code is called formally self-dual.
It turns out that the Nordstrom“Robinson code is the ¬rst member of two in-
¬nite families of non-linear codes, the Kerdock codes and Preparata codes. The
nth codes Kn and Pn in each sequence have length 4n+1 and are distance-invariant,
and their weight enumerators are related by the transformation of MacWilliams™
Theorem. (They are said to be formal duals.)
For twenty years this observation de¬ed explanation, until a paper by Ham-
mons, Kumar, Calderbank, Sloane and Sol´ [19] presented the answer to the puz-
e
zle. We now describe this brie¬‚y.

9
10 Chapter 2. Codes over Z4

2.1 The Gray map
The solution involves codes over the alphabet Z4 , the integers mod 4. We re-
gard the four elements of Z4 as being arranged around a circle, and de¬ne the dis-
tance dL between two of them as the number of steps apart they are: for example,
dL (1, 3) = 2, but dL (0, 3) = 1. Now we replace the Hamming distance between
two words a = (a1 , . . . , an ) and b = (b1 , . . . , bn ) of Zn by the Lee distance, de¬ned
4
by
n
dL (a, b) = ‘ dL (ai , bi ).
i=1
Similarly the Lee weight of a is wtL (a) = dL (a, 0).
Now, if C is a Z4 -linear code, that is, an additive subgroup of Zn , then the Lee
4
weight enumerator of C is given by

‘ X 2n’wtL (c)Y wtL (c).
LWC (X,Y ) =
c∈C

(Note that the maximum possible Lee weight of a word of length n is 2n.)
It turns out that there is a version of MacWilliams™ Theorem connecting the
Lee weight enumerators of a Z4 -linear code C and its dual C⊥ (with respect to the
natural inner product).
The set Z4 , with the Lee metric dL , is isometric to the set Z2 with the Hamming
2
metric, under the Gray map γ, de¬ned by

γ(0) = 00, γ(1) = 01, γ(2) = 11 γ(3) = 10.

2 11
u u
 d  d
  d   d
u du1 u du01
3 10
   
d   d  
d   d  
du u
  d 
0 00

(More generally, a Gray map on the integers mod 2n is a bijection to Zn such
2
that the images of consecutive integers lie at Hamming distance 1. Gray maps are
used in analog-to-digital conversion.)
Now we extend the de¬nition of the Gray map to map from Zn to Z2n by
4 2

γ(a1 , . . . , an ) = (γ(a1 ), . . . , γ(an )).

It is easily seen that γ is an isometry from Zn (with the Lee metric) to Z2n (with
4 2
the Hamming metric).
2.2. Chains of binary codes 11

The Gray map is non-linear, so the image of a Z4 -linear code C is usually a
non-linear binary code. But the isometry property shows that γ(C) is necessarily
distance-invariant, and that its weight enumerator is equal to the Lee weight enu-
merator of C. Thus, taking a Z4 -linear code and its dual, and applying the Gray
map, we obtain a pair of formally self-dual non-linear binary codes.
Hammons et al. show that, if this procedure is applied to the Z4 analogue of
the extended Hamming codes and their duals, then the Preparata and Kerdock
codes are obtained. Thus, the mystery is explained. (There is a small historical
inaccuracy in this statement. They obtained, not the original Preparata codes, but
another family of codes with the same weight enumerators.)
There is a more general weight enumerator associated with a Z4 -linear code
C. This is the symmetrised weight enumerator of C, de¬ned as follows:

‘ X n0(c)Y n2(c)Z n13(c),
SWC (X,Y, Z) =
c∈C

where n0 (c) is the number of coordinates of C equal to zero; n2 (c) the number
of coordinates equal to 1; and n13 (c) the number of coordinates equal to 1 or 3.
Since these coordinates contribute respectively 0, 2, and 1 to the Lee weight, we
have
LWC (X,Y ) = SWC (X 2 ,Y 2 , XY ).



2.2 Chains of binary codes
Another approach to Z4 -linear codes is via a representation as pairs of Z2 -
linear codes. Let C be a Z4 -linear code. We construct binary codes C1 and C2 as
follows. C1 is obtained just by reading the words of C modulo 2; and C2 is obtained
by selecting the words of C in which all coordinates are even, and replacing the
entries 0 and 2 mod 4 by 0 and 1 mod 2.

Theorem 2.1 The pair (C1 ,C2 ) of binary codes associated with a Z4 -linear codes
C satis¬es

(a) C1 ⊆ C2 ;

(b) |C| = |C1 | · |C2 |;

(c) WC1 (X,Y ) = SWC (X, X,Y )/|C2 | and WC2 (X,Y ) = SWC (X,Y, 0).
12 Chapter 2. Codes over Z4

Proof (a) If v ∈ C, then doubling v gives a word with all coordinates even; the
corresponding word in C2 is obtained by reading v mod 2. So C1 ⊆ C2 .
(b) C1 is the image of C under the natural homomorphism from Zn to Zn , and
4 2
C2 is naturally bijective with the kernel of this map; so |C| = |C1 | · |C2 |.
The proof of (c) is an exercise.

We call a pair (C1 ,C2 ) of binary linear codes with C1 ⊆ C2 a chain of binary
codes.
Every chain of binary codes arises from a Z4 -linear code in the manner of the
theorem. For suppose that binary codes C1 and C2 are given with C1 ⊆ C2 . Let

C = {v1 + 2v2 : v1 ∈ C1 , v2 ∈ C2 },

where the elements 0 and 1 of Z2 are identi¬ed with 0 and 1 in Z4 for this construc-
tion. Then the preceding construction applied to C recovers C1 and C2 . So every
chain of codes (that is, every pair (C1 ,C2 ) with C1 ⊆ C2 ) arises from a Z4 -linear
code.
However, the correspondence fails to be bijective, and many important prop-
erties are lost. Fore example, the two Z4 -codes

{000, 110, 220, 330} {000, 112, 220, 332}
and

give rise to the same pair of binary codes (with C1 = C2 = {000, 110}) but have
different symmetrised weight enumerators (and so different Lee weight enumera-
tors).
The problem of describing all Z4 -linear codes arising from a given chain has
not been solved. It resembles in some ways the “extension problem” in group
theory.


Exercises
2.1. Prove that the Nordstrom“Robinson code as de¬ned in Exercise 1.3 is
distance-invariant and has the claimed weight enumerator.
2.2. Prove Theorem 2.1(c). Verify the conclusion directly for the two codes in the
example following the theorem. Construct the images of these two codes under
the Gray map.
2.3. Show that the Z4 -linear code with generator matrix
« 
13121000
¬1 0 3 1 2 1 0 0·
¬ ·
1 0 0 3 1 2 1 0
10003121
2.2. Chains of binary codes 13

is equal to its dual and has Lee weight enumerator

X 16 + 112X 10Y 6 + 30X 8Y 8 + 112X 6Y 10 +Y 16 .

(This is the code whose Gray map image is the Nordstrom“Robinson code.)
2.4. Prove that, for any a, b ∈ Z4 , we have

γ(a + b) = γ(a) + γ(b) + (γ(a) + γ(’a)) — (γ(b) + γ(’b)),

where — denotes componentwise product: (a, b) — (c, d) = (ac, bd).
Hence prove that a (not necessarily linear) binary code C is equivalent to the
Gray map image of a linear Z4 code if and only if there is a ¬xed-point-free
involutory permutation σ of the coordinates such that, for all u, v ∈ C, we have

u + v + (u + uσ) — (v + vσ) ∈ C,

where — is the componentwise product of binary vectors of arbitrary length.
(De¬ne σ so that, if u = γ(c), then uσ = γ(’c); this permutation interchanges
the two coordinates corresponding to each coordinate of the Z4 code.)
14 Chapter 2. Codes over Z4
CHAPTER 3




Matroids

The notion of linear independence of a family of vectors in a vector space satis¬es
two simple conditions (namely, a subfamily of a linearly independent family is lin-
early independent, and the well-known exchange property), from which most of
its familiar properties hold: the existence and constant size of bases, the rank and
nullity theorem, etc. These properties crop up in various other situations. Indeed,
the exchange property is credited to Steinitz who observed it for the notion of al-
gebraic independence of elements in a ¬eld over an algebraically closed sub¬eld.
This leads to the concept of the transcendence degree of a ¬eld extension. Fur-
thermore, subsets of the edge set of a graph which induce acyclic graphs (forests),
and subfamilies of families of sets possessing systems of distinct representatives,
also satisfy these conditions.
The underlying abstract structure was given the name “matroid” by Whitney
(a generalisation of “matrix”). Tutte observed that a two-variable generalisation
of the chromatic polynomial of a graph could also be extended to this setting;
this is the Tutte polynomial of the matroid. In this chapter, we provide a brief
introduction to these concepts.

3.1 The basics

Let E be a set. A matroid M on E is a pair (E, J ), where J is a non-empty
family of subsets of E (called independent sets) with the properties


(a) if I ∈ J and J ⊆ I, then J ∈ J ;

15
16 Chapter 3. Matroids

(b) (the exchange property) if I1 , I2 ∈ J and |I1 | < |I2 |, then there exists e ∈ I2 \ I1
such that I1 ∪ {e} ∈ J .

As noted earlier, matroids were introduced by Whitney to axiomatise the no-
tion of linear independence in a vector space. Indeed, if E is a family of vectors in
a vector space V , and J is the set of linearly independent subsets of E, then (E, J )
is a matroid. Such a matroid is called a vector matroid.
Note that we speak of a family rather than a set of vectors here, since the same
vector may occur more than once. (Any family containing a repeated vector is to
be regarded as linearly dependent.) If we think of the vectors as the n columns
of a matrix, we can regard the set E of elements of the matroid as the index set
{1, 2, . . . , n} for the columns; then a subset I of E is independent if and only if the
family of columns with indices in I is linearly independent.
More formally, a representation of a matroid (E, J ) over a ¬eld F is a map
χ from E to an F-vector space with the property that a subset I of E belongs to
J if and only if χ(I) is linearly independent. Two representations χ, χ of M are
equivalent if there is an invertible linear transformation of V whose composition
with χ is χ .
We will frequently meet the special case where E consists of all the vectors
in an n-dimensional vector space over GF(q). This will be referred to as the
(complete) vector matroid, and denoted by V (n, q).
As referred to in the introduction, the following are also examples of matroids:

(a) Let E be a ¬nite family of elements in a vector space, and J the set of af¬ne
independent subfamilies. (A family (v j : j ∈ J) is af¬ne independent if the
relation ‘ c j v j = 0, where c j are scalars with ‘ c j = 0, implies that c j = 0
for all j.) Then (E, J ) is a matroid. Such a matroid is called af¬ne.

(b) Let K be an algebraically closed ¬eld containing an algebraically closed sub-
¬eld F. Let E be a ¬nite family of elements of K, and J the set of all
subfamilies of E which are algebraically independent over F. Then (E, J )
is a matroid. Such a matroid is called algebraic.

(c) Let G = (V, E) be a ¬nite graph (loops and multiple edges are allowed). Let
J be the set of all subsets A of E for which the graph (V, A) is acyclic (that
is, a forest). Then (E, J ) is a matroid. Such a matroid is called graphic, and
is denoted by M(G).

(d) Let (Xe : e ∈ E) be a family of sets. Let J be the family of all subsets I ⊆ E
for which the subfamily (Xe : e ∈ I) possesses a transversal (that is, there is
a family (xe : e ∈ I) of distinct elements such that xe ∈ Xe for all e ∈ I). Then
(E, J ) is a matroid. Such a matroid is called transversal.
3.1. The basics 17

It follows from the second axiom that all maximal independent sets in a ma-
troid M have the same cardinality k, called the rank of M. These maximal inde-
pendent sets are called the bases of M. It is possible to recognise when a family
B of subsets of E consists of the bases of a matroid on E. This is the case if and
only if
(a) no element of B properly contains another;
(b) if B1 , B2 ∈ B and y ∈ B2 \ B1 , then there exists x ∈ B1 \ B2 such that B1 \ {x} ∪
{y} ∈ B. (This property is also referred to as the exchange property.)
We can extend the de¬nition of rank to all subsets of E: the rank ρA of an
arbitrary subset A of E is the cardinality of the largest independent set contained
in A. It is also possible to recognise when a function ρ from the power set of a
set E to the non-negative integers is the rank function of a matroid. (Again, the
exchange property shows that any two maximal independent subsets of A have the
same cardinality.)
The set of all complements of bases of M is the set of bases of another ma-
troid M — on E, called the dual of M. This is most easily proved by showing that
conditions (a) and (b) above for a family B of sets imply the same condition for
the family of complements.
A ¬‚at in a matroid M = (E, J ) is a subset F of E with the property that ρ(F ∪
{x}) = ρF + 1 for all x ∈ E \ F. If ρF = k and A is an independent subset of F of
cardinality k, then F = {x ∈ E : ρ(A ∪ {x}) = ρA}. A ¬‚at whose rank is one less
than that of E is called a hyperplane.
The ¬‚ats of a matroid form a lattice (in which the meet operation is intersec-
tion), which is atomic and submodular; these properties of a lattice ensure that it
arises as the lattice of ¬‚ats of a matroid.
There are many other equivalent ways of de¬ning matroids: via circuits, cocir-
cuits, ¬‚ats, hyperplanes, etc. We do not pursue this here but refer to the books [25]
and [30].
Let M = (E, J ) be a matroid of rank r, and let k be a non-negative integer
with k ¤ r. The truncation of M to rank k is the matroid on E whose family of
independent sets is
Jk = {I ∈ J : |I| ¤ k}.
The ¬‚ats of the truncation are all the ¬‚ats of rank less than k of the original matroid
together with the whole set E.
We conclude with some simple examples of matroids. The free matroid on a
¬nite set E is the matroid in which every subset of E is independent. If |E| = n, this
matroid is denoted by Fn . The uniform matroid Ur,n , with r ¤ n, is the truncation
of the free matroid Fn to rank r; in other words, its independent sets are all the
subsets of E of cardinality at most r.
18 Chapter 3. Matroids

3.2 Deletion and contraction
The roots of matroid theory in graph theory explain much of the terminology
used. For example, the use of the letter E for the set of elements of a matroid
arises from its use as the edge set of a graph. In this section, we will meet loops,
deletion and contraction, all of which are more transparent for graphic matroids.
Let M = (E, J ) be a matroid. The element e ∈ E is called a loop if {e} ∈ J , or
/
equivalently, if ρ{e} = 0. In a graphic matroid, e is a loop if and only if it is a loop
of the underlying graph. Thus, an element is a loop if and only if it is contained
in no basis.
The element e ∈ E is a coloop if it is a loop in the dual matroid M — . Thus, e is a
coloop if and only if it is contained in every basis of M; that is, ρ(A∪{e}) = ρA+1
whenever e ∈ A. In a graphic matroid, e is a coloop if and only if it is a bridge, an
/
element whose removal increases by one the number of connected components.
Let e be an element which is not a coloop. The deletion of E is the matroid
M\e on the set E \ {e} in which a subset A is independent if and only if it is
independent in M (and doesn™t contain e). There is no compelling reason to forbid
the deletion of coloops, but it makes the theory tidier “ see the next paragraph.
In a graphic matroid, deletion of e corresponds to deletion of the edge e from the
graph.
Let e be an element which is not a loop. The contraction of e is the matroid
M/e on the set E \ {e} in which a set A is independent if and only if A ∪ {e} is
independent in M. (Here it is clear that contracting a loop would make no sense, so
our earlier restriction will preserve duality.) In a graphic matroid, contraction of e
corresponds to contraction of the edge e, that is, identifying the vertices forming
the two ends of e.

Proposition 3.1 Let e be an element of the matroid M which is not a loop. Then
e is not a coloop of M — , and

(M/e)— = M — \e.

Deletion and contraction form the basic inductive method for studying ma-
troids, as we will see.


3.3 Rank polynomial and Tutte polynomial
Let M be a matroid on the set E, having rank function ρ. The Tutte polynomial
of M is most easily de¬ned as follows:

‘ (x ’ 1)ρE’ρA(y ’ 1)|A|’ρA.
T (M; x, y) =
A⊆E
3.3. Rank polynomial and Tutte polynomial 19


For example, the Tutte polynomial of the uniform matroid Ur,n is
r n
n n
T (Ur,n ; x, y) = ‘ (x ’ 1) + ‘
r’i
(y ’ 1)i’r ,
i i=r+1 i
i=0

since a set A of cardinality i ¤ r satis¬es ρE ’ ρA = r ’ i and |A| ’ ρA = 0, while
a set A of cardinality i ≥ r + 1 satis¬es ρE ’ ρA = 0 and |A| ’ ρA = i ’ r.
The appearance of the terms x ’ 1 and y ’ 1 in the polynomial is a historical
accident. Tutte de¬ned his polynomial by a completely different method, depend-
ing on the choice of an ordering of the elements of the matroid, but giving a result
independent of the ordering. Meanwhile, the rank polynomial of M was de¬ned
as
R(M; x, y) = ‘ xρE’ρA y|A|’ρA .
A⊆E

Crapo [11] showed that in fact T (M; x, y) = R(M; x ’ 1, y ’ 1).
A number of simple matroid invariants can be extracted from the Tutte poly-
nomial, as the next result shows. The proof is an exercise.

Proposition 3.2 Let M be a matroid on n elements.

(a) The number of bases of M is equal to T (M; 1, 1).

(b) The number of independent sets of M is equal to T (M; 2, 1).

(c) The number of spanning sets of M is equal to T (M; 1, 2).

(d) T (M; 2, 2) = 2n .

Calculation of the Tutte polynomial is possible by an inductive method using
deletion and contraction, as follows.

/ /
Theorem 3.3 (a) T (0; x, y) = 1, where 0 is the empty matroid.

(b) If e is a loop, then T (M; x, y) = yT (M\e; x, y).

(c) If e is a coloop, then T (M; x, y) = xT (M/e; x, y).

(d) If e is neither a loop nor a coloop, then

T (M; x, y) = T (M\e; x, y) + T (M/e; x, y).
20 Chapter 3. Matroids

Proof (a) is trivial. For the other parts, we note that each subset A of M/e or M\e
corresponds to a pair of subsets A and A ∪ {e} of M. let M = M\e and M = M/e
(where appropriate), and use ρM , ρM and ρM for the rank functions of the three
matroids M, M , M , and E = E = E \ {e}.
If e is a loop, then we have

ρM E = ρM E ,
ρM A = ρM A ∪ {e} = ρM A,
|A ∪ {e}| = |A| + 1, |E| = |E | + 1.

Thus the two terms in the sum for T (M) are respectively 1 and y ’ 1 times the
term in T (M ) corresponding to A, and so (b) holds.
The other two parts are proved similarly.

As an illustration of the use of the inductive method, we consider the chromatic
polynomial of a graph G, the polynomial PG with the property that PG (k) is equal
to the number of proper k-colourings of G.

Corollary 3.4 Let G = (V, E) be a graph. Then

PG (k) = (’1)ρ(G) kκ(G) T (M(G); 1 ’ k, 0),

where κ(G) is the number of connected components of G and ρ(G) + κ(G) the
number of vertices.

Proof The matroid M(G) associated with G has rank ρE = n ’ κ(G), where n is
the number of vertices. Let k be any positive integer.
The chromatic polynomial satis¬es the following recursion:

(a) If G has n vertices and no edges, then PG (k) = kn .

(b) If G contains a loop, then PG (k) = 0.

(c) If e is an edge which is not a loop, then

PG (k) = PG\e (k) ’ PG/e (k),

where G\e and G/e are the graphs obtained from G by deleting and con-
tracting e, respectively.

Here (a) is clear since any vertex-colouring of the null graph is proper; and (b)
is trivial. For (c), we note that, if e has vertices v and w, the proper colourings c
of G\e can be divided into two classes:
3.4. Perfect matroid designs 21

(a) those with c(v) = c(w), which yield proper colourings of G;

(b) those with c(v) = c(w), which yield proper colourings of G/e.

Now we show by induction on the number of edges that

PG (k) = (’1)ρ(G) kκ(G) T (M(G); 1 ’ k, 0).

This is clear when there are no edges since ρ(G) = 0, κ(G) = n and T (M(G)) = 1.
It is also clear if there is a loop, since T (M(G); x, 0) = 0 in that case by part (b) of
Theorem 3.3. If e is a coloop then deletion of e increases κ by 1 and decreases ρ
by 1; also PG\e (k) = kPG (k)/(k ’ 1), since a fraction (k ’ 1)/k of the colourings
of G\e will have the ends of e of different colours. So the inductive step is a
consequence of part (c) of Theorem 3.3.
Finally, if e is neither a loop nor a coloop, use (c) above and (d) of Theo-
rem 3.3.

The Tutte polynomials of a matroid and its dual are very simply related:

Proposition 3.5

T (M — ; x, y) = T (M; y, x).



Proof Let A be a subset of E and let E — = E and A— = E \ A. If ρM and ρM— are
the rank functions of M and M — respectively, we have

|A— | ’ ρM — (A— ) = ρM (E) ’ ρM (A),
ρM— (E — ) ’ ρM — (A— ) = |A| ’ ρM (A).

So the term in T (M — ) arising from A— is equal to the term in T (M) arising from A
but with x and y interchanged.


3.4 Perfect matroid designs
A perfect matroid design, or PMD, is a matroid having the property that the
cardinality of a ¬‚at depends only on its rank. If the rank is r, and the cardinality of
an i-¬‚at is ki for i = 0, . . . , r (with, of course, kr = n, the total number of elements
of the matroid), then we describe it as a PMD(k0 , k1 , . . . , kr ).
In a PMD(k0 , k1 , . . . , kr ), the number of loops is k0 ; deleting the loops gives a
PMD(0, k1 ’ k0 , . . . , kr ’ k0 ). So usually nothing is lost by assuming that k0 = 0.
22 Chapter 3. Matroids

In a PMD(0, k1 , k2 , . . . , kr ), each element is one of a family of k1 parallel el-
ements. Identifying these classes, we obtain a PMD(0, 1, k2 /k1 , . . . , kr /k1 ). So
again we often assume that k1 = 1. This reduction is a bit more problematic, as
we will see when we consider group actions.
Other operations on PMDs which yield PMDs are deletion, contraction, and
truncation.
Not very many PMDs are known. The list below includes all PMDs with
k0 = 0 and k1 = 1 which are not proper truncations.
(a) The free matroid on n elements (the matroid in which every set is indepen-
dent) is a PMD(0, 1, . . . , n).

(b) The complete vector matroid V (n, q) is a PMD(1, q, q2 , . . . , qn ). (The ele-
ments of this matroid are the vectors in GF(q)n , and independence is the
usual notion of linear independence.) If we delete the zero vector and shrink
each 1-dimensional subspace to a point, we obtain the projective geometry
PG(n ’ 1, q), which is a PMD(0, 1, q + 1, . . . , (qn ’ 1)/(q ’ 1)).
(c) The af¬ne geometry AG(n, q) is a PMD(0, 1, q, q2 , . . . , qn ). (The elements of
this matroid are the vectors in GF(q)n , but independence is now the notion
of af¬ne independence de¬ned earlier: vectors v1 , . . . , vd are af¬ne indepen-
dent if there is no linear dependence

c1 v1 + · · · + cd vd = 0

where c1 + · · · + cd = 0 and the ci not all zero. (An equivalent condition for
d ≥ 1 is that the vectors v2 ’ v1 , . . . , vd ’ v1 are linearly independent.)

(d) Let t, k, n be positive integers with t < k < n. A Steiner system S(t, k, n)
consists of a set X of n points, and a set B of subsets of S called blocks, such
that any t points are contained in a unique block. From a Steiner system,
we obtain a matroid on the set of points as follows: every set of cardinality
at most t is independent; and a set of cardinality t + 1 is independent if and
only if it is not contained in a block. This is a PMD(0, 1, . . . ,t ’ 1, k, n) in
which the hyperplanes are the blocks.

(e) The points and lines of an af¬ne space AG(d, 3) form a Steiner triple system
(that is, a Steiner system S(2, 3, n)) with the property that any three points
not contained in a block lie in a unique subsystem with 9 points (an af¬ne
plane). Marshall Hall [17] discovered that there are other Steiner triple sys-
tems with this property. These are now called Hall triple systems. Such a
system gives rise to a PMD(0, 1, 3, 9, n) of rank 4, where a 3-set is indepen-
dent if it is not a block, and a 4-set is independent if it is not contained in an
3.4. Perfect matroid designs 23

af¬ne plane. The number of points in a Hall triple system must be a power
of 3.

See Deza [12] for a survey of perfect matroid designs.
The following theorem is due to Mphako [24].

Theorem 3.6 Let M be a PMD(k0 , . . . , kr ). Then the Tutte polynomial of M is
determined by the numbers k0 , . . . , kr .

Proof It is enough to determine the number a(m, i) of subsets of the domain
which have cardinality m and rank i for all m and i: for
r n
T (M; x, y) = ‘ ‘ a(m, i)(x ’ 1)k’i(y ’ 1)m’i,
i=0 m=i

where n = kr is the number of points.
Let s(i, j) be the number of i-¬‚ats containing a given j-¬‚at for j ¤ i. Then

i’1
n ’ kh
s(i, j) = ∏ .
ki ’ kh
h= j


For let (x1 , . . . , x j ) be a basis for a j-¬‚at Fj . The number of ways of choosing
x j+1 , . . . , xi so that (x1 , . . . , xi ) is independent is the numerator of the above ex-
pression. Then this set spans an i-¬‚at Fi containing Fj , and the number of ways of
extending (x1 , . . . , x j ) to a basis for Fi is the denominator.
Now we have
i
ni
= ‘ a(m, j)s(i, j).
s(i, 0)
m j=0

For the left-hand side counts the number of choices of an i-¬‚at Fi and a subset
of Fi of cardinality m. This subset has rank j for some j ¤ i, and spans a j-¬‚at
contained in Fi . So each m-set of rank j contributes s(i, j) to the count.
This is a triangular system of equations for a(m, j) with diagonal coef¬cients
s(i, i) = 1. We see that the a(m, j) are indeed determined by k0 , . . . , kr .

Exercises

3.1. Prove that algebraic matroids, graphic matroids, and transversal matroids do
indeed satisfy the matroid axioms.
24 Chapter 3. Matroids

3.2. In this exercise, we prove that a graphic matroid is representable over any
¬eld.
Let G = (V, E) be a graph, where V = {v1 , . . . , vn } and E = {e1 , . . . , em }.
Choose arbitrarily an orientation of each edge ei (that is, the edge ei has an initial
and a terminal vertex, which may be the same). Now construct an n — m matrix
A = (ai j ) as follows:
+1 if e j is a non-loop with terminal vertex vi ;
ai j = ’1 if e j is a non-loop with initial vertex vi ;
0 otherwise.
Prove that, given any cycle in the graph, the sum of the columns corresponding
to the edges in the cycle (with signs ±1 chosen appropriately) is zero. Prove also
that if a set of edges contains no cycle, then there is a row containing a single
non-zero entry in the corresponding columns.
Hence show that, for any ¬eld F, a set of columns of A is linearly indepen-
dent over F if and only if the corresponding set of edges of G forms an acyclic
subgraph.
3.3. What are the bases, the ¬‚ats, the hyperplanes, and the rank function of the
uniform matroid Ur,n ? What is the dual of this matroid?
3.4. Prove that the matroid U2,4 is not graphic.
3.5. Prove that every af¬ne matroid can be represented as a vector matroid in a
space of dimension one greater than the one affording the af¬ne representation.
3.6. Let M be a graphic matroid arising from a connected graph G = (V, E) on n
vertices. Prove that the rank function is given by
ρA = n ’ κ(A),
where κ(A) is the number of connected components of the graph (V, A).
3.7. Let M(G) be a graphic matroid, where the graph G = (V, E) is connected.
Show that a set A ⊆ E is independent in M(G)— if the removal of A does not
disconnect G.
3.8. Construct
(a) non-isomorphic graphs G1 , G2 for which the graphic matroids are isomorphic;
(b) non-isomorphic graphic matroids M(G1 ), M(G2 ) which have the same Tutte
polynomial.
3.9. As we mentioned in Chapter 1, the binary Golay code is a [24, 12, 8] code
containing 759 words of weight 8. Prove that the 759 subsets of cardinality 8
of {1, . . . , 24} which support codewords of weight 8 are the blocks of a Steiner
system S(5, 8, 24).
3.4. Perfect matroid designs 25

3.10. Show that the blocks of a Steiner system S(t + 1, 2t, n) are the supports of
words of minimum weight in a linear binary code if and only if the system has the
symmetric difference property: if B1 and B2 are blocks for which |B1 © B2 | = t,
then their symmetric difference B1 B2 is a block.
Find examples with t = 2.
26 Chapter 3. Matroids
CHAPTER 4




Matroids and codes

There is a very close correspondence between linear codes, on one hand, and ma-
troids (speci¬cally, representations of matroids) on the other “ the two types of
structure correspond exactly, up to the natural de¬nition of equivalence in each
case. Among other things, this correspondence leads us to the theorem of Curtis
Greene, showing that the weight enumerator of a code is a specialisation of the
Tutte polynomial of the corresponding matroid. This then provides a combinato-
rial proof of MacWilliams™ Theorem on the weight enumerators of dual codes.
As we already noted, Carrie Rutherford represented a Z4 -linear code C by a
chain of binary codes. She went on to associate a three-variable analogue of the
Tutte polynomial to such a chain. This polynomial specialises to give various
properties of C (though not its symmetrised weight enumerator). We describe this
in the last section of the chapter.

4.1 The correspondence

Let A be a k — n matrix over a ¬eld F, satisfying the condition that the rows of
A are linearly independent, so that the row space of A has dimension k.
There are two different structures that can be built from A.
First, the row space of A is an [n, k] code over F, that is, a k-dimensional
subspace of F n . Now row operations on A simply change the basis for the code,
leaving the actual code completely unaltered. Column permutations, and multipli-
cations of columns by non-zero scalars, replace the code by a monomial equivalent
code.
Second, there is a matroid M on the set E = {1, 2, . . . , n}, in which a set I is

27
28 Chapter 4. Matroids and codes

independent if and only if the family of columns of A whose indices belong to I is
linearly independent. (We cannot quite say that the elements of E are the columns
and independence is linear independence, since E might have repeated columns.)
More precisely, the function χ mapping i to the ith column is a representation of
M over F. How do the elementary operations affect the matroid representation?
We see that row operations on A don™t change M but replace the representation
χ by an equivalent representation. (Two representations are called equivalent if
they differ by an invertible linear transformation of the embedding vector space.)
On the other hand, column permutations and scalar multiplications replace M
by an isomorphic matroid; effectively, permutations re-label the elements, while
scalar multiplications have no effect at all.
So, if we call two matrices A and A CM-equivalent if A is obtained from
A by a row operation and a monomial transformation of the columns, we see
that CM-equivalence classes of matroids correspond bijectively to both monomial
equivalence classes of linear codes, and equivalence classes of representations of
matroids, under the natural notions of equivalence in each case.
Thus we expect information to transfer back and forth between code and ma-
troid.
It is possible to go directly from the vector matroid to the code, without the
intervening matrix, as follows.
Let v1 , . . . , vn be vectors spanning the vector space V . The corresponding code
is
{(v1 f , . . . , vn f ) : f ∈ V — },
where V — is the dual space of V , and v f is the image of v under f . THis is because
the function giving the ith coordinate of a vector is an element of the dual space,
and these functions form a basis for the dual space.
I leave as an exercise the problem of ¬nding a matrix-free construction of the
matroid from the code.
It is a simple exercise to show the following:

Proposition 4.1 If the matroid M corresponds to the code C, then the dual ma-
troid M — corresponds to the dual code C⊥ .

Proof If the matrix A happens to be in the form [Ik B], where Ik is a k — k iden-
tity matrix and B is k — n ’ k, then both the dual code and the dual matroid are
represented by the matrix [’B In’k ].


4.2 Greene™s Theorem
The following theorem was proved by Greene [16].
4.2. Greene™s Theorem 29

Theorem 4.2 Let C be a code over a ¬eld with q elements, and M the correspond-
ing vector matroid. Then

x + (q ’ 1)y x
WC (x, y) = yn’dim(C) (x ’ y)dim(C) T M; , .
x’y y



Note that, if X = (x + (q ’ 1)y)/(x ’ y) and Y = x/y, then

(X ’ 1)(Y ’ 1) = q.

So the weight enumerator is an evaluation of the Tutte polynomial along a partic-
ular hyperbola in the “Tutte plane”.

Proof The proof is by induction. For M, we have the “deletion-contraction rule”
of Theorem 3.3.
The analogues of deletion and contraction of a matroid are the operations of
puncturing and shortening a code.
To puncture a code at the ith position, we simply delete the ith coordinate
from all codewords. To shorten it at the ith position, we take the subcode consist-
ing of all codewords with zero in the ith position, and then delete this position.
We denote by C and C the codes obtained by puncturing and shortening C in a
speci¬ed position. It is easy to see that puncturing and shortening correspond to
deletion and contraction of the corresponding element of the matroid.
A loop in the M corresponds to a coordinate where all codewords have the
entry 0. A coloop is a bit more complicated, but can be described as a coordinate
such that (after row operations) the ¬rst entry in that column of the generator
matrix is 1, while all other entries in that column or in the ¬rst row are 0.
If the element e of the matroid corresponds to the distinguished coordinate,
we have the following recursive scheme for the weight enumerator:

(a) If C has length 0, then WC (X,Y ) = 1.

(b) If e is a loop, then WC (X,Y ) = XWC (X,Y ).

(c) If e is a coloop, then WC (X,Y ) = (X + (q ’ 1)Y )WC (X,Y ).

(d) If e is neither a loop or a coloop, then

WC (X,Y ) = YWC (X,Y ) + (X ’Y )WC (X,Y ).
30 Chapter 4. Matroids and codes

Part (a) is obvious; part (b) holds because each word in C has one extra zero
than the corresponding word in C . Part (c) holds because each word w in C gives
rise to q words in C (all possible entries occur in the added coordinate), of which
one has the same weight as w and q ’ 1 have weight one greater.
Finally, suppose that e is neither a loop nor a coloop. Let W1 and W2 be the
sums of terms in WC corresponding to words with zero, resp. non-zero, entry in
position e. Then WC = W1 + W2 . We also have WC = W1 /X + W2 /Y , and WC =
W1 /X. The assertion follows.
Now induction, together with Theorem 3.3, proves the theorem.

From Theorem 4.2 and Proposition 3.5, we can deduce MacWilliams™ The-
orem 1.4, which shows that the weight enumerator of the dual code C⊥ can be
calculated from that of C.
Theorem 4.3
1
WC (x + (q ’ 1)y, x ’ y).
WC⊥ (x, y) =
|C|

Proof Since C⊥ has dimension n ’ dim(C) and corresponds to the dual matroid
M — , we have
X X + (q ’ 1)Y
WC⊥ (X,Y ) = Y dim(C) (X ’Y )n’dim(C) T M; , .
X ’Y
Y
On the other hand, we have
1
WC (X + (q ’ 1)Y, X ’Y )
|C|
qX X + (q ’ 1)Y
= q’ dim(C) (X ’Y )n’dim(C) (qY )dim(C) T M; , .
X ’Y
qY
The two expressions are equal.

Note that this proof is entirely combinatorial, in contrast to the algebraic proof
given in Chapter 1.


4.3 Is there a Z4 version?
There does not seem to be any way to produce a matroid which captures a
Z4 -linear code in the way that we have seen for linear codes over ¬elds. How-
ever, we already saw that many features of a Z4 -linear code C are captured by a
pair (C1 ,C2 ) of binary codes. On this basis, Rutherford [27] considered certain
4.3. Is there a Z4 version? 31

pairs of matroids, and attached to such pairs a three-variable analogue of the Tutte
polynomial. This polynomial gives some features of C as specialisations.
The following section is entirely based on her work.
Let M1 and M2 be two matroids on the same set E. We say that (M1 , M2 ) is a
matroid pair, or that M1 is a quotient of M2 , if there is a matroid N on a set E ∪ X
such that M1 = N/X and M2 = N\X. (Deleting or contracting a set of points just
means deleting or contracting the points one at a time.)
It can be shown that we may choose N and X so that |X| = ρM2 (E) ’ ρM1 (E),
and X is independent and E is spanning in N. Note that every set A ⊆ E which
is independent in M1 is also independent in M2 . This condition however is not
suf¬cient for (M1 , M2 ) to be a matroid pair: see Exercise 4.3.
It is true that
— —
(a) of (M1 , M2 ) is a matroid pair, then so is (M2 , M1 );

(b) for any matroid M on n elements, (M, Fn ) and (Fn— , M) are matroid pairs.

Let (C1 ,C2 ) be a chain of binary codes, and M1 and M2 the associated ma-
troids. Then (M1 , M2 ) form a matroid pair. This is because we can ¬nd matrices A
and B such that A and A are generator matrices for C1 and C2 respectively; then
B
we can take N to correspond to the code with generator matrix

OA
.
IB

In this case, we call the pair (M1 , M2 ) a matroid chain over Z2 .
Note that not every matroid pair is a matroid chain, even if the individual
matroids are representable: see Exercise 4.3. Note also that, if (M1 , M2 ) is a
— —
matroid chain over Z2 , then so is (M2 , M1 ).
Let M = (M1 , M2 ) be a matroid pair. Rutherford de¬nes the generalised rank
polynomial, which I shall call for brevity the Rutherford polynomial, of the pair to
be
G(M ; v, x, y) = ‘ v|B|’|A| xρ1 E’ρ1 B y|A|’ρ2 A ,
A⊆B⊆E

where ρ1 and ρ2 are the rank functions of M1 and M2 . (In fact, we could use
the analogue of the Tutte polynomial rather than the rank polynomial, by putting
v ’ 1, x ’ 1, y ’ 1 in place of v, x, y here, but the difference is inessential; I have
chosen to follow Rutherford.)
The Rutherford polynomial has a number of interesting specialisations:

Theorem 4.4 Let G(M ; v, x, y) be the Rutherford polynomial of a matroid pair
M = (M1 , M2 ). Let R(Mi ; x, y) be the rank polynomial of Mi , for i = 1, 2.
32 Chapter 4. Matroids and codes

x
(a) G(M ; v, x, 1) = (1 + v)ρ1 E R(M1 ; , 1 + v).
1+v
y
(b) G(M ; v, 1, y) = (1 + v)|E|’ρ2 E R(M2 ; 1 + v, ).
1+v
(c) If M1 = M2 = M, then G(M ; 0, x, y) = R(M; x, y).

(d) If M1 = Fn— and M2 = M, then G(M ; 0, x, y) = R(M; 1, y).

(e) If M2 = Fn and M1 = M, then G(M ; 0, x, y) = R(M; x, 1).

However, the fact that a chain of binary codes does not even determine the
symmetrised weight enumerator (or Lee weight enumerator) of the corresponding
Z4 -linear code shows that we cannot obtain these weight enumerators from the
Rutherford polynomial by specialisation.
It seems likely that the Rutherford polynomial can be extended to chains of
arbitrary length of codes over arbitrary ¬elds.


Exercises
4.1. Describe the matroids corresponding to the Hamming code of Chapter 1 and
its dual.
4.2. Show that the matroid associated to a linear code is uniform if and only if
the code is MDS. (See Exercise 1.3.)
4.3. Find an example of two matroids M1 and M2 on a set E such that every
independent set in M1 is independent in M2 but (M1 , M2 ) is not a matroid pair.
4.4. Find an example of two matroids M1 and M2 on a set E such that both M1
and M2 are representable over Z2 and (M1 , M2 ) is a matroid pair but not a matroid
chain over Z2 .
4.5. Let (M1 , M2 ) be a matroid pair on E, and let ρi be the rank function of Mi
for i = 1, 2. Prove that

0 ¤ ρ2 A ’ ρ1 A ¤ ρ2 E ’ ρ1 E

for any set A ⊆ E.
4.6. Calculate the weight enumerator of the code associated with a representation
of U3,n over GF(q). Find examples with n = q + 1.
CHAPTER 5




Permutation groups

In the second half of the notes, we introduce the last strand, permutation groups,
and braid it together with codes and matroids.
Traditionally, permutation groups arise as automorphism groups of algebraic
or combinatorial structures. The procedure here will be a bit different: the groups
will be built from the algebraic structure of codes, and matroids will arise from
the ¬xed point structure of permutation groups.
Before this, we give a brief account of permutation groups and their associated
cycle index polynomials.
The treatment here is somewhat brief, since full accounts are available else-
where. In addition to the classic treatments by Wielandt [32] and Passman [26],
there are more recent books by Cameron [4] and Dixon and Mortimer [13].

5.1 Orbits and stabiliser
The set of all permutations of a set „¦ is called the symmetric group on „¦.
Usually we take „¦ to be the set {1, . . . , n}, and denote the symmetric group by Sn ,
for some positive integer n. The order of Sn is n!.
The convention of using „¦ for the permutation domain and lower-case Greek
letters for its elements was established by Wielandt in his book. We also use the
convention that permutations act on the right, so that the image of ± under the
permutation g is denoted by ±g. Thus, the result of applying the permutation g
followed by h is written gh, and we have ±(gh) = (±g)h.
As is well known, any permutation can be written as a product of disjoint
cycles: we call this the cycle decomposition. For example, the permutation of

33
34 Chapter 5. Permutation groups

{1, . . . , 5} which maps 1 to 4, 2 to 5, 3 to 1, 4 to 3, and 5 to 2 has cycle decompo-
sition (1, 4, 3)(2, 5). The cycle decomposition is unique up to writing the cycles
in a different order and starting them at different points: for example,
(1, 4, 3)(2, 5) = (5, 2)(3, 1, 4).

. 1
( 3)



>>