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).