यूक्लिडियन दूरी मैट्रिक्स

गणित में, यूक्लिडियन डिस्टेंस मैट्रिक्स एक है n×n मैट्रिक्स (गणित) के एक सेट के अंतर का प्रतिनिधित्व करता है {{mvar|n}यूक्लिडियन अंतरिक्ष में } बिंदु (ज्यामिति)। अंक के लिए $x_{1},x_{2},\ldots ,x_{n}$ में k-विमीय स्थान ℝ^k, उनके यूक्लिडियन दूरी मैट्रिक्स के तत्व A उनके बीच की दूरियों के वर्ग द्वारा दिए गए हैं। वह है

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

कहाँ $\|\cdot \|$ यूक्लिडियन मानदंड को दर्शाता है ℝ^k.

$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}}$

(आवश्यक रूप से यूक्लिडियन नहीं) दूरी मैट्रिक्स के संदर्भ में, प्रविष्टियों को सामान्यतः सीधे दूरीअर्थात के रूप में परिभाषित किया जाता है, उनके वर्ग नहीं। चूंकि, यूक्लिडियन स्थितियोंमें, दूरियों के वर्गों का उपयोग वर्गमूलों की गणना से बचने और प्रासंगिक प्रमेयों और एल्गोरिदम को सरल बनाने के लिए किया जाता है।

यूक्लिडियन दूरी मैट्रिसेस ग्राम मैट्रिक्स (डॉट उत्पादों के मैट्रिसेस, उनके बीच वैक्टर और कोणों के मानदंडों का वर्णन करते हुए) से निकटता से संबंधित हैं। रैखिक बीजगणित के तरीकों का उपयोग करके उत्तरार्द्ध का आसानी से विश्लेषण किया जाता है। यह यूक्लिडियन दूरी मैट्रिसेस को चिह्नित करने और अंक पुनर्प्राप्त करने की अनुमति देता है $x_{1},x_{2},\ldots ,x_{n}$ कि इसका एहसास हो। एक बोध, यदि यह उपस्तिथ है, कठोर परिवर्तनों तक अद्वितीय है, अर्थात आइसोमेट्री | यूक्लिडियन अंतरिक्ष (रोटेशन (गणित), परावर्तन (गणित), अनुवाद (ज्यामिति)) के दूरी-संरक्षण परिवर्तन।

व्यावहारिक अनुप्रयोगों में, दूरियां शोर माप हैं या मनमाने ढंग से समानता माप अनुमानों से आती हैं (आवश्यक नहीं कि मीट्रिक (गणित))। लक्ष्य यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा ऐसे डेटा की कल्पना करना हो सकता है, जिसकी दूरी मैट्रिक्स किसी दिए गए असमानता मैट्रिक्स के साथ-साथ संभव हो - इसे बहुआयामी स्केलिंग के रूप में जाना जाता है। वैकल्पिक रूप से, डेटा के दो सेट पहले से ही यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा दर्शाए गए हैं, कोई पूछ सकता है कि वे आकार में कितने समान हैं, अर्थात, वे एक कठोर परिवर्तन से कितनी निकटता से संबंधित हो सकते हैं। दूरी-संरक्षण परिवर्तन - यह प्रोक्रस्ट्स विश्लेषण है। कुछ दूरियाँ गायब भी हो सकती हैं या बिना लेबल के आ सकती हैं (मैट्रिक्स के अतिरिक्त एक अनियंत्रित सेट या मल्टीसेट के रूप में), जिससे अधिक जटिल एल्गोरिथम कार्य हो सकते हैं, जैसे कि ग्राफ़ प्राप्ति समस्या या टर्नपाइक समस्या (एक रेखा पर बिंदुओं के लिए)।

गुण

इस तथ्य से कि यूक्लिडियन दूरी एक मीट्रिक (गणित) है, मैट्रिक्स है A में निम्नलिखित गुण होते हैं।

