हैडामर्ड आव्यूह

See also: Walsh matrix

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

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

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

गुण

मान लीजिए कि H क्रम n का एक हैडामर्ड आव्यूह होता है। H का स्थानान्तरण इसके व्युत्क्रम से निकटता से संबंधित होता है। वास्तव में:

$HH^{\textsf {T}}=nI_{n}$

जहां n × n पहचान आव्यूह I_nहोता है और H^T का स्थानान्तरण होता है H यह देखने के लिए कि यह सत्य है, ध्यान दें कि H की पंक्तियाँ वास्तविक संख्याओं के क्षेत्र में सभी आयतीय सदिश होता हैं और प्रत्येक की लंबाई है ${\sqrt {n}}$. इस लंबाई से H को विभाजित करने पर आयतीय आव्यूह मिलता है जिसका स्थानान्तरण इस प्रकार इसका व्युत्क्रम होता है। लंबाई से गुणा करने पर फिर से उपरोक्त समानता प्राप्त होती है। नतीजतन,

$\operatorname {det} (H)=\pm n^{n/2},$

जहां det(H) H का निर्धारक होता है।

मान लीजिए कि M क्रम n का जटिल आव्यूह है, जिसकी प्रविष्टियाँ |M से घिरी हुई हैं_ij| ≤ 1, प्रत्येक i, j के लिए 1 और n के बीच होता है। फिर हैडामर्ड की असमानता होता है | हैडामर्ड की निर्धारक सीमा यह बताती है

$|\operatorname {det} (M)|\leq n^{n/2}.$

इस सीमा में समानता वास्तविक आव्यूह M के लिए प्राप्त की जाती है यदि M एक हैडामर्ड आव्यूह होता है।

हैडामर्ड आव्यूह का क्रम 1, 2, या 4 का गुणज होना चाहिए था।

सिल्वेस्टर का निर्माण

हैडामर्ड आव्यूह के उदाहरण वास्तव में पहली बार 1867 में जेम्स जोसेफ सिल्वेस्टर द्वारा बनाए गए थे। मान लीजिए कि H क्रम n का हैडामर्ड आव्यूह होता है। फिर विभाजित आव्यूह

${\begin{bmatrix}H&H\\H&-H\end{bmatrix}}$

क्रम 2n का हैडामर्ड आव्यूह होता है। इस अवलोकन को बार-बार क्रियान्वित किया जा सकता है और आव्यूह निम्नलिखित अनुक्रम की ओर ले जाता है, जिसे वॉल्श आव्यूह भी कहा जाता है।

${\begin{aligned}H_{1}&={\begin{bmatrix}1\end{bmatrix}},\\H_{2}&={\begin{bmatrix}1&1\\1&-1\end{bmatrix}},\\H_{4}&={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}},\end{aligned}}$

और

$H_{2^{k}}={\begin{bmatrix}H_{2^{k-1}}&H_{2^{k-1}}\\H_{2^{k-1}}&-H_{2^{k-1}}\end{bmatrix}}=H_{2}\otimes H_{2^{k-1}},$

के लिए $2\leq k\in N$, कहाँ $\otimes$ क्रोनकर उत्पाद को दर्शाता है।

इस प्रकार, सिल्वेस्टर ने क्रम 2^k के हैडामर्ड आव्यूह का निर्माण किया और प्रत्येक गैर -नकारात्मक पूर्णांक k होता है ।

सिल्वेस्टर के आव्यूह में कई विशेष गुण होता हैं। वे सममित आव्यूह होता हैं और,जब k ≥ 1 (2^k  > 1), निशान (रैखिक बीजगणित) शून्य होता है। पहले स्तंभ और पहली पंक्ति के सभी तत्व धनात्मक संख्या होता हैं। अन्य सभी पंक्तियों और स्तंभों के तत्वों को चिह्न (गणित) के बीच समान रूप से विभत किया गया है। सिल्वेस्टर आव्यूह वाल्श समारोह के साथ निकटता से जुड़े हुए हैं।

वैकल्पिक निर्माण

