यूक्लिडियन दूरी मैट्रिक्स: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
गणित में, यूक्लिडियन डिस्टेंस मैट्रिक्स एक है {{math|''n''×''n''}} [[मैट्रिक्स (गणित)]] के एक सेट के अंतर का प्रतिनिधित्व करता है {{mvar|''n''}[[यूक्लिडियन अंतरिक्ष]] में } [[बिंदु (ज्यामिति)]]
गणित में, '''यूक्लिडियन दूरी आव्यूह''' {{math|''n''×''n''}} [[मैट्रिक्स (गणित)|आव्यूह (गणित)]]<nowiki> के समुच्चय के अंतर का प्रतिनिधित्व करता है {{mvar|</nowiki>''n''}[[यूक्लिडियन अंतरिक्ष]] में } [[बिंदु (ज्यामिति)]] के समान हैं।
अंक के लिए <math>x_1,x_2,\ldots,x_n</math> में {{mvar|''k''}}-विमीय स्थान {{math|ℝ<sup>''k''</sup>}}, उनके यूक्लिडियन दूरी मैट्रिक्स के तत्व {{mvar|''A''}} उनके बीच की दूरियों के वर्ग द्वारा दिए गए हैं।
 
वह है
इस प्रकार <math>x_1,x_2,\ldots,x_n</math> के मान के लिए इसमें {{mvar|''k''}}-विमीय स्थान {{math|ℝ<sup>''k''</sup>}} हैं, जिसके लिए यूक्लिडियन दूरी आव्यूह के तत्व {{mvar|''A''}} उनके बीच की दूरियों के वर्ग द्वारा दिए गए हैं।
 
यह मान इस प्रकार हैं-


:कथन <math>\begin{align}
:कथन <math>\begin{align}
Line 8: Line 10:
\end{align}
\end{align}
</math>
</math>
कहाँ <math>\|\cdot\|</math> [[यूक्लिडियन मानदंड]] को दर्शाता है {{math|ℝ<sup>''k''</sup>}}.
जहाँ <math>\|\cdot\|</math> [[यूक्लिडियन मानदंड]] {{math|ℝ<sup>''k''</sup>}} को दर्शाता है।


:<math>A = \begin{bmatrix}
:<math>A = \begin{bmatrix}
Line 17: Line 19:
d_{n1}^2 & d_{n2}^2 & d_{n3}^2 & \dots & 0 \\
d_{n1}^2 & d_{n2}^2 & d_{n3}^2 & \dots & 0 \\
\end{bmatrix} </math>
\end{bmatrix} </math>
(आवश्यक रूप से यूक्लिडियन नहीं) [[दूरी मैट्रिक्स]] के संदर्भ में, प्रविष्टियों को सामान्यतः सीधे दूरीअर्थात के रूप में परिभाषित किया जाता है, उनके वर्ग नहीं।
(आवश्यक रूप से यूक्लिडियन नहीं) [[दूरी मैट्रिक्स|दूरी आव्यूह]] के संदर्भ में, प्रविष्टियों को सामान्यतः सीधे दूरीअर्थात के रूप में परिभाषित किया जाता है।
चूंकि, यूक्लिडियन स्थितियोंमें, दूरियों के वर्गों का उपयोग वर्गमूलों की गणना से बचने और प्रासंगिक प्रमेयों और एल्गोरिदम को सरल बनाने के लिए किया जाता है।
 
चूंकि यूक्लिडियन स्थितियों में, दूरियों के वर्गों का उपयोग वर्गमूलों की गणना से बचने और प्रासंगिक प्रमेयों और एल्गोरिदम को सरल बनाने के लिए किया जाता है।
 
यूक्लिडियन दूरी आव्यूह [[ग्राम मैट्रिक्स|ग्राम आव्यूह]] ([[डॉट उत्पाद|डॉट उत्पादों]] के आव्यूह को उनके बीच के सदिश और कोणों के मानदंडों का वर्णन करते हुए) से निकटता से संबंधित रहता हैं।
 
रैखिक बीजगणित के तरीकों का उपयोग करके उत्तरार्द्ध का सरलता से विश्लेषित किया जाता है।
 
यह यूक्लिडियन दूरी आव्यूह को चिह्नित करने और अंक पुनर्प्राप्त करने की अनुमति देता है, इस प्रकार <math>x_1,x_2,\ldots,x_n</math> के मान से यह पता चलता हैं। इस कारण यदि यह उपस्तिथ है तो [[कठोर परिवर्तन|कठोर परिवर्तनों]] तक  यह मान अद्वितीय अर्थात [[आइसोमेट्री]]  रहता है। इस प्रकार यूक्लिडियन अंतरिक्ष ([[रोटेशन (गणित)|घूर्णन (गणित)]], परावर्तन (गणित), [[अनुवाद (ज्यामिति)]]) के दूरी-संरक्षण परिवर्तन के समान हैं।


यूक्लिडियन दूरी मैट्रिसेस [[ग्राम मैट्रिक्स]] ([[डॉट उत्पाद]]ों के मैट्रिसेस, उनके बीच वैक्टर और कोणों के मानदंडों का वर्णन करते हुए) से निकटता से संबंधित हैं।
व्यावहारिक अनुप्रयोगों में दूरियां मुख्यतः इस ध्वनि की माप को प्रदर्शित करता हैं तथा स्वयं से समानता की माप करके इन्हें अनुमानों से इंगित करता हैं, (आवश्यक  नहीं कि [[मीट्रिक (गणित)]])
रैखिक बीजगणित के तरीकों का उपयोग करके उत्तरार्द्ध का आसानी से विश्लेषण किया जाता है।
यह यूक्लिडियन दूरी मैट्रिसेस को चिह्नित करने और अंक पुनर्प्राप्त करने की अनुमति देता है <math>x_1,x_2,\ldots,x_n</math> कि इसका एहसास हो।
एक बोध, यदि यह उपस्तिथ है, [[कठोर परिवर्तन]]ों तक अद्वितीय है, अर्थात [[आइसोमेट्री]] | यूक्लिडियन अंतरिक्ष ([[रोटेशन (गणित)]], परावर्तन (गणित), [[अनुवाद (ज्यामिति)]]) के दूरी-संरक्षण परिवर्तन।


