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

This article is about matrices whose entries are integer numbers. For use of term unimodular in connection with polynomial matrices, see Unimodular polynomial matrix.

गणित में, एक यूनिमॉड्यूलर मैट्रिक्स एम एक उलटा मैट्रिक्स पूर्णांक मैट्रिक्स है जिसमें निर्धारक +1 या -1 होता है। समतुल्य रूप से, यह एक पूर्णांक मैट्रिक्स है जो पूर्णांकों पर व्युत्क्रमणीय मैट्रिक्स है: एक पूर्णांक मैट्रिक्स N है जो इसका व्युत्क्रम है (ये क्रैमर के नियम के तहत समतुल्य हैं)। इस प्रकार हर समीकरण Mx = b, जहां एम और बी दोनों में पूर्णांक घटक होते हैं और एम यूनिमॉड्यूलर होता है, एक पूर्णांक समाधान होता है। n × n यूनिमॉड्यूलर मेट्रिसेस एक समूह (गणित) बनाते हैं जिसे n × n सामान्य रैखिक समूह कहा जाता है $\mathbb {Z}$, जिसे निरूपित किया जाता है $\operatorname {GL} _{n}(\mathbb {Z} )$.

यूनिमॉड्यूलर मेट्रिसेस के उदाहरण

यूनिमॉड्यूलर मेट्रिसेस मैट्रिक्स गुणन के तहत सामान्य रैखिक समूह का एक उपसमूह बनाते हैं, अर्थात निम्नलिखित मैट्रिसेस यूनिमॉड्यूलर हैं:

• पहचान मैट्रिक्स
• एक यूनिमॉड्यूलर मैट्रिक्स उलटा मैट्रिक्स व्युत्क्रम
• दो यूनिमॉड्यूलर मैट्रिसेस का मैट्रिक्स गुणन

अन्य उदाहरणों में शामिल हैं:

• पास्कल मैट्रिक्स
• क्रमपरिवर्तन मैट्रिक्स
• आदिम पायथागॉरियन ट्रिपल्स के टर्नरी ट्री में तीन ट्रांसफ़ॉर्मेशन मैट्रिसेस
• [[ प्रतिबिंब मैट्रिक्स ]], शियर मैपिंग (दोनों निर्धारक 1 के साथ) और परावर्तन मैट्रिक्स (निर्धारक -1) के लिए कुछ रूपांतरण मैट्रिक्स।
• जाली कमी और मेट्रिसेस के हर्मिट सामान्य रूप में इस्तेमाल किया जाने वाला यूनिमॉड्यूलर मैट्रिक्स (संभवतः निहित)।
• दो यूनिमॉड्यूलर मैट्रिसेस का क्रोनकर उत्पाद भी एकमॉड्यूलर होता है। यह इस प्रकार है $\det(A\otimes B)=(\det A)^{q}(\det B)^{p},$ जहाँ p और q क्रमशः A और B की विमाएँ हैं।

कुल एकरूपता

एक पूरी तरह से यूनिमॉड्यूलर मैट्रिक्स (टीयू मैट्रिक्स) एक मैट्रिक्स है जिसके लिए प्रत्येक वर्ग व्युत्क्रमणीय मैट्रिक्स | गैर-एकवचन submatrix यूनिमॉड्यूलर है। समतुल्य रूप से, प्रत्येक वर्ग सबमैट्रिक्स में निर्धारक 0, +1 या -1 होता है। एक पूरी तरह से यूनिमॉड्यूलर मैट्रिक्स को वर्गाकार होने की आवश्यकता नहीं है। परिभाषा से यह इस प्रकार है कि पूरी तरह से अनिमॉड्यूलर मैट्रिक्स का कोई भी सबमैट्रिक्स अपने आप में पूरी तरह से यूनिमॉड्यूलर (TU) है। इसके अलावा यह इस प्रकार है कि किसी भी टीयू मैट्रिक्स में केवल 0, +1 या -1 प्रविष्टियां हैं। विलोम (तर्क) सत्य नहीं है, अर्थात, केवल 0, +1 या -1 प्रविष्टियों वाला मैट्रिक्स आवश्यक रूप से एक-मॉड्यूलर नहीं है। एक मैट्रिक्स टीयू है अगर और केवल अगर इसका स्थानांतरण टीयू है।