यदि हम समूह समरूपता का उपयोग करके हैडामर्ड आव्यूह के तत्वों को ख़ाक करते हैं $\{1,-1,\times \}\mapsto \{0,1,\oplus \}$, हम सिल्वेस्टर के हैडामर्ड आव्यूह के वैकल्पिक निर्माण का वर्णन कर सकते हैं। पहले आव्यूह पर विचार करें $F_{n}$, द $n\times 2^{n}$ आव्यूह जिसके स्तंभ में सभी n-बिट संख्याएं आरोही गिनती क्रम में व्यवस्थित होती हैं। हम परिभाषित कर सकते हैं $F_{n}$ द्वारा पुनरावर्ती

${\begin{aligned}F_{1}&={\begin{bmatrix}0&1\end{bmatrix}}\\F_{n}&={\begin{bmatrix}0_{1\times 2^{n-1}}&1_{1\times 2^{n-1}}\\F_{n-1}&F_{n-1}\end{bmatrix}}.\end{aligned}}$

प्रेरण द्वारा यह दिखाया जा सकता है कि उपरोक्त समरूपता के तहत हैडामर्ड आव्यूह की छवि दी गई है

$H_{2^{n}}=F_{n}^{\textsf {T}}F_{n}.$

यह निर्माण दर्शाता है कि हैडामर्ड आव्यूह की पंक्तियाँ $H_{2^{n}}$ लम्बाई के रूप में देखा जा सकता है $2^{n}$ रैखिक कोड लोकप्रिय नोटेशन n, और रैखिक कोड गुणों का रैखिक त्रुटि-सुधार कोड $2^{n-1}$ रैखिक कोड लोकप्रिय संकेतन के साथ $F_{n}.$

इस कोड को वॉल्श कोड भी कहा जाता है। इसके विपरीत, हैडामर्ड कोड, हैडामर्ड से निर्मित होता है $H_{2^{n}}$ थोड़ी अलग प्रक्रिया से होता है.

हैडमार्ड अनुमान

Unsolved problem in mathematics:

Is there a Hadamard matrix of order 4k for every positive integer k?

(more unsolved problems in mathematics)

हैडामर्ड आव्यूह के सिद्धांत में सबसे महत्वपूर्ण खुला प्रश्न अस्तित्व होता है। हैडामर्ड अनुमान का प्रस्ताव है कि प्रत्येक सकारात्मक पूर्णांक k के लिए क्रम 4k का हैडामर्ड आव्यूह उपस्थित होता है। हैडामर्ड अनुमान का श्रेय पाले को भी दिया गया है, यद्यपि पाले के काम से पहले अन्य लोगों द्वारा इस पर परोक्ष रूप से विचार किया गया था।

सिल्वेस्टर के निर्माण का सामान्यीकरण यह साबित करता है कि यदि $H_{n}$ और $H_{m}$ तो क्रमशः n और m क्रम हैडामर्ड आव्यूह हैं $H_{n}\otimes H_{m}$ क्रम nm का हैडामर्ड आव्यूह होता है। छोटे क्रम के ज्ञात होने के बाद इस परिणाम का उपयोग उच्च क्रम के हैडामर्ड आव्यूह का उत्पादन करने के लिए किया जाता है।

सिल्वेस्टर के 1867 के निर्माण से क्रम 1, 2, 4, 8, 16, 32 आदि के हैडामर्ड आव्यूह प्राप्त हुए थे। क्रम 12 और 20 के हैडामर्ड आव्यूह का निर्माण बाद में हैडामर्ड द्वारा (1893 में) किया गया था। 1933 में, रेमंड पेली ने पेले निर्माण की खोज की, जो क्रम q + 1 का हैडामर्ड आव्यूह उत्पन्न करता है जब q कोई अभाज्य संख्या शक्ति है जो 3 मापांक 4 के अनुरूप संबंध है और जो क्रम 2 (q + 1) का हडामर्ड आव्यूह उत्पन करता है जब q अभाज्य घात है जो 1 मापांक 4 के सर्वांगसम होता है। उनकी विधि परिमित क्षेत्र का उपयोग करती है।

