Hadamard's maximal determinant problem
हैडमर्ड की अधिकतम निर्धारक समस्या, जिसका नाम जैक्स हैडमर्ड के नाम पर रखा गया है, 1 या-1 के बराबर तत्वों के साथ एक मैट्रिक्स के सबसे बड़े निर्धारक के लिए पूछता है। 0 या 1 के बराबर तत्वों वाले मैट्रिक्स के लिए अनुरूप प्रश्न समतुल्य है क्योंकि, जैसा कि नीचे दिखाया जाएगा, आकार n के एक {1,-1} मैट्रिक्स का अधिकतम निर्धारक आकार n-1 के एक {0,1} मैट्रिक्स के अधिकतम निर्धारक का 2n-1 गुना है। यह समस्या हैडमर्ड द्वारा 1893 के पेपर में पेश की गई थी जिसमें उन्होंने अपने प्रसिद्ध निर्धारक बाउंड को प्रस्तुत किया था और सामान्य आकार के मैट्रिक्स के लिए अनसुलझा बना हुआ है। हैडमर्ड की सीमा का तात्पर्य है कि n आकार के {1,-1}-मैट्रिक में अधिकतम nn/2 पर निर्धारक होता है। हदामार्ड ने देखा कि सिल्वेस्टर का एक निर्माण मैट्रिक्स के उदाहरण उत्पन्न करता है जो 2 की घात n होने पर सीमा प्राप्त करते हैं, और 12 और 20 के अपने आकार के उदाहरण प्रस्तुत करते हैं। उन्होंने यह भी दिखाया कि सीमा केवल तभी प्राप्त की जा सकती है जब n 1,2, या 4 के गुणक के बराबर हो। अतिरिक्त उदाहरणों का निर्माण बाद में स्कार्पिस और पाले और बाद में कई अन्य लेखकों द्वारा किया गया। इस तरह के मैट्रिक्स को अब हदामर्ड मैट्रिक्स के रूप में जाना जाता है। उन्होंने गहन अध्ययन प्राप्त किया है। मैट्रिक्स आकार n जिसके लिए n ष्ण 1,2, या 3 (मॉड 4) पर कम ध्यान दिया गया है। सबसे शुरुआती परिणाम बारबा के कारण हैं, जिन्होंने एन विषम के लिए हैडमर्ड की सीमा को कड़ा कर दिया, और विलियमसन, जिन्होंने एन = 3,5,6 और 7 के लिए सबसे बड़े निर्धारक पाए। कुछ महत्वपूर्ण परिणामों में बारबा, एहलिच और वोज्तास के कारण, n ष्ण, 1,2, या 3 (मॉड 4) के लिए सख्त सीमाएं शामिल हैं, जो, हालांकि, हमेशा प्राप्य नहीं होने के लिए जाने जाते हैं, n ष्ण, या 2 (मॉड 4) के लिए सीमा प्राप्त करने वाले मैट्रिक्स के कुछ अनंत अनुक्रम, विशिष्ट n ष्ण, या 2 (मॉड 4) के लिए सीमा प्राप्त करने वाले कई मैट्रिक्स, विशिष्ट n ष्ण, या 3 (मॉड 4) के लिए सीमा प्राप्त नहीं करने वाले कई मैट्रिक्स, लेकिन जो संपूर्ण गणना द्वारा अधिकतम निर्धारक होने के लिए साबित हुए हैं। सांख्यिकी में प्रयोगों का प्रारूप {1, −1} मैट्रिक्स X (आवश्यक रूप से वर्ग नहीं) का उपयोग करता है जिसके लिए सूचना मैट्रिक्स XTX में अधिकतम निर्धारक होता है। (संकेतन XT X के स्थानांतर को दर्शाता है।) इस तरह के मैट्रिक्स को डी-इष्टतम डिजाइन के रूप में जाना जाता है। यदि एक्स एक वर्ग मैट्रिक्स है, तो इसे संतृप्त डी-इष्टतम डिजाइन के रूप में जाना जाता है। हैडमर्ड मैट्रिक्स n × n हैडमर्ड मैट्रिक्स की कोई भी दो पंक्तियाँ ऑर्थोगोनल होती हैं। {1, −1} मैट्रिक्स के लिए, इसका मतलब है कि कोई भी दो पंक्तियाँ प्रविष्टियों के ठीक आधे में भिन्न होती हैं, जो तब असंभव है जब n एक विषम संख्या है। जब n ष्ण2 (मॉड 4), दो पंक्तियाँ जो दोनों तीसरी पंक्ति के ऑर्थोगोनल हैं, एक दूसरे के लिए ऑर्थोगोनल नहीं हो सकती हैं। एक साथ, इन कथनों का तात्पर्य है कि एक n × n हैडमार्ड मैट्रिक्स केवल तभी मौजूद हो सकता है जब n = 1,2, या 4 का गुणक हो। हैडमर्ड मैट्रिक्स का अच्छी तरह से अध्ययन किया गया है, लेकिन यह ज्ञात नहीं है कि क्या प्रत्येक n के लिए एक n × n हैडमर्ड मैट्रिक्स मौजूद है जो 4 का एक सकारात्मक गुणक है। सबसे छोटा n जिसके लिए एक n × n हडामर्ड मैट्रिक्स मौजूद नहीं है, वह 668 है। {1, −1} मैट्रिक्स की समतुल्यता और सामान्यीकरण निम्नलिखित में से कोई भी ऑपरेशन, जब एक {1, −1} मैट्रिक्स आर पर किया जाता है, तो आर के निर्धारक को केवल एक माइनस संकेत से बदल देता हैः एक पंक्ति की नकारात्मकता। एक कॉलम का निषेध। दो पंक्तियों का आदान-प्रदान। दो स्तंभों का आदान-प्रदान। दो {1, −1} मैट्रिक्स, R1 और R2, को समकक्ष माना जाता है यदि R1 को उपरोक्त संचालन के कुछ अनुक्रम द्वारा R2 में परिवर्तित किया जा सकता है। समतुल्य मैट्रिक्स के निर्धारक बराबर होते हैं, संभवतः एक संकेत परिवर्तन को छोड़कर, और पंक्तियों और स्तंभों के नकारात्मक और क्रमपरिवर्तन के माध्यम से आर को मानकीकृत करना अक्सर सुविधाजनक होता है। A {1, −1} मैट्रिक्स को सामान्यीकृत किया जाता है यदि इसकी पहली पंक्ति और स्तंभ के सभी तत्व 1 के बराबर हों। जब किसी मैट्रिक्स का आकार विषम होता है, तो कभी-कभी एक अलग सामान्यीकरण का उपयोग करना उपयोगी होता है जिसमें प्रत्येक पंक्ति और स्तंभ में तत्वों की सम संख्या 1 और तत्वों की विषम संख्या-1 होती है। इनमें से किसी भी सामान्यीकरण को पहले दो ऑपरेशनों का उपयोग करके पूरा किया जा सकता है। {1, −1} और {0,1} मैट्रिक्स के लिए अधिकतम निर्धारक समस्याओं का संबंध सामान्यीकृत n × n {1, −1} मैट्रिक्स के सेट से (n − 1) × (n-1) {0,1} मैट्रिक्स के सेट तक एक-से-एक नक्शा है जिसके तहत निर्धारक का परिमाण 21 − n के कारक से कम हो जाता है। इस मानचित्र में निम्नलिखित चरण शामिल हैं। {1, −1} मैट्रिक्स की पंक्ति 1 को पंक्ति 2 से n तक घटाएँ। (इससे निर्धारक नहीं बदलता है।) (n−1) × (n−1) उपमैट्रिक्स को निकालें जिसमें पंक्तियाँ 2 से n और कॉलम 2 से n शामिल हैं। इस मैट्रिक्स में तत्व 0 और-2 हैं। (इस उपमैट्रिक्स का निर्धारक मूल मैट्रिक्स के समान है, जैसा कि चरण 1 में प्राप्त मैट्रिक्स के कॉलम 1 पर एक सह-कारक विस्तार करके देखा जा सकता है।) {0,1} मैट्रिक्स प्राप्त करने के लिए उपमैट्रिक्स को-2 से विभाजित करें। (यह निर्धारक को (−2) 1 − n से गुणा करता है।) उदाहरण-इस उदाहरण में, मूल मैट्रिक्स में निर्धारक −16 है और इसकी छवि में निर्धारक 2 = −16· (−2) −3 है। चूँकि एक {0,1} मैट्रिक्स का निर्धारक एक पूर्णांक है, इसलिए एक n × n {1, −1} मैट्रिक्स का निर्धारक 2n − 1 का एक पूर्णांक गुणक है। अधिकतम निर्धारक ग्राम मैट्रिक्स पर ऊपरी सीमाएँ मान लीजिए कि R एक n बटा n {1, −1} मैट्रिक्स है। आर के ग्राम मैट्रिक्स को मैट्रिक्स जी = आरआरटी के रूप में परिभाषित किया गया है। इस परिभाषा से यह पता चलता है कि G एक पूर्णांक मैट्रिक्स है, सममित है, धनात्मक-समपरिमित है, जिसमें स्थिर विकर्ण होता है जिसका मान n के बराबर होता है। R की पंक्तियों को नकारने या उन पर क्रमपरिवर्तन लागू करने के परिणामस्वरूप G की पंक्तियों और संबंधित स्तंभों दोनों पर समान नकारात्मकता और क्रमपरिवर्तन लागू होता है। हम मैट्रिक्स G′ = RTR को भी परिभाषित कर सकते हैं। मैट्रिक्स G वैक्टरों के एक समूह का सामान्य ग्राम मैट्रिक्स है, जो R की पंक्तियों के सेट से प्राप्त होता है, जबकि G′ R के कॉलम के सेट से प्राप्त ग्राम मैट्रिक्स है। प्रत्येक ज्ञात अधिकतम-निर्धारक मैट्रिक्स एक सामान्य मैट्रिक्स के बराबर होता है, लेकिन यह ज्ञात नहीं है कि हमेशा ऐसा होता है या नहीं। हैडमर्ड की सीमा (सभी एन के लिए) हैडमर्ड की सीमा को यह नोट करके प्राप्त किया जा सकता है कि |det R। = (डेट G) 1/2 ≤ (डेट nI) 1/2 = nn/2, जो इस अवलोकन का एक परिणाम है कि nI, जहां I, n द्वारा n पहचान मैट्रिक्स है, 1-4 गुणों को संतुष्ट करने वाले मैट्रिक्स के बीच अधिकतम निर्धारक का अद्वितीय मैट्रिक्स है। वह डेट आर 2n−1 का एक पूर्णांक गुणक होना चाहिए जिसका उपयोग एक और प्रदर्शन प्रदान करने के लिए किया जा सकता है कि हैडमर्ड की सीमा हमेशा प्राप्य नहीं होती है। जब n विषम होता है, तो बद्ध nn/2 या तो गैर-पूर्णांक या विषम होता है, और इसलिए n = 1 को छोड़कर अप्राप्य होता है। जब n = 2k के साथ k विषम होता है, तो 2 को हडमर्ड की सीमा को विभाजित करने की उच्चतम शक्ति 2k होती है जो 2n−1 से कम होती है जब तक कि n = 2 न हो। इसलिए, हैडमर्ड की सीमा तब तक अप्राप्य है जब तक कि n = 1,2, या 4 का गुणक न हो। जब n विषम होता है, तो ग्राम मैट्रिक्स के लिए गुण 1 को G से मजबूत किया जा सकता है जो एक विषम-पूर्णांक मैट्रिक्स है। यह एक तेज ऊपरी सीमा को प्राप्त करने की अनुमति देता हैः |det R। = (डेट G) 1/2 ≤ (डेट (n-1) I + J) 1/2 = (2n−1) 1/2 (n−1) (n−1)/2, जहां J ऑल-वन मैट्रिक्स है। यहाँ (n-1) I + J अधिकतम-निर्धारक मैट्रिक्स है जो संशोधित गुण 1 और गुण 2-4 को संतुष्ट करता है। यह पंक्तियों के किसी भी समूह और स्तंभों के संबंधित समूह को-1 से गुणा करने के लिए अद्वितीय है। सीमा तब तक प्राप्य नहीं है जब तक कि 2n−1 एक पूर्ण वर्ग न हो, और इसलिए n ष्ण 3 (मॉड 4) होने पर कभी भी प्राप्य नहीं है। इलिच-वोज्तास n ष्ण2 (मॉड 4) के लिए बंधे होते हैं जब n सम होता है, तो R की पंक्तियों के समूह को दो उपसमुच्चय में विभाजित किया जा सकता है। सम प्रकार की पंक्तियों में तत्वों की सम संख्या 1 और तत्वों की सम संख्या-1 होती है। विषम प्रकार की पंक्तियों में तत्वों की विषम संख्या 1 और तत्वों की विषम संख्या-1 होती है। एक ही प्रकार की दो पंक्तियों का बिंदु उत्पाद n (मॉड 4) के लिए सर्वांगसम है; विपरीत प्रकार की दो पंक्तियों का बिंदु उत्पाद n + 2 (मॉड 4) के लिए सर्वांगसम है। जब n ष्ण2 (मॉड 4), इसका तात्पर्य है कि, R की पंक्तियों को क्रमबद्ध करके, हम मानक रूप मान सकते हैं, जहाँ A और D सममित पूर्णांक मैट्रिक्स हैं जिनके तत्व 2 (मॉड 4) के सर्वांगसम हैं और B एक मैट्रिक्स है जिसके तत्व 0 (मॉड 4) के सर्वांगसम हैं। 1964 में, एलिच और वोज्तास ने स्वतंत्र रूप से दिखाया कि इस रूप के अधिकतम निर्धारक मैट्रिक्स में, ए और डी दोनों आकार एन/2 के हैं और (एन-2) आई + 2जे के बराबर हैं जबकि बी शून्य मैट्रिक्स है। यह इष्टतम रूप पंक्तियों के किसी भी समूह और स्तंभों के संबंधित समूह को-1 से गुणा करने और पंक्तियों और स्तंभों में एक क्रमपरिवर्तन के एक साथ अनुप्रयोग करने के लिए अद्वितीय है। इसका तात्पर्य है बाध्य डेट R ≤ (2n−2) (n−2) (n−2)/2। एहलिच ने दिखाया कि यदि आर सीमा प्राप्त करता है, और यदि आर की पंक्तियों और स्तंभों को क्रमबद्ध किया जाता है ताकि जी = आरआरटी और जी ′ = आरटीआर दोनों का मानक रूप हो और उपयुक्त रूप से सामान्यीकृत हो, तो हम लिख सकते हैं कि डब्ल्यू, एक्स, वाई, और जेड (एन/2) × (एन/2) मैट्रिक्स हैं जिसमें स्थिर पंक्ति और स्तंभ योग डब्ल्यू, एक्स, वाई, और जेड हैं जो जेड =-डब्ल्यू, वाई = एक्स, और डब्ल्यू 2 + एक्स 2 = 2एन-2 को संतुष्ट करते हैं। इसलिए एलिच-वोज्तास सीमा तब तक प्राप्य नहीं है जब तक कि 2n−2 को दो वर्गों के योग के रूप में व्यक्त नहीं किया जाता है। जब n विषम होता है, तो पंक्तियों को-1 से गुणा करने की स्वतंत्रता का उपयोग करके, यह शर्त लगाई जा सकती है कि R की प्रत्येक पंक्ति में तत्वों की सम संख्या 1 और तत्वों की विषम संख्या-1 हो। यह दिखाया जा सकता है कि, यदि इस सामान्यीकरण को माना जाता है, तो G के गुण 1 को G से मजबूत किया जा सकता है जो n (मॉड 4) के अनुरूप पूर्णांक तत्वों के साथ एक मैट्रिक्स है। जब n ष्ण 1 (मॉड 4) होता है, तो बारबा का इष्टतम रूप इस मजबूत गुण को संतुष्ट करता है, लेकिन जब n ष्ण 3 (मॉड 4) होता है, तो ऐसा नहीं होता है। इसका मतलब है कि बाद के मामले में सीमा को तेज किया जा सकता है। एहलिच ने दिखाया कि जब n ष्ण 3 (मॉड 4) होता है, तो मजबूत गुण 1 का तात्पर्य है कि G के अधिकतम-निर्धारक रूप को B − J के रूप में लिखा जा सकता है, जहां J ऑल-वन मैट्रिक्स है और B एक ब्लॉक-डायगोनल मैट्रिक्स है, जिसके विकर्ण खंड (n-3) I + 4J के रूप में हैं। इसके अलावा, उन्होंने दिखाया कि इष्टतम रूप में, खंडों की संख्या, s, n पर निर्भर करती है जैसा कि नीचे दी गई तालिका में दिखाया गया है, और प्रत्येक खंड का आकार या तो r या आकार r + 1 है जहां n = 11 को छोड़कर जहां दो संभावनाएं हैं, इष्टतम रूप पंक्तियों के किसी भी सेट और स्तंभों के संबंधित सेट को-1 से गुणा करने और पंक्तियों और स्तंभों में क्रमपरिवर्तन के एक साथ अनुप्रयोग करने के लिए अद्वितीय है। यह इष्टतम रूप उस सीमा की ओर ले जाता है जहां v = n − rs आकार r + 1 के खंडों की संख्या है और u = s − v आकार r के खंडों की संख्या है। कोहन ने सीमा का विश्लेषण किया और निर्धारित किया कि, n = 3 के अलावा, यह केवल n = 112t2 ± 28t + 7 के लिए कुछ सकारात्मक पूर्णांक t के लिए एक पूर्णांक है। तमुरा ने द्विघात रूपों की तर्कसंगत समतुल्यता पर हैसे-मिंकॉव्स्की प्रमेय का उपयोग करके सीमा की प्राप्ति पर अतिरिक्त प्रतिबंध प्राप्त किए, और दिखाया कि सबसे छोटा n> 3 जिसके लिए एलिच की सीमा 511 है। आकार 21 तक के अधिकतम निर्धारक आकार n = 21 तक के {1, −1} मैट्रिक्स के अधिकतम निर्धारक निम्नलिखित तालिका में दिए गए हैं। आकार 22 सबसे छोटा खुला केस है। तालिका में, D (n) 2n−1 से विभाजित अधिकतम निर्धारक का प्रतिनिधित्व करता है। समान रूप से, डी (एन) आकार एन-1 के {0,1} मैट्रिक्स के अधिकतम निर्धारक का प्रतिनिधित्व करता है। संदर्भ संयुक्त अभिकल्पना मैट्रिक गणित में अनसुलझी समस्याएं