• मैट्रिक्स के विकर्ण पर सभी तत्व A शून्य हैं (अर्थात यह एक खोखला मैट्रिक्स है); इसलिए एक मैट्रिक्स का निशान A शून्य है।
• A सममित मैट्रिक्स है (अर्थात $a_{ij}=a_{ji}$).
• ${\sqrt {a_{ij}}}\leq {\sqrt {a_{ik}}}+{\sqrt {a_{kj}}}$ (त्रिकोण असमानता द्वारा)
• $a_{ij}\geq 0$

आयाम में k, यूक्लिडियन दूरी मैट्रिक्स में रैंक (रैखिक बीजगणित) से कम या उसके बराबर है k+2. यदि अंक $x_{1},x_{2},\ldots ,x_{n}$ सामान्य स्थिति में हैं, रैंक बिल्कुल है min(n, k + 2).

एक और यूक्लिडियन दूरी मैट्रिक्स प्राप्त करने के लिए दूरियों को किसी भी शक्ति से कम किया जा सकता है। अर्थात यदि $A=(a_{ij})$ एक यूक्लिडियन दूरी मैट्रिक्स है, तो $({a_{ij}}^{s})$ प्रत्येक के लिए एक यूक्लिडियन दूरी मैट्रिक्स है 0<s<1.

ग्राम मैट्रिक्स से संबंध

अंकों के अनुक्रम का ग्राम मैट्रिक्स $x_{1},x_{2},\ldots ,x_{n}$ में k-विमीय स्थान ℝ^k है n×n आव्यूह $G=(g_{ij})$ उनके डॉट उत्पाद (यहां एक बिंदु $x_{i}$ 0 से उस बिंदु तक वेक्टर के रूप में माना जाता है):

$g_{ij}=x_{i}\cdot x_{j}=\|x_{i}\|\|x_{j}\|\cos \theta$, कहाँ $\theta$ वेक्टर के बीच का कोण है $x_{i}$ और $x_{j}$.

विशेष रूप से

$g_{ii}=\|x_{i}\|^{2}$ की दूरी का वर्ग है $x_{i}$ 0 से।

इस प्रकार ग्राम मैट्रिक्स वैक्टर के मानदंडों और कोणों का वर्णन करता है (0 से) $x_{1},x_{2},\ldots ,x_{n}$.

होने देना $X$ हो k×n मैट्रिक्स युक्त $x_{1},x_{2},\ldots ,x_{n}$ स्तंभों के रूप में। तब

$G=X^{\textsf {T}}X$, क्योंकि $g_{ij}=x_{i}^{\textsf {T}}x_{j}$ (देख के $x_{i}$ कॉलम वेक्टर के रूप में)।

मैट्रिसेस जिन्हें विघटित किया जा सकता है $X^{\textsf {T}}X$, अर्थात्, सदिशों के कुछ अनुक्रमों के ग्राम आव्यूह (के स्तंभ $X$), अच्छी तरह से समझ गए हैं - ये ठीक सकारात्मक अर्ध निश्चित मैट्रिक्स हैं।

यूक्लिडियन दूरी मैट्रिक्स को ग्राम मैट्रिक्स से संबंधित करने के लिए, इसे देखें

$d_{ij}^{2}=\|x_{i}-x_{j}\|^{2}=(x_{i}-x_{j})^{\textsf {T}}(x_{i}-x_{j})=x_{i}^{\textsf {T}}x_{i}-2x_{i}^{\textsf {T}}x_{j}+x_{j}^{\textsf {T}}x_{j}=g_{ii}-2g_{ij}+g_{jj}$

अर्थात मानदंड और कोण दूरी तय करते हैं। ध्यान दें कि ग्राम मैट्रिक्स में अतिरिक्त जानकारी होती है: 0 से दूरी।