पॉलीहेड्रल कॉम्बिनेटरिक्स और संयोजन अनुकूलन में पूरी तरह से यूनिमॉड्यूलर मैट्रिसेस बेहद महत्वपूर्ण हैं क्योंकि वे यह सत्यापित करने का एक त्वरित तरीका देते हैं कि एक रेखीय कार्यक्रम रैखिक प्रोग्रामिंग # इंटीग्रल रेखीय कार्यक्रम है (एक अभिन्न इष्टतम है, जब कोई इष्टतम मौजूद है)। विशेष रूप से, यदि ए टीयू है और बी अभिन्न है, तो रूपों के रैखिक कार्यक्रम जैसे $\{\min cx\mid Ax\geq b,x\geq 0\}$ या $\{\max cx\mid Ax\leq b\}$ किसी भी सी के लिए इंटीग्रल ऑप्टिमा है। इसलिए यदि ए पूरी तरह से यूनिमॉड्यूलर है और बी इंटीग्रल है, तो संभव क्षेत्र का हर चरम बिंदु (जैसे। $\{x\mid Ax\geq b\}$) अभिन्न है और इस प्रकार व्यवहार्य क्षेत्र एक रैखिक प्रोग्रामिंग # इंटीग्रल लीनियर प्रोग्राम पॉलीहेड्रॉन है।

आम पूरी तरह से एक मॉड्यूलर मैट्रिसेस

1. द्विदलीय ग्राफ का गैर-उन्मुख घटना मैट्रिक्स, जो द्विदलीय मिलान (ग्राफ सिद्धांत) के लिए गुणांक मैट्रिक्स है, पूरी तरह से अनिमॉड्यूलर (TU) है। (एक गैर-द्विपक्षीय ग्राफ का गैर-उन्मुख घटना मैट्रिक्स टीयू नहीं है।) अधिक आम तौर पर, हेलर और टॉमपकिंस द्वारा एक पेपर के परिशिष्ट में, ए.जे. हॉफमैन और डी. गेल निम्नलिखित सिद्ध करते हैं। होने देना $A$ एक m ​​by n मैट्रिक्स हो जिसकी पंक्तियों को दो असम्बद्ध सेटों में विभाजित किया जा सकता है $B$ और $C$. फिर निम्नलिखित चार शर्तें एक साथ आवश्यक हैं और ए के लिए पूरी तरह से एकरूप होने के लिए पर्याप्त शर्तें हैं:

• प्रत्येक प्रविष्टि में $A$ 0, +1, या -1 है;
• का हर स्तंभ $A$ अधिकतम दो गैर-शून्य (यानी, +1 या -1) प्रविष्टियाँ शामिल हैं;
• यदि किसी कॉलम में दो गैर-शून्य प्रविष्टियाँ हैं $A$ एक ही चिन्ह है, तो एक की पंक्ति अंदर है $B$, और दूसरे में $C$;
• यदि किसी कॉलम में दो गैर-शून्य प्रविष्टियाँ हैं $A$ विपरीत चिह्न हैं, तो दोनों की पंक्तियाँ अंदर हैं $B$, या दोनों में $C$.

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

3. लगातार-वाले संपत्ति: यदि ए 0-1 मैट्रिक्स है (या इसमें अनुमति दी जा सकती है) जिसमें प्रत्येक पंक्ति के लिए, 1 लगातार दिखाई देते हैं, तो ए टीयू है। (टीयू मैट्रिक्स के स्थानान्तरण के बाद से कॉलम के लिए भी यही है।) 4. प्रत्येक नेटवर्क मैट्रिक्स टीयू है। नेटवर्क मैट्रिक्स की पंक्तियाँ एक ट्री के अनुरूप होती हैं T = (V, R), जिनके प्रत्येक आर्क में एक मनमाना अभिविन्यास है (यह आवश्यक नहीं है कि रूट वर्टेक्स आर मौजूद हो जैसे कि पेड़ आर में या आर से बाहर हो)। कॉलम एक ही वर्टेक्स सेट वी पर चाप के दूसरे सेट सी के अनुरूप हैं। पंक्ति आर और कॉलम में प्रविष्टि की गणना करने के लिए C = st, टी में एस-टू-टी पथ पी देखें; तो प्रविष्टि है:

• +1 यदि चाप आर पी में आगे दिखाई देता है,
• −1 यदि चाप R, P में पीछे की ओर प्रकट होता है,
• 0 यदि चाप R, P में प्रकट नहीं होता है।

श्रिजवर (2003) में और देखें।

5. घौइला-हौरी ने दिखाया कि पंक्तियों के प्रत्येक उपसमूह आर के लिए एक मैट्रिक्स टीयू आईएफ़ है, एक असाइनमेंट है $s:R\to \pm 1$ पंक्तियों के संकेतों का ताकि हस्ताक्षरित राशि $\sum _{r\in R}s(r)r$ (जो मैट्रिक्स के समान चौड़ाई का एक पंक्ति वेक्टर है) में इसकी सभी प्रविष्टियाँ हैं $\{0,\pm 1\}$ (अर्थात पंक्ति-सबमैट्रिक्स में अधिकतम एक में हाइपरग्राफ की विसंगति है)। यह और कई अन्य यदि-और-केवल-यदि लक्षण श्रिजवर (1998) में सिद्ध होते हैं।

