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 $n$ points dans un espace euclidien. Si l'on note $A$ une matrice de distance euclidienne et$x_{1},x_{2},\ldots ,x_{n}$ des points sont définis dans un espace de dimension $m$, alors les éléments de $A$ sont donnés par

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

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

$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 $a_{ij}$ décrit le carré de la distance entre les $i$^ème et $j$^ème points de l'ensemble. Par les propriétés de la norme euclidienne, la matrice $A$ a les propriétés suivantes :

• Tous les éléments sur la diagonale de $A$ sont nuls (l'on parle alors de matrice creuse).
• La trace de $A$ est zéro (par la propriété ci-dessus).
• $A$ est symétrique (c'est-à-dire que $a_{ij}=a_{ji}$).
• ${\sqrt {a_{ij}}}\leq {\sqrt {a_{ik}}}+{\sqrt {a_{kj}}}$ (par l'inégalité triangulaire)
• $a_{ij}\geq 0$
• Le nombre de valeurs uniques (distinctes) non nulles d'une matrice de distance euclidienne de taille $n\times n$ est borné supérieurement par $n(n-1)/2$ en raison de la symétrie et du fait d'être creuse.
• En dimension m, le rang d'une matrice de distance euclidienne est inférieur ou égal à $m+2$ . Si les points $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