व्यावहारिक अनुप्रयोगों में, दूरियां शोर माप हैं या मनमाने ढंग से समानता माप अनुमानों से आती हैं (आवश्यक  नहीं कि [[मीट्रिक (गणित)]])।
लक्षित यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा ऐसे डेटा की कल्पना करना हो सकता है, जिसकी दूरी आव्यूह किसी दिए गए असमानता आव्यूह के साथ-साथ संभव हो - इसे [[बहुआयामी स्केलिंग]] के रूप में जाना जाता है।
लक्ष्य यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा ऐसे डेटा की कल्पना करना हो सकता है, जिसकी दूरी मैट्रिक्स किसी दिए गए असमानता मैट्रिक्स के साथ-साथ संभव हो - इसे [[बहुआयामी स्केलिंग]] के रूप में जाना जाता है।
 
वैकल्पिक रूप से, डेटा के दो सेट पहले से ही यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा दर्शाए गए हैं, कोई पूछ सकता है कि वे आकार में कितने समान हैं, अर्थात, वे एक कठोर परिवर्तन से कितनी निकटता से संबंधित हो सकते हैं। दूरी-संरक्षण परिवर्तन - यह प्रोक्रस्ट्स विश्लेषण है।
वैकल्पिक रूप से, डेटा के दो समुच्चय पहले से ही यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा दर्शाए गए हैं, कोई पूछ सकता है कि वे आकार में कितने समान रहता हैं, अर्थात कठोर परिवर्तन से कितनी निकटता से संबंधित हो सकते हैं। इस प्रकार दूरी-संरक्षण परिवर्तन के अनुसार यह प्रोक्रस्ट्स विश्लेषण द्वारा प्रदर्शित होता है। इसमें कुछ दूरियाँ विलुप्त भी हो सकती हैं या बिना लेबल के उपयोग की जा सकती हैं (आव्यूह के अतिरिक्त एक अनियंत्रित समुच्चय या मल्टीसमुच्चय के रूप में उपयोग होता हैं), जिससे अधिक जटिल एल्गोरिथम कार्य हो सकते हैं, जैसे कि ग्राफ़ प्राप्ति समस्या या टर्नपाइक समस्या (एक रेखा पर बिंदुओं के लिए) के समान हैं।<ref name="DPRZ">{{harvtxt|Dokmanic|Parhizkar|Ranieri|Vetterli|2015}}</ref><ref>{{harvtxt|So|2007}}</ref>
कुछ दूरियाँ गायब भी हो सकती हैं या बिना लेबल के सकती हैं (मैट्रिक्स के अतिरिक्त एक अनियंत्रित सेट या मल्टीसेट के रूप में), जिससे अधिक जटिल एल्गोरिथम कार्य हो सकते हैं, जैसे कि ग्राफ़ प्राप्ति समस्या या टर्नपाइक समस्या (एक रेखा पर बिंदुओं के लिए)<ref name="DPRZ">{{harvtxt|Dokmanic|Parhizkar|Ranieri|Vetterli|2015}}</ref><ref>{{harvtxt|So|2007}}</ref>
== गुण ==
== गुण ==


इस तथ्य से कि यूक्लिडियन दूरी एक मीट्रिक (गणित) है, मैट्रिक्स है {{mvar|''A''}} में निम्नलिखित गुण होते हैं।
इस तथ्य से कि यूक्लिडियन दूरी मीट्रिक (गणित) को प्रदर्शित करती है, {{mvar|''A''}} आव्यूह है जिसमें निम्नलिखित गुण होते हैं।


* मैट्रिक्स के विकर्ण पर सभी तत्व {{mvar|''A''}} शून्य हैं (अर्थात यह एक [[खोखला मैट्रिक्स]] है); इसलिए [[एक मैट्रिक्स का निशान]] {{mvar|''A''}} शून्य है।
* आव्यूह के विकर्ण पर सभी तत्व {{mvar|''A''}} शून्य हैं (अर्थात यह एक [[खोखला मैट्रिक्स|खोखला आव्यूह]] है); इसलिए [[एक मैट्रिक्स का निशान|एक आव्यूह का निशान]] {{mvar|''A''}} शून्य है।
* {{mvar|''A''}} [[सममित मैट्रिक्स]] है (अर्थात <math>a_{ij} = a_{ji}</math>).
* {{mvar|''A''}} [[सममित मैट्रिक्स|सममित आव्यूह]] (अर्थात <math>a_{ij} = a_{ji}</math>) है।
* <math> \sqrt{a_{ij}} \le \sqrt{a_{ik}} + \sqrt{a_{kj}} </math> (त्रिकोण असमानता द्वारा)
* <math> \sqrt{a_{ij}} \le \sqrt{a_{ik}} + \sqrt{a_{kj}} </math> (त्रिकोण असमानता द्वारा)
* <math> a_{ij}\ge 0</math>
* <math> a_{ij}\ge 0</math>
आयाम में {{mvar|''k''}}, यूक्लिडियन दूरी मैट्रिक्स में [[रैंक (रैखिक बीजगणित)]] से कम या उसके बराबर है {{math|''k''+2}}. यदि अंक <math>x_1,x_2,\ldots,x_n</math> [[सामान्य स्थिति]] में हैं, रैंक बिल्कुल है {{math|min(''n'', ''k'' + 2).}}
आयाम में {{mvar|''k''}}, यूक्लिडियन दूरी आव्यूह में [[रैंक (रैखिक बीजगणित)]] से कम या {{math|''k''+2}} के बराबर है, इस प्रकार यदि <math>x_1,x_2,\ldots,x_n</math> [[सामान्य स्थिति]] में हैं, तो रैंक {{math|min(''n'', ''k'' + 2).}} रहती हैं।


