مصفوفة دائرية

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 70 صور
الموسوعة الحرة

في الجبر الخطي ، المصفوفة الدائرية هي مصفوفة مربعة تتكون جميع صفوفها من نفس العناصر، ويتم تدوير كل صف عنصرًا واحدًا إلى اليمين بالنسبة للصف السابق. وهي نوع خاص من مصفوفات توبليتز .

في التحليل العددي ، تُعدّ المصفوفات الدائرية مهمة لأنها تُقطّر بواسطة تحويل فورييه منفصل ، وبالتالي يمكن حلّ المعادلات الخطية التي تحتوي عليها بسرعة باستخدام تحويل فورييه سريع . [ 1 ] ويمكن تفسيرها تحليليًا على أنها النواة التكاملية لمؤثر الالتفاف على المجموعة الدورية.جن{\displaystyle C_{n}}ولذا، تظهر هذه الخاصية بكثرة في الأوصاف الرسمية للعمليات الخطية الثابتة مكانيًا. كما أنها بالغة الأهمية في أجهزة الراديو الحديثة المعرفة بالبرمجيات، والتي تستخدم تقنية تعدد الإرسال بتقسيم التردد المتعامد لتوزيع الرموز (البتات) باستخدام بادئة دورية . وهذا يُمكّن من تمثيل القناة بمصفوفة دائرية، مما يُبسط عملية معادلة القناة في مجال التردد .

في علم التشفير ، يتم استخدام مصفوفة دائرية في خطوة MixColumns من معيار التشفير المتقدم .

تعريف

أنن×ن{\displaystyle n\times n}مصفوفة دائريةج{\displaystyle C}يأخذ الشكل ج=[ج0جن-1⋯ج2ج1ج1ج0جن-1ج2⋮ج1ج0⋱⋮جن-2⋱⋱جن-1جن-1جن-2⋯ج1ج0]{\displaystyle 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}}} أو منقولة هذا الشكل (باختيار الترميز). إذا كان كلجأنا{\displaystyle c_{i}}هوص×ص{\displaystyle p\times p}المصفوفة المربعة ، ثمنص×نص{\displaystyle np\times np}مصفوفةج{\displaystyle C}تُسمى مصفوفة دائرية كتلية .

يتم تحديد المصفوفة الدائرية بالكامل بواسطة متجه واحد،ج{\displaystyle c}، والذي يظهر كأول عمود (أو صف) منج{\displaystyle C}الأعمدة (والصفوف، على التوالي) المتبقية منج{\displaystyle C}كل منها عبارة عن تبديلات دورية للمتجهج{\displaystyle c}مع إزاحة تساوي فهرس العمود (أو الصف، على التوالي)، إذا تم فهرسة الأسطر من0{\displaystyle 0}لن-1{\displaystyle n-1}(للتبديل الدوري للصفوف نفس تأثير التبديل الدوري للأعمدة.) الصف الأخير منج{\displaystyle C}هو المتجهج{\displaystyle c}تم إزاحتها بمقدار واحد في الاتجاه المعاكس.

تُعرّف المصادر المختلفة المصفوفة الدائرية بطرق مختلفة، على سبيل المثال كما هو مذكور أعلاه، أو باستخدام المتجهج{\displaystyle c}يتوافق مع الصف الأول بدلاً من العمود الأول من المصفوفة؛ وربما مع اتجاه إزاحة مختلف (والذي يسمى أحيانًا مصفوفة مضادة للدوران ).

متعددة الحدودو(x)=ج0+ج1x+⋯+جن-1xن-1{\displaystyle f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}}يُطلق عليه اسم متعددة الحدود المرتبطة بالمصفوفةج{\displaystyle C}.

ملكيات

المتجهات الذاتية والقيم الذاتية

المتجهات الذاتية المعيارية لمصفوفة دائرية هي أنماط فورييه، وهي: vج=1ن(1،ωج،ω2ج،...،ω(ن-1)ج)تي،ج=0،1،...،ن-1،{\displaystyle v_{j}={\frac {1}{\sqrt {n}}}\left(1,\omega ^{j},\omega ^{2j},\ldots ,\omega ^{(n-1)j}\right)^{T},\quad j=0,1,\ldots ,n-1,} أينω=خبرة⁡(2πأنان){\displaystyle \omega =\exp \left({\tfrac {2\pi i}{n}}\right)}هو بدائين{\displaystyle n}الجذر النوني للوحدة وأنا{\displaystyle i}هي الوحدة التخيلية .

