Acta Applicandae Mathematicae 10 (1987), 213-235 by D. Reidel Publishing Company

213

© 1987

Some Mathematical Problems in Seriation R. R. L A X T O N

Clare College, Cambridge, England and Department of Mathematics, University of Nottingham, Nottingham, England (Received: 23 September 1986; revised: 6 August 1987)

Abstract. Some mathematical aspects of sedation are studied in this paper. Certain conditions on an abundance or an incidence matrix have been given in the past which imply that there exists a permutation of its rows so that the resulting matrix is a O matrix (in which case the original matrix is said to be a pre-Q). These types of results have applications to chronologically ordering archaeological provenances under certain circumstances. Unfortunately these conditions are deficient both theoretically and practically, in that for much archaeological data the conditions are not necessarily true yet the corresponding provenances do have chronological orderings. Here we are able to generalize these results in two ways. First we are able to establish necessary and sufficient conditions on the rows of a matrix for it to be pre-Q. These conditions are local in that they concern only certain triples and quadruples of the rows. Secondly, we are able to interpret seriation in terms of a ternary relation R on a set A and prove the results in this general context. In this form the theorem says that if only certain of the triples and quadruples are R-strings, then the whole set A is an R-string, and so has a linear order consistent with the ternary relation R. This would appear to generalize a theorem of P. C. Fishburn. Both aspects of the generalization mean that the results stated herein have a wider applicability than those given heretofore. Possibly more importantly than this is that they lead to numerical invariants, called the fixing number and the related linear rigidity, of such an R-string on A. The archaeological interpretation of these is given in the paper and data supplied which illustrates this point. Finally various other conditions on products and representations of relations are stated which imply that A is an R-string. One of these generalizes and completes a theorem of D. G. Kendall.

AMS subject clamfication (1980): 40--XX. Key words.. Archaeology, abundance matrix, seriation, O matrix, ternary relation, R-string.

1. Introduction

1.1. A R C H A E O L O G I C A L B A C K G R O U N D

A formal approach to the chronological ordering of a collection of provenances, be they graves, middens, archaeological sites, etc, is via the associated incidence or abundance matrix which records the different types of artifacts they contain. This approach, called seriation, is based on the assumption that a particular form of an artifact which comes into use in a society increases in popularity and use at the expense of other forms as time passes and, after reading a peak of popularity, falls away in popularity and use as other rival forms come into use. Or, to put it

214

R.R. LAXTON

more formally, the self-same form never definitely drops and then definitely increases in popularity and use in a society as time passes. If, furthermore, these different forms of artifacts present in the provenances in various amounts can be assumed to reflect fully the relative quantities of these within the society as a whole at the time of their sealing or disuse, then the incidence and abundance matrices of the different forms within the provenances can be made to furnish a relative ordering of the times when they were sealed up or became disused. (A more detailed discussion of the conditions for seriation to apply in an archaeological context is given in [1].) By way of illustration of this argument, the abundance matrix and the corresponding incidence matrix for the proportions and incidence of four different types of painted pottery contained in six of the levels, one below the other, of a room within a refuse mound at an archaeological site is given in Table I [2]. In this order, the numbers in any column of the abundance matrix never strictly decrease and then strictly increase again on going down the columns, whilst in the incidence matrix this is equivalent to the fact that in each column the ones are in single blocks. In such a form an abundance matrix is called a O matrix and an incidence matrix a P matrix (see [1, 3, 4, 5]). (Proportions are used in this paper though this is not necessary for the definition of an abundance matrix; thus incidence matrices are special cases of abundance matrices.) That the one is a O matrix and the other a P matrix reflects the fact that the ordering of their rows corresponds to the stratigraphic order of the respective levels; the order from bottom to top is the relative ordering of the times from earliest to latest when they were deposited. The problem we are concerned with here, seriation, goes one stage further. If the above proportions and incidences of painted pottery had come from six graves scattered about a cemetery, say, then there would, in general, be no

Talkie I. Proportions of pottery types

T o p m o s t level Second level Third level Fourth level Fifth level B o t t o m m o s t level

Incidence of pottery types

A

B

C

D

A

B

C

D

10 15 45 45 85 95

10 50 35 30 5 5

80 35 5 0 0 0

0 0 15 25 10 0

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 0 0 0

0 0 1 1 1 0

A b u n d a n c e Matrix

Incidence Matrix

215

SOME MATHEMATICAL PROBLEMS IN SERIATION

stratigraphic order to suggest a chronological order for them. In these circumstances the six rows in the abundance and incidence matrices would have had no particular order. Say in this hypothetical case that the respective abundance and incidence rows had been labelled randomly as follows al

45

30

0

25

al

1

1

0

1

a2

95

5

0

0

a2

1

1

0

0

a3

15

50

35

0

a3

1

1

1

0

a4

85

5

0

10

a4

1

1

0

1

a5

10

10

80

0

a5

1

1

1

0

a6

45

35

5

15

a6

1

l

1

1

The problem then, in the absence of any other evidence such as the above stratigraphic one, is to determine if the rows of these matrices can be permuted so that the conditions discussed above are met. That is, if for some ordering of the rows the quantities in all columns never strictly decrease and then increase again, or for an incidence matrix, if the ones in all the columns appear in single blocks in each column. If a permutation of the rows can be found which does this then the abundance matrix is called a pre-Q and the incidence matrix a pre-P matrix [1, 5]. The resulting order, if it occurs, is then a candidate for a chronological ordering of the corresponding provenances. (We also say that a resulting Q matrix is a Q-form of the initial matrix.) Of course, the complete inversion of the rows of any P or Q matrix is also a P or Q matrix, respectively, and so is also a candidate for the chronological ordering of the provenances. This is one of the stages where further archaeological evidence or opinion is needed to furnish a chronological ordering. If a matrix has only one Q-form, apart from the complete inversion of its rows, we say that it has unique Q-form and the Q matrix is a unique Q matrix. Consider the following three abundance matrices 0 90 [910 0 0 10

10 9~ ] [

0 90 10 10 100 0

10 0 90 80 ] [ 10 10 80 10

10] 80 10 "

The first matrix is not a pre-Q matrix. The second is a unique Q matrix. The third matrix is also a Q matrix but so is that obtained by interchanging the second and third rows. That is, it is not a unique Q matrix. The formal theory of seriation is concerned with determining if an abundance (incidence) matrix is pre-Q (pre-P) or not and, if it is, whether a resulting Q-form of it is unique or not. Even if it is known that an abundance matrix is pre-Q, there remains the practical problem of finding a permutation of its rows to make it a Q matrix. Several archaeological problems involving seriation are described in the Pro-

216

R.R. LAXTON

ceedings of the Anglo-Romanian Conference on Mathematics in the Archaeological and Historical Sciences [6] together with descriptions of various practical methods for seriating large data matrices. Marquardt [7] describes in considerable detail more recent work, especially in its practical implementation (see also [8] for a new approach to the practical problem). We do not consider this practical problem here even though it is very important and has itself many points of theoretical interest. 1.2. THEORETICAL BACKGROUND

The theory of seriation began with Robinson [9], Brainard [10], Kendall [11] and Fulkerson and Gross in [12]. Both Kendall and Wilkinson extended this work in a number of papers in the late 60s and early 70s [3, 4, 13, I4]. The approach taken by Wilkinson was via Hamiltonian circuits, with the vertices corresponding to the rows of the data matrices, and this was recently reworked by Shuchat [15]. Kendall, on the other hand, developed by the theory of similarity measures and similarity matrices and Roberts [16, 17] has elaborated and extended several of the results in graph theoretic terms (see also Skrien [18]). Let A = (ais) be an m × n abundance matrix with rows a l , . . . , a,,. Put S(ai, ak)---= ~ min{aij, j=l

akj}