एक और यूक्लिडियन दूरी मैट्रिक्स प्राप्त करने के लिए दूरियों को किसी भी शक्ति से कम किया जा सकता है। अर्थात यदि <math>A=(a_{ij})</math> एक यूक्लिडियन दूरी मैट्रिक्स है, तो <math>({a_{ij}}^s)</math> प्रत्येक के लिए एक यूक्लिडियन दूरी मैट्रिक्स है {{math|0<''s''<1}}.<ref>{{Cite journal |last=Maehara |first=Hiroshi |date=2013 |title=परिमित मीट्रिक रिक्त स्थान के यूक्लिडियन एम्बेडिंग|journal=Discrete Mathematics |language=en |volume=313 |issue=23 |pages=2848–2856 |doi=10.1016/j.disc.2013.08.029 |issn=0012-365X|doi-access=free }} Theorem 2.6</ref>
यूक्लिडियन दूरी आव्यूह प्राप्त करने के लिए दूरियों को किसी भी शक्ति से कम किया जा सकता है। अर्थात यदि <math>A=(a_{ij})</math> एक यूक्लिडियन दूरी आव्यूह है, तो <math>({a_{ij}}^s)</math> प्रत्येक के लिए एक यूक्लिडियन दूरी आव्यूह {{math|0<''s''<1}} है।<ref>{{Cite journal |last=Maehara |first=Hiroshi |date=2013 |title=परिमित मीट्रिक रिक्त स्थान के यूक्लिडियन एम्बेडिंग|journal=Discrete Mathematics |language=en |volume=313 |issue=23 |pages=2848–2856 |doi=10.1016/j.disc.2013.08.029 |issn=0012-365X|doi-access=free }} Theorem 2.6</ref>
== ग्राम मैट्रिक्स से संबंध ==
== ग्राम आव्यूह से संबंध ==
अंकों के अनुक्रम का ग्राम मैट्रिक्स <math>x_1,x_2,\ldots,x_n</math> में {{mvar|''k''}}-विमीय स्थान {{math|ℝ<sup>''k''</sup>}}
अंकों के अनुक्रम का ग्राम आव्यूह <math>x_1,x_2,\ldots,x_n</math> में {{mvar|''k''}}-विमीय स्थान {{math|ℝ<sup>''k''</sup>}}है। इस कारण {{math|''n''×''n''}} आव्यूह <math>G = (g_{ij})</math> के [[डॉट उत्पाद]] (यहां एक बिंदु <math>x_i</math> 0 से उस बिंदु तक वेक्टर के रूप में माना जाता है):
है {{math|''n''×''n''}} आव्यूह <math>G = (g_{ij})</math> उनके [[डॉट उत्पाद]] (यहां एक बिंदु <math>x_i</math> 0 से उस बिंदु तक वेक्टर के रूप में माना जाता है):
: <math>g_{ij} = x_i \cdot x_j = \|x_i\| \|x_j\| \cos \theta</math>, जहाँ <math>\theta</math> वेक्टर के बीच का कोण <math>x_i</math> और <math>x_j</math> है।
: <math>g_{ij} = x_i \cdot x_j = \|x_i\| \|x_j\| \cos \theta</math>, कहाँ <math>\theta</math> वेक्टर के बीच का कोण है <math>x_i</math> और <math>x_j</math>.
विशेष रूप से
विशेष रूप से
: <math>g_{ii} = \|x_i\|^2</math> की दूरी का वर्ग है <math>x_i</math> 0 से।
: <math>g_{ii} = \|x_i\|^2</math> की दूरी <math>x_i</math> से 0 का वर्ग है ।
इस प्रकार ग्राम मैट्रिक्स वैक्टर के मानदंडों और कोणों का वर्णन करता है (0 से) <math>x_1,x_2,\ldots,x_n</math>.
इस प्रकार ग्राम आव्यूह सदिश के मानदंडों और कोणों (0 से) <math>x_1,x_2,\ldots,x_n</math> का वर्णन करता है


होने देना <math>X</math> हो {{math|''k''×''n''}} मैट्रिक्स युक्त <math>x_1,x_2,\ldots,x_n</math> स्तंभों के रूप में।
होने देना <math>X</math> हो {{math|''k''×''n''}} आव्यूह युक्त <math>x_1,x_2,\ldots,x_n</math> स्तंभों के रूप में रहता हैं।
तब
: इस प्रकार <math>G = X^\textsf{T} X</math>, होने पर <math>g_{ij} = x_i^\textsf{T} x_j</math> (देख के <math>x_i</math> कॉलम वेक्टर के रूप में रहता हैं)।
: <math>G = X^\textsf{T} X</math>, क्योंकि <math>g_{ij} = x_i^\textsf{T} x_j</math> (देख के <math>x_i</math> कॉलम वेक्टर के रूप में)।
आव्यूह जिन्हें <math>X^\textsf{T}X</math> के रूप में विघटित किया जा सकता है, अर्थात् सदिशों के कुछ अनुक्रमों के ग्राम आव्यूह (के स्तंभ <math>X</math>), अच्छी तरह से समझ गए हैं - ये ठीक तरह से [[सकारात्मक अर्ध निश्चित मैट्रिक्स|धनात्मक अर्ध निश्चित आव्यूह]] हैं।
मैट्रिसेस जिन्हें विघटित किया जा सकता है <math>X^\textsf{T}X</math>, अर्थात्, सदिशों के कुछ अनुक्रमों के ग्राम आव्यूह (के स्तंभ <math>X</math>), अच्छी तरह से समझ गए हैं - ये ठीक [[सकारात्मक अर्ध निश्चित मैट्रिक्स]] हैं।


 
यूक्लिडियन दूरी आव्यूह को ग्राम आव्यूह से संबंधित करने के लिए उपयोग किया जाता हैं, इसे इस प्रकार लिखा जा सकता हैं।
यूक्लिडियन दूरी मैट्रिक्स को ग्राम मैट्रिक्स से संबंधित करने के लिए, इसे देखें
: <math>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}</math>
: <math>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}</math>
अर्थात मानदंड और कोण दूरी तय करते हैं।
अर्थात मानदंड और कोण दूरी तय करते हैं।
ध्यान दें कि ग्राम मैट्रिक्स में अतिरिक्त जानकारी होती है: 0 से दूरी।
ध्यान दें कि ग्राम आव्यूह में अतिरिक्त जानकारी होती है: 0 से दूरी इस प्रकार होगी।


