Distance matrix

In general, a distance matrix is a weighted adjacency matrix of some graph. In a network, a directed graph with weights assigned to the arcs, the distance between two nodes of the network can be defined as the minimum of the sums of the weights on the shortest paths joining the two nodes.[2] This distance function, while well defined, is not a metric. There need be no restrictions on the weights other than the need to be able to combine and compare them, so negative weights are used in some applications. Since paths are directed, symmetry can not be guaranteed, and if cycles exist the distance matrix may not be hollow.

An algebraic formulation of the above can be obtained by using the min-plus algebra. Matrix multiplication in this system is defined as follows: Given two ${\displaystyle n\times n}$ matrices ${\displaystyle A=(a_{ij})}$ and ${\displaystyle B=(b_{ij})}$, their distance product ${\displaystyle C=(c_{ij})=A\star B}$ is defined as an ${\displaystyle n\times n}$ matrix such that ${\displaystyle c_{ij}=\min _{k=1}^{n}\{a_{ik}+b_{kj}\}}$. Note that the off-diagonal elements that are not connected directly will need to be set to infinity or a suitable large value for the min-plus operations to work correctly. A zero in these locations will be incorrectly interpreted as an edge with no distance, cost, etc.

If ${\displaystyle W}$ is an ${\displaystyle n\times n}$ matrix containing the edge weights of a graph, then ${\displaystyle W^{k}}$ (using this distance product) gives the distances between vertices using paths of length at most ${\displaystyle k}$ edges, and ${\displaystyle W^{n}}$ is the distance matrix of the graph.

An arbitrary graph G on n vertices can be modeled as a weighted complete graph on n vertices by assigning a weight of one to each edge of the complete graph that corresponds to an edge of G and zero to all other edges. W for this complete graph is the adjacency matrix of G. The distance matrix of G can be computed from W as above, however, Wⁿ calculated by the usual matrix multiplication only encodes the number of paths between any two vertices of length exactly n.

The value of a distance matrix formalism in many applications is in how the distance matrix can manifestly encode the metric axioms and in how it lends itself to the use of linear algebra techniques. That is, if M = (x_ij) with 1 ≤ i, j ≤ N is a distance matrix for a metric distance, then

1. the entries on the main diagonal are all zero (that is, the matrix is a hollow matrix), i.e. x_ii = 0 for all 1 ≤ i ≤ N,
2. all the off-diagonal entries are positive (x_ij > 0 if i ≠ j), (that is, a non-negative matrix),
3. the matrix is a symmetric matrix (x_ij = x_ji), and
4. for any i and j, x_ij ≤ x_ik + x_kj for all k (the triangle inequality). This can be stated in terms of tropical matrix multiplication

When a distance matrix satisfies the first three axioms (making it a semi-metric) it is sometimes referred to as a pre-distance matrix. A pre-distance matrix that can be embedded in a euclidean space is called a Euclidean distance matrix.

Another common example of a metric distance matrix arises in coding theory when in a block code the elements are strings of fixed length over an alphabet and the distance between them is given by the Hamming distance metric. The smallest non-zero entry in the distance matrix measures the error correcting and error detecting capability of the code.

For example, suppose these data are to be analyzed, where pixel Euclidean distance is the distance metric.

Raw data

The distance matrix would be:

These data can then be viewed in graphic form as a heat map. In this image, black denotes a distance of 0 and white is maximal distance.

Graphical View

• Data clustering
• Computer Vision
• Min-plus matrix multiplication