Reading a Finite Distance Table
A distance table on a finite set makes the metric axioms concrete: every condition can be checked using finitely many entries. The main discipline is to keep the checks separate. A table can satisfy symmetry and every triangle inequality yet fail to distinguish two different points; it can also have positive off-diagonal entries and fail only the triangle inequality.
Let \(X\) be a finite set. A proposed distance assigns a real number \(d(x,y)\) to each ordered pair \((x,y)\in X\times X\). The table has one row and one column for each point. Its entry in row \(x\), column \(y\), is \(d(x,y)\).
Because the codomain is \([0,\infty)\), every entry must be nonnegative. The identity axiom says more than “the diagonal is zero”: it requires \(d(x,x)=0\) and \(d(x,y)>0\) whenever \(x\ne y\). Symmetry means that entries reflected across the table’s diagonal agree. The triangle axiom must hold for every ordered triple; it is not enough to inspect only triples that look adjacent in the table.
A Finite Checklist and Its Justification
Proof. If the table defines a metric, nonnegativity follows from the specified codomain \([0,\infty)\). Taking \(x=y\) in the identity axiom gives \(d(x,x)=0\). Taking \(x\ne y\) gives \(d(x,y)\ne0\), and nonnegativity then gives \(d(x,y)>0\). Symmetry and the triangle inequalities are metric axioms, so all listed checks hold.
Conversely, suppose all the listed checks hold. The diagonal entries are zero, and every off-diagonal entry is positive. Therefore \(d(x,y)=0\) holds exactly when \(x=y\). The reflected entries agree, so the function is symmetric. The assumed inequalities give the triangle axiom for every triple. Together with the nonnegative entries, these are all the metric requirements. \(\square\)
This test also covers the degenerate finite sets. If \(X=\varnothing\), there is one function from \(X\times X\) to \([0,\infty)\), and every axiom holds vacuously because there are no points to test. If \(X\) has one point, the sole entry must be zero; the triangle axiom then holds because \(0\leq0+0\).
Once nonnegativity, zero diagonal, symmetry, and positive off-diagonal entries are established, the remaining work is the triangle check. In a symmetric table, a triple of distinct points has three side lengths. It is enough to compare the largest with the sum of the other two.
Proof. Write the three distances in increasing order as \(u\leq v\leq w\). If all three triangle inequalities hold, the inequality for the largest side gives \(w\leq u+v\). Conversely, suppose \(w\leq u+v\). The other two inequalities also hold: since \(u,v\geq0\), we have \(v\leq v+u\leq w+u\), and \(u\leq u+v\leq w+v\). These are the inequalities for the sides \(v\) and \(u\). Thus the largest-side test is equivalent to all three inequalities. \(\square\)
Repeated points do not require extra calculations once the diagonal is zero and symmetry holds. For example, the triangle inequality with \(x=z\) reads \(0\leq d(x,y)+d(y,x)\), which follows from nonnegativity. With \(x=y\), it reads \(d(x,z)\leq0+d(x,z)\), an equality. The case \(y=z\) is also an equality. Consequently, for a symmetric table that already passes the identity checks, only triples of distinct points need to be checked.
Worked Checks
Worked Example: A Table That Does Define a Metric
Let \(X=\{a,b,c\}\), and consider the symmetric table below.
| \(d\) | \(a\) | \(b\) | \(c\) |
|---|---|---|---|
| \(a\) | 0 | 2 | 4 |
| \(b\) | 2 | 0 | 3 |
| \(c\) | 4 | 3 | 0 |
Every entry is nonnegative. The diagonal entries are \(d(a,a)=d(b,b)=d(c,c)=0\), and the off-diagonal entries are \(2,4,3\), all positive. The reflected entries agree: \(d(a,b)=d(b,a)=2\), \(d(a,c)=d(c,a)=4\), and \(d(b,c)=d(c,b)=3\).
There is one triple of distinct points, with side lengths \(2,4,3\). The largest is \(4\), and the sum of the other two is \(2+3=5\), so \(4\leq5\). To check all three inequalities directly, \(4\leq2+3=5\), \(3\leq2+4=6\), and \(2\leq4+3=7\). Triples with repeated points satisfy the inequalities by the repeated-point calculation above.
Conclusion and check: the table defines a metric. In particular, the potentially tightest inequality is \(d(a,c)\leq d(a,b)+d(b,c)\); substituting the entries gives \(4\leq2+3=5\), as required.
Worked Example: A Triangle Inequality Fails
Keep \(X=\{a,b,c\}\), but use the symmetric table with \(d(a,b)=1\), \(d(b,c)=1\), and \(d(a,c)=3\), with zero diagonal.
| \(d\) | \(a\) | \(b\) | \(c\) |
|---|---|---|---|
| \(a\) | 0 | 1 | 3 |
| \(b\) | 1 | 0 | 1 |
| \(c\) | 3 | 1 | 0 |
All entries are nonnegative, the diagonal is zero, the off-diagonal entries \(1,1,3\) are positive, and the table is symmetric. But for the ordered triple \((a,b,c)\), the triangle inequality would require \(d(a,c)\leq d(a,b)+d(b,c)\). Substitution gives \(3\leq1+1=2\), which is false because \(3>2\).
Conclusion and check: this is not a metric. The witness is the specific triple \(a,b,c\): travelling from \(a\) to \(c\) has assigned distance \(3\), while the two table entries through \(b\) sum to \(2\). The other two sides of this triple do satisfy their inequalities: \(1\leq3+1=4\) and \(1\leq3+1=4\). One failed inequality is sufficient to reject the table.
Worked Example: Distinct Points at Distance Zero
On \(X=\{a,b,c\}\), set \(d(a,b)=0\), \(d(a,c)=2\), and \(d(b,c)=2\); reflect these entries across the diagonal and put zero on the diagonal.
| \(d\) | \(a\) | \(b\) | \(c\) |
|---|---|---|---|
| \(a\) | 0 | 0 | 2 |
| \(b\) | 0 | 0 | 2 |
| \(c\) | 2 | 2 | 0 |
The entries are nonnegative, the table is symmetric, and the diagonal entries are zero. The only triple of distinct points has distances \(0,2,2\). Its largest-side check is \(2\leq0+2=2\), so all three triangle inequalities hold: \(2\leq0+2=2\), \(2\leq0+2=2\), and \(0\leq2+2=4\).
Nevertheless, \(a\ne b\) while \(d(a,b)=0\). The identity axiom requires positive distance between every pair of distinct points, so the table is not a metric. Check: the problematic entry is the off-diagonal zero \(d(a,b)=0\), not a triangle inequality; the triangle test alone cannot establish the identity axiom.
Worked Example: A Symmetry Failure
On \(X=\{a,b,c\}\), put zero on the diagonal and use the following directed entries: \(d(a,b)=1\), \(d(b,a)=2\), and \(d(a,c)=d(c,a)=d(b,c)=d(c,b)=2\).
| \(d\) | \(a\) | \(b\) | \(c\) |
|---|---|---|---|
| \(a\) | 0 | 1 | 2 |
| \(b\) | 2 | 0 | 2 |
| \(c\) | 2 | 2 | 0 |
The entries are nonnegative, the diagonal entries are zero, and every off-diagonal entry is positive. But the pair \(a,b\) witnesses a failure of symmetry: \(d(a,b)=1\), whereas \(d(b,a)=2\), so \(d(a,b)\ne d(b,a)\). The table is therefore not a metric. There is no need to finish the triangle checks once a required axiom has failed.
A Reliable Routine and a Common Pitfall
For any proposed finite table, use the following order. It catches basic failures before spending time on every triple.
Confirm every entry is a real number in \([0,\infty)\). A negative entry cannot be a metric distance.
Verify that every diagonal entry is zero and every off-diagonal entry is strictly positive. Record the two distinct points if an off-diagonal zero occurs.
Compare each pair of reflected entries. If they differ, name the pair and both values.
For a symmetric table, consider each set of three distinct points once. Compare the largest of its three distances with the sum of the other two; if it is too large, state the triple and the failed inequality.
Common pitfall. A frequent wrong conclusion is: “The table is symmetric, has a zero diagonal, and passes every triangle check, so it is a metric.” That conclusion omits the requirement that distinct points have positive distance. In the third worked example, the triangle calculation \(2\leq0+2=2\) is correct, but \(a\ne b\) and \(d(a,b)=0\). The correction is to check all parts of identity: diagonal zero and off-diagonal strictly positive. Conversely, positivity and symmetry do not guarantee the triangle axiom, as the second example shows.
On a set with \(n\) points, there are only finitely many entries and triples to inspect. Symmetry and the largest-side reduction can shorten the work, but they do not replace the axioms: each check has a distinct purpose, and each failed check should be reported with its specific entry, pair, or triple.
Check Your Understanding
For each proposed table, identify the checks needed and give a specific witness if it is not a metric.
- On \(\{p,q\}\), the diagonal entries are zero and \(d(p,q)=d(q,p)=5\). Does this define a metric?
- Three distinct points have symmetric distances \(2,3,6\). Which triangle inequality fails, if any?
- Can a symmetric table with zero diagonal and positive off-diagonal entries fail to be a metric? State the remaining axiom that must be checked.
- On three points, the symmetric side lengths are \(1,4,5\). Use the largest-side test to decide whether this triple satisfies all triangle inequalities.
- What is the metric test on the empty set, and why are its axioms satisfied?