Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Name of this matrix property?
Replies: 1   Last Post: Sep 6, 2013 4:26 AM

 tyapca7@gmail.com Posts: 3 Registered: 9/6/13
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 off-diagonal elements are non-decreasing
> >"as you go towards the diagonal". Formally,

>
> > a_{i,j} >= a_{i,j+1} for i<j
> > a_{i,j} >= a_{i-1,j} for i<j
> > a_{i,j} >= a_{i,j-1} 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", "R-form" or the matrix is called and R-matrix.
> 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 pre-R. 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
> R-form.
> "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 pre-P matrix and S = A A' is an R matrix, then A is a P
> matrix".
>
> If the matrix is pre-P then the permutations needed to make it into P-form
> can be computed in O(n^2), [Fulkerson & Gross, 65].
>
> Gelfand has published a method of reordering a pre-R 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 permutation-based heuristics will find the R-form,
> if the matrix is pre-R.
>
> Much work has been done to define pre-P-ness, pre-R-ness and pre-Q-ness
> (unimodal abundance matrices), for matrices which do not have the P, R or Q
> properties. This makes the problem a "bit" harder (actually
> NP-complete). 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 D-A where D is positive and diagonal?)

>
> I don't know much more on R-matrices, only P-matrices 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="293-301",
> 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, 835-855.
>
>
> @incollection{Wilkinson:71,
> author="Wilkinson, Edward M.",
> title="Archaeological seriation and the travelling salesman problem",
> pages="276-283",
> 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",
> }
>
>
> @article{Wilkinson:74,
> author="Wilkinson, Edward M.",
> title="Techniques of data analysis - seriation theory",
> journal="Archaeo-Physika, Technische und naturwissenschaftliche
> Beitr{\"{a}}ge zur Feldarch{\"{a}}ologie",
> year="1974",
>
> volume="5",
> number="2",
> pages="3-142",
> }
>
> --
> 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.