Proof of Proposition 5.10 — path distance matrix is nonsingular
ProvedGeometryOfGraphs.Cube.path_distance_matrix_nonsingulardeterminantsdistance-matricesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and index a path's vertices by . Its distance matrix , with , has nonzero determinant:
The paper cites this fact in the rank lower bound for even cycles. The matrix is zero and is excluded.
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace GeometryOfGraphs.Cube
/-- The distance matrix of a path with at least two vertices is nonsingular. -/
theorem path_distance_matrix_nonsingular (m : ℕ) (hm : 2 ≤ m) :
(Matrix.of (fun r s : Fin m =>
|((r : ℕ) : ℝ) - ((s : ℕ) : ℝ)|)).det ≠ 0 := by sorry
end GeometryOfGraphs.Cube
Source
N. Linial, E. London, Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), p. 233, proof of Proposition 5.10, citing [44] pp. 64–65; https://doi.org/10.1007/BF01200757
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.