6. हॉफमैन और जोसेफ क्रुस्कल निम्नलिखित प्रमेय को सिद्ध किया। मान लीजिए $G$ 2-डायसाइकिल के बिना एक निर्देशित ग्राफ है, $P$ में सभी द्विपथों का समुच्चय है $G$, और $A$ का 0-1 घटना मैट्रिक्स है $V(G)$ बनाम $P$. फिर $A$ पूरी तरह से एकतरफा है अगर और केवल अगर हर साधारण मनमाने ढंग से उन्मुख चक्र में $G$ बारी-बारी से आगे और पीछे की ओर चाप होते हैं।

7. मान लीजिए एक मैट्रिक्स में 0-($\pm$1) प्रविष्टियाँ और प्रत्येक कॉलम में, प्रविष्टियाँ ऊपर से नीचे तक घटती नहीं हैं (इसलिए सभी -1s शीर्ष पर हैं, फिर 0s, फिर 1s तल पर हैं)। फुजीशिगे ने दिखाया कि मैट्रिक्स TU है यदि प्रत्येक 2-बाय-2 सबमैट्रिक्स में निर्धारक है $0,\pm 1$.

8. पॉल सीमोर (गणितज्ञ) (1980) सभी टीयू मैट्रिसेस का पूर्ण लक्षण वर्णन साबित हुआ, जिसका वर्णन हम यहां केवल अनौपचारिक रूप से करते हैं। सीमोर का प्रमेय यह है कि एक मैट्रिक्स टीयू है अगर और केवल अगर यह कुछ नेटवर्क मैट्रिसेस का एक निश्चित प्राकृतिक संयोजन है और एक विशेष 5-बाय -5 टीयू मैट्रिक्स की कुछ प्रतियां हैं।

ठोस उदाहरण

1. निम्नलिखित मैट्रिक्स पूरी तरह से एक-मॉड्यूलर है:

$A=\left[{\begin{array}{rrrrrr}-1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\end{array}}\right].$

यह मैट्रिक्स निम्न नेटवर्क पर मैक्स-फ्लो मिन-कट प्रमेय समस्या के रैखिक प्रोग्रामिंग फॉर्मूलेशन में बाधाओं के गुणांक मैट्रिक्स के रूप में उत्पन्न होता है:

File:Graph for example adjacency matrix.svg2. फॉर्म का कोई मैट्रिक्स

$A=\left[{\begin{array}{ccccc}&\vdots &&\vdots \\\dotsb &+1&\dotsb &+1&\dotsb \\&\vdots &&\vdots \\\dotsb &+1&\dotsb &-1&\dotsb \\&\vdots &&\vdots \end{array}}\right].$

पूरी तरह से एक-मॉड्यूलर नहीं है, क्योंकि इसमें निर्धारक -2 का एक वर्ग उपमैट्रिक्स है।

सार रेखीय बीजगणित

सार बीजगणित मैट्रिक्स को किसी भी विनिमेय रिंग (गणित) से प्रविष्टियों के साथ मानता है $R$, पूर्णांकों तक सीमित नहीं है। इस संदर्भ में, एक यूनिमॉड्यूलर मैट्रिक्स वह है जो रिंग के ऊपर उल्टा होता है; समतुल्य, जिसका निर्धारक एक इकाई (रिंग थ्योरी) है। यह समूह (गणित) निरूपित है $\operatorname {GL} _{n}(R)$. एक आयताकार $k$-द्वारा-$m$ मैट्रिक्स को यूनिमॉड्यूलर कहा जाता है अगर इसे बढ़ाया जा सकता है $m-k$ पंक्तियों में $R^{m}$ एक यूनिमॉड्यूलर वर्ग मैट्रिक्स के लिए। एक क्षेत्र (गणित) पर, यूनिमॉड्यूलर का वही अर्थ है जो उलटा मैट्रिक्स | गैर-एकवचन है। यहां यूनिमॉड्यूलर कुछ रिंग (अक्सर पूर्णांक) में गुणांक वाले मैट्रिसेस को संदर्भित करता है जो उस रिंग पर उलटा होता है, और एक गैर-एकवचन का उपयोग करता है जिसका अर्थ है कि मेट्रिसेस जो क्षेत्र में उलटा हो।

यह भी देखें

• संतुलित मैट्रिक्स
• नियमित मैट्रोइड
• विशेष रैखिक समूह
• कुल दोहरी अखंडता
• हर्माइट सामान्य रूप

संदर्भ

• Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), "Section 13.2", Combinatorial Optimization: Algorithms and Complexity, Mineola, N.Y.: Dover Publications, p. 316, ISBN 978-0-486-40258-1
• Alexander Schrijver (1998), Theory of Linear and Integer Programming. John Wiley & Sons, ISBN 0-471-98232-6 (mathematical)
• Alexander Schrijver (2003), Combinatorial Optimization: Polyhedra and Efficiency, Springer

बाहरी कड़ियाँ

• Mathematical Programming Glossary by Harvey J. Greenberg
• Unimodular Matrix from MathWorld
• Software for testing total unimodularity by M. Walter and K. Truemper