कैसे जांचें कि एम एन आकार के वैक्टर रैखिक रूप से स्वतंत्र हैं या नहीं?

Question

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

अब समस्या
मैं आयाम n के मीटर वैक्टर रैखिक स्वतंत्र हैं, तो जाँच करने के लिए कोशिश कर रहा हूँ। यदि एम == एन आप वैक्टर का उपयोग करके सिर्फ एक मैट्रिक्स बना सकते हैं और जांच सकते हैं कि निर्धारक है! = 0. लेकिन क्या होगा अगर < एन?

कोई संकेत?

---

this video lecture भी देखें।

Answer 1

वैक्टर के एक मैट्रिक्स (प्रति पंक्ति एक पंक्ति) का निर्माण, और इस मैट्रिक्स पर Gaussian elimination निष्पादित करें। यदि मैट्रिक्स पंक्तियों में से कोई भी रद्द हो जाता है, तो वे रैखिक रूप से स्वतंत्र नहीं हैं।

मामूली मामला तब होता है जब एम> एन, इस मामले में, वे रैखिक रूप से स्वतंत्र नहीं हो सकते हैं।

Answer 2

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

संख्यात्मक अस्थिरता की देखभाल करें। संख्यात्मक व्यंजनों में अध्याय दो की शुरुआत में चेतावनी देखें।

Answer 3

यदि m<n, तो आपको उन पर कुछ ऑपरेशन करना होगा (कई संभावनाएं हैं: गॉसियन उन्मूलन, ऑर्थोगोनलाइजेशन इत्यादि, समीकरणों को हल करने के लिए लगभग किसी भी परिवर्तन का उपयोग किया जा सकता है) और परिणाम की जांच करें (उदाहरण के लिए। गॉसियन उन्मूलन => शून्य पंक्ति या स्तंभ, ऑर्थोगोनलाइजेशन => शून्य वेक्टर, एसवीडी => शून्य एकवचन संख्या)

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

Answer 4

अगर कंप्यूटिंग शक्ति शायद सबसे अच्छा तरीका है के एकमात्र मूल्यों को खोजने के है, एक समस्या नहीं है मैट्रिक्स। असल में आपको M'*M के eigenvalues ​​खोजने की आवश्यकता है और सबसे छोटे से सबसे छोटे अनुपात को देखें। यदि अनुपात बहुत बड़ा नहीं है, तो वेक्टर स्वतंत्र हैं।

Answer 5

एक और तरीका है यह देखना होगा कि मीटर पंक्ति वैक्टर रैखिक स्वतंत्र हैं, जब आकार MXN का मैट्रिक्स एम में डाल दिया, गणना करने के लिए है

det(M * M^T) 

अर्थात एक MXM वर्ग मैट्रिक्स के निर्धारक। यह शून्य होगा यदि केवल और यदि एम में कुछ निर्भर पंक्तियां होंगी। हालांकि गॉसियन उन्मूलन सामान्य रूप से तेज होना चाहिए।

Answer 6

मैं इन दिनों इस समस्या पर काम कर रहा हूं।

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

सामान्य मैट्रिक्स के लिए लागू करने के लिए सबसे अच्छा जवाब में से एक यह हो सकता है: http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB

आप विभिन्न भाषाओं में दोनों छद्म कोड और स्रोत कोड प्राप्त कर सकते हैं। मेरे लिए, मैं सी ++ के लिए अजगर स्रोत कोड बदल, का कारण बनता है सी ++ उपरोक्त लिंक पर प्रदान कोड किसी भी तरह जटिल और मेरे सिमुलेशन में लागू करने के लिए अनुचित है।

आशा यह आप में मदद मिलेगी, और अच्छी किस्मत ^^

Answer 7

क्षमा आदमी, मेरी गलती ...

---

स्रोत उपरोक्त लिंक पर प्रदान कोड, पता चला है कि कम से कम गलत मैंने जिस पायथन कोड का परीक्षण किया है और मैंने जिस सी ++ कोड को बदल दिया है वह हर समय सही उत्तर उत्पन्न नहीं करता है। (जबकि ऊपर के लिंक में exmample के लिए, परिणाम सही :) है -)

अजगर कोड का परीक्षण करने के लिए बस mtx साथ

[30,10,20,0],[60,20,40,0] 

और प्राप्त परिणाम को बदलने की तरह होगा:

[1,0,0,0],[0,1,2,0] 

फिर भी, मुझे इसका एक तरीका मिला है। यह इस बार मैंने rref फ़ंक्शन को C++ में matalb स्रोत कोड को बदल दिया है। आप rref के स्रोत कोड प्राप्त करने के लिए मैटलैब चला सकते हैं और type rref कमांड का उपयोग कर सकते हैं।

बस ध्यान दें कि यदि आप कुछ वाकई बड़े मूल्य या वास्तव में छोटे मूल्य के साथ काम कर रहे हैं, तो सुनिश्चित करें किडेटाटाइप का उपयोग C++ में करें। अन्यथा, परिणाम को छोटा कर दिया जाएगा और matlab परिणाम के साथ असंगत होगा।

मैं ns2 में बड़े सिमुलेशन का आयोजन किया गया है, और सभी मनाया परिणाम ध्वनि कर रहे हैं। आशा है कि यह आप और किसी भी अन्य जो समस्या encontered है में मदद मिलेगी ...

Answer 8

एक बहुत ही सरल तरीके से, कि, कुशल नहीं सबसे computationally है बस m=n जब तक यादृच्छिक पंक्तियों को दूर करने के लिए और फिर निर्धारक चाल लागू है।

• m < n: पंक्तियों को हटाने (वैक्टर कम करने) तक मैट्रिक्स वर्ग है, और फिर
• m = n: जाँच लें कि निर्धारक 0 है (जैसा कि आपने कहा था)
• m < n (वैक्टर की संख्या है उनकी लंबाई से अधिक): वे रैखिक रूप से निर्भर हैं (हमेशा)।

कारण, संक्षेप में, कि m x n समीकरणों के सिस्टम के लिए किसी भी समाधान भी समीकरणों के n x n प्रणाली (आप Av=0 हल करने के लिए कोशिश कर रहे हैं) के लिए एक समाधान है। बेहतर स्पष्टीकरण के लिए, Wikipedia देखें, जो मुझे इससे बेहतर समझाता है।