एक अंगूठी पर रैखिक समीकरण

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

एक ही समीकरण के मामले में, समस्या दो भागों में विभाजित होती है।सबसे पहले, आदर्श सदस्यता समस्या, जिसमें शामिल हैं, एक गैर-समरूप समीकरण दिया गया है

a_{1}x_{1}+\cdots +a_{k}x_{k}=b

साथ $a_{1},\ldots ,a_{k}$ और $b$ किसी दिए गए अंगूठी में (गणित) $R$ , यह तय करने के लिए कि क्या इसका समाधान है $x_{1},\ldots ,x_{k}$ में $R$ , और, यदि कोई हो, तो एक प्रदान करने के लिए।यह तय करने के लिए मात्रा है $b$ द्वारा उत्पन्न आदर्श (रिंग थ्योरी) से संबंधित है $a i$ ।इस समस्या का सबसे सरल उदाहरण है, के लिए $k = 1$ और $b = 1$ , तय करने के लिए अगर $a$ में एक इकाई (रिंग थ्योरी) है $R$ ।

Syzygy समस्या शामिल है, दी गई है $k$ तत्वों $a_{1},\ldots ,a_{k}$ में $R$ , Syzygy (गणित) के मॉड्यूल (गणित) के जनरेटर की एक प्रणाली प्रदान करने के लिए $(a_{1},\ldots ,a_{k}),$ यह उन तत्वों के सबल के जनरेटर की एक प्रणाली है $(x_{1},\ldots ,x_{k})$ में $R k$ यह सजातीय समीकरण के समाधान हैं

a_{1}x_{1}+\cdots +a_{k}x_{k}=0.

सबसे सरल मामला, जब

k = 1

एनीहिलेटर (रिंग थ्योरी) के जनरेटर की एक प्रणाली खोजने के लिए मात्रा

a 1

।

आदर्श सदस्यता समस्या के समाधान को देखते हुए, कोई भी इसे Syzygies के मॉड्यूल के तत्वों को जोड़कर सभी समाधानों को प्राप्त करता है।दूसरे शब्दों में, सभी समाधान इन दो आंशिक समस्याओं के समाधान द्वारा प्रदान किए जाते हैं।

कई समीकरणों के मामले में, उपप्रकारों में एक ही अपघटन होता है।पहली समस्या सबमॉड्यूल सदस्यता समस्या बन जाती है।दूसरे को Syzygy समस्या भी कहा जाता है।

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

लेख मुख्य छल्ले पर विचार करता है जिसके लिए रैखिक बीजगणित प्रभावी है।

सामान्यताएं

Syzygy समस्या को हल करने में सक्षम होने के लिए, यह आवश्यक है कि Syzygies का मॉड्यूल बारीक रूप से उत्पन्न मॉड्यूल है, क्योंकि एक अनंत सूची को आउटपुट करना असंभव है।इसलिए, यहां माना जाने वाली समस्याएं केवल एक नूथियन रिंग, या कम से कम एक सुसंगत अंगूठी के लिए समझ में आती हैं।वास्तव में, यह लेख निम्नलिखित परिणाम के कारण Noetherian अभिन्न डोमेन तक सीमित है।^[1]

एक Noetherian अभिन्न डोमेन को देखते हुए, यदि आदर्श सदस्यता समस्या को हल करने के लिए एल्गोरिदम हैं और एकल समीकरण के लिए Syzygies समस्या है, तो कोई भी समीकरणों की प्रणालियों से संबंधित समान समस्याओं के लिए एल्गोरिदम से कटौती कर सकता है।

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

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

प्रभावी छल्ले के गुण

होने देना $R$ एक प्रभावी कम्यूटेटिव रिंग बनें।

यदि कोई तत्व परीक्षण के लिए एक एल्गोरिथ्म है $a$ एक शून्य भाजक है: यह रैखिक समीकरण को हल करने की मात्रा है $ax = 0$ ।
यदि कोई तत्व परीक्षण के लिए एक एल्गोरिथ्म है $a$ एक इकाई (रिंग थ्योरी) है, और यदि यह है, तो इसके व्युत्क्रम की गणना करना: यह रैखिक समीकरण को हल करने की मात्रा है $ax = 1$ ।
एक आदर्श दिया I द्वारा उत्पन्न a₁, ..., a_k,
- यदि दो तत्वों के परीक्षण के लिए एक एल्गोरिथ्म है $R$ में एक ही छवि है $R / I$ : की छवियों की समानता का परीक्षण $a$ और $b$ समीकरण को हल करने के लिए मात्रा $a = b + a 1 z 1 + \dots + a k z k$ ;
- रैखिक बीजगणित प्रभावी है $R / I$ : एक रैखिक प्रणाली को हल करने के लिए $R / I$ , यह इसे लिखने के लिए पर्याप्त है $R$ और के एक तरफ जोड़ने के लिए $i$ समीकरण $a 1 z i,1 + \dots + a k z i, k$ (के लिए $i = 1, ...$ ), जहां $z i, j$ नए अज्ञात हैं।
रैखिक बीजगणित बहुपद रिंग पर प्रभावी है $R[x_{1},\ldots ,x_{n}]$ यदि और केवल अगर किसी के पास एक एल्गोरिथ्म है जो बहुपद के बहुपद की डिग्री की एक ऊपरी सीमा की गणना करता है जो समीकरणों के रैखिक प्रणालियों को हल करते समय हो सकता है: यदि कोई एल्गोरिदम को हल करता है, तो उनके आउटपुट डिग्री देते हैं।Converse (LOGIC), यदि कोई समाधान में होने वाली डिग्री की ऊपरी सीमा को जानता है, तो कोई अज्ञात गुणांक के साथ अज्ञात बहुपदों को बहुपद के रूप में लिख सकता है।फिर, चूंकि दो बहुपद समान होते हैं यदि और केवल अगर उनके गुणांक समान हैं, तो समस्या के समीकरण गुणांक में रैखिक समीकरण बन जाते हैं, जिन्हें एक प्रभावी रिंग पर हल किया जा सकता है।