and write Ao A T = (bik) with bik = S(ai, ak). This is an m × m symmetric matrix, called a similarity matrix of A by Kendall [4]. Clearly if A is actually an incidence matrix, then A o A T = A A T. A symmetric matrix is said to be an R matrix, R for Robinson, or have R-form if (i) in going to the right along a row from the first column to the diagonal, the elements never decrease, and (ii) in going down a column from the diagonal to the last row the elements never increase. Thus the similarity of the above three 3 × 3 abundance matrices are

[00 10l(i 10 10

100 10

10 100

2

100 10

01[o0

10 100

20 20

100 30

30 100

respectively. All are R matrices. The similarity matrices of the abundance matrices of the pottery types in the stratigraphic order and the random order (see above) are 50 45 60 20 90" 55 25 20 15 15" "100 "100 50 100 20 90 15 50 55 45 20 20 55 100 45 20 100 20 55 55 55 100 90 60 50 25 60 90 20 100 15 60 45 90 100 60 50 20 20 15 55 15 100 25 20 60 60 100 90 15 90 50 55 60 25 100 20 50 50 90 100 15

SOME MATHEMATICALPROBLEMSIN SERIATION

217

respectively. Here the first is an R matrix and the second is not. Indeed Kendall showed that if A is a O matrix then its similarity matrix A o A T is a R matrix. This forms the basis of Kendall's multidimensional scaling technique of seriation [4]. Unfortunately it is not true that if A o A T is an R matrix then A is a O matrix as the first example of the 3 x 3 matrices shows. Nevertheless, Kendall's proofs [4, 6] contains implicitly an extra condition which supplies a converse result. At the time the statement of the converse may not have seemed altogether natural but in the light of what we prove here in a more general setting it does become so. The following result has been proved. T H E O R E M 1 (Laxton [5]). Suppose that in an m × n abundance matrix A, the following conditions are true. (i) Every subset of three rows of A is pre- Q and each in their resulting O form is a unique 3 x n 0 matrix. (ii) Every subset of four rows of A is pre- O. Then A is pre-O.

Thus if certain local conditions are everywhere satisfied, the global result follows. As remarked at the time, this result is very similar to the classical result of Menger [19] that if every four points of a semi-metric space S are collinear in Euclidean space, then S is collinear. Menger's proof depends heavily on the properties of Euclidean space and so in a certain sense the first condition in the above result can be thought of as replacing these. The above result can be strengthened since implicit in its proof is that not only is A pre-O but the resulting O form of A is a unique O matrix, though this was not stated at the time. Kendall's result with its converse can now be stated as follows. T H E O R E M 2 (Kendall [3, 4, 6].) A n abundance matrix A is a O matrix if and only if (i) A o A T is an R matrix and (ii) every subset of three rows of A is pre-O. Thus if a global and certain local conditions are everywhere satisfied than the global result follows once again (see Boneva [20] who also proves a converse of Kendall's theorem). As we have noted above, if the three rows al, m2, a3 of an abundance matrix are, in this order, a O matrix, then so is a3, a2, al. Thus being a O matrix is really about a2 being between m~ and m3 and this gives rise to a symmetric, ternary relation on the rows of A. In this more general language Theorem 1 had already been proved by Fishburn ([21], [22] Ch. 4, Th. 6), though with the conditions expressed in a slightly different form. This latter work is motivated by the connection between interval orders and the relationship of betweenness (see also Varecza [23]).

218

R.R. LAXTON

As a matter of fact, Theorem 1 in either its special or its more general form is unsatisfactory for use in seriation. The problem arises from the condition (i) that every triple of rows of A have a unique Q form. Thus in the example of pottery types, three of its rows can be permuted into a Q form in essentially two quite different ways a6

45

35

5

15

a~

45

30

0

25

al

45

30

0

25

a6

45

35

5

15

a2

95

5

0

0

a2

95

5

0

0

i.e., one is not the inverse of the other. Here although condition (i) of Theorem 1 is not satisfied the conclusion is since A is pre-Q. So Theorem 1 is not general enough. As we noted in the original article [5], rows of a triple do not satisfy the uniqueness property if they are too 'similar' to each other (as here) or if they are too 'dissimilar' and have little or no types in common. Both readily occur in practice. Consider the following P matrix

A =

1 1 1

The first three rows can be ordered in two ways: 1

0

0

1

1

0

1

1

0

1

1

1

1

1

1

1

0

0

and both are P matrices and so the uniqueness in condition (i) of the above result [5] is not satisfied - yet all four rows together do have a unique P form! This shows that even if the resulting O matrix is unique, the uniqueness condition on its triples of rows is not necessary. Furthermore in practice, in seriation there may well be essentially different orderings of all the rows of an abundance matrix which are O matrices. In such cases the above result [5] will not apply since, as we remarked immediately after Theorem 1 the resulting O matrix is a unique O matrix under the conditions (i) and (ii). The aim in this paper is to develop a local/global theory along the lines stated above but which is complete in the sense that it covers all cases. This we believe will add to the structure of the theory of seriation. Also it will be developed within the framework of ternary relations, as developed by Fishburn [21, 22] and others, so that possibly the results will have wider meaning. A hint at the direction we take can be seen in the work of Menger cited above. In order to get the global result he did not demand that all quadruples of points in the semimetric space S be collinearly embedded in a Euclidean space but only certain of them.

SOME MATHEMATICAL PROBLEMS IN SERIATION

219

1.3. NOTATION Let A = {a, b , . . . , n} be a finite set. (A, R) denotes a ternary relation R on A (Roberts [24], Fishburn [22]). For economy we write (a~a2a3)• R in place of (al, a2, a3) • R. Throughout R is taken to be symmetric, i.e., if (a~a2a3) • R then (a3a2al) • R.

(i) (a~a2... ad) • R means that (atajak) • R for all 1 ~< i < j < k ~< d (an Rstring in Fishburn's terminology [22]). (ii) [ a l a 2 . . . a d ] • R means that there exists a permutation 7rE Sa such that ( a ~ l ) a ~ 2 ) . •. and)) • R. (iii) ( a l a 2 . . . ad)e R means that there is one and only one permutation 7r~ Sd such that (a~(1)a,~(2)... a,~(d))• R, apart from that giving rise to the complete inversion ( a , ~ a ) . . . a ~ 2 ) a , ~ l ) ) c R implied by the symmetry condition. If (ala2.. . aa)• R and ( a l a 2 . . . ad)~ R, we write { ( a l a 2 . . . ad)) e R. Thus ((abc)) ~ R means that b is strictly between a and c (Fishburn [22], p. 58). (iv) By [ a l . . . ad(b~.., b,,)]• R we mean an R-string with the at appearing among the bj in some order but with the b~ appearing in the order bl, bE,..., bin. We can also write this as [ C ( b x . . . b,,)], where C - {al . . . . , aa}. By [ ( a l . . . ad)(b~.., bin)] • R we mean an R-string with the at appearing among the bj with the members of each set appearing in the order given. Similar definitions apply to ( a , . . . ad(b~ . . . b,,))~ R, (C(bl . .. b,O)~ R and ( ( a l . . . aa)(bl . .. b,,))e R. (v) Finally we write ( a , . . . tit.., ad)~ R in place of ( a l . . . at-~at+~.., a d ) • R, i.e., precisely at is missing from the R-string, and similarly with the other brackets. a and b are said to be interchangeable with respect to R when (aataj) ~ R if and only if (bata~) c R, (ajaaj) c R if and only if (atbaj) ~ R and (aiaja) • R if and only if (a~a~b)• R. Clearly this gives rise to an equivalence relation E on A and (ALE, R) is a symmetric ternary system still. Throughout we can, if desired, work with this system in place of (A, R) using one representative per class. D E F I N I T I O N . If A is the set of rows of an abundance matrix, then we define (abe) e R if and only if bi ~>min{a~, ci} for all i, where a = ( a x . . . a~... a,,), b = ( b l . . . b t . . . b,) and ¢ = ( c 1 . . . c i . . . cn) are three rows of A. Thus, R is a (symmetric) ternary relation on the rows of A and (abe) • R if and only if these three rows are a Q matrix in this order. Throughout this article whenever the set A under discussion is the set of rows of an abundance (incidence) matrix, then the ternary relation (A, R) is the one defined here. In terms of ternary relations Theorem 1 becomes Theorem 3 (see also the remark stated immediately after Theorem 1).

220

R.R. LAXTON

T H E O R E M 3. L e t ( A , R ) be a symmetric ternary relation. If (i) (ata2a3) c R and (ii) [ala2a3a4]e R for all distinct al, a 2 , a 3 , a4 E A , then (ab . . . n ) ~ R . An exact translation of the previous proof gives a proof of this theorem. As we noted above, another proof of this using different though essentially equivalent conditions had already been given by Fishburn [21, 22]. Both proofs use the idea of extending an R-string of d elements to an R-string of (d + 1) elements and in this way a linear order on A is finally obtained; the uniqueness of this order arises from the local uniqueness condition (i). We seek to generalize this theorem for the reasons given at the end of the previous section.

2. The Main Theorem and Fixing-Strings The main theorem states T H E O R E M 4. Let (A, R ) be a symmetric ternary relation on at least three elements and Ul . . . . . Uk, k >! 2, be distinct elements of A such that k = 2 or for k > 2 , (ul . . . u k ) c R . If

(i) ( a b ( U l . . . ~. . . . uk)) e R and ( a ( u l . . . Uk)) E R and (ii) [ a b c ( u l . . . fii . . . uk)]e R and [ a b ( u l . . . uk)]e R /or all distinct elements a, b, c ~ A\{u~ . . . . , uk} and for all i = 1 . . . . , k, then

(A\ { u l , . . . , uk}(ul . . . uk)> ~ R. In words, this theorem says that when the two sets of local conditions are satisfied, A has a linear order (is itself an R-string) with the elements u l , . . . , uk in this order and the remaining elements distributed among them in some order. Before we prove this theorem we make one or two comments. DEFINITION. A k-tuple (ul . . . . . uk) satisfying the conditions of the theorem is called a fixing k-string, or fixing-string for short, for A. If A = {ul} we define (ul) to be a fixing-string for A. Similarly if A = {u~, u2} we define (ut, u2) to be a fixing-string for A. Notice that the uniqueness of the resulting linear order (A\ {u~ . . . . , uk} ( u l . . . uk))e R of all the elements of A is only relative to the order in the fixing-string. If another ordering of ul . . . . . Uk, other than a complete inversion of its elements, gives rise to a fixing-string for A, then a different linear ordering of A is obtained. Indeed there may exist different fixing-strings for A. Thus, for example, if A ={at, a2, ar} (see the introduction), then since both (a~a2ar)~ R and (ala6~) ~ R, uniqueness is lacking and so the second part of condition (i) of the theorem cannot be satisfied by any pair of elements and so A has no fixing pair. Trivially all three elements are fixing-strings for A but in two quite distinct ways. Clearly if [ a b . . . n] ~ R , then A has a fixing n-string - all n elements of A.

SOME MATHEMATICAL PROBLEMS IN SERIATION

221

This may be the only possible fixing-string as the above example shows. T h a t is one extreme. T h e other extreme is implied by the original theorem, T h e o r e m 3. This says that when certain conditions are valid a n y t w o distinct elements of A form a fixing 2-tuple for A. Observe that if the conditions of T h e o r e m 4 are met then ( B ( u t . . . Uk)) C R for any subset B of A \ { u l . . . . , Uk}, since this merely omits some elements from A\ ( u l , . . . , Uk}. T h e o r e m 4 is proved in a series of lemmas. L E M M A 1. I f [al.

• •

a i . . . a j . . . am] e R, ( ( a l . • • t i i . . . a j . . . a~)) e R

and ((ax . . . a, . . . Ct~ . . . a m ) ) e R w i t h ] >- i + 2, then ( ( a l . . . al . . . aj . . . a,,)) c R . Proof. Let (a,,
. . (t,,~u).

. . a~).

. . a~m))

e R

and (a,,o) • • • a,,t,) • • • fi,,tv) • • • a,,t,,)) ~ R. By the uniqueness conditions of the lemma and the symmetry of R and since 1 or m is in each R-string, we can take ¢r to be the identity map on { t , . . . , m}\ {i, j}. Thus (at • • • ai-lti,,t,)a~+~ • • • a j - t a ~ o ) a i + t . . ,

