वलय पर रैखिक समीकरण

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

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

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

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

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

$a_{1}x_{1}+\cdots +a_{k}x_{k}=0.$ सबसे सरल स्थिति, कब k = 1 के एनीहिलेटर के जनरेटर की एक प्रणाली खोजने के लिए a₁.

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

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

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

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

सामान्यता

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

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

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

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

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

माना R एक प्रभावी क्रमविनिमेय वलय है :

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

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

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

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

• 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 बेज़ाउट की पहचान के गुणांक, और के लिए u तथा v का भागफल −b तथा a द्वारा as + bt; इस विकल्प का तात्पर्य है कि वर्ग आव्यूह का निर्धारक है 1.)

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

मुख्य स्थितियों जहाँ यह सामान्यतः उपयोग किया जाता है, एक क्षेत्र पर एकतरफा बहुपदों की वलय पर रैखिक प्रणालियों की स्थिति है। इन स्थितियों में, उपरोक्त यूनिमॉड्यूलर आव्यूह की गणना के लिए विस्तारित यूक्लिडियन एल्गोरिथ्म का उपयोग किया जा सकता है; अधिक जानकारी हेतु देखिए बहुपद महानतम सामान्य भाजक § बेज़ाउट सर्वसमिका और विस्तारित GCD एल्गोरिथम § Notes।

एक क्षेत्र पर बहुपद वलयो से अधिक

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

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

संदर्भ

• 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.