== पूर्णांक या एक प्रमुख आदर्श डोमेन पर == पर

पूर्णांक पर इस लेख में संबोधित सभी समस्याओं को हल करने के लिए एल्गोरिदम हैं।दूसरे शब्दों में, रैखिक बीजगणित पूर्णांक पर प्रभावी है;विवरण के लिए रेखीय डायोफेंटाइन तंत्र देखें।

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

फॉर्म के समीकरणों को हल करना $ax = b$ , अर्थात् परीक्षण कि क्या $a$ का भाजक है $b$ , और, यदि यह मामला है, तो भागफल की गणना $a / b$ ,
कंप्यूटिंग बेज़आउट की पहचान, अर्थात्, दिया गया $a$ और $b$ , कम्प्यूटिंग $s$ और $t$ ऐसा है कि $as + bt$ का एक सबसे बड़ा सामान्य भाजक है $p$ और $q$ ।

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

उपरोक्त दो एल्गोरिदम का अर्थ है कि दिया गया $a$ और $b$ प्रिंसिपल आदर्श डोमेन में, एक एल्गोरिथ्म एक अनिमॉड्यूलर मैट्रिक्स की गणना है

{\begin{bmatrix}s&t\\u&v\end{bmatrix}}

ऐसा है कि

{\begin{bmatrix}s&t\\u&v\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}\gcd(a,b)\\0\end{bmatrix}}.

(यह एल्गोरिथ्म लेने के लिए प्राप्त किया जाता है $s$ और $t$ Bézout की पहचान के गुणांक, और के लिए $u$ और $v$ का भागफल $- b$ और $a$ द्वारा $as + bt$ ;इस विकल्प का तात्पर्य है कि वर्ग मैट्रिक्स का निर्धारक है $1$ ।)

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

मुख्य मामला जहां यह आमतौर पर उपयोग किया जाता है, वह एक क्षेत्र पर एकतरफा बहुपद की अंगूठी पर रैखिक प्रणालियों का मामला है।इस मामले में, विस्तारित यूक्लिडियन एल्गोरिथ्म का उपयोग उपरोक्त अनिमॉड्यूलर मैट्रिक्स की गणना के लिए किया जा सकता है;देखना Polynomial greatest common divisor § Bézout's identity and extended GCD algorithm जानकारी के लिए।

अधिक बहुपद पर एक क्षेत्र पर छल्ले

रैखिक बीजगणित एक बहुपद रिंग पर प्रभावी है $k[x_{1},\ldots ,x_{n}]$ एक क्षेत्र पर (गणित) $k$ ।यह पहली बार 1926 में ग्रेट हरमन द्वारा साबित किया गया था।^[2] हरमन के परिणामों से उत्पन्न एल्गोरिदम केवल ऐतिहासिक रुचि के हैं, क्योंकि प्रभावी कंप्यूटर गणना की अनुमति देने के लिए उनकी कम्प्यूटेशनल जटिलता बहुत अधिक है।

सबूत कि रैखिक बीजगणित बहुपद रिंग और कंप्यूटर कार्यान्वयन पर प्रभावी है, वर्तमान में सभी ग्रोबनर आधार पर आधारित हैं। ग्रोबनर आधार सिद्धांत।

संदर्भ

↑ Richman, Fred (1974). "Constructive aspects of Noetherian rings". Proc. Amer. Math. Soc. 44 (2): 436–441. doi:10.1090/s0002-9939-1974-0416874-9.
↑ Hermann, Grete (1926). "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale". Mathematische Annalen. 95: 736–788. doi:10.1007/BF01206635. S2CID 115897210.. English translation in Communications in Computer Algebra 32/3 (1998): 8–30.

David A. Cox; John Little; Donal O'Shea (1997). Ideals, Varieties, and Algorithms (second ed.). Springer-Verlag. ISBN 0-387-94680-2. Zbl 0861.13012.
Aschenbrenner, Matthias (2004). "Ideal membership in polynomial rings over the integers" (PDF). J. Amer. Math. Soc. AMS. 17 (2): 407–441. doi:10.1090/S0894-0347-04-00451-5. S2CID 8176473. Retrieved 23 October 2013.

[1] Richman, Fred (1974). "Constructive aspects of Noetherian rings". Proc. Amer. Math. Soc. 44 (2): 436–441. doi:10.1090/s0002-9939-1974-0416874-9.

[2] Hermann, Grete (1926). "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale". Mathematische Annalen. 95: 736–788. doi:10.1007/BF01206635. S2CID 115897210.. English translation in Communications in Computer Algebra 32/3 (1998): 8–30.

[1]

[2]

एक अंगूठी पर रैखिक समीकरण

Contents

सामान्यताएं

प्रभावी छल्ले के गुण

अधिक बहुपद पर एक क्षेत्र पर छल्ले

संदर्भ

Navigation menu

Search