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

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

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

गुण

अभिलक्षणिक सदिश और अभिलक्षणिक मान

एक चक्रीय आव्यूह के सामान्यीकृत अभिलक्षणिक सदिश फूरियर मोड के रुप में होते है, अर्थात्,

$$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$ काल्पनिक इकाई है।

यह समझ कर समझा जा सकता है कि एक चक्रीय आव्यूह के साथ गुणन एक कनवल्शन को लागू करता है। फूरियर स्पेस में कनवल्शन मल्टीप्लिकेशन बन जाते हैं। इसलिए एक फूरियर मोड के साथ एक चक्रीय आव्यूह का उत्पाद उस फूरियर मोड के एक से अधिक का उत्पादन करता है यानी यह एक अभिलक्षणिक सदिश के रुप में होता है।

इसी अभिलक्षणिक सदिश ​​द्वारा दिया जाता है

$$\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$. के अभिलक्षणिक मान $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}$) ज्यामितीय रूप से, नियमित रूप से कोने पर एन- गोन के रुप में होता है, यह वास्तविक रेखा या वृत्त पर आवधिक कार्यों के लिए असतत अनुरूप है।

फिर, ऑपरेटर सिद्धांत के परिप्रेक्ष्य से, एक चक्रीय आव्यूह असतत अभिन्न परिवर्तन का कर्नेल है, अर्थात् फलन के लिए कनवल्शन ऑपरेटर $(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}}.$$

किसी भी वास्तविक सममित आव्यूह के अभिलक्षणिक मान ​​वास्तविक रुप में होते है। यह संबंधित अभिलक्षणिक मान ​​बन जाते हैं

$$\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$ और इसके निर्धारक और सभी अभिलक्षणिक मान ​​वास्तविक रुप में होते है।

यदि 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