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

For the symmetric graphs, see Circulant graph.

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

संख्यात्मक विश्लेषण में, सर्कुलेंट मैट्रिसेस महत्वपूर्ण होती है, क्योंकि वे असतत फूरियर रूपांतरण द्वारा विकर्णित होते हैं और इसलिए उन्हें सम्मलित करने वाले रैखिक समीकरणों को तेजी से फूरियर रूपांतरण का उपयोग करके हल किया जा सकता है। [1] उन्हें विश्लेषणात्मक रूप से चक्रीय समूह $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