Incidence matrices, interval graphs and seriation in archeology

David G. Kendall

Vol. 28 (1969), No. 3, 565–570

DOI: 10.2140/pjm.1969.28.565

Abstract

The work of Fulkerson and Gross on incidence matrices shows that the question, whether a given incidence matrix A can be so re-arranged by rows as to bring together all the 1’s in each separate column, can be settled if one merely knows A through the symmetrised product A^TA. Suppose it is known that such a row re-arrangement exists; it is proved here that A can then be re-arranged in the required way if one merely knows A through the dual symmetrised product, AA^T.

Thus A^TA and AA^T contain respectively (i) information sufficient to decide on the possibility or otherwise of such a re-arrangement, and (ii) information sufficient to determine a sorting algorithm.

Implications for archaeology are briefly discussed.

Mathematical Subject Classification

Primary: 05.25

Milestones

Received: 11 January 1968

Published: 1 March 1969