इसके विपरीत दूरियां $d_{ij}$ के जोड़े के बीच n+1 अंक $x_{0},x_{1},\ldots ,x_{n}$ के बीच डॉट उत्पाद निर्धारित करें n वैक्टर $x_{i}-x_{0}$ (1≤i≤n):

$g_{ij}=(x_{i}-x_{0})\cdot (x_{j}-x_{0})={\frac {1}{2}}\left(\|x_{i}-x_{0}\|^{2}+\|x_{j}-x_{0}\|^{2}-\|x_{i}-x_{j}\|^{2}\right)={\frac {1}{2}}(d_{0i}^{2}+d_{0j}^{2}-d_{ij}^{2})$

(इसे ध्रुवीकरण पहचान के रूप में जाना जाता है)।

लक्षण वर्णन

एक के लिए n×n आव्यूह A, अंकों का एक क्रम $x_{1},x_{2},\ldots ,x_{n}$ में k-आयामी यूक्लिडियन स्थान ℝ^k का बोध कहा जाता है A में ℝ^k यदि A उनकी यूक्लिडियन दूरी मैट्रिक्स है। कोई सामान्यता के नुकसान के बिना मान सकता है कि $x_{1}=\mathbf {0}$ (क्योंकि अनुवाद (ज्यामिति) द्वारा $-x_{1}$ दूरी बनाए रखता है)।

Theorem (Schoenberg criterion, independently shown by Young & Householder) —  A symmetric hollow n×n matrix A with real entries admits a realization in ℝ^k if and only if the (n-1)×(n-1) matrix $G=(g_{ij})_{2\leq i,j\leq n}$ defined by

$g_{ij}={\frac {1}{2}}(a_{1i}+a_{1j}-a_{ij})$

is positive semidefinite and has rank at most k.

यह पिछली चर्चा से इस प्रकार है क्योंकि G अधिक से अधिक रैंक का धनात्मक अर्धनिश्चित है k यदि और केवल यदि इसे विघटित किया जा सकता है $G=X^{\textsf {T}}X$ कहाँ X एक k×n आव्यूह। इसके अतिरिक्त, के कॉलम X में एक अहसास दें ℝ^k. इसलिए, किसी भी विधि को विघटित करने के लिए G एक अहसास खोजने की अनुमति देता है। दो मुख्य दृष्टिकोण चॉल्स्की अपघटन के प्रकार हैं या मैट्रिक्स के वर्ग रूट को खोजने के लिए eigendecomposition का उपयोग करना G, निश्चित मैट्रिक्स#अपघटन देखें।

प्रमेय का कथन पहले बिंदु को अलग करता है $x_{1}$. उसी प्रमेय का एक अधिक सममित संस्करण निम्नलिखित है:

Corollary —  A symmetric hollow n×n matrix A with real entries admits a realization if and only if A is negative semidefinite on the hyperplane $H=\{v\in \mathbf {R} ^{n}\colon e^{\textsf {T}}v=0\}$, that is

$v^{\textsf {T}}Av\leq 0$ for all $v\in \mathbf {R} ^{n}$ such that $\textstyle \sum _{i=1}^{n}v_{i}=0$.

अन्य लक्षण वर्णन में केली-मेंजर निर्धारक सम्मिलित है। विशेष रूप से, ये एक सममित खोखला मैट्रिक्स दिखाने की अनुमति देते हैं n×n मैट्रिक्स में वसूली योग्य है ℝ^k यदि और केवल यदि हर (k+3)×(k+3) प्रिंसिपल सबमैट्रिक्स है। दूसरे शब्दों में, एक मीट्रिक (गणित)#अर्धमिति बहुत से बिंदुओं पर आइसोमेट्री है ℝ^k यदि और केवल यदि हर k+3 अंक हैं। व्यवहार में, संख्यात्मक त्रुटियों, माप में शोर, या वास्तविक यूक्लिडियन दूरी से डेटा नहीं आने के कारण निश्चितता या रैंक की स्थिति विफल हो सकती है। ऐसे बिंदु जो इष्टतम समान दूरी का एहसास करते हैं, फिर एकवचन मूल्य अपघटन या अर्ध-निश्चित प्रोग्रामिंग जैसे रैखिक बीजगणितीय उपकरण का उपयोग करके सेमीडिफिनिट सन्निकटन (और निम्न रैंक सन्निकटन, यदि वांछित हो) द्वारा पाया जा सकता है। इसे बहुआयामी स्केलिंग के रूप में जाना जाता है। इन विधियों के विभिन्न प्रकार अपूर्ण दूरी डेटा से भी निपट सकते हैं।

