Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Name of this matrix property?
Posted:
Sep 6, 2013 4:26 AM


On Thursday, 28 July 1994 18:48:48 UTC+2, Bo Arlif wrote: > boman@sccm.stanford.edu (Erik Boman) writes: > > >I have come across a class of matrices which I do not know what is called. > >They have the property that the offdiagonal elements are nondecreasing > >"as you go towards the diagonal". Formally, > > > a_{i,j} >= a_{i,j+1} for i<j > > a_{i,j} >= a_{i1,j} for i<j > > a_{i,j} >= a_{i,j1} for i>j > > a_{i,j} >= a_{i+1,j} for i>j > > >Does anybody know what this property is called? > > In archaeology, biology, psychology, social sciences and some other fields > its called "Robinson Form", "Rform" or the matrix is called and Rmatrix. > The property is named after the archaeologist Robinson (see > ref. below). The notation R was first used by D.G. Kendall and is used in > Archaeological Seriation. > > If the matrix can be permuted to Rform, then its called preR. If the > matrix is a similarity matrix constructed from a incidence > matrix/contingency table, then there is a close relationship between "the > consequtive 1's property"/"Petrie form" and the similarity matrix having > Rform. > "If A is a P matrix, then S = A A' is an R matrix". > The reverse is however not true. Further: > "If A is a preP matrix and S = A A' is an R matrix, then A is a P > matrix". > > If the matrix is preP then the permutations needed to make it into Pform > can be computed in O(n^2), [Fulkerson & Gross, 65]. > > Gelfand has published a method of reordering a preR matrix S to form a R > matrix. Its correctnes is however only proven if all elements off the > diagonal are distinct. Stronger results most probably exist. > > In practice all simple permutationbased heuristics will find the Rform, > if the matrix is preR. > > Much work has been done to define prePness, preRness and preQness > (unimodal abundance matrices), for matrices which do not have the P, R or Q > properties. This makes the problem a "bit" harder (actually > NPcomplete). The are strong relations between P and R forms and finding a > maximal hamiltonian path [Wilkinson, 71,74]. > > > > >Are there special theorems that hold for this class of matrices > >if A>=0? (or for DA where D is positive and diagonal?) > > I don't know much more on Rmatrices, only Pmatrices and Seriation. > > > >Thanks, > >Erik Boman > >boman@sccm.stanford.edu > > > REFERENCES > > @article{Robinson:51, > author="Robinson, W. S.", > year="1951", > title="A method for chronologically ordering archaeological deposits", > pages="293301", > journal="American Antiquity", > address="Salt Lake City", > volume="16", > } > > > Fulkerson, D.R. & Gross, O.A. (1965) Incidence Matrices and Interval > Graphs. Pacific Journal of Mathematics, 15, 3, 835855. > > > @incollection{Wilkinson:71, > author="Wilkinson, Edward M.", > title="Archaeological seriation and the travelling salesman problem", > pages="276283", > booktitle="Mathematics in the Archaeological and Historical Sciences", > editor="Hodson, F. R. and Kendall, David G. and Tautu, P.", > year="1971", > publisher="Edinburgh University Press", > address="Edinburgh", > } > > > @article{Wilkinson:74, > author="Wilkinson, Edward M.", > title="Techniques of data analysis  seriation theory", > journal="ArchaeoPhysika, Technische und naturwissenschaftliche > Beitr{\"{a}}ge zur Feldarch{\"{a}}ologie", > year="1974", > > volume="5", > number="2", > pages="3142", > } > >  > Bo Arlif, B.Sc., boar@diku.dk > Graduate Student at the University of Copenhagen,  Institute of > Computer Science (major) and Institute of Prehistoric and Classical > Archaeology (minor). >  > Bo Arlif, B.Sc., boar@diku.dk > Graduate Student at the University of Copenhagen,  Institute of > Computer Science (major) and Institute of Prehistoric and Classical > Archaeology (minor).
I've compiled a bibliography of seriation methods here: https://www.researchgate.net/publication/251571839_Bibliography_of_seriation_methods?ev=prf_pub in case you were interested. Best regards, Peter.