(يمكن فهم ذلك من خلال إدراك أن الضرب بمصفوفة دائرية يُنفذ عملية التفاف. في فضاء فورييه، تصبح عمليات الالتفاف ضربًا. وبالتالي فإن حاصل ضرب مصفوفة دائرية مع نمط فورييه ينتج عنه مضاعف لهذا النمط، أي أنه متجه ذاتي.)

تُعطى القيم الذاتية المقابلة بواسطةλج=ج0+ج1ω-ج+ج2ω-2ج+⋯+جن-1ω-(ن-1)ج،ج=0،1،...،ن-1.{\displaystyle \lambda _{j}=c_{0}+c_{1}\omega ^{-j}+c_{2}\omega ^{-2j}+\dots +c_{n-1}\omega ^{-(n-1)j},\quad j=0,1,\dots ,n-1.}

المحدد

نتيجةً للصيغة الصريحة للقيم الذاتية المذكورة أعلاه، يمكن حساب محدد المصفوفة الدائرية على النحو التالي: المحققج=∏ج=0ن-1(ج0+جن-1ωج+جن-2ω2ج+⋯+ج1ω(ن-1)ج).{\displaystyle \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}).} بما أن عملية النقل لا تغير القيم الذاتية للمصفوفة، فإن الصيغة المكافئة هي المحققج=∏ج=0ن-1(ج0+ج1ωج+ج2ω2ج+⋯+جن-1ω(ن-1)ج)=∏ج=0ن-1و(ωج).{\displaystyle \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}).}

رتبة

رتبة المصفوفة الدائريةج{\displaystyle C}يساوين-د{\displaystyle n-d}أيند{\displaystyle d}هي درجة متعددة الحدودالقاسم المشترك الأكبر(و(x)،xن-1){\displaystyle \gcd(f(x),x^{n}-1)}[ 2 ]​

خصائص أخرى

  • أي عنصر دائري هو متعدد حدود مصفوفي (أي متعدد الحدود المرتبط به) في مصفوفة التبديل الدوريةP{\displaystyle P}:ج=ج0أنا+ج1P+ج2P2+⋯+جن-1Pن-1=و(P)،{\displaystyle C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),}أينP{\displaystyle P}يتم تحديدها بواسطة المصفوفة المرافقةP=[00⋯0110⋯000⋱⋱⋮⋮⋮⋱⋱000⋯010].{\displaystyle 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}}.}
  • مجموعة​​ن×ن{\displaystyle n\times n}تشكل المصفوفات الدائريةن{\displaystyle n}- فضاء متجهي ذو أبعاد بالنسبة لعمليتي الجمع والضرب القياسي. يمكن تفسير هذا الفضاء على أنه فضاء الدوال على المجموعة الدورية من الرتبةن{\displaystyle n}،جن{\displaystyle C_{n}}أو ما يعادلها كحلقة المجموعة لـجن{\displaystyle C_{n}}.
  • تشكل المصفوفات الدائرية جبرًا تبادليًا ، لأنه لأي مصفوفتين دائريتين معطيتينأ{\displaystyle A}وب{\displaystyle B}المجموعأ+ب{\displaystyle A+B}المنتج متداولأب{\displaystyle AB}وهو دوراني، وأب=بأ{\displaystyle AB=BA}.
  • بالنسبة لمصفوفة دائرية غير منفردةأ{\displaystyle A}، وعكسهأ-1{\displaystyle A^{-1}}وهي أيضًا مصفوفة دائرية. بالنسبة لمصفوفة دائرية مفردة، فإن معكوسها الزائف من نوع مور-بنروزأ+{\displaystyle A^{+}}هو دوراني.
  • مصفوفة تحويل فورييه المنفصلة من الرتبةن{\displaystyle n}يُعرَّف بأنه بواسطة