am) ~ R

and (at...

a i - l a ~ u ) a i + l . . . a j - l a ~ ( t , ) a j + l • . . am) E R .

Now since j - 1 / > i + 1 it follows that ~ ( u ) = i and ~ v ) = j also by the stated uniqueness. Thus ( ( a l . . • a i . . . a t . . . a,,)) ~ R. D E F I N I T I O N . If [ a l . . . a i . . . a t . . . a,n] c R and j/> i + 2, we call ( ( a t . . . t i i . . , a j . . . am)) c R and ( ( a l . . . ai... ~j... am)) c R a d e f i n i n g p a i r for ( ( a l . . . a i . . . at... am))C R. L E M M A 2. U n d e r the conditions o f the t h e o r e m ( a b ( u ~ . . . uk)) e R for distinct a, b e A\ { U l , . . . , Uk}. Proof. [ a b ( u l . . . uk)] E R by condition (ii) of the theorem; write this in the form ( b i b 2 . . . bk+lbk+2). By condition (i), ( ( b 2 . . . bk+lbk+2))e R and ( ( b t b 2 . . . bk+t)) R (irrespective of whether a or b or a u~ has been excluded). Since k + 2 i> 4 > 1 + 2 these are a defining pair for ((bl . . . bk+2)) ~ R by L e m m a 1, as required. By means of this lemma a binary relation < will be defined on A. < will, of course, depend on the k-tuple (Ul . . . . . uk).

222

R.R. LAXTON

(a) Let a and b be two distinct elements of A \ { u s , . . . , Uk}. Then by condition (ii) of the theorem and the lemma one and only one of [(ab)(Ul . . . Uk)] ~ R ,

[(ba)(uz . . . uk)] c R

