एक रैखिक प्रणाली mod 2 के लिए समाधान का अस्तित्व
चलो $A$ एक (तिरछा) सममित मैट्रिक्स पर हो $\mathbb{Z}/2$। (वास्तव में, मैं ले जाएगा$A$ एक उन्मुख फ़्रेम लिंक के मैट्रिक्स को जोड़ने के रूप में $S^3$या मैट्रिक्स एक बंद चिकनी 4-गुना पर चौराहे के रूप का प्रतिनिधित्व करता है। हालाँकि, निम्न कथन सामान्य रूप से पकड़ में आता है।) मैं निम्नलिखित रेखीय प्रणाली में दिलचस्पी रखता हूँ$\mathbb{Z}/2$, $$a_{i1}x_1+a_{i2}x_2\cdots+a_{in}x_n=a_{ii},\quad i=1,\cdots,n.$$
इस प्रणाली को हमेशा एक समाधान के लिए जाना जाता है। 3-मैनिफोल्ड्स के टोपोलॉजी पर cf Saveliev का व्याख्यान ।) लेकिन मैं यह नहीं देख सकता कि यह सच क्यों है$A$ निरर्थक है $\mathbb{Z}/2$। क्या इस प्रकार की रैखिक प्रणालियों से निपटने के लिए एक सामान्य तरीका है?
जवाब
यह सच है, लेकिन यह थोड़ा मुश्किल है। विचार केवल रूप में मैट्रिक्स लिखने के लिए है$$ A=BB^T $$ इस तरह से कि कॉलम का स्थान $B$ के बराबर है $A$। के सभी कॉलम$A$ स्तंभों के रैखिक संयोजन हैं $B$, लेकिन यह मेरे लिए स्पष्ट नहीं है कि रिवर्स समावेशन कैसे प्राप्त किया जाए (यह स्पष्ट रूप से सभी विकल्पों के लिए सही नहीं है $B$) का है।
इसलिए इस समय मैं पूरी तरह से स्व-निहित प्रमाण नहीं लिख सकता, मुझे दो लेखों को संदर्भित करने की आवश्यकता है:
- ए। लेम्पेल, मैट्रिक्स फैक्टरिज़ेशन ओवर$GF(2)$ और ट्रेस-ऑर्थोगोनल बेस के $GF(2^m)$, SIAM जे। कंप्यूटर।, वॉल्यूम। 4, पीपी 175-186, जून 1975।
- जी। सीरौसी, ए। लेम्पेल, कुछ रीड-मुलर कोड्स की अधिकतम संभावना, डिकोडिंग , सूचना के सिद्धांत पर IEEE लेनदेन। आईटी -29, सं। 3, मई 1983।
IIRC केवल पहली जरूरत है। मैं बाद को शामिल करता हूं, क्योंकि मैंने इसे पढ़कर पूर्व पाया।
पहले लेख में लेम्पेल (लेम्पेल-ज़िव की प्रसिद्धि की समस्या) हल है। वह किसी दिए गए सममित को लिखना चाहता है$n\times n$ आव्यूह $A$ ऊपर $\Bbb{Z}_2$ फार्म में $A=BB^T$जितनी कुशलता से संभव हो। यही है, वह कॉलम की संख्या को कम करना चाहता है$m$ का $B$। उसका जवाब यह है कि
सामान्य रूप से $m$ रैंक के बराबर है $r(A)$ का $A$। अपवाद तब आता है जब विकर्ण$A$ सभी शून्य है, जब $m=1+r(A)$ सबसे अच्छा हम कर सकते हैं।
हम इस प्रश्न को हल करने के लिए लेम्पेल के परिणाम को लागू कर सकते हैं।
- यदि का विकर्ण $A$सभी शून्य है, दावा तुच्छ है। हम प्रयोग कर सकते हैं$x_i=0$ सबके लिए $i$।
- जब ऐसा नहीं होता है, तो स्तंभों की संख्या $B$ के पद के बराबर है $A$। जैसा$A=BB^T$ का कॉलम स्थान $A$ फिर उसी के बराबर है $B$।
- तो यह दिखाने के लिए पर्याप्त है कि विकर्ण $A$ के कॉलम स्पेस में समाहित है $B$।
- समीकरण $A=BB^T$ मतलब कि $a_{ii}$ आंतरिक उत्पाद के बराबर है $(B_i,B_i)$ की $i$फेंकना $B_i$ का $B$ खुद के साथ।
- परंतु $B_i$ बाइनरी है, इसलिए $(B_i,B_i)$ बस उस की प्रविष्टियों का योग है $i$वें पंक्ति के रूप में $x^2=x$ सबके लिए $x\in\Bbb{Z}_2$।
- इसलिए विकर्ण $A$ के कॉलम का योग है $B$।
- इसलिए विकर्ण $A$ के कॉलम स्पेस में भी है $A$ और हम कर रहे हैं
इससे बेवजह कीचड़ लगता है। उपयोग करने का विचार$A=BB^T$सहज रूप से मेरे पास आया। मैंने कई उदाहरणों की गणना की और देखा कि के कॉलम$B$विकर्ण तक योग। प्रकाश बल्ब समय!
द $\mathbb{Z}_2$ एक बंद चिकनी पर चौराहे का रूप $4$-मानिफोल्ड हमेशा पॉइंकेयर द्वैत द्वारा nondegenerate है।