इसके विपरीत दूरियां <math>d_{ij}</math> के जोड़े के बीच {{math|''n''+1}} अंक <math>x_0,x_1,\ldots,x_n</math> के बीच डॉट उत्पाद निर्धारित करें {{mvar|''n''}} वैक्टर <math>x_i-x_0</math> ({{math|1≤''i''≤''n''}}):
इसके विपरीत दूरियां <math>d_{ij}</math> के जोड़े के बीच {{math|''n''+1}} अंक <math>x_0,x_1,\ldots,x_n</math> के बीच डॉट उत्पाद निर्धारित करें {{mvar|''n''}} सदिश <math>x_i-x_0</math> ({{math|1≤''i''≤''n''}}):
: <math>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)</math>
: <math>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)</math>
(इसे [[ध्रुवीकरण पहचान]] के रूप में जाना जाता है)।
(इसे [[ध्रुवीकरण पहचान]] के रूप में जाना जाता है)।
Line 65: Line 67:
== लक्षण वर्णन ==
== लक्षण वर्णन ==
एक के लिए {{math|''n''×''n''}} आव्यूह {{mvar|''A''}}, अंकों का एक क्रम <math>x_1,x_2,\ldots,x_n</math> में {{mvar|''k''}}-आयामी यूक्लिडियन स्थान {{math|ℝ<sup>''k''</sup>}}
एक के लिए {{math|''n''×''n''}} आव्यूह {{mvar|''A''}}, अंकों का एक क्रम <math>x_1,x_2,\ldots,x_n</math> में {{mvar|''k''}}-आयामी यूक्लिडियन स्थान {{math|ℝ<sup>''k''</sup>}}
का बोध कहा जाता है {{mvar|''A''}} में {{math|ℝ<sup>''k''</sup>}} यदि {{mvar|''A''}} उनकी यूक्लिडियन दूरी मैट्रिक्स है।
का बोध कहा जाता है {{mvar|''A''}} में {{math|ℝ<sup>''k''</sup>}} यदि {{mvar|''A''}} उनकी यूक्लिडियन दूरी आव्यूह है।
कोई सामान्यता के नुकसान के बिना मान सकता है कि <math>x_1 = \mathbf{0}</math> (क्योंकि अनुवाद (ज्यामिति) द्वारा <math>-x_1</math> दूरी बनाए रखता है)।
 
किसी सामान्यता की हानि के बिना मान सकता है कि <math>x_1 = \mathbf{0}</math> (क्योंकि अनुवाद (ज्यामिति) द्वारा <math>-x_1</math> दूरी बनाए रखता है)।


{{Math theorem|name=Theorem<ref>{{harvtxt|So|2007}}, Theorem 3.3.1, p. 40</ref>
{{Math theorem|name=Theorem<ref>{{harvtxt|So|2007}}, Theorem 3.3.1, p. 40</ref>
Line 72: Line 75:
independently shown by Young &amp; Householder<ref>{{Cite journal |last1=Young |first1=Gale |last2=Householder |first2=A. S. |s2cid=122400126 |date=1938-03-01 |title=Discussion of a set of points in terms of their mutual distances |journal=Psychometrika |language=en |volume=3 |issue=1 |pages=19–22 |doi=10.1007/BF02287916 |issn=1860-0980}}</ref>
independently shown by Young &amp; Householder<ref>{{Cite journal |last1=Young |first1=Gale |last2=Householder |first2=A. S. |s2cid=122400126 |date=1938-03-01 |title=Discussion of a set of points in terms of their mutual distances |journal=Psychometrika |language=en |volume=3 |issue=1 |pages=19–22 |doi=10.1007/BF02287916 |issn=1860-0980}}</ref>
|
|
A symmetric [[hollow matrix|hollow]] {{math|''n''×''n''}} matrix {{mvar|''A''}} with real entries admits a realization in {{math|ℝ<sup>''k''</sup>}} if and only if the {{math|(''n''-1)×(''n''-1)}} matrix <math>G = (g_{ij})_{2 \leq i,j \leq n}</math> defined by
एक सममित [[hollow matrix|hollow]] {{math|''n''×''n''}} आव्यूह x {{mvar|''A''}} वास्तविक प्रविष्टियों के साथ एक बोध को स्वीकार करता है {{math|ℝ<sup>''k''</sup>}} यदि {{math|(''n''-1)×(''n''-1)}} आव्यूह <math>G = (g_{ij})_{2 \leq i,j \leq n}</math> के द्वारा प्रदर्शित किया जाता हैं।
: <math>g_{ij} = \frac{1}{2}(a_{1i} + a_{1j} - a_{ij})</math>
: <math>g_{ij} = \frac{1}{2}(a_{1i} + a_{1j} - a_{ij})</math>
is [[positive semidefinite matrix|positive semidefinite]] and has [[matrix rank|rank]] at most {{mvar|''k''}}.
[[सकारात्मक अर्धनिश्चित मैट्रिक्स|सकारात्मक अर्धनिश्चित]] है और है [[matrix rank|rank]] अधिक से अधिक {{mvar|''k''}} के समान हैं।
}}
}}
यह पिछली चर्चा से इस प्रकार है क्योंकि {{mvar|''G''}} अधिक से अधिक रैंक का धनात्मक अर्धनिश्चित है {{mvar|''k''}} यदि और केवल यदि इसे विघटित किया जा सकता है <math>G = X^\textsf{T} X</math> कहाँ {{mvar|''X''}} एक {{math|''k''×''n''}} आव्यूह।<ref>{{harvtxt|So|2007}}, Theorem 2.2.1, p. 10</ref>
 
इसके अतिरिक्त, के कॉलम {{mvar|''X''}} में एक अहसास दें {{math|ℝ<sup>''k''</sup>}}.
यह पिछली चर्चा से इस प्रकार है क्योंकि {{mvar|''G''}} अधिक से अधिक रैंक का धनात्मक अर्धनिश्चित है {{mvar|''k''}} यदि और केवल यदि इसे विघटित किया जा सकता है <math>G = X^\textsf{T} X</math> जहाँ {{mvar|''X''}} एक {{math|''k''×''n''}} आव्यूह।<ref>{{harvtxt|So|2007}}, Theorem 2.2.1, p. 10</ref>
इसके अतिरिक्त, के कॉलम {{mvar|''X''}} में {{math|ℝ<sup>''k''</sup>}} को प्रदर्शित करने में सहायक हैं।
 