is true. Put a < b if it is the first and b < a if it is the second. (b) P u t u i < u j i f l ~ < i < j ~ < k . (c) ( a ( u l . . . Uk)) ~ R for a ~ R\ {ul . . . . , Uk} by condition (i). if ( ( a u l . . . Uk)) R put a < u d for all d = l . . . . . k. If for some i, l~ ua for all d = 1 . . . . . i and a < ua for all d = i + 1 , . . . , k. If ( ( U l . . . uka)) ~ R put ua < a for all d = 1 , . . . , k. This completes the definition of the binary relation < on A. Since one and only one of a < b, b < a is true for all distinct a, b ~ A, it is asymmetric and complete (and irrettexive since a < a is false for all a ~ A). L E M M A 3. < is transitive on A under the conditions o f the theorem. Proof. The proof involves a number of cases. Let a < b and b < c. (a) Let a, b, c c A \ { U l , . . . , Uk}. Thus [ ( a b ) ( u l . . . uk)]c R and [(bc) ( U l . . . Uk)] S R. Exactly one of [ ( a c ) ( u l . . . Uk)] ~ R or [ ( c a ) ( u l . . . Uk)] S R; tO prove that a < c it needs to be the former. Let ( U l . . . u H a u i . . . Uj_lbUs . . . Uk)~ R and

(1)

(ul...

U g _ l b U s . . . Uh--lCUh... Uk) C R

with h >/g >/i. From these and the uniqueness condition (i) of T h e o r e m 4, ((ul...ui-lbus...uk))cR and ( ( u l . . . u s - l b u g . . . U k ) ) E R and so j = g . Thus, (ul . . . u H a u i

... u~-lbui. .. uk)~ R

and

(2)

( U l . . . U j - l b U i . . . U h - l C U h . . . Uk) e R and again from these and the uniqueness condition (i), ((uz...Ui-laui...Uk))CR

and

((Ul...Uh-lCUh...Uk))~R

(3)

with h >~ g = j >~ i. Let h >I i + 1. Thus a < ui <~ Uh-~ < C and since [ a c ( u l . . . Uk)] C R , these relations in (3) form a defining pair for ((Ul . . . u H a u i . . . Uh-lCUh... Uk)) C R . Thus, a
Let h = i. T h e n h = j = i and so in this case relations in (2) become (Ul...

u~-labui..,

uk)~ R

and

(ul...

Ui-lbCUl... u~)~ R.

(4)

Say i - 1/> 1. From these and the uniqueness condition (i) of the theorem, ((u2...uHabui...uk))cR and ( ( u 2 . . . u i - l b c u ~ . . . u k ) ) c R . These together

SOME MATHEMATICAL PROBLEMS IN SERIATION

223

with [ a b c ( u 2 . . . u k ) ] • R given by condition (iS) are a defining pair for ( ( u 2 . . . u ~ _ ~ a b c u ~ . . , u k ) ) ~ R which with the uniqueness condition (i) imply that ( ( u 2 . . . u H a c u ~ . . , u k ) ) ~ R . Also, the first of the relations in (4) with the uniqueness condition (i) gives ((Ux... U ~ - l a u i . . . U k ) ) • R . These together with [ac(ul... uk)]• R given by condition (iS) are a defining pair for ((UlU2 • • • Ui-laCUi • • • Uk))E R . Thus a < c in the case i - 1/> 1. Say i = 1. The relations in (3) become (abUl...

uk)• R

and

(bCUl...

(5)

Uk)• R.

From the uniqueness condition (i), and since k i> 2, we get

((abUl...

Uk--1)) •

R

and

uk-1))• R.

