Konstrukcja bazy z macierzy odległości między wektorami

[lastsigma]

Algebrę liniową już miałem dawno temu na studiach (informatyka).

Zastanawiam się nad następującym tematem:
Mam daną macierz odległości (Euklidesowej) między wektorami. Czy w oparciu o tą macierz można skonstruować bazę, której wektory będą jednostkowe i odległości między nimi będą takie jak w zadanej macierzy odległości?
Innymi słowy próbuję zamienić macierz odległości na zbiór wektorów jednostkowych i liniowo niezależnych. Czy ta konstrukcja jest możliwa i czy jest to jakiś znany problem?

Myślałem o takim podejściu że zaczynam od wektora \(\displaystyle{ \left\langle 1,0,..,0\right\rangle}\)
Następnie konstruuję wektor \(\displaystyle{ \left\langle v_{11},v_{12},..,0\right\rangle}\), który jest jednostkowy i jego odległość od \(\displaystyle{ \left\langle 1,0,..,0\right\rangle}\) jest zgodna z daną macierzą odległości. Następnie biorę wektor jednostkowy postaci \(\displaystyle{ \left\langle v_{21},v_{22},v_{23},..,0\right\rangle}\) i na podstawie odległości do wektorów już skonstruowanych wyznaczam jego współrzędne. Kontynuuję ten proces żeby wyznaczyć wszystkie wektory. Czy to działa? Czy jest na to jakiś znany algorytm?

[Dasio11]

Nie dla każdej macierzy istnieje taki zestaw wektorów.


Najpierw sformalizujmy pytanie: dana jest liczba naturalna \(\displaystyle{ n}\) i macierz

\(\displaystyle{ A = \begin{pmatrix} a_{11} & \ldots &a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \ldots & a_{nn} \end{pmatrix}}\)

o wyrazach rzeczywistych \(\displaystyle{ \left< a_{i j} : 1 \le i, j \le n \right>}\). Czy istnieje ciąg \(\displaystyle{ \left< v_i : 1 \le i \le n \right>}\) wektorów jednostkowych w \(\displaystyle{ \RR^n}\), taki że \(\displaystyle{ d( v_i, v_j ) = a_{ij}}\) dla \(\displaystyle{ 1 \le i, j \le n}\) ?


Istnieją oczywiste warunki konieczne, aby takie wektory istniały, wynikające z aksjomatów metryki:

\(\displaystyle{ $\begin{align*}
\bullet \, & d(u, u) = 0 \\
\bullet \, & d(u, v) = d(v, u) \\
\bullet \, & d(u, w) \le d(u, v) + d(v, w)
\end{align*}$}\)

dla dowolnych \(\displaystyle{ u, v, w \in \RR^n}\). Podstawiając za \(\displaystyle{ u, v, w}\) wektory \(\displaystyle{ v_i, v_j, v_k}\), otrzymujemy warunki, które muszą spełniać elementy macierzy \(\displaystyle{ A}\):

\(\displaystyle{ $\begin{align*}
\bullet \, & a_{ii} = 0 \\
\bullet \, & a_{ij} = a_{ji} \\
\bullet \, & a_{ik} \le a_{ij} + a_{jk}
\end{align*}$}\)

dla dowolnych \(\displaystyle{ 1 \le i, j, k \le n}\). Ponadto skoro wszystkie wektory \(\displaystyle{ v_i}\) są jednostkowe, tj. \(\displaystyle{ d( 0, v_i ) = 1}\) dla \(\displaystyle{ 1 \le i \le n}\), to podstawienie do aksjomatów metryki wektorów \(\displaystyle{ v_i, 0, v_j}\) za \(\displaystyle{ u, v, w}\) daje, oprócz warunków zachodzących automatycznie, dodatkowe ograniczenie \(\displaystyle{ a_{ij} \le 2}\).


Nie są to jednak warunki wystarczające. Dla macierzy

\(\displaystyle{ A = \begin{pmatrix} 0 & 2 & 2 \\ 2 & 0 & 2 \\ 2 & 2 & 0 \end{pmatrix}}\)

nie istnieje odpowiadający ciąg \(\displaystyle{ \left< v_1, v_2, v_3 \right>}\) wektorów jednostkowych w \(\displaystyle{ \RR^3}\).

[lastsigma]

Istotnie. Zdałem sobie sprawę, że na pewno te warunki konieczne z aksjomatów metryki będą musiały zachodzić. Bardziej mnie zastanawia jednak problem znalezienia tych wektorów, gdy to możliwe. No i oczywiście pozostaje pytanie o warunek konieczny i wystarczający.