इसलिए, किसी भी विधि को विघटित करने के लिए {{mvar|''G''}} एक अहसास खोजने की अनुमति देता है।
इसलिए, किसी भी विधि को विघटित करने के लिए {{mvar|''G''}} एक अहसास खोजने की अनुमति देता है।
दो मुख्य दृष्टिकोण चॉल्स्की अपघटन के प्रकार हैं या मैट्रिक्स के वर्ग रूट को खोजने के लिए [[eigendecomposition]] का उपयोग करना {{mvar|''G''}}, निश्चित मैट्रिक्स#अपघटन देखें।
दो मुख्य दृष्टिकोण चॉल्स्की अपघटन के प्रकार हैं या आव्यूह के वर्ग रूट को खोजने के लिए [[eigendecomposition]] का उपयोग करना {{mvar|''G''}}, निश्चित आव्यूह#अपघटन देखें।


प्रमेय का कथन पहले बिंदु को अलग करता है <math>x_1</math>. उसी प्रमेय का एक अधिक सममित संस्करण निम्नलिखित है:
प्रमेय का कथन पहले बिंदु को अलग करता है <math>x_1</math>. उसी प्रमेय का एक अधिक सममित संस्करण निम्नलिखित है:
{{Math theorem|name=Corollary<ref>{{harvtxt|So|2007}}, Corollary 3.3.3, p. 42</ref>|
{{Math theorem|name=Corollary<ref>{{harvtxt|So|2007}}, Corollary 3.3.3, p. 42</ref>|
A symmetric [[hollow matrix|hollow]] {{math|''n''×''n''}} matrix {{mvar|''A''}} with real entries admits a realization if and only if {{mvar|''A''}}
एक सममति [[hollow matrix|hollow]] {{math|''n''×''n''}} आव्यूह {{mvar|''A''}} वास्तविक प्रविष्टियों के साथ अगर और केवल अगर एक अहसास को स्वीकार करता है {{mvar|''A''}}
is negative semidefinite on the hyperplane <math>H=\{v \in \mathbf{R}^n \colon e^\textsf{T}v = 0\}</math>, that is
हाइपरप्लेन पर ऋणात्मक अर्धनिश्चित है <math>H=\{v \in \mathbf{R}^n \colon e^\textsf{T}v = 0\}</math>, जो इस प्रकार हैं
: <math>v^\textsf{T} A v \leq 0</math> for all <math>v \in \mathbf{R}^n</math> such that <math>\textstyle\sum_{i=1}^n v_i = 0</math>.
: <math>v^\textsf{T} A v \leq 0</math> for all <math>v \in \mathbf{R}^n</math> के कारण <math>\textstyle\sum_{i=1}^n v_i = 0</math>.
}}
}}
अन्य लक्षण वर्णन में केली-मेंजर निर्धारक सम्मिलित है।
अन्य लक्षण वर्णन में केली-मेंजर निर्धारक सम्मिलित है।
विशेष रूप से, ये एक सममित खोखला मैट्रिक्स दिखाने की अनुमति देते हैं {{math|''n''×''n''}} मैट्रिक्स में वसूली योग्य है {{math|ℝ<sup>''k''</sup>}} यदि और केवल यदि हर {{math|(''k''+3)×(''k''+3)}} [[प्रिंसिपल सबमैट्रिक्स]] है।
विशेष रूप से, ये एक सममित खोखला आव्यूह दिखाने की अनुमति देते हैं, इस प्रकार  {{math|''n''×''n''}} आव्यूह में {{math|ℝ<sup>''k''</sup>}} के मान के योग्य है, इस कारण यदि हर {{math|(''k''+3)×(''k''+3)}} [[प्रिंसिपल सबमैट्रिक्स|नियम उप आव्यूह]] है।
दूसरे शब्दों में, एक मीट्रिक (गणित)#अर्धमिति बहुत से बिंदुओं पर आइसोमेट्री है {{math|ℝ<sup>''k''</sup>}} यदि और केवल यदि हर {{math|''k''+3}} अंक हैं।<ref>
 
दूसरे शब्दों में, एक मीट्रिक (गणित) अर्धमिति बहुत से बिंदुओं पर आइसोमेट्री {{math|ℝ<sup>''k''</sup>}} है, इस प्रकार यदि  {{math|''k''+3}} एक मान हैं।<ref>
{{Cite journal |last=Menger |first=Karl |date=1931 |title=New Foundation of Euclidean Geometry |journal=American Journal of Mathematics |volume=53 |issue=4 |pages=721–745 |doi=10.2307/2371222|jstor=2371222 }}
{{Cite journal |last=Menger |first=Karl |date=1931 |title=New Foundation of Euclidean Geometry |journal=American Journal of Mathematics |volume=53 |issue=4 |pages=721–745 |doi=10.2307/2371222|jstor=2371222 }}
</ref>
</ref> व्यवहारिक रूप से, संख्यात्मक त्रुटियों के लिए इसकी माप में या वास्तविक यूक्लिडियन दूरी से डेटा नहीं आने के कारण निश्चितता या रैंक की स्थिति विफल हो सकती है।
व्यवहार में, संख्यात्मक त्रुटियों, माप में शोर, या वास्तविक यूक्लिडियन दूरी से डेटा नहीं आने के कारण निश्चितता या रैंक की स्थिति विफल हो सकती है।
ऐसे बिंदु जो इष्टतम समान दूरी का एहसास करते हैं, फिर एकवचन मूल्य अपघटन या अर्ध-निश्चित प्रोग्रामिंग जैसे रैखिक बीजगणितीय उपकरण का उपयोग करके सेमीडिफिनिट सन्निकटन (और निम्न रैंक सन्निकटन, यदि वांछित हो) द्वारा पाया जा सकता है।
इसे बहुआयामी स्केलिंग के रूप में जाना जाता है।
इन विधियों के विभिन्न प्रकार अपूर्ण दूरी डेटा से भी निपट सकते हैं।