((bCUl...

(6)

Since [ a b C ( U l . . . Uk-1)] • R by condition (iS), the relations in (6) are a defining pair for ((abCUl . . . Uk-1)) • R. This and the uniqueness condition (i) again imply that ( ( a c u l . . . uk-1))• R. The first relation in (5) implies ( ( a u l . . . U k ) ) • R by condition (i). Since k t> 2 [ a c ( u l . . . UR)] • R these two relations form a defining pair for ( ( a c u l . . . Uk)) • R . Thus a < c again. This completes the proof for a, b, c • A\ {ul . . . . , uk}. (b) Let a, b • A\ {ul . . . . . uk} and c = uh for some h, 1 ~< h <~ k. As previously in part (a) we conclude from the relations in (1) that g = / to give h 1> i and (ul...

ui-laui..,

us-lbus...

Uh-lUh...

Uk)• R

and (Ul.-- U i - l b U s . . .

Uh--lUh . . . U k ) •

R.

(7)

From the first of these and the uniqueness condition (i) we get ( ( U l . . . u i - l a u ~ . . . U s - l U j . . . Uh . . . U k ) ) • R and so a < uh = c, as required.

(c) a • A\ {ul . . . . , uk}, b = us and c =

Uh, k >! h > g >t 1.

In this case the first relation in (1) is ( u l . . . a . . . u s . . . Uh • • • Uk) • R which by condition (i) implies ((Ul . . • a . . . u s . . . Uh . . . Uk)) E R . Hence, a < Uh = C, again. (d) Finally, if a = ui, b = u s = u s and c = Uh, h > j > i then a < c immediately. This completes the proof of the Lemma. Since < is transitive, complete and asymmetric on A, it is a transitive tournament and so defines a u n i q u e linear order on A [25]. Without loss of generality, let this be a < b < . . . < Ul < . . . < Uk < • • • < n. It has to be shown that this implies ( a b . . . u l . . . Uk . . . n ) • R . L E M M A 4. I f d < e < f , t h e n (de]') • R . P r o o f . Since d < e and e < f we have h/> j I> i

224

R.R. LAXTON (Ul

• • •

u~-ldu, . . . ui_aeuj . . . uk) ~ R

and (ul...

(8)

Us-leu~... Uh-1]:Uh... Uk) • R ,

where we have employed the same argument as at the beginning of the proof of Lemma 3 to deduce that e is in the same position in both relations (see below (1)). There are two cases to consider. (a) i > 1. From (8) and the uniqueness condition (i) we get ( ( i l l . . . dui . . . Uj_leui . . . u k ) ) • R and ((/~1

• . •

U j - l e u j . . . U h - l f U h . . . Uk))• R.

Since [ d e f ( u l . . . uk)] • R by condition (ii) these are a defining pair for ((ill . . . d . . . e . . . f . . . Uk)) • R (.f is missing in the first and d in the second relation and e is between them so that the conditions of Lemma 1 are satisfied). Hence, the triple (def) • R also. (b) i = 1. The relations in (8) become (dul . . . u j - l e u i . . , uk) • R

and

(ul . . . u j - l e u s . . .

Uh--lfUh

..

.

Uk) • R .

Again, dropping Ul from these we have ((drip... u j _ ~ e u j . . . Uk))• R

and ((fii... u j _ ~ e u j . . . U h - I [ U , . . . Uk))• R

by the uniqueness condition (i). By the same argument as in (a) these, with [ d e f ( u l . . . uk)]• R, form a defining pair for ( ( d i l l . . . e . . . [ . . . U k ) ) • R and so (deD • R agai n. This proves that ( a b . . . U l . . . u k . . . n) • R . Now with u l , . . . , uk in this fixed order, no other relation among a, b, . . . . n is possible since the ordering d 'to the left' of e in this relation gives d < e and < is asymmetric. Thus ((ab . . .

Ul.

,.

Uk . ..

n))

•

R.

This completes the proof of Theorem 4. As we observed above, if A = {a, b , . . . , n} and [ a b . . . n] • R , then in some order all the n elements are a fixing n-tuple for A. DEFINITION. If [ a b . . . n] • R denotes by p = p ( A , R ) the least k such that A has a fixing k-string and call p the fixing n u m b e r of (A, R). If [A[ = 1, 2 we set p ( A , R ) = 1, 2, respectively. Also put r = r ( A ) = n - p and call r the (linear) rigidity number of (A, R). Clearly r(A, R) = 0 if IA I = 1 or 2 and generally r ( A , R) = 0 if and only if all the elements of A provide the only fixing-string of A. The maximum linear rigidity occurs when r = n - 2. I L L U S T R A T I V E E X A M P L E S . The ternary relation R is that between the rows of an abundance matrix (see the definition before Theorem 3). A = {al, a2, a3, a4, as}.

SOME MATHEMATICAL PROBLEMS IN SERIATION

225

Example 1 al = ( 1 1 1 0 0 0 ) a4 =

(001111)

a2 = (111100)

a3 = (011110)

a5 = (000111)

((ala2a3a4as)) c R. Also ((aiajak)) ~ R for all i, /, k with 1 ~< i < j < k ~< 5. Hence, any pair (a~, aj), i # j, forms a fixing 2-string for A. Thus p = 2 and r = 3.

Example 2 al - ( 1 0 0 )

az = ( 1 1 0 )

a4 : ( 0 1 1 )

as = (001)

a3 = (111)

and ((ala2a3a4as)) E R. Now ((a3a4as))¢R, ((ala4as))¢R, ((alazas))¢R ((ala2a3)) ~ R and since these triples include all elements of A, there can be no fixing pair for A (condition (i) will not be satisfied). But ((aiajakat)) s R for all 1 ~ < i < j < k < l ~< 5 and so any triple of rows of A ordered as shown forms a fixing 3-string for A. Thus p = 3 and r = 2.

Example 3 az = ( 1 0 0 0 )

a2 = ( 1 1 0 0 )

a4 = (0011)

a5 = (0001)

a3 = ( 0 1 1 0 )

((aiaEa3a4as)) c R. Only ((ala2a3a4))~ R and ((a2a3a4as))c R among the quadruples in A and so each pair (al, aj), i < j, is in some quadruple of distinct elements with (a~a~aka~))¢ R. Thus, A can have no fixing 3-string but, for example, (a~a2a3a4) forms a fixing 4-string for A. Thus p = 4 and r = 1.

Example 4 al = ( 1 0 0 0 0 )

a2 = ( 0 1 0 0 0 )

a4 = (00010)

a5 = ( 0 0 0 0 1 )

a3 = ( 0 0 1 0 0 )

Clearly (a~a~aka~am) ~ R for any order of the elements and so all the elements of A will need to be fixed in some order to form a fixing 5-tuple for A. Thus p = 5 and r = 0. In Example 2 above ((a~a2a3a4as))~ R, i.e., the linear order of A is unique, apart from complete inversion of course. (a3a4as) ~ R and is a defining triple but ((a3a4as)) d R. The reason the resulting linear ordering of A is unique is that the triple is contained in a quadruple, (a2, a3, a4, as) and ((a2a3a4as))c R. This is a particular case of the following result. T H E O R E M 5. Let A = {a, b . . . . . n} with [ a b . . . n] ~ R.

(i) If

( U l . - - //-/t . . . Uid Uk) E R and (ui~ . . . uid) is a fixing string of A, then (Ul • • • ui, . . . u~ . . . Uk) is a fixing string of A. (ii) Cab... n) c R if and only if p = 2 or A contains a fixing string ( U l . . . Uk) with ( ( u l . . . uk))c R. . . .

226

R . R . LAXTON

Proof. (i) Let (ulu2... Uk) as a (B(ul...uk))eR ( C ( v l . . . vt))~ R

(v~...ul)cR

be an R-string containing a fixing string substring. As we remarked after the statement of Theorem 4, for any B ~ A \ { u l . . . u k } . Hence, ( ( V l . . . v l ) ) c R and so for any C ~_ A\{vL . . . . . vl}. Hence, the uniqueness condition (i) of the theorem is true and condition (ii) is true simply by virtue of [ab ... n] ~ R. Thus (vl ... vl) is a fixing string of A. (ii) If p = 2 and (uxu2) is a fixing string for A, then by Theorem 4 (A\ {Ul, u2}(ulu2))c R. But any linear ordering of A will have ul and u2 in the order (Ul u2) or (u2 ul), and since both fix A uniquely, and as one is the inverse of the other, there can be only one linear ordering and its complete inverse. If (ul . . . uk) ~ R is a fixing string with ( ( u l . . . uk)) c R then any linear orderings of A must have Ul . . . . . Uk in this order (or its complete inverse) and so be fixed by (u~... uk). Hence, the result. The converse is obvious by taking (ab... n) as a fixing string.

Example 5. In the pottery example given in the introduction, ((asa3a6ala4a2)) c R by Theorem 5 since {al, as} is a fixing pair. Thus p - - 2 and r--4. On the other hand, the pair {a2, as} is not a fixing pair since (aEa4as) e R and (azasa4) s R. This is because a2 and a4 are abundance rows of two levels with very similar contents. Example 6. Flints from Mesolithic sites in Southern England [26]. bl = (85,

3,

12,

0,

0,

0,

0)

bz=(67,

10,

23,

0,

0,

0,

0)

b3 = (26,

40,

8,

0,

0,

26,

0)

(26,

29,

8,

3,

0,

33,

1)

b5=(20,

3,

4,

42,

18,

0,

13)

(20,

1,

4,

13,

58,

0,

4)

b4 --

b6 =

Here there are no defining pairs or triples. {bl, b2, b4, bs} is a defining quadruple, thus p = 4 and r = 2. Thus, whereas the pottery levels example has a low fixing number, the lowest it can possibly be, and correspondingly a high linear rigidity, the mesolithic sites example has a comparatively high fixing number and corresponding a very low linear rigidity. The fixing number differentiates between these two linear sequences. In practice, too, the low fixing number for the pottery reflects the fact that the data comes from a well defined stratographic sequence of levels which, the excavator remarked, showed little if any signs of serious disturbance [2] whilst the high fixing number for the mesolithic example reflects the fact that there are but six sites spread throughout Southern England and covering a wide time span. Interestingly, some of these sites have been dated by 14C; 7500 bc for bl, 7000 bc for bz and 6400 bc for b5 [26]. Hence, assuming these dates are firm, the archaeologist can accept (blb2bs)c R and the bl, b2, b5 are three of the four

SOME MATHEMATICAL PROBLEMS IN SERIATION

227

elements of the defining quadruple used. (The flint types have been grouped for illustrative purposes; only six sites were chosen so that comparison could be made with the pottery example; see [26] for further details.) In practice, it is advantageous to have a low linear fixing number p. For if from external evidence or otherwise an archaeologist is able to accept, or even suggest, that (ul... up) e R corresponds to the correct chronological ordering of these few provenances and if these form a fixing p-string for the set A of all the provenances, then relative to this accepted order of a few, a unique linear ordering of all elements of A will be obtained.

3. Products and Representations Given (A, R) with A = {a, b . . . . . n} it is of some importance to have ready criteria to determine if l a b . . , n] ~ R. Two properties are especially useful in this respect; if A has a product structure so that knowledge about the components can be used and if A has a functional representation (cf. Roberts, [24], Ch. 5 and 3, respectively). (A, R) has both of these in the seriation problem, since the objects a~ of A are vectors in some R" and functional representations of (A, R) forms the basis of much of Kendall's work on seriation. We will develop the theory in the context of symmetric ternary relations. DEFINITION. A ternary relation (A, R) is said to be the intersection of the ternary relations (A,R~) . . . . ,(A,R,) provided (ala~aa)cR if and only if (ala2a3) ~ Ri for all al, a2, a3 E A and all i = 1 , . . . , r. Thus,

,z.' (A, R) = H (A, Ri). i=l

DEFINITION. A function S: A x A ~ [ 0 , ~ ) (A, R) if for al, a2, a3 E A,

is called a similarity function of

(i) S(at, a2)= S(a2, al) and (ii) S(al, a3) <~ S(al, a=), S(a2, a3) whenever (ala2a3)~ R (cf. Gelfand [27] where various similarity functions are considered and Kendall

[4]). DEFINITION. A similarity function S is said to be [aith[ul for (A, R) if for a l , a2, a3 E A

(iii) (ala2a3) c R whenever S(al, a3) ~< S(al, a2), S(a2, a3). In the case when S is faithful we write (A, R(S)). Let S be a similarity function defined on (A, R). A new ternary relation Rs can be defined on A given by (ala2a3)e Rs if and only if S(al, a 3 ) ~< S ( a l , a2), S(a2, a3). Then S is faithful for (A, Rs) and S is faithful for (A, R) if and only if R = R s . If (a~a2a3)cR, then (ala2a3)cRs and so R C_Rs; in general the

228

R.R. LAXTON

converse is not true; the difference usually arises in multidimensional spaces. On the other hand, in one-dimensional space the equality R = Rs is to be expected in seriation. Let (A, R) : N (A, R,) i=l

and let each R~ have a similarity function S~. Put

S(a, b) = ~, S~(a, b) for all a, b ~ A. i=l

If (ala2a3)cR, then (ala2a3)~Ri for all i and so Si(al,a3)<~Si(al,a2), Si(a2, a3) for all i. Consequently S(al, a3) ~< S(al, a2), S(a2, a3). Thus, S is a similarity function for (A, R) called the sum of the component similarity functions (cf. [24], Ch. 5). Such sums are important in the following case. Let A = {al . . . . . an} with ai = (ai . . . . . ai,) ~ R ' and each air >I O. Write (aiasak)~ Ra if and only if aja ~> min{aia, au} and put Sk(ai, a t) = min{a~, asa} (cf. Kendall [4]). Thus (aiasak) e Ra if and only if Sk(ai, ak) = min{aia, au} ~< min{a~, ask}, min{asa , au} = Sk(aias), Sk(as, ak) and so S~ is faithful for (A, Rd), d = 1 . . . . . r. Furtheremore, for this similarity function Sk, if (aiajak) d Ra, then aid < am, ak~, with strict inequality holding, and so sk(a~, ak) = min{alk, ask} > min{a~, aid}, min{asd, au} = Sd(a~, at), Sk(as , ak). (Here are elsewhere in the rest of this article the inequalities < and > are meant to be strict.) The sum S of these Sk is

S(ai, at) = ~ min{a~, asa}, d

Kendall's similarity function for an abundance matrix [4]. Another faithful similarity function S~ with this property is S~(al, aj) = a~ajd and for which the sum S' of the S~ is S'(al, a t) = ai • at, the inner product of ai and aj. Both this similarity function S' and Kendall's are straight generalizations of Kendall's original similarity function defined for an incidence matrix [4]. DEFINITION. A faithful similarity function S of (A, R) is said to be strong if (aiajak) ~ R implies S(ai, ak) > S(ai, aj) and S(a~, ak) > S(aj, ak). The following result is a general formulation of Theorem 2 (Kendall) discussed in the introduction.

SOME MATHEMATICAL PROBLEMS IN SERIATION

229

T H E O R E M 6. Let (A, R) --- ~ (A, R,) i=l

where S~ is a strong faithful similarity function for (A, R~), i = 1 , . . . , r, and let S be the sum of the Si. If (i) (aa... an)~ Rs and (ii) [a~ajak] c R for all 1 <~i < j < k <~n,

then (al ... a,)c R. Proof. Assume that ( a l . . . ~ ) ¢ R. Hence, there exists a 1 ~< i < j < k ~< n such that (a~ajak)¢ R and so by definition there exists an l, 1 ~< l~< r, for which (a~aiak) ¢ Rl. Since St is strong this implies that Sl(ai, ak) > Sz(aiai)

(10)

Sl( ai , ak) > S~(aiak).

(11)

and

But by condition (i) of the theorem (aiajak) c Rs and so since S is the sum of the

Sd, ~, Sa(a,,ak)<~ ~, Sn(a,,a,), d~l

~, Sd(ai, ak) ~< ~ Sd(ai, ak). d=l

(12)

d=l

(13)

d=l

Equations (10) and (12) imply that there exists a g, 1 <~ g <~ r, such that

Sg( a,.ak) < Sg( a,a~)

(14)

and (11) and (13) that there exists an h, 1 ~ h ~< r such that

Sh( a~ak) < Sh( ajak).

(15)

The faithfulness of Ss and (14) implies that (aiakai) ~ Rs, that of Sh and (15) that (asaiak) ¢ Rh and we know that (aiasak) ~ Rt. By symmetry this means that

[ a~aiak] ¢ Rg ('1 Rh i"1 RID N Ri = R i=l

and this contradicts condition (ii) of the theorem. The point of this theorem is that the global condition on Rs involves only nonnegative real numbers. It is of interest to notice that the strong condition on the component functions S~ is necessary. Many other quite natural similarity functions could be considered (Gelfand [27]) but they will not suffice for this result if they are not strong.

230

R.R. LAXTON

Let A = { a l , . . . , an} be an abundance matrix with rows ai = (air . . . . . a~,) and Sa(aj, a k ) = m i n { a ~ , aka} for each d = 1. . . . . r. Assume that in each column {ala, a2a . . . . . a,a} of A all the elements are distinct. Then given any nonempty subset B of rows of A for each d, there exists an a~ ~ B whose d - c o m p o n e n t a~a is least among all d-components of elements in B. That is,

Sa(ai, aj) = min{a~, aia} < min{aka, au} = Sd(ak , at) for all a t, ak, a~ e B with ak, a~ ~ al. This example from abundance matrices motivates the following definition. D E F I N I T I O N . (A, R) is said to be a set with minimal elements everywhere if it satisfies the following condition. Let for each nonempty subset B of A and each d, 1 ~< d ~< r, there exist a aa e B (depending on B and d) such that Sa(aa, b) < Sa(c, d) for all b, c, d ~ B and c, d ~ aa. Clearly aa is unique. An element a c B is called a minimal element of B if a = aa for some d, 1 ~< d ~< r. The first two of the three 3 × 3 matrices given in the introduction of this article have rows with minimal elements everywhere, the third does not. If A has minimal elements everywhere, so does any nonempty subset B of A. D E F I N I T I O N . If ( a l . . . an) ~ R, then ax and a, are called outside elements of this R-string.

[aiajak]~ R for some distinct a~, aj, ak C B and 1 <~i < j < k <~n. Proof. Say on the contrary that a~, as, ak are three minimal elements of A and that (aiajak)E R. Since a i is a minimal element, there exists a d such that Sa(a~ak) < Sa(aiak), which contradicts the fact that Sa(aiak) <~ Sa(aiaj), Sa(asak). L E M M A 5. If there are more than two minimal elements in B, then

T H E O R E M 7. Let

(A, R) = 0 (A, Rd), d=l

Sa be faithful, strong similarity functions for all d, S the sum of the Sa and A be a set with minimal elements everywhere. If [aiaiaka~] ~ R for all 1 <~ i < j < k < l <~ n, then [ab. . . n] ~ R. A n y minimal element of A is an outside element of any linear ordering of A. L E M M A 6. If al is a minimal element o r b = {al, a2,. . ., ah} and [ala2. . . ah] E

R, then al must be an outside element of any linear ordering of (B, R). Proof. Let 7r be a permutation of 2 . . . . . h such that (a~2). • • a ~ . . . a.n.(h))C R. If a~ is not an outside element of this R-string, then there exists some 2 <~ i < j ~< h such that (a~alai)~R. Thus for all d = l . . . . . r, (aialai)~Ra and so Sa(al, aj) <~ Sa(ai, al), Sa(al, ai). But since al is a minimal element of B, there exists an e, 1 <~ e ~< r, such that Se(al, a~) < Se(ai, as), which is a contradiction.

231

SOME MATHEMATICAL PROBLEMS IN SERIATION

Proof of Theorem 7. By Lemma 5, A = {al, a2 . . . . , a~} has at most two minimal elements since [a~aiak] c R for all I ~< i < ] < k ~< n. The proof is by induction on n; it is true for n -- 3 and 4. So take n 1> 5. (a) A has only one minimal element, say al. Let B = {a2 . . . . . a~}. R is a ternary relation for r

(B, R ) = j'~ (B, Ra) d=l

and Sd is a faithful, strong similarity function for (B, R~) for all d with S as their sum. Since B c A, it satisfies the conditions of the theorem and so by induction [ a : . . . a , ] ~ R; without loss of generality take ( a 2 . . . a , ) c R. We claim that (a~a2...a,)eR. For if not, there must exist i, j, 2<~i Sa(a~, a~), Sd(o,, aj), as Sa is faithful and strong, and so in particular, Sa(a~, a~)> Sa(a~, a~). But this contradicts the uniqueness of the minimal element a~ of A and the fact that each d has associated with it a minimal element of A. (b) A has two minimal elements, say a~ and a , . Let B = { a ~ , . . . , a , } ; by Lemma 5 it has at most two minimal elements and clearly a, is one of these. There are two cases to consider. (i) Assume that a, is the only minimal element of B. Let C = {al . . . . , a,_l}; by induction hypothesis [ a ~ . . . a,-1] ~ R and since al is clearly a minimal element of C, it must be an outside element in any linear ordering of C. Without loss of generality, let (a~a2...a,,_~)~R; we claim that (a~a2... a,-la,,)~ R. For if not either (a~aia,)~ R for some i, 2 ~< i ~< n - 1 or (a~aja,) ¢ R for some 2 ~< i < ] ~< n - 1. But since [a~aia,] ~ R and [aiaj~] ~ R by the conditions of the theorem, this contradicts Lemma 6 which states that the minimal elements must be outside elements of any linear ordering containing them. (ii) Assume that B has two minimal elements, a, and, say, a2. By the induction hypothesis [a2... an]E R and so by Lemma 6, ( a 2 a ~ ( 3 ) . . . a~(,_~)a,)c R for some permutation ~ of 3 . . . . , n - 1. We prove that (ala2a,,(3)... a~,,_~)a,)c R also. If this is not true, then either (alaja,) ~ R or (ala2ak)q~R for some l, l < / < n or k, 2 < k < n . The former is not possible by Lemma 6 since by assumption [ala2a,,]e R and al and a. are the minimal elements of A. So say (a~a2ak)¢R. By hypothesis [ala2aka,,]c R. Also ((a2akan))ER since a2 and an are the two minimal elements of B. Similarly since [a~a2a,,]eR and al and a, are the two minimal elements of A we have ((a~a2a,))~ R by Lemma 6. But then, given [ala2aka,,] ~ R, ( ( a l a 2 a n ) ) c R and ((a2aka,,))e R are a defining pair for (ala2aka,,)~ R (Lemma 1). Thus (ala~ak)e R, which is a contradiction. Consider the following B = {bl, b2, b3, b4, b5}

two

examples

A = {al, a2, a3, a4, as}

and

232

R.R. LAXTON al = (1, 1)

bl = (1, ~ )

a2 = (½, ½)

b2 = (½, ~)

83 = (1, 41-)

b3 = (~,¼)

1 1

1 1

a4 = (~, ~)

b4 = (~, ~)

a5 = ( 1 , ~6)

b5 = ( ~ , 1).

Each nonempty subset of elements of A has precisely one minimal element and A has many distinct linear orders. In B each nonempty subset has two minimal elements and B has precisely one linear order; the one shown. In fact the only fixing string for A is all five elements whilst the two minimal elements {bl, b5} of B are a fixing pair. This follows from the next theorem. T H E O R E M 8. With the assumptions as in the previous theorem (i) if every nonempty subset B of A has precisely one minimal element, then the

only fixing string of A is A itself, (ii) if every subset B of A with at least two elements has two minimal elements,

then the two minimal elements of A form a fixing pair. Proof (i) This follows immediately from the observation that if a l is the minimal element of B, { u l , . . . , uk}c_ B, (ul ... uk) c R and al ~ ui, i = 1 . . . . , k, then (alul... uk) ~ R and ( u l . . . u k a l ) C R. Hence, al must be in any fixing string of B. (ii) Let ul and u2 be the two minimal elements of A. By assumption [a~ajakuk]e R and [aiaiuzu2]e R, k = 1, 2. Now [aiajuk]c R. If a~ is the other minimal element of this set of three elements, then ((aiajui))~ R. Also ((ul aiu2)) R for any a~ e A. Hence, the conditions of Theorem 4 are fulfilled and so (ulu2) is a fixing pair for A. Example. The following abundance matrix is for five types of pottery from all the levels in a refuse mound (in the example used previously in the introduction the abundance matrix was of the contents of one house within the mound, [2]).

Level d (~p) e f g h i j k 1 m(bottom)

Row d e ! g h i j k ! at

4 6 8 18 23 32 39 49 62 87

6 14 19 48 54 48 43 30 20 3

86 75 71 30 20 5 0 0 0 0

0 0 1 3 3 14 18 21 18 10

4 4 2 0 0 0 0 0 0 0

SOME MATHEMATICAL PROBLEMS IN SERIATION

233

It is easy to check that the rows for levels g to m have two minimal elements for every subset with at least two elements. Thus ((g, h, i, j, k, !, m))e R and {g, m} is a fixing pair for them, by Theorem 8. Also ((de|)) e R since d and ! are minimal elements for these rows. By looking at column 4 we see immediately that ((defghijklm)) c R. It is then easy to check that {g, m} is, in fact, a fixing pair for all 10 rows. The lowness of the fixing number p = 2 and the correspondingly high linear rigidity r = 8 presumably reflects the fact that these are the proportions of painted pottery from a well-defined stratigraphic sequence of levels which, according to the excavator, show little signs of disturbance [2] and so is very closely associated with their chronological order.

4. Concluding Remarks As we remarked in the introduction, we have only been concerned with certain theoretical aspects of seriation, in particular, necessary and sufficient conditions on the rows of an abundance matrix in order that the matrix be a pre-O. In this limited respect we would seem to have been successful and what has emerged are two related invariants of R-strings, the fixing number and the linear rigidity, which, we hope to have demonstrated, have archaeological meaning and application for abundance matrices which are pre-O. We have not been concerned here with the practical problem of determining a permutation 7r of the rows of a pre-O matrix which results in a O-form for its rows. Also we have not considered how to deal with an abundance matrix which is not pre-Q. It may not be pre-Q for several reasons. Firstly, there may be a certain amount of 'noise' to the data which transforms a pre-O into a non pre-O matrix. Provided the 'noise' is not too great it should be possible to deal with this case (see [6, 7, 8] and the references contained in these), although a satisfactory definition of an almost 'pre-O' matrix has not been given. Secondly, the matrix may not be data from provenances which have a chronological ordering. For example, the differences in their contents may reflect sociological or regional differences rather than chronological ones. More practically the differences in contents may reflect a mixture of these latter differences and the archaeologist is quite likely to be aware of this. In any event, an attempt to interpret the resulting data matrix as a pre-O or 'almost pre-O' to reflect chronological ordering would be quite erroneous. In this respect a possibly interesting way to discuss and interpret such data is to represent the set of similarities by means of an additive similarity tree or a sum of such trees (Hartigan [28], Sattath and Tversky [29]) instead of the more traditional spacial representation. As yet the author has not undertaken any investigation of the computational aspects of the ideas developed here, or implemented any of them on a computer. Clearly this needs to be done if the theory is to be used with large abundance matrices. The chapter on 'Automatic seriation' in Doran and Hodson [30] is relevant here, especially as the authors note that external evidence to help

234

R.R. LAXTON

arrange seriation units in a chronological sequence is often available. Finally we remark that although we have confined our attention entirely to the seriation of archaeological data, seriating data occurs in other disciplines, as well as archaeology. For example, it is applicable to psychology (Coombs and Smith [31], Hubert [32]), to the ordering of opinions (Roberts [17, 24]) and to genetics (Benzer [33]). In the latter Benzer was able to demonstrate by means of seriation that the arrangement of the units within a gene is linear. Acknowledgements My thanks are due to the Master and Fellows of Clare College for having me as a Senior Academic Visitor and to Professor D. Williams and his colleagues for making available to me the facilities of the Statistical Laboratory, University of Cambridge, during the Spring Term of 1986. I am also greatly indebted to the referees for their comments. References 1. Wilkinson, E. M.: 'Techniques of data analysis-seriation theory', Archaeo-Physica 5 (1974), 1-142. 2. Burgh, R. F.: 'Ceramic profiles in the western mound at Awatovi, North Eastern Arizona', Am. Antiquity 25 (1959), 184-202. 3. Kendall, D. G.: 'Some problems and methods on statistical archaeology', World Archaeology 1 (1969), 68-76. 4. Kendall, D. G.: 'Incidence matrices, interval graphs and seriation in archaeology', Pacific J. Math. 28 (1969), 565-570. 5. Laxton, R. R." 'A measure of Pre-Q-ness with applications to archaeology', J. Archaeological Sci. 3 (1976), 43-54. 6. Hodson, F. R., Kendall, D. G., and Thutu, P.: Mathematics in the archaeological and historical sciences', Proceedings of the Anglo-Romanian Conference, Mamaia 1970, Edinburgh University Press, Edinburgh, 1971. 7. Marquardt, W. H.: 'Advances in archaeological sedation' in M. B. Schiffer (ed.), Advances in Archaeological Method and Theory, Academic Press, New York, 1978, pp. 266-314. 8. Ihm, P. and van Groenewoud, H.: 'Correspondence analysis and Gaussian ordination', in J. M Chambers, J. Gordesch, A. Klas, L. Lebart, and P.P. Sint (eds.) Lectures in Computational Statistics, Physica-Verlag, Vienna, 1984, pp. 5-60. 9. Robinson, W. S.: 'A method for chronologically ordering archaeological deposits', Am. Antiquity 16 (1951), 293-301. 10. Brainard, G. W.: 'The place of chronological ordering in archaeological analysis', Am. Antiquity 16 (1951), 301-313. 11. Kendall, D. G.: 'A statistical approach to Hinder Petrie's sequence dating', Bull. Intemat. Star. Inst. 40 (1963), 657-680. 12. Fulkerson, D. R. and Gross, O. A.: 'Incidence matrices and interval graphs', Pacific J. Math. 15 (1965), 835-855. 13. Kendall, D. G.: 'Seriation from abundance matrices', in [6], pp. 215-222. 14. Kendall, D. G.: 'Abundance matrices and seriation in archaeology', Zeit. Wahrscheinlickkeitstheorie 17 (1971), 104-112. 15. Shuchat, A.: 'Matrix and network models in archaeology', Math. Magazine 57 (1984), 3-14. 16. Roberts, F. S.: Graph Theory and its Applications to Problems of Society, CBMS-NSF Monograph No. 29, Society for Industrial and Applied Mathematics, Philadelphia, 1978.

SOME MATHEMATICAL PROBLEMS IN SERIATION

235

17. Roberts, F. S.: 'Indifference and sedation', in F. Harary (ed.) Topics in Graph Theory, Annals of New York Academy of Sciences, New York, 328, 1979, pp. 173-182. 18. Skrien, D.: 'Chronological orderings of interval graphs'. Discrete Appl. Math. 8 (1984), 69-83. 19. Menger, K.: 'Untersuchungen fiber allgemeine Metrik', Mathematische Annalen 100 (1928), 75-163. (Also in L. M. Blumenthal, Distance Geometry, Oxford University Press, London, 1953, pp. 90-121.) 20. Boneva, L. I.: 'An extension to seriation based on incidence matrices', Studia Math. Bulg. 7 (1984), 3-9. 21. Fishburn, P. C.: 'Betweeness, orders and interval graphs', J. Pure Appl. Algebra 1 (1971), 159-178. 22. Fishburn, P. C.: Interval Orders and Interval Graphs, Wiley, New York, 1985, pp. 57-75. 23. Varecza, A.: 'Are two given elements neighbouring?', Discrete Math. 42 (1982), 107-117. 24. Roberts, F. S.: Measurement Theory, with Applications to Decisionmaking, Utility and the Social Sciences, Addison-Wesley, Reading, Mass., 1979, pp. 242-243. 25. Roubens, M. and Vincke, P.: Preference Modelling, Lecture Notes in Economic and Mathematical Systems, Springer-Verlag, Berlin, 1985, pp. 11-18. 26. Jacobi, R. M., Laxton, R. R., and Switsur, V. R.: 'Seriation and dating of Mesolithic sites in Southern England', Revue D'Archemetrie 4 (1980), 165-173. 27. Gelfand, A. E.: 'Rapid sedation methods with archaeological applications', in [6], pp. 186-201. 28. Hartigan, J. A.: 'Representation of similarity matrices by trees', J. Am. Stat. Assoc. 62 (1967), 1140-1158. 29. Sattath, S. and Tversky, A.: 'Additive similarity trees', Psychometrika 42 (1977), 319-345. 30. Doran, J. E. and Hodson, F. R.: Mathematics and Computers in Archaeology, Edinburgh University Press, Edinburgh, 1975, pp. 267-284, 31. Coombs, C. H. and Smith, J. E. K.: 'On the detection of structures in attitudes and developmental processes', Psychological Rev. 80 (1973), 337-351. 32. Hubert, L.: 'Some applications of graph theory and related non-metric techniques to problems of approximate sedation: the case of symmetric proximity measures', British J. Math. Star. Psychology 27 (1974), 133-153. 33. Benzer, S.: 'On the topology of the genetic fine structure', Proc. Nat. Acad. Sci. 45 (1959), 1607-1620.