परिचालित मैट्रिक्स

For the symmetric graphs, see Circulant graph.

रैखिक बीजगणित में, एक स्क्वायर मैट्रिक्स एक वर्ग मैट्रिक्स होता है जिसमें सभी पंक्ति वैक्टर समान तत्वों से बने होते हैं और प्रत्येक पंक्ति वेक्टर पूर्ववर्ती पंक्ति वेक्टर के सापेक्ष एक तत्व को दाहिनी ओर घुमाया जाता है। यह एक विशेष प्रकार का Toeplitz मैट्रिक्स है।

संख्यात्मक विश्लेषण में, सर्कुलेंट मैट्रिसेस महत्वपूर्ण हैं क्योंकि वे असतत फूरियर रूपांतरण द्वारा डायगोनलाइज़ेबल_मैट्रिक्स # डायगोनलाइज़ेशन हैं, और इसलिए रेखीय समीकरण जिनमें वे शामिल हैं, एक तेज़ फूरियर रूपांतरण का उपयोग करके जल्दी से हल किए जा सकते हैं। वे चक्रीय समूह पर एक कनवल्शन ऑपरेटर के अभिन्न कर्नेल के रूप में # विश्लेषणात्मक व्याख्या हो सकते हैं $C_{n}$ और इसलिए अक्सर स्थानिक रूप से अपरिवर्तनीय रैखिक संचालन के औपचारिक विवरण में दिखाई देते हैं। यह संपत्ति आधुनिक सॉफ्टवेयर परिभाषित रेडियो में भी महत्वपूर्ण है, जो चक्रीय उपसर्ग का उपयोग करके प्रतीकों (बिट्स) को फैलाने के लिए समकोणकार आवृति विभाजन बहुसंकेतन का उपयोग करती है। यह चैनल को एक सर्कुलेंट मैट्रिक्स द्वारा प्रदर्शित करने में सक्षम बनाता है, आवृत्ति डोमेन में चैनल समानता को सरल करता है।

क्रिप्टोग्राफी में, उन्नत एन्क्रिप्शन मानक के रिजेंडेल मिक्स कॉलम चरण में एक सर्कुलेंट मैट्रिक्स का उपयोग किया जाता है।

परिभाषा

एक $n\times n$ मैट्रिक्स की परिक्रमा $C$ रूप धारण कर लेता है

$$C={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &c_{2}&c_{1}\\c_{1}&c_{0}&c_{n-1}&&c_{2}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{n-2}&&\ddots &\ddots &c_{n-1}\\c_{n-1}&c_{n-2}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}$$

या इस रूप का स्थानान्तरण (संकेतन के विकल्प द्वारा)। जब पद $c_{i}$ एक है $p\times p$ स्क्वायर मैट्रिक्स, फिर $np\times np$ आव्यूह $C$ एक ब्लॉक-परिसंचारी मैट्रिक्स कहा जाता है।

एक सर्कुलेंट मैट्रिक्स पूरी तरह से एक वेक्टर द्वारा निर्दिष्ट होता है, $c$, जो के पहले कॉलम (या पंक्ति) के रूप में दिखाई देता है $C$. के शेष स्तंभ (और पंक्तियाँ, क्रमशः)। $C$ वेक्टर के प्रत्येक चक्रीय क्रमपरिवर्तन हैं $c$ कॉलम (या पंक्ति, सम्मान) इंडेक्स के बराबर ऑफ़सेट के साथ, यदि लाइनों को 0 से अनुक्रमित किया जाता है $n-1$. (पंक्तियों के चक्रीय क्रमपरिवर्तन का वही प्रभाव होता है जो स्तंभों के चक्रीय क्रमपरिवर्तन का होता है।) की अंतिम पंक्ति $C$ सदिश है $c$ एक के बाद एक उलटफेर किया।

अलग-अलग स्रोत सर्कुलेंट मैट्रिक्स को अलग-अलग तरीकों से परिभाषित करते हैं, उदाहरण के लिए ऊपर, या वेक्टर के साथ $c$ मैट्रिक्स के पहले कॉलम के बजाय पहली पंक्ति के अनुरूप; और संभवतः शिफ्ट की एक अलग दिशा के साथ (जिसे कभी-कभी एंटी-सर्कुलेंट मैट्रिक्स कहा जाता है)।

बहुपद $f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}$ मैट्रिक्स का संबद्ध बहुपद कहा जाता है $C$.

गुण

ईजेनवेक्टर और ईजेनवैल्यू

एक सर्कुलेंट मैट्रिक्स के सामान्यीकृत eigenvectors फूरियर मोड हैं, अर्थात्,