सबसे छोटा क्रम जिसे सिल्वेस्टर और पैली के तरीकों के संयोजन से नहीं बनाया जा सकता है वह 92 होता है। इस क्रम का हैडामर्ड आव्यूह 1962 में जेपीएल में लियोनार्ड बॉमर्ट, सोलोमन डब्ल्यू गोलोम्ब और मार्शल हॉल (गणितज्ञ) द्वारा एक कंप्यूटर का उपयोग करके पाया गया था। जॉन विलियमसन (गणितज्ञ) के कारण, उन्होंने निर्माण का उपयोग किया था, इससे कई अतिरिक्त क्रम प्राप्त हुए थे। हैडामर्ड आव्यूह के निर्माण की कई अन्य विधियाँ अब ज्ञात होता हैं।

2005 में, हादी खराघानी और बेहरूज़ तायफेह-रेज़ाई ने क्रम 428 के हैडामर्ड आव्यूह के अपने निर्माण को प्रकाशित किया गया था । परिणामस्वरूप, सबसे छोटा क्रम जिसके लिए कोई हैडामर्ड आव्यूह वर्तमान में ज्ञात नही होता है, यह 668 होता है।

As of 2014, 2000 से कम या उसके बराबर 4 के 12 गुणज हैं जिनके लिए उस क्रम का कोई हैडामर्ड आव्यूह ज्ञात नहीं होता है। वे हैं:

668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, और 1964।

समानता और विशिष्टता

दो हैडामर्ड आव्यूह को तुल्यता संबंध माना जाता है यदि एक को दूसरे से पंक्तियों या स्तंभों को अस्वीकार करके, या पंक्तियों या स्तंभों को परस्पर बदलकर प्राप्त किया जा सकता है। समतुल्यता तक, क्रम 1, 2, 4, 8, और 12 का एक अद्वितीय हैडामर्ड आव्यूह है। क्रम 16 के 5, क्रम 20 के 3, क्रम 24 के 60, और क्रम 28 के 487 असमान आव्यूह हैं। लाखों असमान आव्यूह क्रम 32, 36, और 40 के लिए जाने जाते हैं। तुल्यता संबंध का उपयोग करना समतुल्य संबंध की तुलना करना, समतुल्यता की धारणा जो स्थानान्तरण की भी अनुमति देती है, क्रम 16 के 4, क्रम 20 के 3, क्रम 24 के 36, और 294 हैं क्रम 28 का.

हैडामर्ड आव्यूह भी निम्नलिखित अर्थों में विशिष्ट रूप से पुनर्प्राप्त करने योग्य हैं: यदि हैडामर्ड आव्यूह $H$ आदेश की $n$ है $O(n^{2}/\log n)$ प्रविष्टियाँ बेतरतीब ढंग से हटा दी जाती हैं, तो अत्यधिक संभावना के साथ, कोई मूल आव्यूह को पूरी तरह से पुनर्प्राप्त कर सकता है $H$ क्षतिग्रस्त से. पुनर्प्राप्ति के एल्गोरिदम की कम्प्यूटेशनल लागत आव्यूह व्युत्क्रम के समान है।

विशेष मामले

गणितीय साहित्य में हैडामर्ड आव्यूह के कई विशेष मामलों की जांच की गई है।

स्क्यू हैडामर्ड आव्यूह

एक हैडामर्ड आव्यूह एच तिरछा है यदि $H^{\textsf {T}}+H=2I.$ किसी भी पंक्ति और उसके संबंधित कॉलम को -1 से गुणा करने के बाद एक तिरछा हैडामर्ड आव्यूह तिरछा हैडामर्ड आव्यूह बना रहता है। यह संभव बनाता है, उदाहरण के लिए, एक स्क्यू हैडामर्ड आव्यूह को सामान्य बनाना ताकि पहली पंक्ति में सभी तत्व 1 के बराबर हों।

