Κυκλοτερής πίνακας

Στη γραμμική άλγεβρα, ένας **κυκλοτερής πίνακας** είναι ένας τετραγωνικός πίνακας στον οποίο όλες οι γραμμές αποτελούνται από τα ίδια στοιχεία και κάθε γραμμή περιστρέφεται κατά ένα στοιχείο προς τα δεξιά σε σχέση με την προηγούμενη γραμμή. Πρόκειται για ένα ιδιαίτερο είδος πίνακα Τόεπλιτς.

Στην αριθμητική ανάλυση, οι κυκλοτερείς πίνακες είναι σημαντικοί επειδή διαγωνοποιούνται με έναν διακριτό μετασχηματισμό Φουριέ, και ως εκ τούτου οι γραμμικές εξισώσεις που τους περιέχουν μπορούν να επιλυθούν γρήγορα με τη χρήση ενός γρήγορου μετασχηματισμού Φουριέ. Μπορούν να ερμηνευθούν αναλυτικά ως ο ολοκληρωτικός πυρήνας ενός τελεστή συνέλιξης στην κυκλική ομάδα C_n και ως εκ τούτου εμφανίζονται συχνά σε επίσημες περιγραφές χωρικά αναλλοίωτων γραμμικών πράξεων. Αυτή η ιδιότητα είναι επίσης κρίσιμη στα σύγχρονα ραδιοφωνικά συστήματα καθορισμένου λογισμικού, τα οποία χρησιμοποιούν την ορθογώνια πολυπλεξία διαίρεσης συχνότητας για να διαδώσουν τα σύμβολα (bits) χρησιμοποιώντας ένα κυκλικό πρόθεμα. Αυτό επιτρέπει την αναπαράσταση του καναλιού από έναν κυκλοτερή πίνακα, απλοποιώντας την εξισορρόπηση του καναλιού στο πεδίο της συχνότητας.

Στην κρυπτογραφία, ένας κυκλοτερής πίνακας χρησιμοποιείται στο βήμα MixColumns (Μείξη στηλών) του προηγμένου προτύπου κρυπτογράφησης.

## Ορισμός

Ένας 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)^{T},\quad j = 0, 1, \ldots, n-1,

όπου \omega=\exp \left(\tfrac{2\pi i}{n}\right) είναι μια πρωταρχική n-th ρίζα της μονάδας και i είναι η φανταστική μονάδα.

(Αυτό μπορεί να γίνει κατανοητό συνειδητοποιώντας ότι ο πολλαπλασιασμός με έναν κυκλοτερή πίνακα υλοποιεί μια συνέλιξη. Στο χώρο Φουριέ, η συνέλιξη μετατρέπεται σε πολλαπλασιασμό. Επομένως, το γινόμενο ενός κυκλοτερούς πίνακα με έναν τρόπο Φουριέ δίνει ένα πολλαπλάσιο αυτού του τρόπου Φουριέ, δηλαδή είναι ένα ιδιοδιάνυσμα).

Οι αντίστοιχες ιδιοτιμές δίνονται από

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

### Ορίζουσα

Ως συνέπεια του ρητού τύπου για τις ιδιοτιμές παραπάνω,
η ορίζουσα ενός κυκλοτερούς πίνακα μπορεί να υπολογιστεί ως εξής:

\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^+ είναι κυκλοτερή. F_n \text{ είναι μοναδιαίο}, \text{ όπου } F_n = [v_0,v_1,\dots,v_{n-1}]= \frac{1}{\sqrt{n}}(f_{kj}) \text{ με } f_{kj} = e^{2\pi i/n \cdot kj}, \,\text{ για } 0 \leq k,j \leq n-1.
* Ο πίνακας F_n που αποτελείται από τα ιδιοδιανύσματα ενός κυκλοτερούς πίνακα σχετίζεται με τον διακριτό μετασχηματισμό Φουριέ και τον αντίστροφο μετασχηματισμό του:Συνεπώς, ο πίνακας U_n διαγωνοποιεί τον C. Στην πραγματικότητα, έχουμε C = F_n\operatorname{diag}(\sqrt n \cdot F_n^{\dagger} c) F_n^{\dagger} , όπου c είναι η πρώτη στήλη του C. Οι ιδιοτιμές του C δίνονται από το γινόμενο F_n^{\dagger} c. Αυτό το γινόμενο μπορεί εύκολα να υπολογιστεί με γρήγορο μετασχηματισμό Φουριέ. Αντίστροφα, για κάθε διαγώνιο πίνακα D, το γινόμενο F_nDF_n^{\dagger} είναι κυκλοτερές.
* Έστω p(x) το (μονικό) χαρακτηριστικό πολυώνυμο ενός n \times n κυκλοτερούς πίνακα C. Τότε η κλιμακωτή παράγωγος \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}

(Δείτε  για την απόδειξη)

## Αναλυτική ερμηνεία
Οι κυκλικοί πίνακες μπορούν να ερμηνευθούν γεωμετρικά, γεγονός που εξηγεί τη σύνδεση με τον διακριτό μετασχηματισμό Φουριέ.

Ας θεωρήσουμε τα διανύσματα στο \R^n ως συναρτήσεις στους ακέραιους αριθμούς με περίοδο n, (δηλαδή, ως περιοδικές δι-άπειρες ακολουθίες: \dots,a_0,a_1,\dots,a_{n-1},a_0,a_1,\dots) ή ισοδύναμα, ως συναρτήσεις στην κυκλική ομάδα τάξης n (συμβολίζεται C_n ή \Z/n\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^*-άλγεβρα της \Z/n\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}.