$$v_{j}={\frac {1}{\sqrt {n}}}\left(1,\omega ^{j},\omega ^{2j},\ldots ,\omega ^{(n-1)j}\right),\quad j=0,1,\ldots ,n-1,$$

कहाँ $\omega =\exp \left({\tfrac {2\pi i}{n}}\right)$ आदिम है $n$-एकता की जड़ और $i$ काल्पनिक इकाई है।

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

इसी eigenvalues ​​द्वारा दिया जाता है

$$\lambda _{j}=c_{0}+c_{n-1}\omega ^{j}+c_{n-2}\omega ^{2j}+\dots +c_{1}\omega ^{(n-1)j},\quad j=0,1,\dots ,n-1.$$

निर्धारक

ऊपर दिए गए आइगेनमानों के स्पष्ट सूत्र के परिणामस्वरूप, एक सर्कुलेंट मैट्रिक्स के निर्धारक की गणना इस प्रकार की जा सकती है:

$$\det(C)=\prod _{j=0}^{n-1}(c_{0}+c_{n-1}\omega ^{j}+c_{n-2}\omega ^{2j}+\dots +c_{1}\omega ^{(n-1)j}).$$

चूंकि ट्रांसपोज़ लेने से मैट्रिक्स के ईगेनवेल्यूज़ नहीं बदलते हैं, एक समकक्ष फॉर्मूलेशन है

$$\det(C)=\prod _{j=0}^{n-1}(c_{0}+c_{1}\omega ^{j}+c_{2}\omega ^{2j}+\dots +c_{n-1}\omega ^{(n-1)j})=\prod _{j=0}^{n-1}f(\omega ^{j}).$$

रैंक

सर्कुलेंट मैट्रिक्स का रैंक (रैखिक बीजगणित)। $C$ के बराबर है $n-d$, कहाँ $d$ बहुपद के बहुपद की घात है $\gcd(f(x),x^{n}-1)$.

अन्य गुण

• चक्रीय क्रमचय मैट्रिक्स में कोई भी सर्कुलेंट एक मैट्रिक्स बहुपद (अर्थात् संबद्ध बहुपद) है $P$:
  $$C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),$$
  कहाँ $P$ द्वारा दिया गया है
  $$P={\begin{bmatrix}0&0&\cdots &0&1\\1&0&\cdots &0&0\\0&\ddots &\ddots &\vdots &\vdots \\\vdots &\ddots &\ddots &0&0\\0&\cdots &0&1&0\end{bmatrix}}.$$
• का सेट (गणित)। $n\times n$ सर्कुलेंट मेट्रिसेस एक बनाता है $n$-डिमेंशन (सदिश स्थल ) वेक्टर स्पेस जोड़ और स्केलर गुणन के संबंध में। इस स्थान को क्रम के चक्रीय समूह (समूह सिद्धांत) पर कार्यों के स्थान के रूप में व्याख्या किया जा सकता है $n$, $C_{n}$, या समकक्ष के समूह की अंगूठी के रूप में $C_{n}$.
• सर्कुलेंट मेट्रिसेस एक क्रमविनिमेय बीजगणित बनाते हैं, क्योंकि किसी भी दो सर्कुलेंट मेट्रिसेस के लिए $A$ और $B$, योग $A+B$ परिचालित है, उत्पाद $AB$ परिचालित है, और $AB=BA$.
• नॉनसिंगुलर सर्कुलेंट मैट्रिक्स के लिए $A$, इसका उलटा $A^{-1}$ परिवृत्ती भी है। एक विलक्षण सर्कुलेंट मैट्रिक्स के लिए, इसका मूर-पेनरोज़ इनवर्स|मूर-पेनरोज़ स्यूडोइनवर्स $A^{+}$ परिवृत्ती है।
• गणित का सवाल $U$ जो एक सर्कुलेंट मैट्रिक्स के ईजेनवेक्टरों से बना है, डिस्क्रीट फूरियर ट्रांसफॉर्म # द एकात्मक डीएफटी और इसके व्युत्क्रम ट्रांसफॉर्म से संबंधित है:
  $$U_{n}^{*}={\frac {1}{\sqrt {n}}}F_{n},\quad {\text{and}}\quad U_{n}={\frac {1}{\sqrt {n}}}F_{n}^{-1},{\text{ where }}F_{n}=(f_{jk}){\text{ with }}f_{jk}=e^{-2jk\pi i/n},\,{\text{for }}0\leq j,k<n.$$
  नतीजतन मैट्रिक्स $U_{n}$ विकर्णीय मैट्रिक्स $C$. वास्तव में, हमारे पास है
  $$C=U_{n}\operatorname {diag} (F_{n}c)U_{n}^{*}={\frac {1}{n}}F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},$$
  कहाँ $c$ का प्रथम स्तंभ है $C$. के eigenvalues $C$ उत्पाद द्वारा दिया जाता है $F_{n}c$. इस उत्पाद की तेजी से फूरियर रूपांतरण द्वारा आसानी से गणना की जा सकती है। इसके विपरीत, किसी भी विकर्ण मैट्रिक्स के लिए $D$, उत्पाद $F_{n}^{-1}DF_{n}$ वे इसे प्रसारित करते हैं।