1972 में रीड और ब्राउन ने दिखाया कि क्रम n का एक दोगुना नियमित टूर्नामेंट (ग्राफ सिद्धांत) मौजूद है यदि और केवल तभी जब क्रम n + 1 का एक तिरछा हैडमार्ड आव्यूह मौजूद हो। क्रम n के गणितीय टूर्नामेंट में, प्रत्येक n खिलाड़ी एक खेलता है प्रत्येक अन्य खिलाड़ी के विरुद्ध मैच, प्रत्येक मैच में एक खिलाड़ी की जीत और दूसरे की हार होती है। यदि प्रत्येक खिलाड़ी समान संख्या में मैच जीतता है तो एक टूर्नामेंट नियमित होता है। एक नियमित टूर्नामेंट दोगुना नियमित होता है यदि दो अलग-अलग खिलाड़ियों द्वारा पराजित विरोधियों की संख्या अलग-अलग खिलाड़ियों की सभी जोड़ियों के लिए समान हो। चूंकि खेले गए प्रत्येक n (n−1) /2 मैचों में से एक खिलाड़ी की जीत होती है, इसलिए प्रत्येक खिलाड़ी (n−1) /2 मैच जीतता है (और समान संख्या में हारता है)। चूंकि किसी दिए गए खिलाड़ी द्वारा पराजित (n−1)/2 खिलाड़ियों में से प्रत्येक (n−3)/2 अन्य खिलाड़ियों से भी हार जाता है, खिलाड़ी जोड़ियों की संख्या (i,j) इस प्रकार है कि j, i और दोनों से हार जाता है दिया गया खिलाड़ी (n−1) (n−3) / 4 है। यदि जोड़ियों की अलग-अलग गिनती की जाए तो एक ही परिणाम प्राप्त होना चाहिए: दिया गया खिलाड़ी और (n−1) अन्य खिलाड़ियों में से कोई भी एक साथ समान संख्या में समान संख्या को हराता है विरोधियों. इसलिए पराजित विरोधियों की यह सामान्य संख्या (n−3) / 4 होनी चाहिए। एक अतिरिक्त खिलाड़ी को पेश करके एक स्क्यू हैडामर्ड मैट्रिक्स प्राप्त किया जाता है जो सभी मूल खिलाड़ियों को हरा देता है और फिर खिलाड़ियों द्वारा लेबल की गई पंक्तियों और स्तंभों के साथ एक मैट्रिक्स बनाता है। नियम है कि पंक्ति i, कॉलम j में 1 होता है यदि i = j या i, j को हरा देता है और -1 यदि j, i को हरा देता है। रिवर्स में यह पत्राचार एक तिरछा हैडामर्ड मैट्रिक्स से दोगुना नियमित टूर्नामेंट उत्पन्न करता है, यह मानते हुए कि तिरछा हैडामर्ड आव्यूह सामान्यीकृत है ताकि पहली पंक्ति के सभी तत्व 1 के बराबर हों।

नियमित हैडामर्ड आव्यूह

रेगुलर हैडामर्ड आव्यूह वास्तविक हैडामर्ड आव्यूह हैं जिनकी पंक्ति और स्तंभ का योग बराबर होता है। एक नियमित n×n Hadamard आव्यूह के अस्तित्व पर आवश्यक शर्त यह है कि n एक पूर्ण वर्ग हो। एक घूम आव्यूह स्पष्ट रूप से नियमित है, और इसलिए एक सर्कुलर हैडामर्ड आव्यूह को पूर्ण वर्ग क्रम का होना होगा। इसके अलावा, यदि n×n सर्कुलर हैडामर्ड

आव्यूह n > 1 के साथ मौजूद है तो n आवश्यक रूप से 4u के रूप का होगा²तुम्हारे साथ अजीब.

सर्कुलर हैडामर्ड आव्यूह

हालाँकि, सर्कुलर हैडामर्ड आव्यूह अनुमान यह दावा करता है कि, ज्ञात 1×1 ​​और 4×4 उदाहरणों के अलावा, ऐसा कोई आव्यूह मौजूद नहीं है। यह 10 से कम यू के 26 मूल्यों को छोड़कर सभी के लिए सत्यापित किया गया था⁴.

सामान्यीकरण

एक बुनियादी सामान्यीकरण एक वजन आव्यूह है। वेइंग आव्यूह एक वर्ग आव्यूह है जिसमें प्रविष्टियाँ शून्य भी हो सकती हैं और जो संतुष्ट करती है $WW^{\textsf {T}}=wI$ कुछ w के लिए, इसका वजन। एक वजन आव्यूह जिसका वजन उसके क्रम के बराबर है, एक हैडामर्ड आव्यूह है।

