9. Anti-Robinson Matrices for Symmetric Proximity Data
Society for Industrial and Applied Mathematics eBooks · 2006
Denoting an arbitrary symmetric n × n matrix by A = {aij}, where the main diagonal entries are considered irrelevant and assumed to be zero (i.e., aii = 0 for 1 ≤ i ≤ n), A is said to have an anti-Robinson (AR) form if after some reordering of the rows and columns of A the entries within each row and column have a distinctive pattern: moving away from the zero main diagonal entry within any row or any column, the entries never decrease. Generally, matrices having AR forms can appear both in spatial representations for a set of proximities as functions of the absolute differences in coordinate values along some axis or for classificatory structures that are characterized through an ultrametric. To illustrate, we first let P = {pij} be a given n × n proximity (dissimilarity) matrix among the distinct pairs of n objects in a set S = {O1, O2, …, On} (where pii = 0 for 1 ≤ i ≤ n). Then, suppose, for example, a two-dimensional Euclidean representation is possible for P and its entries are very well representable by the distances in this space, and thus pij ≈ ( x1i − x1j )2 + ( x2i − x2j )2 , where xki and xkj are the coordinates on the kth axis (for k = 1 and 2) for objects Oi and Oj (and the symbol ≈ is used to indicate approximation). Here, a simple monotonic transformation (squaring) of the proximities should then be fitted well by the sum of two matrices both having AR forms, i.e., { p ij 2 } ≈ { ( x1i − x1j )2 } +{ ( x2i − x2j )2 }. In a classificatory framework, if {pij} were well representable, say, as a sum of two matrices, A1 = {aij(1) } and A2 = {aij(2) }, each satisfying the ultrametric inequality, i.e., aij(k ) ≤ max{aih(k ), ahj(k) } for k = 1 and 2, then { pij } ≈ { a ij (1) }+ { a ij (2) } , and each of the constituent matrices can be reordered to display an AR form. As can be seen in Part II of this monograph, any matrix whose entries satisfy the ultrametric inequality can be represented by a sequence of partitions that are hierarchically related.