Background

One problem in archaeology is that of putting sites and artifacts in proper chronological order. Radiocarbon dating is only so accurate and sometimes local geological effects are difficult to adjust for when dating elements. Thus we need some way to determine local time ordering of sites and artifacts.

Suppose we have a dig site containing several (M) graves and in those graves we find different types of pottery and other artifacts. Suppose we place those items from all the graves into N different categories. Now, archaeologists make the assumption that two graves that are close together in time would be more likely to share artifacts, while ones that are farther apart would not. Equivalently, the more graves that artifacts share, the closer they are in time. This leads to a method of seriation.

Math

Taking the archaeologists data we can construct a M by N matrix A where A(i,j) = 1 if grave i contains artifact type j, and = 0 otherwise. There are two useful matrices we can compute from A: G = AA^T and V = A^TA. G is M by M and indicates the number of artifacts shared by two graves. V is N by N and indicates the number of graves shared by two artifacts.

Here's a simple case with M=4 graves and N=3 artifacts:

A = [1 0 1
     1 0 0
     0 1 1
     0 1 0]
G = A*A'
    2 1 1 0
    1 1 0 0
    1 0 2 1
    0 0 1 1
V = A'*A
    2 0 1
    0 2 1
    1 1 2

Using the assumption that having something in common means closer in time, we can use matrix G to put the graves in order by looking at how they share items. From G we see that (1,2), (1,3) and (3,4) share items while all other pairings don't. Thus since 3 & 2 are close to 1, but not close to each other, and 4 is close to 3 but not to 1, we have two possible orderings: 4-3-1-2 or its reverse. Hopefully some other information would tell us which was the more likely time ordering.

Repeating this same process with V, we see that the ordering of the artifacts is 1-3-2 or its reverse.

Exercises

Here's some data for a 10 grave, 13 artifact digsite. Put the graves and the artifacts in chronological order. Hint: once you've computed G (or V), make a graph using the matrix as the adjacency matrix, then you can see the possible orderings. There may be more than one reasonable answer.

	Artifact (1 means found in grave)
Grave	1	2	3	4	5	6	7	8	9	10	11	12	13
1	1	0	0	0	1	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	1	0	1	0	1	0	0
3	0	1	1	0	0	0	1	1	0	1	0	1	1
4	0	0	0	1	0	0	0	0	1	0	0	0	0
5	1	0	0	0	1	0	1	0	0	0	0	1	0
6	0	0	0	0	0	0	0	0	1	0	0	0	1
7	0	1	1	1	0	0	0	0	0	0	0	0	1
8	0	1	0	0	0	1	0	0	0	0	0	0	0
9	1	0	0	0	0	1	0	1	1	0	1	0	0
10	0	1	0	0	0	0	0	0	0	1	0	0	0