Fن=(وجك) مع وجك=هـ-2πأنا/ن⋅جك،ل 0≤ج،ك≤ن-1.{\displaystyle F_{n}=(f_{jk}){\text{ with }}f_{jk}=e^{-2\pi i/n\cdot jk},\,{\text{for }}0\leq j,k\leq n-1.} توجد روابط مهمة بين المصفوفات الدائرية ومصفوفات تحويل فورييه المنفصلة. في الواقع، يمكن إثبات ذلك. ج=Fن-1التشخيص⁡(Fنج)Fن،{\displaystyle C=F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},}أينج{\displaystyle c}هو العمود الأول منج{\displaystyle C}القيم الذاتية لـج{\displaystyle C}يتم تحديدها بواسطة المنتجFنج{\displaystyle F_{n}c}يمكن حساب هذا المنتج بسهولة عن طريق تحويل فورييه السريع . [ 3 ]

  • يتركص(x){\displaystyle p(x)}ليكن متعدد الحدود المميز ( الأحادي ) لـن×ن{\displaystyle n\times n}مصفوفة دائريةج{\displaystyle C}ثم المشتق المُقاس1نص′(x){\textstyle {\frac {1}{n}}p'(x)}هي متعددة الحدود المميزة لما يلي(ن-1)×(ن-1){\displaystyle (n-1)\times (n-1)}المصفوفة الفرعية لـج{\displaystyle C}:جن-1=[ج0جن-1⋯ج3ج2ج1ج0جن-1ج3⋮ج1ج0⋱⋮جن-3⋱⋱جن-1جن-2جن-3⋯ج1ج0]{\displaystyle 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}}}( انظر [ 4 ] للإثبات ).

التفسير التحليلي

يمكن تفسير المصفوفات الدائرية هندسيًا ، مما يفسر العلاقة مع تحويل فورييه المنفصل.

ضع في اعتبارك المتجهات فيRن{\displaystyle \mathbb {R} ^{n}}كدوال على الأعداد الصحيحة ذات الدورةن{\displaystyle n}، (أي، كمتتابعات دورية ثنائية اللانهاية:...،أ0،أ1،...،أن-1،أ0،أ1،...{\displaystyle \dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots }أو بصورة مكافئة، كدوال على المجموعة الدورية من الرتبةن{\displaystyle n}(يشار إليه)جن{\displaystyle C_{n}}أوZ/نZ{\displaystyle \mathbb {Z} /n\mathbb {Z} }) هندسياً، على (رؤوس) المنتظمن{\displaystyle n}-gon : هذا نظير منفصل للدوال الدورية على الخط الحقيقي أو الدائرة .

ثم، من منظور نظرية المؤثرات ، فإن المصفوفة الدائرية هي نواة تحويل تكاملي منفصل ، أي مؤثر الالتفاف للدالة.(ج0،ج1،...،جن-1){\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}هذا التفاف دائري منفصل . صيغة التفاف الدوال(بأنا):=(جأنا)*(أأنا){\displaystyle (b_{i}):=(c_{i})*(a_{i})}يكون

بك=∑أنا=0ن-1أأناجك-أنا{\displaystyle b_{k}=\sum _{i=0}^{n-1}a_{i}c_{k-i}}

(تذكر أن المتتاليات دورية) وهو ناتج ضرب المتجه(أأنا){\displaystyle (a_{i})}بواسطة المصفوفة الدائرية لـ(جأنا){\displaystyle (c_{i})}.

ثم يقوم تحويل فورييه المنفصل بتحويل الالتفاف إلى ضرب، وهو ما يتوافق في سياق المصفوفة مع عملية التقطير.

الج*{\displaystyle C^{*}}الجبر - لجميع المصفوفات الدائرية ذات المدخلات المركبة متماثل مع المجموعةج*{\displaystyle C^{*}}-جبرZ/نZ.{\displaystyle \mathbb {Z} /n\mathbb {Z} .}

العلاقة بالعمليات الثابتة

في الإحصاء ومعالجة الإشارات ، تنشأ المصفوفات الدائرية بشكل طبيعي كمصفوفات تباين للعمليات الثابتة بالمعنى الواسع، والتي تُلاحظ على مصفوفة دائرية أو مع شروط حدودية دورية. وبشكل أعم، فإن مصفوفة التباين لعملية ثابتة على مصفوفة خطية هي مصفوفة توبليتز ، وتكون مصفوفات توبليتز دائرية تقاربياً مع ازدياد الأبعاد. [ 5 ] هذا التكافؤ التقاربي هو السبب في أن التحليل الطيفي القائم على تحويل فورييه المنفصل (DFT) هو الأمثل تقاربياً للعمليات الثابتة: إذ يقوم تحويل فورييه المنفصل بتحويل المصفوفات الدائرية إلى مصفوفات قطرية بدقة، ويحول مصفوفات توبليتز إلى مصفوفات قطرية تقريبياً، وبالتالي تكون معاملات تحويل فورييه المنفصل غير مترابطة تقاربياً للبيانات الثابتة.

المصفوفات الدائرية المتناظرة

بالنسبة للمصفوفة الدائرية المتناظرةج{\displaystyle C}أحدهما لديه شرط إضافي وهوجن-أنا=جأنا{\displaystyle c_{n-i}=c_{i}}وبالتالي يتم تحديده بواسطة⌊ن/2⌋+1{\displaystyle \lfloor n/2\rfloor +1}عناصر. ج=[ج0ج1⋯ج2ج1ج1ج0ج1ج2⋮ج1ج0⋱⋮ج2⋱⋱ج1ج1ج2⋯ج1ج0].{\displaystyle 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}}.}