Οι ιδιοτιμές κάθε πραγματικού συμμετρικού πίνακα είναι πραγματικές.
Οι αντίστοιχες ιδιοτιμές  \vec{\lambda}= \sqrt n \cdot F_n^{\dagger} cγίνονται:

\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 k j )} \\
& = & c_0+ c_{n/2} \omega_k^{n/2} + 2 c_1 \Re \omega_k + 2 c_2 \Re \omega_k^2 + \dots + 2c_{n/2-1} \Re \omega_k^{n/2-1} \end{array}

για n ζυγά, και

\begin{array}{lcl} \lambda_k & = & c_0 + 2\sum_{j=1}^{\frac{n-1}{2}} c_j \cos{(-\frac{2\pi}{n}\cdot k j )}  \\ 
 & = & c_0 + 2 c_1 \Re \omega_k + 2 c_2 \Re \omega_k^2 + \dots + 2c_{(n-1)/2} \Re \omega_k^{(n-1)/2} \end{array}


για n περιττό, όπου \Re z δηλώνει το πραγματικό μέρος του z.
Αυτό μπορεί να απλοποιηθεί περαιτέρω χρησιμοποιώντας το γεγονός ότι \Re \omega_k^j = \Re e^{-\frac{2\pi i}{n} \cdot kj} = \cos(-\frac{2\pi}{n} \cdot kj) και \omega_k^{n/2}=e^{-\frac{2\pi i}{n} \cdot k \frac{n}{2}} =e^{-\pi i \cdot k} ανάλογα με το k ζυγό ή μονό.

Οι συμμετρικοί κυκλοτερείς πίνακες ανήκουν στην κατηγορία των δισυμμετρικών πινάκων.

## Ερμιτιανοί κυκλοτερείς πίνακες

Η μιγαδική εκδοχή του κυκλικού πίνακα, πανταχού παρούσα στη θεωρία επικοινωνιών, είναι συνήθως Ερμιτιανή. Στην περίπτωση αυτή c_{n-i} = c_i^*, \; i \le 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}.


Ο Τι (Tee)  συζήτησε τους περιορισμούς στις ιδιοτιμές για την ερμητική συνθήκη.

## Εφαρμογές

### Σε γραμμικές εξισώσεις

Δεδομένης μιας εξίσωσης πίνακα
: 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\Z}\, \right]^{\rm T}.

Αυτός ο αλγόριθμος είναι πολύ ταχύτερος από την τυπική απαλοιφή Γκάους, ειδικά εάν χρησιμοποιείται γρήγορος μετασχηματισμός Φουριέ.

### Στη θεωρία γραφημάτων

Στη θεωρία γραφημάτων, ένα γράφημα ή ένας διγράφος του οποίου ο πίνακας γειτνίασης είναι κυκλοτερής ονομάζεται κυκλοτερής γράφος/διγράφος. Αντίστοιχα, ένας γράφος είναι κυκλοτερής εάν η ομάδα αυτομορφισμού του περιέχει έναν κύκλο πλήρους μήκους. Οι σκάλες Μόμπιους είναι παραδείγματα κυκλικών γραφημάτων, όπως και τα γραφήματα Παλέι για σώματα πρώτης τάξης.

## Δημοσιεύσεις
* 
* 
* 
* 
* 
* 
* 
* 

## Δείτε επίσης

* Field Arithmetic
* Πραγματικό προβολικό επίπεδο
* Μιγαδικός αριθμός
* Αντιερμιτιανός πίνακας
* Μέγιστος κοινός διαιρέτης
* Υπολογιστική βιολογία
* Ελάσσων (γραμμική άλγεβρα)
* Προβολή (γραμμική άλγεβρα)
* Συμμετρικός πίνακας
* Πίνακας γειτνίασης
* Πολλαπλασιασμός πινάκων
* Επαναλαμβανόμενη συνάρτηση
* Ιδιοτιμές και ιδιοδιανύσματα
* Θεωρία γράφων
* Θεωρία πιθανοτήτων
* High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form

## Εξωτερικοί σύνδεσμοι

* English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
* Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
* Matrix calculator
* Matrix Analysis
* Complex-Valued Matrix Derivatives: With Applications in Signal Processing ...
* Exercises of Matrices and Linear Algebra
* Multidimensional Statistical Analysis and Theory of Random Matrices ...
* Quantum Probability and Spectral Analysis of Graphs.
* Symplectic Methods in Harmonic Analysis and in Mathematical Physics...
* Lie Groups: An Introduction Through Linear Groups
* Vibrational Spectroscopy with Neutrons: With Applications in Chemistry ..
* Toeplitz and Circulant Matrices: A Review...
* Special Matrices Of Mathematical Physics: Stochastic, Circulant And Bell ...

## Παραπομπές


* 
* IPython Notebook demonstrating properties of circulant matrices
* 

Κατηγορία:Αριθμητική γραμμική άλγεβρα
Κατηγορία:Γραμμική άλγεβρα
Κατηγορία:Θεωρήματα της γραμμικής άλγεβρας
Κατηγορία:Πίνακες (μαθηματικά)
Κατηγορία:Αφηρημένη άλγεβρα
Κατηγορία:Αριθμητική ανάλυση
Κατηγορία:Ορίζουσες