Matrice de distance euclidienne

En mathématiques, une matrice de distance euclidienne est une matrice de taille n × n représentant l'espacement d'un ensemble de ${\displaystyle n}$ points dans un espace euclidien. Si l'on note ${\displaystyle A}$ une matrice de distance euclidienne et ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ des points sont définis dans un espace de dimension ${\displaystyle m}$, alors les éléments de ${\displaystyle A}$ sont donnés par

${\displaystyle {\begin{aligned}A&=(a_{ij});\\a_{ij}&=d_{ij}^{2}\;=\;\lVert x_{i}-x_{j}\rVert _{2}^{2}\end{aligned}}}$

où ${\displaystyle \|\cdot \|_{2}}$ désigne la norme euclidienne sur ${\displaystyle \mathbb {R} ^{m}}$. Ainsi, la matrice des distances euclidienne sera de la forme :

${\displaystyle A={\begin{bmatrix}0&d_{12}^{2}&d_{13}^{2}&\dots &d_{1n}^{2}\\d_{21}^{2}&0&d_{23}^{2}&\dots &d_{2n}^{2}\\d_{31}^{2}&d_{32}^{2}&0&\dots &d_{3n}^{2}\\\vdots &\vdots &\vdots &\ddots &\vdots &\\d_{n1}^{2}&d_{n2}^{2}&d_{n3}^{2}&\dots &0\\\end{bmatrix}}}$

Propriétés

Pour faire simple, l'élément ${\displaystyle a_{ij}}$ décrit le carré de la distance entre les ${\displaystyle i}$^ème et ${\displaystyle j}$^ème points de l'ensemble. Par les propriétés de la norme euclidienne, la matrice ${\displaystyle A}$ a les propriétés suivantes :

• Tous les éléments sur la diagonale de ${\displaystyle A}$ sont nuls (propriété de la séparation d'une distance, la distance séparant un point de lui même est nulle).
• La trace de ${\displaystyle A}$ est zéro (par la propriété ci-dessus).
• ${\displaystyle A}$ est symétrique (c'est-à-dire que ${\displaystyle a_{ij}=a_{ji}}$, un corollaire de la symétrie d'une distance).
• ${\displaystyle {\sqrt {a_{ij}}}\leq {\sqrt {a_{ik}}}+{\sqrt {a_{kj}}}}$ (par l'inégalité triangulaire)
• ${\displaystyle a_{ij}\geq 0}$
• Le nombre de valeurs uniques (distinctes) non nulles d'une matrice de distance euclidienne de taille ${\displaystyle n\times n}$ est borné supérieurement par ${\displaystyle n(n-1)/2}$ en raison de la symétrie et du fait d'avoir une diagonale nulle.
• En dimension m, le rang d'une matrice de distance euclidienne est inférieur ou égal à ${\displaystyle m+2}$ . Si les points ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ sont en position générale, le rang est exactement min(n, m + 2).

Voir également

• Matrice d'adjacence
• Coplanarité
• Géométrie de distance
• Matrice de distance
• Matrice aléatoire euclidienne
• L'échelle multidimensionnelle classique, une technique de visualisation qui rapproche une matrice de dissimilarité arbitraire par une matrice de distance euclidienne
• Déterminant de Cayley-Menger

Références

• James E. Gentle, Matrix Algebra : Theory, Computations, and Applications in Statistics, Springer-Verlag, 2007, 528 p. (ISBN 978-0-387-70872-0 et 0-387-70872-3, lire en ligne), p. 299