القيم الذاتية لأي مصفوفة متناظرة حقيقية هي قيم حقيقية. القيم الذاتية المقابلة لهاλ→=ن⋅Fن†ج{\displaystyle {\vec {\lambda }}={\sqrt {n}}\cdot F_{n}^{\dagger }c}يصبح: λك=ج0+جن/2هـ-πأنا⋅ك+2∑ج=1ن2-1ججكوس⁡(-2πن⋅كج)=ج0+جن/2ωكن/2+2ج1ℜωك+2ج2ℜωك2+⋯+2جن/2-1ℜωكن/2-1{\displaystyle {\begin{array}{lcl}\lambda _{k}&=&c_{0}+c_{n/2}e^{-\pi i\cdot k}+2\sum _{j=1}^{{\frac {n}{2}}-1}c_{j}\cos {(-{\frac {2\pi }{n}}\cdot kj)}\\&=&c_{0}+c_{n/2}\omega _{k}^{n/2}+2c_{1}\Re \omega _{k}+2c_{2}\Re \omega _{k}^{2}+\dots +2c_{n/2-1}\Re \omega _{k}^{n/2-1}\end{array}}} لن{\displaystyle n}بل وحتى ، و λك=ج0+2∑ج=1ن-12ججكوس⁡(-2πن⋅كج)=ج0+2ج1ℜωك+2ج2ℜωك2+⋯+2ج(ن-1)/2ℜωك(ن-1)/2{\displaystyle {\begin{array}{lcl}\lambda _{k}&=&c_{0}+2\sum _{j=1}^{\frac {n-1}{2}}c_{j}\cos {(-{\frac {2\pi }{n}}\cdot kj)}\\&=&c_{0}+2c_{1}\Re \omega _{k}+2c_{2}\Re \omega _{k}^{2}+\dots +2c_{(n-1)/2}\Re \omega _{k}^{(n-1)/2}\end{array}}} لن{\displaystyle n}غريب ، حيثℜz{\displaystyle \Re z}يشير إلى الجزء الحقيقي منz{\displaystyle z}ويمكن تبسيط ذلك أكثر باستخدام حقيقة أنℜωكج=ℜهـ-2πأنان⋅كج=كوس⁡(-2πن⋅كج){\displaystyle \Re \omega _{k}^{j}=\Re e^{-{\frac {2\pi i}{n}}\cdot kj}=\cos(-{\frac {2\pi }{n}}\cdot kj)}وωكن/2=هـ-2πأنان⋅كن2=هـ-πأنا⋅ك{\displaystyle \omega _{k}^{n/2}=e^{-{\frac {2\pi i}{n}}\cdot k{\frac {n}{2}}}=e^{-\pi i\cdot k}}.اعتمادا عليك{\displaystyle k}زوجي أو فردي.

تنتمي المصفوفات الدائرية المتناظرة إلى فئة المصفوفات ثنائية التناظر .

المصفوفات الدائرية الهرميتية

النسخة المعقدة من المصفوفة الدائرية، الشائعة في نظرية الاتصالات، هي عادةً هيرميتية . في هذه الحالةجن-أنا=جأنا*،أنا≤ن/2{\displaystyle c_{n-i}=c_{i}^{*},\;i\leq n/2}ومحددها وجميع قيمها الذاتية حقيقية.

