Vol. 28, No. 3, 1969

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 297: 1
Vol. 296: 1  2
Vol. 295: 1  2
Vol. 294: 1  2
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Vol. 290: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
Author Index
To Appear
 
ISSN: 0030-8730
Incidence matrices, interval graphs and seriation in archeology

David G. Kendall

Vol. 28 (1969), No. 3, 565–570
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 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
Milestones
Received: 11 January 1968
Published: 1 March 1969
Authors
David G. Kendall