Editing Distance matrix (section)

== Non-metric distance matrix ==
In general, a distance matrix is a weighted [[adjacency matrix]] of some graph.  In a [[Network (mathematics)|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 (where the number of steps in the path is bounded).<ref>[[Frank Harary]], Robert Z. Norman and Dorwin Cartwright (1965) ''Structural Models: An Introduction to the Theory of Directed Graphs'', pages 134–8, [[John Wiley & Sons]] {{mr|id=0184874}}</ref> 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 negative-weight cycles exist the distance matrix may not be [[Hollow matrix|hollow]] (and in the absence of a bound on the step count, the matrix may be undefined).

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 {{math|''n'' × ''n''}} matrices {{math|1=''A'' = (''a{{sub|ij}}'')}} and {{math|1=''B'' = (''b{{sub|ij}}'')}}, their distance product {{math|1=''C'' = (''c{{sub|ij}}'') = ''A'' ⭑ ''B''}} is defined as an {{math|''n'' × ''n''}} matrix such that 
:<math>c_{ij} = \min_{k=1}^n \{a_{ik} + b_{kj}\}.</math>
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 {{mvar|W}} is an {{math|''n'' × ''n''}} matrix containing the edge weights of a [[Graph (discrete mathematics)|graph]], then {{mvar|W{{sup|k}}}} (using this distance product) gives the distances between vertices using paths of length at most {{mvar|k}} edges, and so is the distance matrix of the graph when the step count bound is set to ''k''. If there are no loops of negative weight, {{mvar|W{{sup|n}}}} will give the true distance matrix, with no bound, because removing repeated vertices from a path cannot lower its weight. On the other hand, if ''i'' and ''j'' are on a negative-weight loop, {{mvar|W{{sup|k}}{{sub|ij}}}} will decrease without bound as ''k'' increases.

An arbitrary graph {{mvar|G}} on {{mvar|n}} vertices can be modeled as a weighted [[complete graph]] on {{mvar|n}} vertices by assigning a weight of one to each edge of the complete graph that corresponds to an edge of {{mvar|G}} and infinity to all other edges. {{mvar|W}} for this complete graph is the [[adjacency matrix]] of {{mvar|G}}. The distance matrix of {{mvar|G}} can be computed from {{mvar|W}} as above; by contrast, if normal matrix multiplication is used, and unlinked vertices are represented with 0, {{mvar|W{{sup|n}}}} would instead encode the number of paths between any two vertices of length exactly {{mvar|n}}. 
<!--
== Comparison with related matrices ==

=== Comparison with adjacency matrix ===
Distance matrices are related to [[Adjacency matrix|adjacency matrices]], with the differences that (a)&nbsp;the latter only provides the information which vertices are connected but does not tell about ''costs'' or ''distances'' between the vertices and (b)&nbsp;an entry of a distance matrix is smaller if two elements are closer, while "close" (connected) vertices yield larger entries in an adjacency matrix.
-->