Vol. 28, No. 3, 1969

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 307: 1  2
Vol. 306: 1  2
Vol. 305: 1  2
Vol. 304: 1  2
Vol. 303: 1  2
Vol. 302: 1  2
Vol. 301: 1  2
Vol. 300: 1  2
Online Archive
The Journal
Editorial Board
Submission Guidelines
Submission Form
Policies for Authors
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author Index
To Appear
Other MSP Journals
Incidence matrices, interval graphs and seriation in archeology

David G. Kendall

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

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 ATA. 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, AAT.

Thus ATA and AAT 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
Received: 11 January 1968
Published: 1 March 1969
David G. Kendall