बिना लेबल वाला डेटा, अर्थात, दूरियों का एक सेट या मल्टीसेट जो विशेष जोड़े को नहीं सौंपा गया है, इससे निपटना बहुत कठिनाई है।
ऐसे बिंदु जो इष्टतम समान दूरी का एहसास करते हैं, फिर एकवचन मूल्य अपघटन या अर्ध-निश्चित प्रोग्रामिंग जैसे रैखिक बीजगणितीय उपकरण का उपयोग करके सेमीडिफिनिट सन्निकटन (और निम्न रैंक सन्निकटन, यदि वांछित हो) द्वारा पाया जा सकता है। इसे बहुआयामी स्केलिंग के रूप में जाना जाता है। इन विधियों के विभिन्न प्रकार अपूर्ण दूरी डेटा से भी निपट सकते हैं।
इस तरह के डेटा उत्पन्न होते हैं, उदाहरण के लिए, डीएनए अनुक्रमण में (विशेष रूप से, [[प्रतिबंध डाइजेस्ट]] से जीनोम रिकवरी) या चरण समस्या।
 
बिंदुओं के दो सेटों को [[ समरूप संरचनाएं ]] कहा जाता है यदि उनके पास दूरियों का एक ही मल्टीसेट हो (किन्तु आवश्यक नहीं कि वे एक कठोर परिवर्तन से संबंधित हों)।
बिना लेबल वाला डेटा, अर्थात, दूरियों का एक समुच्चय या मल्टीसमुच्चय जो विशेष जोड़े को नहीं सौंपा गया है, इससे निपटना बहुत कठिनाई है। इस प्रकार के डेटा उत्पन्न होते हैं, उदाहरण के लिए, डीएनए अनुक्रमण में (विशेष रूप से, [[प्रतिबंध डाइजेस्ट]] से जीनोम रिकवरी) या चरण समस्या को प्रदर्शित करता हैं। बिंदुओं के दो समुच्चयों को [[ समरूप संरचनाएं | समरूप संरचनाएं]] कहा जाता है यदि उनके पास दूरियों का एक ही मल्टीसमुच्चय हो (किन्तु आवश्यक नहीं हैं कि वे कठोर परिवर्तन से संबंधित हों)।
यह तय करना कि क्या दिया गया मल्टीसेट है {{math|''n''(''n''-1)/2}} दिए गए आयाम में दूरी महसूस की जा सकती है {{mvar|''k''}} जोरदार [[ एनपी कठिन ]] है।
 
एक आयाम में इसे टर्नपाइक समस्या के रूप में जाना जाता है; यह एक खुला प्रश्न है कि क्या इसे बहुपद समय में हल किया जा सकता है।
यह तय करना हैं कि क्या दिया गया मल्टीसमुच्चय है, इस कारण {{math|''n''(''n''-1)/2}} दिए गए आयाम में दूरी को मापा जा सकता है, जिसके लिए {{mvar|''k''}} की माप[[ एनपी कठिन | एनपी कठिन]] है। एक आयाम में इसे टर्नपाइक समस्या के रूप में जाना जाता है; यह एक खुला प्रश्न है कि क्या इसे बहुपद समय में हल किया जा सकता है।
जब त्रुटि सलाखों के साथ दूरियों का मल्टीसेट दिया जाता है, तब भी एक आयामी मामला एनपी-हार्ड होता है।
 
फिर भी, कई स्थितियों के लिए व्यावहारिक एल्गोरिदम उपस्तिथ हैं, उदा। यादृच्छिक बिंदु।<ref>{{Cite book |title=असतत और कम्प्यूटेशनल ज्यामिति|last1=Lemke |first1=Paul |chapter=Reconstructing Sets From Interpoint Distances |last2=Skiena |first2=Steven S. |last3=Smith |first3=Warren D. |date=2003 |publisher=Springer Berlin Heidelberg |isbn=978-3-642-62442-1 |editor-last=Aronov |editor-first=Boris |volume=25 |location=Berlin, Heidelberg |pages=597–631 |doi=10.1007/978-3-642-55566-4_27 |editor-last2=Basu |editor-first2=Saugata |editor-last3=Pach |editor-first3=János |editor-last4=Sharir |editor-first4=Micha}}</ref><ref>{{Cite journal |arxiv=1804.02465 |title=दूरस्थ वितरण से पुन: निर्माण बिंदु समूह|first1=Shuai |last1=Huang |first2=Ivan |last2=Dokmanić |journal=IEEE Transactions on Signal Processing |year=2021|volume=69 |pages=1811–1827 |doi=10.1109/TSP.2021.3063458 |s2cid=4746784 }}</ref><ref>{{Cite arXiv |eprint=1212.2386 |title=जोड़ीवार दूरियों से पूर्णांकों का पुनर्निर्माण|first1=Kishore |last1=Jaganathan |first2=Babak |last2=Hassibi|year=2012 |class=cs.DM }}</ref>
जब त्रुटि सलाखों के साथ दूरियों का मल्टीसमुच्चय दिया जाता है, तब भी एक आयामी स्थिति एनपी हार्ड होती है। फिर भी कई स्थितियों के लिए व्यावहारिक एल्गोरिदम उपस्तिथ हैं, उदाहरण के लिए यादृच्छिक बिंदु इसका मुख्य उदाहरण हैं।<ref>{{Cite book |title=असतत और कम्प्यूटेशनल ज्यामिति|last1=Lemke |first1=Paul |chapter=Reconstructing Sets From Interpoint Distances |last2=Skiena |first2=Steven S. |last3=Smith |first3=Warren D. |date=2003 |publisher=Springer Berlin Heidelberg |isbn=978-3-642-62442-1 |editor-last=Aronov |editor-first=Boris |volume=25 |location=Berlin, Heidelberg |pages=597–631 |doi=10.1007/978-3-642-55566-4_27 |editor-last2=Basu |editor-first2=Saugata |editor-last3=Pach |editor-first3=János |editor-last4=Sharir |editor-first4=Micha}}</ref><ref>{{Cite journal |arxiv=1804.02465 |title=दूरस्थ वितरण से पुन: निर्माण बिंदु समूह|first1=Shuai |last1=Huang |first2=Ivan |last2=Dokmanić |journal=IEEE Transactions on Signal Processing |year=2021|volume=69 |pages=1811–1827 |doi=10.1109/TSP.2021.3063458 |s2cid=4746784 }}</ref><ref>{{Cite arXiv |eprint=1212.2386 |title=जोड़ीवार दूरियों से पूर्णांकों का पुनर्निर्माण|first1=Kishore |last1=Jaganathan |first2=Babak |last2=Hassibi|year=2012 |class=cs.DM }}</ref>
== अभ्यावेदन की विशिष्टता ==
== अभ्यावेदन की विशिष्टता ==
एक यूक्लिडियन दूरी मैट्रिक्स को देखते हुए, बिंदुओं का क्रम जो यह महसूस करता है कि यह कठोर परिवर्तनों तक अद्वितीय है - ये यूक्लिडियन अंतरिक्ष की आइसोमेट्री हैं: रोटेशन (गणित), परावर्तन (गणित), अनुवाद (ज्यामिति), और उनकी रचनाएँ।<ref name="DPRZ"/>
एक यूक्लिडियन दूरी आव्यूह को देखते हुए, बिंदुओं का क्रम जो यह महसूस करता है कि यह कठोर परिवर्तनों तक अद्वितीय है - ये यूक्लिडियन अंतरिक्ष की आइसोमेट्री हैं: घूर्णन (गणित), परावर्तन (गणित), अनुवाद (ज्यामिति), और उनकी रचनाएँ।<ref name="DPRZ"/>


