सर्कुलेट मैट्रिक्स

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$.

गुण

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

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

$$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.$$

निर्धारक

उपरोक्त eigenvalues ​​​​के लिए स्पष्ट सूत्र के परिणामस्वरूप, एक परिसंचरण मैट्रिक्स के निर्धारक की गणना इस प्रकार की जा सकती है:

$$\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}).$$

चूँकि ट्रांसपोज़ लेने से मैट्रिक्स के eigenvalues ​​​​नहीं बदलते हैं, एक समतुल्य सूत्रीकरण होता है

$$\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)$ और $\omega _{j}^{n/2}=\exp \left({\pi ij}\right)=\pm 1$ इस पर निर्भर करते हुए $j$ सम और विषम।

सममितीय वृत्ताकार मैट्रिक्स द्विसममितीय मैट्रिक्स के वर्ग से संबंधित हैं।

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

संचार सिद्धांत में सर्वव्यापी सर्कुलर मैट्रिक्स का जटिल संस्करण, आमतौर पर हर्मिटियन मैट्रिक्स है। इस मामले में $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}}.$$

टी हर्मिटियन स्थिति के लिए स्वदेशी मूल्यों पर बाधाओं पर चर्चा की है।

अनुप्रयोग

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

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

$$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