Distance matrix

In mathematics and graph theory, a distance matrix is a matrix A containing the pairwise distances (d) of a set of points a_1...n in the form [[d_ij]]. An example from every-day life are road distance tables that list the pairwise distances between towns (cf. illustration).

Illustration

Fig.1. An every-day example of a distance matrix listing road distances (in km) between important Russian tows.

In the case of stemmatics, the points a_1...n are text-samples from n witnesses. The mapping from a space of text-strings (w) to the distance matrix may be described as f: L(w×n) → ℝ(n×n). For n points this matrix will thus be an n×n-matrix. The distance between the points may be measured by any metric on the underlying space on which the points are defined. Therefore, the mapping f depends on the metric used, i.e. the kind of distance measure one chooses to use between the points. A simple example would be to define any change of a letter as a distance 1, so the distance between a=‘hortus’ and b=‘ortus’ would be d_ab = 1.

From the definition of a metric follow some basic properties: the matrix is symmetrical (the distance from a to b is by definition equal to the one from b to a); its trace is 0 (the distance between a and a must be 0 for all a); all entries d_ab ≤ 0, and equal to 0 if and only if a = b; for its entries the triangle inequality holds (d_ac ≤ d_ab + d_bc). As the matrix is by definition symmetrical, often only its lower left half is given (as in the illustration above) as the upper right half would be its mirror-image.

For manuscript traditions an adequate metric may be defined (one that reflects the psychological “distance” between readings) and a distance matrix calculated. The aim here should be to assign a large distance to changes that are unlikely to happen independently and may be hard to revert by a thinking copyist (cf. LeitfehlerLeitfehler), whereas trivial changes (like orthographic ones) should be assigned a very small distance. Cf. Leitfehler-based method.

There is standard software to approximate the optimal tree from a given distance matrix, e.g. in the open-source PHYLIP package. Note that no oriented tree (i.e. a  real stemma) can be gained from a distance matrix without additional information as the latter does not contain orientation. Cf. polarisation.

Cf. distance-based methods.

In other languages

DE: Distanzmatrix
 FR: matrice de distance
 IT: matrice di distanza

PR