बिना लेबल वाला डेटा, अर्थात, दूरियों का एक सेट या मल्टीसेट जो विशेष जोड़े को नहीं सौंपा गया है, इससे निपटना बहुत कठिनाई है। इस तरह के डेटा उत्पन्न होते हैं, उदाहरण के लिए, डीएनए अनुक्रमण में (विशेष रूप से, प्रतिबंध डाइजेस्ट से जीनोम रिकवरी) या चरण समस्या। बिंदुओं के दो सेटों को समरूप संरचनाएं कहा जाता है यदि उनके पास दूरियों का एक ही मल्टीसेट हो (किन्तु आवश्यक नहीं कि वे एक कठोर परिवर्तन से संबंधित हों)। यह तय करना कि क्या दिया गया मल्टीसेट है n(n-1)/2 दिए गए आयाम में दूरी महसूस की जा सकती है k जोरदार एनपी कठिन है। एक आयाम में इसे टर्नपाइक समस्या के रूप में जाना जाता है; यह एक खुला प्रश्न है कि क्या इसे बहुपद समय में हल किया जा सकता है। जब त्रुटि सलाखों के साथ दूरियों का मल्टीसेट दिया जाता है, तब भी एक आयामी मामला एनपी-हार्ड होता है। फिर भी, कई स्थितियों के लिए व्यावहारिक एल्गोरिदम उपस्तिथ हैं, उदा। यादृच्छिक बिंदु।

अभ्यावेदन की विशिष्टता

एक यूक्लिडियन दूरी मैट्रिक्स को देखते हुए, बिंदुओं का क्रम जो यह महसूस करता है कि यह कठोर परिवर्तनों तक अद्वितीय है - ये यूक्लिडियन अंतरिक्ष की आइसोमेट्री हैं: रोटेशन (गणित), परावर्तन (गणित), अनुवाद (ज्यामिति), और उनकी रचनाएँ।

Theorem —  Let $x_{1},x_{2},\ldots ,x_{n}$ and $y_{1},y_{2},\ldots ,y_{n}$ be two sequences of points in k-dimensional Euclidean space ℝ^k. The distances $\|x_{i}-x_{j}\|$ and $\|y_{i}-y_{j}\|$ are equal (for all 1≤i,j≤n) if and only if there is a rigid transformation of ℝ^k mapping $x_{i}$ to $y_{i}$ (for all 1≤i≤n).

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | Proof