एक अन्य सामान्यीकरण एक जटिल हैडामर्ड आव्यूह को आव्यूह के रूप में परिभाषित करता है जिसमें प्रविष्टियाँ इकाई निरपेक्ष मान की जटिल संख्याएँ होती हैं और जो H को संतुष्ट करती हैं^* = n I_nजहां एच^*एच का संयुग्म स्थानान्तरण है। ऑपरेटर बीजगणित और क्वांटम गणना के सिद्धांत के अध्ययन में कॉम्प्लेक्स हैडामर्ड आव्यूह उत्पन्न होते हैं।

बटनसन-प्रकार हैडामर्ड आव्यूह जटिल हैडामर्ड आव्यूह हैं जिनमें प्रविष्टियाँ q के रूप में ली जाती हैं^{एकता की जड़ें. कॉम्प्लेक्स हैडामर्ड मैट्रिक्स शब्द का उपयोग कुछ लेखकों द्वारा विशेष रूप से केस q = 4 को संदर्भित करने के लिए किया गया है।}

व्यावहारिक अनुप्रयोग

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

यह भी देखें

• संयुक्त डिज़ाइन
• हैडमार्ड परिवर्तन
• पांचवां आव्यूह
• वॉल्श आव्यूह
• वजन आव्यूह
• क्वांटम लॉजिक गेट

अग्रिम पठन

• Baumert, L. D.; Hall, Marshall (1965). "Hadamard matrices of the Williamson type". Math. Comp. 19 (91): 442–447. doi:10.1090/S0025-5718-1965-0179093-2. MR 0179093.
• Georgiou, S.; Koukouvinos, C.; Seberry, J. (2003). "Hadamard matrices, orthogonal designs and construction algorithms". Designs 2002: Further computational and constructive design theory. Boston: Kluwer. pp. 133–205. ISBN 978-1-4020-7599-5.
• Goethals, J. M.; Seidel, J. J. (1970). "A skew Hadamard matrix of order 36". J. Austral. Math. Soc. 11 (3): 343–344. doi:10.1017/S144678870000673X. S2CID 14193297.
• Kimura, Hiroshi (1989). "New Hadamard matrix of order 24". Graphs and Combinatorics. 5 (1): 235–242. doi:10.1007/BF01788676. S2CID 39169723.
• Mood, Alexander M. (1964). "On Hotelling's Weighing Problem". Annals of Mathematical Statistics. 17 (4): 432–446. doi:10.1214/aoms/1177730883.
• Reid, K. B.; Brown, E. (1972). "Doubly regular tournaments are equivalent to skew Hadamard matrices". J. Combin. Theory Ser. A. 12 (3): 332–338. doi:10.1016/0097-3165(72)90098-2.
• Seberry Wallis, Jennifer (1976). "On the existence of Hadamard matrices". J. Comb. Theory A. 21 (2): 188–195. doi:10.1016/0097-3165(76)90062-5.
• Seberry, Jennifer (1980). "A construction for generalized hadamard matrices". J. Statist. Plann. Infer. 4 (4): 365–368. doi:10.1016/0378-3758(80)90021-X.
• Seberry, J.; Wysocki, B.; Wysocki, T. (2005). "On some applications of Hadamard matrices". Metrika. 62 (2–3): 221–239. doi:10.1007/s00184-005-0415-y. S2CID 40646.
• Spence, Edward (1995). "Classification of hadamard matrices of order 24 and 28". Discrete Math. 140 (1–3): 185–242. doi:10.1016/0012-365X(93)E0169-5.
• Yarlagadda, R. K.; Hershey, J. E. (1997). Hadamard Matrix Analysis and Synthesis. Boston: Kluwer. ISBN 978-0-7923-9826-4.

बाहरी संबंध

• Skew Hadamard matrices of all orders up to 100, including every type with order up to 28;
• "Hadamard Matrix". in OEIS
• N. J. A. Sloane. "Library of Hadamard Matrices".
• On-line utility to obtain all orders up to 1000, except 668, 716, 876 & 892.
• JPL: In 1961, mathematicians from NASA’s Jet Propulsion Laboratory and Caltech worked together to construct a Hadamard Matrix containing 92 rows and columns