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

गणित में, यूक्लिडियन दूरी आव्यूह 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) —  एक सममित hollow n×n आव्यूह x A वास्तविक प्रविष्टियों के साथ एक बोध को स्वीकार करता है ℝ^k यदि (n-1)×(n-1) आव्यूह $G=(g_{ij})_{2\leq i,j\leq n}$ के द्वारा प्रदर्शित किया जाता हैं।

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

सकारात्मक अर्धनिश्चित है और है rank अधिक से अधिक k के समान हैं।

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

इसलिए, किसी भी विधि को विघटित करने के लिए G एक अहसास खोजने की अनुमति देता है। दो मुख्य दृष्टिकोण चॉल्स्की अपघटन के प्रकार हैं या आव्यूह के वर्ग रूट को खोजने के लिए eigendecomposition का उपयोग करना G, निश्चित आव्यूह#अपघटन देखें।

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

Corollary —  एक सममति hollow n×n आव्यूह A वास्तविक प्रविष्टियों के साथ अगर और केवल अगर एक अहसास को स्वीकार करता है A हाइपरप्लेन पर ऋणात्मक अर्धनिश्चित है $H=\{v\in \mathbf {R} ^{n}\colon e^{\textsf {T}}v=0\}$, जो इस प्रकार हैं

$v^{\textsf {T}}Av\leq 0$ for all $v\in \mathbf {R} ^{n}$ के कारण $\textstyle \sum _{i=1}^{n}v_{i}=0$.

अन्य लक्षण वर्णन में केली-मेंजर निर्धारक सम्मिलित है। विशेष रूप से, ये एक सममित खोखला आव्यूह दिखाने की अनुमति देते हैं, इस प्रकार n×n आव्यूह में ℝ^k के मान के योग्य है, इस कारण यदि हर (k+3)×(k+3) नियम उप आव्यूह है।

दूसरे शब्दों में, एक मीट्रिक (गणित) अर्धमिति बहुत से बिंदुओं पर आइसोमेट्री ℝ^k है, इस प्रकार यदि k+3 एक मान हैं। व्यवहारिक रूप से, संख्यात्मक त्रुटियों के लिए इसकी माप में या वास्तविक यूक्लिडियन दूरी से डेटा नहीं आने के कारण निश्चितता या रैंक की स्थिति विफल हो सकती है।

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

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

यह तय करना हैं कि क्या दिया गया मल्टीसमुच्चय है, इस कारण n(n-1)/2 दिए गए आयाम में दूरी को मापा जा सकता है, जिसके लिए k की माप एनपी कठिन है। एक आयाम में इसे टर्नपाइक समस्या के रूप में जाना जाता है; यह एक खुला प्रश्न है कि क्या इसे बहुपद समय में हल किया जा सकता है।

जब त्रुटि सलाखों के साथ दूरियों का मल्टीसमुच्चय दिया जाता है, तब भी एक आयामी स्थिति एनपी हार्ड होती है। फिर भी कई स्थितियों के लिए व्यावहारिक एल्गोरिदम उपस्तिथ हैं, उदाहरण के लिए यादृच्छिक बिंदु इसका मुख्य उदाहरण हैं।

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

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

Theorem —  मान लीजिए $x_{1},x_{2},\ldots ,x_{n}$ और $y_{1},y_{2},\ldots ,y_{n}$ जो कि क्रम में दो बिंदु हैं k-dimensional Euclidean space ℝ^k इस प्रकार यह दूरी $\|x_{i}-x_{j}\|$ और $\|y_{i}-y_{j}\|$ के समान हैं। (for all 1≤i,j≤n) यह केवल कठोर परिवर्तन के अनुसार ℝ^k मैपिंग करता हैं $x_{i}$ to $y_{i}$ (for all 1≤i≤n).

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | प्रमाण

कठोर परिवर्तन दूरियों को बनाए रखते हैं इसलिए एक दिशा स्पष्ट होती है। मान लीजिए दूरियां $\|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.