• होने देना $p(x)$ (मोनिक बहुपद) एक की विशेषता बहुपद हो $n\times n$ मैट्रिक्स की परिक्रमा $C$, और जाने $p'(x)$ का व्युत्पन्न होना $p(x)$. फिर बहुपद ${\textstyle {\frac {1}{n}}p'(x)}$ निम्नलिखित का अभिलाक्षणिक बहुपद है $(n-1)\times (n-1)$ का सबमैट्रिक्स $C$:
  $$C_{n-1}={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &c_{3}&c_{2}\\c_{1}&c_{0}&c_{n-1}&&c_{3}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{n-3}&&\ddots &\ddots &c_{n-1}\\c_{n-2}&c_{n-3}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}$$
  (देखना सबूत के लिए)।

विश्लेषणात्मक व्याख्या

सर्कुलेंट मेट्रिसेस की व्याख्या ज्यामितीय रूप से की जा सकती है, जो असतत फूरियर रूपांतरण के साथ संबंध की व्याख्या करता है।

में वैक्टर पर विचार करें $\mathbb {R} ^{n}$ अवधि के साथ पूर्णांकों पर कार्य के रूप में $n$, (यानी, आवधिक द्वि-अनंत अनुक्रम के रूप में: $\dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots$) या समकक्ष, आदेश के चक्रीय समूह पर कार्य करता है $n$ ($C_{n}$ या $\mathbb {Z} /n\mathbb {Z}$) ज्यामितीय रूप से, नियमित रूप से (कोने पर)। $n$-gon: यह वास्तविक रेखा या वृत्त पर आवधिक कार्यों के लिए असतत अनुरूप है।

फिर, ऑपरेटर सिद्धांत के परिप्रेक्ष्य से, एक सर्कुलेंट मैट्रिक्स असतत अभिन्न परिवर्तन का कर्नेल है, अर्थात् फ़ंक्शन के लिए कनवल्शन ऑपरेटर $(c_{0},c_{1},\dots ,c_{n-1})$; यह एक असतत गोलाकार कनवल्शन है। कार्यों के दृढ़ संकल्प के लिए सूत्र $(b_{i}):=(c_{i})*(a_{i})$ है

$$b_{k}=\sum _{i=0}^{n-1}a_{i}c_{k-i}$$

(याद रखें कि अनुक्रम आवधिक हैं) जो वेक्टर का उत्पाद है $(a_{i})$ सर्कुलेंट मैट्रिक्स के लिए $(c_{i})$.

असतत फूरियर रूपांतरण तब कनवल्शन को गुणन में परिवर्तित करता है, जो मैट्रिक्स सेटिंग में विकर्णीकरण से मेल खाता है। $C^{*}$वें>-जटिल संख्या प्रविष्टियों के साथ सभी परिसंचारी मैट्रिसेस का बीजगणित समूह के लिए समरूप है $C^{*}$-बीजगणित का $\mathbb {Z} /n\mathbb {Z}$.

सममित परिसंचारी आव्यूह

एक सममित परिसंचरण मैट्रिक्स के लिए $C$ एक की अतिरिक्त शर्त है कि $c_{n-i}=c_{i}$. इस प्रकार यह द्वारा निर्धारित किया जाता है $\lfloor n/2\rfloor +1$ तत्व।

$$C={\begin{bmatrix}c_{0}&c_{1}&\cdots &c_{2}&c_{1}\\c_{1}&c_{0}&c_{1}&&c_{2}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{2}&&\ddots &\ddots &c_{1}\\c_{1}&c_{2}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}.$$

किसी भी वास्तविक सममित मैट्रिक्स के eigenvalues ​​वास्तविक हैं। संबंधित eigenvalues ​​बन जाते हैं:

$$\lambda _{j}=c_{0}+2c_{1}\Re \omega _{j}+2c_{2}\Re \omega _{j}^{2}+\dots +2c_{n/2-1}\Re \omega _{j}^{n/2-1}+c_{n/2}\omega _{j}^{n/2}$$

के लिए $n$ समानता (गणित), और

$$\lambda _{j}=c_{0}+2c_{1}\Re \omega _{j}+2c_{2}\Re \omega _{j}^{2}+\dots +2c_{(n-1)/2}\Re \omega _{j}^{(n-1)/2}$$