{{Math theorem|name=Theorem|
{{Math theorem|name=Theorem|
Line 111: Line 115:
The distances <math>\|x_i-x_j\|</math> and <math>\|y_i-y_j\|</math> are equal (for all {{math|1≤''i'',''j''≤''n''}}) if and only if there is a rigid transformation of {{math|ℝ<sup>''k''</sup>}} mapping <math>x_i</math> to <math>y_i</math> (for all {{math|1≤''i''≤''n''}}).
The distances <math>\|x_i-x_j\|</math> and <math>\|y_i-y_j\|</math> are equal (for all {{math|1≤''i'',''j''≤''n''}}) if and only if there is a rigid transformation of {{math|ℝ<sup>''k''</sup>}} mapping <math>x_i</math> to <math>y_i</math> (for all {{math|1≤''i''≤''n''}}).
}}
}}
{{Collapse top|title=Proof}}
{{Collapse top|title=प्रमाण}}
कठोर परिवर्तन दूरियों को बनाए रखते हैं इसलिए एक दिशा स्पष्ट होती है।
कठोर परिवर्तन दूरियों को बनाए रखते हैं इसलिए एक दिशा स्पष्ट होती है।
मान लीजिए दूरियां <math>\|x_i-x_j\|</math> और <math>\|y_i-y_j\|</math> बराबर हैं।
मान लीजिए दूरियां <math>\|x_i-x_j\|</math> और <math>\|y_i-y_j\|</math> बराबर हैं।
Line 123: Line 127:




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


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

Revision as of 00:43, 28 April 2023

गणित में, यूक्लिडियन दूरी आव्यूह n×n आव्यूह (गणित) के समुच्चय के अंतर का प्रतिनिधित्व करता है {{mvar|n}यूक्लिडियन अंतरिक्ष में } बिंदु (ज्यामिति) के समान हैं।

इस प्रकार के मान के लिए इसमें k-विमीय स्थान k हैं, जिसके लिए यूक्लिडियन दूरी आव्यूह के तत्व A उनके बीच की दूरियों के वर्ग द्वारा दिए गए हैं।

यह मान इस प्रकार हैं-

कथन

जहाँ यूक्लिडियन मानदंड k को दर्शाता है।

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

चूंकि यूक्लिडियन स्थितियों में, दूरियों के वर्गों का उपयोग वर्गमूलों की गणना से बचने और प्रासंगिक प्रमेयों और एल्गोरिदम को सरल बनाने के लिए किया जाता है।

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

रैखिक बीजगणित के तरीकों का उपयोग करके उत्तरार्द्ध का सरलता से विश्लेषित किया जाता है।

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

व्यावहारिक अनुप्रयोगों में दूरियां मुख्यतः इस ध्वनि की माप को प्रदर्शित करता हैं तथा स्वयं से समानता की माप करके इन्हें अनुमानों से इंगित करता हैं, (आवश्यक नहीं कि मीट्रिक (गणित))।

लक्षित यूक्लिडियन अंतरिक्ष में बिंदुओं द्वारा ऐसे डेटा की कल्पना करना हो सकता है, जिसकी दूरी आव्यूह किसी दिए गए असमानता आव्यूह के साथ-साथ संभव हो - इसे बहुआयामी स्केलिंग के रूप में जाना जाता है।

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

गुण

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

  • आव्यूह के विकर्ण पर सभी तत्व A शून्य हैं (अर्थात यह एक खोखला आव्यूह है); इसलिए एक आव्यूह का निशान A शून्य है।
  • A सममित आव्यूह (अर्थात ) है।
  • (त्रिकोण असमानता द्वारा)

आयाम में k, यूक्लिडियन दूरी आव्यूह में रैंक (रैखिक बीजगणित) से कम या k+2 के बराबर है, इस प्रकार यदि सामान्य स्थिति में हैं, तो रैंक min(n, k + 2). रहती हैं।

यूक्लिडियन दूरी आव्यूह प्राप्त करने के लिए दूरियों को किसी भी शक्ति से कम किया जा सकता है। अर्थात यदि एक यूक्लिडियन दूरी आव्यूह है, तो प्रत्येक के लिए एक यूक्लिडियन दूरी आव्यूह 0<s<1 है।[3]

ग्राम आव्यूह से संबंध

अंकों के अनुक्रम का ग्राम आव्यूह में k-विमीय स्थान kहै। इस कारण n×n आव्यूह के डॉट उत्पाद (यहां एक बिंदु 0 से उस बिंदु तक वेक्टर के रूप में माना जाता है):

, जहाँ वेक्टर के बीच का कोण और है।

विशेष रूप से

की दूरी से 0 का वर्ग है ।

इस प्रकार ग्राम आव्यूह सदिश के मानदंडों और कोणों (0 से) का वर्णन करता है