कठोर परिवर्तन दूरियों को बनाए रखते हैं इसलिए एक दिशा स्पष्ट होती है। मान लीजिए दूरियां $\|x_{i}-x_{j}\|$ और $\|y_{i}-y_{j}\|$ बराबर हैं। व्यापकता के नुकसान के बिना हम मान सकते हैं $x_{1}=y_{1}={\textbf {0}}$ द्वारा बिंदुओं का अनुवाद करके $-x_{1}$ और $-y_{1}$, क्रमश। फिर (n-1)×(n-1) शेष सदिशों का ग्राम आव्यूह $x_{i}=x_{i}-x_{1}$ सदिशों के ग्राम आव्यूह के समान है $y_{i}$ (2≤i≤n). वह है, $X^{\textsf {T}}X=Y^{\textsf {T}}Y$, कहाँ X और Y हैं k×(n-1) कॉलम के रूप में संबंधित वैक्टर युक्त मैट्रिसेस। इसका तात्पर्य है कि एक ऑर्थोगोनल मैट्रिक्स मौजूद है k×k आव्यूह Q ऐसा है कि QX=Y, निश्चित सममित मैट्रिक्स देखें#एकात्मक परिवर्तनों तक अद्वितीयता। Q के एक ओर्थोगोनल परिवर्तन का वर्णन करता है ℝk (अनुवाद के बिना घुमावों और प्रतिबिंबों की रचना) जो मैप करता है $x_{i}$ को $y_{i}$ (और 0 से 0)। अंतिम कठोर परिवर्तन द्वारा वर्णित है $T(x)=Q(x-x_{1})+y_{1}$.

अनुप्रयोगों में, जब दूरियां त्रुटिहीन रूप से मेल नहीं खाती हैं, तो प्रोक्रेस्ट्स विश्लेषण का लक्ष्य दो बिंदु सेटों को कठोर परिवर्तनों के माध्यम से जितना संभव हो उतना करीब से जोड़ना है, सामान्यतः एकवचन मूल्य अपघटन का उपयोग करना। साधारण यूक्लिडियन स्थितियोंको ऑर्थोगोनल प्रोक्रस्ट्स समस्या या वाहबा की समस्या के रूप में जाना जाता है (जब टिप्पणियों को अलग-अलग अनिश्चितताओं के लिए भारित किया जाता है)। अनुप्रयोगों के उदाहरणों में उपग्रहों के झुकाव का निर्धारण करना, अणु संरचना (रसायन सूचना विज्ञान में), प्रोटीन संरचना (जैव सूचना विज्ञान में संरचनात्मक संरेखण), या हड्डी संरचना (जीव विज्ञान में सांख्यिकीय आकार विश्लेषण) की तुलना करना सम्मिलित है।

यह भी देखें

• सहखंडज मैट्रिक्स
• समतलीयता
• दूरी ज्यामिति
• खोखला मैट्रिक्स
• दूरी मैट्रिक्स
• यूक्लिडियन यादृच्छिक मैट्रिक्स
• मौलिक बहुआयामी स्केलिंग, एक विज़ुअलाइज़ेशन तकनीक जो एक यूक्लिडियन दूरी मैट्रिक्स द्वारा एक मनमाना असमानता मैट्रिक्स का अनुमान लगाती है
• केली-मेंजर निर्धारक
• अर्ध निश्चित एम्बेडिंग

संदर्भ

• Dokmanic, Ivan; Parhizkar, Reza; Ranieri, Juri; Vetterli, Martin (2015). "Euclidean Distance Matrices: Essential theory, algorithms, and applications". IEEE Signal Processing Magazine. 32 (6): 12–30. arXiv:1502.07541. doi:10.1109/MSP.2015.2398954. ISSN 1558-0792. S2CID 8603398.
• James E. Gentle (2007). Matrix Algebra: Theory, Computations, and Applications in Statistics. Springer-Verlag. p. 299. ISBN 978-0-387-70872-0.
• So, Anthony Man-Cho (2007). A Semidefinite Programming Approach to the Graph Realization Problem: Theory, Applications and Extensions (PDF) (PhD) (in English).
• Liberti, Leo; Lavor, Carlile; Maculan, Nelson; Mucherino, Antonio (2014). "Euclidean Distance Geometry and Applications". SIAM Review (in English). 56 (1): 3–69. arXiv:1205.0349. doi:10.1137/120875909. ISSN 0036-1445. S2CID 15472897.
• Alfakih, Abdo Y. (2018). Euclidean Distance Matrices and Their Applications in Rigidity Theory (in English). Cham: Springer International Publishing. doi:10.1007/978-3-319-97846-8. ISBN 978-3-319-97845-1.