के लिए $n$ समता (गणित), जहां $\Re z$ की जटिल संख्या को दर्शाता है $z$. इस तथ्य का उपयोग करके इसे और सरल बनाया जा सकता है $\Re \omega _{j}^{k}=\cos(2\pi jk/n)$.

सममित परिसंचारी आव्यूह द्विसममित आव्यूह के वर्ग से संबंधित हैं।

हर्मिटियन सर्कुलेंट मैट्रिसेस

सर्कुलेंट मैट्रिक्स का जटिल संस्करण, संचार सिद्धांत में सर्वव्यापी, आमतौर पर हर्मिटियन मैट्रिक्स है। इस मामले में $c_{n-i}=c_{i}^{*},\;i\leq n/2$ और इसके निर्धारक और सभी eigenvalues ​​वास्तविक हैं।

यदि n पहली दो पंक्तियाँ भी आवश्यक रूप से रूप लेती हैं

$${\begin{bmatrix}r_{0}&z_{1}&z_{2}&r_{3}&z_{2}^{*}&z_{1}^{*}\\z_{1}^{*}&r_{0}&z_{1}&z_{2}&r_{3}&z_{2}^{*}\\\dots \\\end{bmatrix}}.$$

जिसमें प्रथम तत्व है $r_{3}$ शीर्ष दूसरी छमाही पंक्ति में वास्तविक है।

यदि n विषम है तो हमें प्राप्त होता है

$${\begin{bmatrix}r_{0}&z_{1}&z_{2}&z_{2}^{*}&z_{1}^{*}\\z_{1}^{*}&r_{0}&z_{1}&z_{2}&z_{2}^{*}\\\dots \\\end{bmatrix}}.$$

टी हर्मिटियन स्थिति के लिए eigenvalues ​​पर बाधाओं पर चर्चा की है।

अनुप्रयोग

रैखिक समीकरणों में

एक मैट्रिक्स समीकरण दिया

$$C\mathbf {x} =\mathbf {b} ,$$

कहाँ $C$ आकार का एक गोलाकार वर्ग मैट्रिक्स है $n$ हम समीकरण को वृत्ताकार कनवल्शन के रूप में लिख सकते हैं

$$\mathbf {c} \star \mathbf {x} =\mathbf {b} ,$$

कहाँ $\mathbf {c}$ का प्रथम स्तंभ है $C$, और वैक्टर $\mathbf {c}$, $\mathbf {x}$ और $\mathbf {b}$ प्रत्येक दिशा में चक्रीय रूप से विस्तारित होते हैं। डिस्क्रीट फूरियर ट्रांसफॉर्म # सर्कुलर कनवल्शन प्रमेय और क्रॉस-सहसंबंध प्रमेय का उपयोग करके, हम चक्रीय कनवल्शन को घटक-वार गुणन में बदलने के लिए डिस्क्रीट फूरियर ट्रांसफॉर्म का उपयोग कर सकते हैं

$${\mathcal {F}}_{n}(\mathbf {c} \star \mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )$$

ताकि

$$\mathbf {x} ={\mathcal {F}}_{n}^{-1}\left[\left({\frac {({\mathcal {F}}_{n}(\mathbf {b} ))_{\nu }}{({\mathcal {F}}_{n}(\mathbf {c} ))_{\nu }}}\right)_{\!\nu \in \mathbb {Z} }\right]^{\rm {T}}.$$

यह एल्गोरिथम मानक गाऊसी उन्मूलन की तुलना में बहुत तेज है, खासकर अगर एक तेज फूरियर रूपांतरण का उपयोग किया जाता है।

ग्राफ सिद्धांत में

ग्राफ़ सिद्धांत में, एक ग्राफ़ (असतत गणित) या निर्देशित ग्राफ़ जिसका आसन्न मैट्रिक्स सर्कुलेंट है, एक गोलाकार ग्राफ ़ (या डिग्राफ़) कहा जाता है। समतुल्य रूप से, एक ग्राफ परिचालित होता है यदि इसके ऑटोमोर्फिज्म समूह में एक पूर्ण-लंबाई चक्र होता है। मोबियस लैडर सर्कुलेंट ग्राफ़ के उदाहरण हैं, जैसे कि अभाज्य संख्या क्रम के क्षेत्र (गणित) के लिए पाले ग्राफ हैं।

बाहरी संबंध

• R. M. Gray, Toeplitz and Circulant Matrices: A Review doi:10.1561/0100000006
• Weisstein, Eric W. "Circulant Matrix". MathWorld.
• IPython Notebook demonstrating properties of circulant matrices