एक मैट्रिक्स के वर्गमूल लेने के लिए एल्गोरिथ्म

Question

मान लीजिए $A = A^T$ और मान लीजिए की प्रविष्टियाँ $A$ में हैं $\mathbb{Z}^+$। मैं सभी मैट्रीक ढूंढना चाहता हूं$M$ प्राकृतिक प्रविष्टियों के साथ ताकि: $$M^2 = A$$कोई ऐसा कैसे कर सकता है? मुझे ऐसी तकनीकें पता हैं जो एक मनमाना मैट्रिक्स का एक वर्ग-मूल प्राप्त करेंगी, लेकिन मुझे पूरा सेट चाहिए। मैं इसे बड़े पैमाने पर ~ के लिए कुशलतापूर्वक करने में सक्षम होना चाहता हूं$100 \times 100$।

बेशक, सेट को परिमित होना चाहिए क्योंकि हम सकारात्मक पूर्णांक और मैट्रिक्स पर काम कर रहे हैं $A$ ऊपरी सीमा देता है।

Answer 1

एक उल्टे मैट्रिक्स का पता लगाएं $B$ और विकर्ण मैट्रिक्स $D$ ऐसा है कि $D=B^{-1}AB$। फिर सभी वर्गमूल लें$D_1,...,D_m$ (उनमें से सभी विकर्ण हैं, वहाँ हैं $m\le 2^n$ इनमें से जहां $n$ का आकार है $A$ क्योंकि प्रत्येक गैर-ऋणात्मक संख्या में अधिकतम 2 वर्ग जड़ें होती हैं) $D$ और सभी मैट्रिसेस $BD_iB^{-1}$। देखिए कि इनमें से कौन सी मैट्रिसेस प्राकृतिक संख्या से अधिक हैं।

Answer 2

एक तरह से, यदि आप एक को उत्पन्न कर सकते हैं, तो शेष इस प्रकार है, यदि आपके पास एक समाधान किसी अन्य मैट्रिक्स का है $M'$ समीकरणों के निम्नलिखित सेट का पालन करना होगा: $$(M-M')(M+M')=M^2-M'^2 =0 $$ अब, की परिभाषा के द्वारा $M,\;M'$वे एक साथ orthogonally विकर्ण हैं, इस प्रकार आप WLOG मान सकते हैं कि वे विकर्ण हैं। और भी, आप के मूल मूल्यों को जानते हैं$M,\;M'$ sutisfy $\mu_i^2=\mu'^2_i = \lambda_i\to \mu_i=\mu'_i$ (ये क्रमशः आइजनवेल्स हैं $M,\;M'$ तथा $\lambda$ उसका है $A$)। इसलिए एक और मैट्रिक्स प्राप्त करने के लिए जो आपके प्रश्न का उत्तर देता है शर्त के बराबर है$$(\mu_i+\mu_i')\cdot(\mu_i-\mu_i')=0$$सभी स्वदेशी के लिए। इससे समाधानों का पूरा वर्गीकरण होता है।