Portal de Periódicos da CAPES

Incidence matrices, interval graphs and seriation in archeology

1969; Mathematical Sciences Publishers; Volume: 28; Issue: 3 Linguagem: Inglês

10.2140/pjm.1969.28.565

1945-5844

David G. Kendall,

Algorithms and Data Compression

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 Γs in each separate column, can be settled if one merely knows A through the symmetrised product A T A. 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 T A 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.