होने देना हो k×n आव्यूह युक्त स्तंभों के रूप में रहता हैं।

इस प्रकार , होने पर (देख के कॉलम वेक्टर के रूप में रहता हैं)।

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

यूक्लिडियन दूरी आव्यूह को ग्राम आव्यूह से संबंधित करने के लिए उपयोग किया जाता हैं, इसे इस प्रकार लिखा जा सकता हैं।

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

इसके विपरीत दूरियां के जोड़े के बीच n+1 अंक के बीच डॉट उत्पाद निर्धारित करें n सदिश (1≤in):

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

लक्षण वर्णन

एक के लिए n×n आव्यूह A, अंकों का एक क्रम में k-आयामी यूक्लिडियन स्थान k का बोध कहा जाता है A में k यदि A उनकी यूक्लिडियन दूरी आव्यूह है।

किसी सामान्यता की हानि के बिना मान सकता है कि (क्योंकि अनुवाद (ज्यामिति) द्वारा दूरी बनाए रखता है)।

Theorem[4] (Schoenberg criterion,[5] independently shown by Young & Householder[6]) —  एक सममित hollow n×n आव्यूह x A वास्तविक प्रविष्टियों के साथ एक बोध को स्वीकार करता है k यदि (n-1)×(n-1) आव्यूह के द्वारा प्रदर्शित किया जाता हैं।

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

यह पिछली चर्चा से इस प्रकार है क्योंकि G अधिक से अधिक रैंक का धनात्मक अर्धनिश्चित है k यदि और केवल यदि इसे विघटित किया जा सकता है जहाँ X एक k×n आव्यूह।[7] इसके अतिरिक्त, के कॉलम X में k को प्रदर्शित करने में सहायक हैं।

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

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

Corollary[8] —  एक सममति hollow n×n आव्यूह A वास्तविक प्रविष्टियों के साथ अगर और केवल अगर एक अहसास को स्वीकार करता है A हाइपरप्लेन पर ऋणात्मक अर्धनिश्चित है , जो इस प्रकार हैं

for all के कारण .

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

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

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

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

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

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

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

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

Theorem —  Let and be two sequences of points in k-dimensional Euclidean space k. The distances and are equal (for all 1≤i,jn) if and only if there is a rigid transformation of k mapping to (for all 1≤in).

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

कठोर परिवर्तन दूरियों को बनाए रखते हैं इसलिए एक दिशा स्पष्ट होती है। मान लीजिए दूरियां और बराबर हैं। व्यापकता के नुकसान के बिना हम मान सकते हैं द्वारा बिंदुओं का अनुवाद करके और , क्रमश। फिर (n-1)×(n-1) शेष सदिशों का ग्राम आव्यूह सदिशों के ग्राम आव्यूह के समान है (2≤in). वह है, , कहाँ X और Y हैं k×(n-1) कॉलम के रूप में संबंधित वैक्टर युक्त मैट्रिसेस। इसका तात्पर्य है कि एक ऑर्थोगोनल मैट्रिक्स मौजूद है k×k आव्यूह Q ऐसा है कि QX=Y, निश्चित सममित मैट्रिक्स देखें#एकात्मक परिवर्तनों तक अद्वितीयता। Q के एक ओर्थोगोनल परिवर्तन का वर्णन करता है k (अनुवाद के बिना घुमावों और प्रतिबिंबों की रचना) जो मैप करता है को (और 0 से 0)। अंतिम कठोर परिवर्तन द्वारा वर्णित है .


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

इन अनुप्रयोगों के उदाहरणों में उपग्रहों के झुकाव का निर्धारण करना, अणु संरचना (रसायन सूचना विज्ञान में), प्रोटीन संरचना (जैव सूचना विज्ञान में संरचनात्मक संरेखण), या हड्डी संरचना (जीव विज्ञान में सांख्यिकीय आकार विश्लेषण) की तुलना करना सम्मिलित है।

यह भी देखें

टिप्पणियाँ

  1. 1.0 1.1 Dokmanic et al. (2015)
  2. So (2007)
  3. Maehara, Hiroshi (2013). "परिमित मीट्रिक रिक्त स्थान के यूक्लिडियन एम्बेडिंग". Discrete Mathematics (in English). 313 (23): 2848–2856. doi:10.1016/j.disc.2013.08.029. ISSN 0012-365X. Theorem 2.6
  4. So (2007), Theorem 3.3.1, p. 40
  5. Schoenberg, I. J. (1935). "Remarks to Maurice Fréchet's Article "Sur La Definition Axiomatique D'Une Classe D'Espace Distances Vectoriellement Applicable Sur L'Espace De Hilbert"". Annals of Mathematics. 36 (3): 724–732. doi:10.2307/1968654. ISSN 0003-486X. JSTOR 1968654.
  6. Young, Gale; Householder, A. S. (1938-03-01). "Discussion of a set of points in terms of their mutual distances". Psychometrika (in English). 3 (1): 19–22. doi:10.1007/BF02287916. ISSN 1860-0980. S2CID 122400126.
  7. So (2007), Theorem 2.2.1, p. 10
  8. So (2007), Corollary 3.3.3, p. 42
  9. Menger, Karl (1931). "New Foundation of Euclidean Geometry". American Journal of Mathematics. 53 (4): 721–745. doi:10.2307/2371222. JSTOR 2371222.
  10. Lemke, Paul; Skiena, Steven S.; Smith, Warren D. (2003). "Reconstructing Sets From Interpoint Distances". In Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.). असतत और कम्प्यूटेशनल ज्यामिति. Vol. 25. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 597–631. doi:10.1007/978-3-642-55566-4_27. ISBN 978-3-642-62442-1.
  11. Huang, Shuai; Dokmanić, Ivan (2021). "दूरस्थ वितरण से पुन: निर्माण बिंदु समूह". IEEE Transactions on Signal Processing. 69: 1811–1827. arXiv:1804.02465. doi:10.1109/TSP.2021.3063458. S2CID 4746784.
  12. Jaganathan, Kishore; Hassibi, Babak (2012). "जोड़ीवार दूरियों से पूर्णांकों का पुनर्निर्माण". arXiv:1212.2386 [cs.DM].


संदर्भ