إذا كان n زوجيًا، فإن الصفين الأولين يأخذان بالضرورة الشكل التالي [ر0z1z2ر3z2*z1*z1*ر0z1z2ر3z2*...].{\displaystyle {\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}}.} حيث العنصر الأولر3{\displaystyle r_{3}}في الصف الثاني العلوي، هذا حقيقي.

إذا كان n فرديًا، فسنحصل على [ر0z1z2z2*z1*z1*ر0z1z2z2*...].{\displaystyle {\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}}.}

ناقش تي [ 6 ] القيود المفروضة على القيم الذاتية لشرط هيرميت.

التطبيقات

في المعادلات الخطية

بفرض معادلة مصفوفية

جx=ب،{\displaystyle C\mathbf {x} =\mathbf {b} ,}

أينج{\displaystyle C}هي مصفوفة دائرية بحجمن{\displaystyle n}يمكننا كتابة المعادلة على شكل التفاف دائريج⋆x=ب،{\displaystyle \mathbf {c} \star \mathbf {x} =\mathbf {b} ,} أينج{\displaystyle \mathbf {c} }هو العمود الأول منج{\displaystyle C}والمتجهاتج{\displaystyle \mathbf {c} }،x{\displaystyle \mathbf {x} }وب{\displaystyle \mathbf {b} }يتم تمديدها دوريًا في كل اتجاه. باستخدام نظرية الالتفاف الدائري ، يمكننا استخدام تحويل فورييه المنفصل لتحويل الالتفاف الدوري إلى ضرب عنصري. Fن(ج⋆x)=Fن(ج)Fن(x)=Fن(ب){\displaystyle {\mathcal {F}}_{n}(\mathbf {c} \star \mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )} لهذا السبب. x=Fن-1[((Fن(ب))ν(Fن(ج))ν)ν∈Z]تي.{\displaystyle \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}}.}

هذه الخوارزمية أسرع بكثير من طريقة الحذف الغاوسي القياسية ، خاصة إذا تم استخدام تحويل فورييه السريع .

في نظرية الرسم البياني

في نظرية المخططات ، يُطلق على المخطط أو المخطط الموجه الذي تكون مصفوفة تجاوره دائرية اسم مخطط/مخطط موجه دائري . وبالمثل، يكون المخطط دائريًا إذا احتوت زمرة التشاكل الذاتي الخاصة به على دورة كاملة الطول. تُعد سلالم موبيوس أمثلة على المخططات الدائرية، وكذلك مخططات بالي لحقول ذات رتبة أولية .

مراجع

  1. ^ ديفيس ، فيليب جي (1970). المصفوفات الدائرية . نيويورك: وايلي. رقم ISBN 0-471-05771-1. OCLC 1408988930 . 
  2. ↑ أ. و. إنجلتون (1956). "رتبة المصفوفات الدائرية". مجلة جمعية لندن الرياضية . s1-31 (4): 445– 460. doi : 10.1112/jlms/s1-31.4.445 .
  3. ↑ غولوب، جين هـ .؛ فان لون، تشارلز ف. (1996)، "§4.7.7 الأنظمة الدائرية"، حسابات المصفوفات ( الطبعة الثالثة)، جونز هوبكنز، ISBN  978-0-8018-5414-9
  4. ↑ كوشيل، أولغا؛ تياغلوف، ميخائيل (15 يوليو 2016)، "الدوائر والنقاط الحرجة لكثيرات الحدود"، مجلة التحليل الرياضي والتطبيقات ، 439 (2): 634-650 ، arXiv : 1512.07983 ، doi : 10.1016/j.jmaa.2016.03.005 ، ISSN 0022-247X 
  5. ↑ غريناندر، أولف؛ سيغو، غابور (1958). أشكال توبليتز وتطبيقاتها . بيركلي، كاليفورنيا: مطبعة جامعة كاليفورنيا.
  6. ↑ تي، جي جي (2007). "المتجهات الذاتية للمصفوفات الدائرية الكتلية والمصفوفات الدائرية المتناوبة" (ملف PDF) . مجلة نيوزيلندا للرياضيات . 36 : 195-211 .