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

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

Στην αριθμητική ανάλυση, οι κυκλοτερείς πίνακες είναι σημαντικοί επειδή διαγωνοποιούνται με έναν διακριτό μετασχηματισμό Φουριέ, και ως εκ τούτου οι γραμμικές εξισώσεις που τους περιέχουν μπορούν να επιλυθούν γρήγορα με τη χρήση ενός γρήγορου μετασχηματισμού Φουριέ^[1]. Μπορούν να ερμηνευθούν αναλυτικά ως ο ολοκληρωτικός πυρήνας^[2] ενός τελεστή συνέλιξης στην κυκλική ομάδα $C_{n}$ και ως εκ τούτου εμφανίζονται συχνά σε επίσημες περιγραφές χωρικά αναλλοίωτων γραμμικών πράξεων. Αυτή η ιδιότητα είναι επίσης κρίσιμη στα σύγχρονα ραδιοφωνικά συστήματα καθορισμένου λογισμικού, τα οποία χρησιμοποιούν την ορθογώνια πολυπλεξία διαίρεσης συχνότητας^[3] για να διαδώσουν τα σύμβολα (bits) χρησιμοποιώντας ένα κυκλικό πρόθεμα. Αυτό επιτρέπει την αναπαράσταση του καναλιού από έναν κυκλοτερή πίνακα, απλοποιώντας την εξισορρόπηση του καναλιού στο πεδίο της συχνότητας^[4].

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

Ορισμός

Ένας $n \times n$ κυκλοτερής πίνακας. $C$ έχει τη μορφή

$C = [\begin{matrix} c_{0} & c_{n - 1} & \dots & c_{2} & c_{1} \\ c_{1} & c_{0} & c_{n - 1} & c_{2} \\ ⋮ & c_{1} & c_{0} & ⋱ & ⋮ \\ c_{n - 2} & ⋱ & ⋱ & c_{n - 1} \\ c_{n - 1} & c_{n - 2} & \dots & c_{1} & c_{0} \end{matrix}]$

ή η μεταφορά αυτής της μορφής (με την επιλογή του συμβολισμού). Αν κάθε $c_{i}$ είναι ένας $p \times p$ τετραγωνικός πίνακας, τότε ο $n p \times n p$ πίνακας $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}} {(1, ω^{j}, ω^{2 j}, \dots, ω^{(n - 1) j})}^{T}, j = 0, 1, \dots, n - 1,$

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

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

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

$λ_{j} = c_{0} + c_{1} ω^{j} + c_{2} ω^{2 j} + \dots + c_{n - 1} ω^{(n - 1) j}, j = 0, 1, \dots, n - 1 .$

Ορίζουσα

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

$\det C = \prod_{j = 0}^{n - 1} (c_{0} + c_{n - 1} ω^{j} + c_{n - 2} ω^{2 j} + \dots + c_{1} ω^{(n - 1) j}) .$

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

$\det C = \prod_{j = 0}^{n - 1} (c_{0} + c_{1} ω^{j} + c_{2} ω^{2 j} + \dots + c_{n - 1} ω^{(n - 1) j}) = \prod_{j = 0}^{n - 1} f (ω^{j}) .$

Βαθμός

Ο Βαθμός ενός κυκλοτερούς πίνακα $C$ είναι ίσο με $n - d$ όπου $d$ είναι ο βαθμός του πολυωνύμου $\gcd (f (x), x^{n} - 1)$ .^[5]

Άλλες ιδιότητες

Κάθε κυκλοτερής είναι ένα πολυώνυμο πίνακα (δηλαδή, το σχετικό πολυώνυμο) στον κυκλικό πίνακα μεταθέσεων $P$ : $C = c_{0} I + c_{1} P + c_{2} P^{2} + \dots + c_{n - 1} P^{n - 1} = f (P),$

όπου $P$ δίνεται από τον Συνοδό πίνακα

$P = [\begin{matrix} 0 & 0 & \dots & 0 & 1 \\ 1 & 0 & \dots & 0 & 0 \\ 0 & ⋱ & ⋱ & ⋮ & ⋮ \\ ⋮ & ⋱ & ⋱ & 0 & 0 \\ 0 & \dots & 0 & 1 & 0 \end{matrix}] .$

Το σύνολο των $n \times n$ κυκλοτερών πινάκων σχηματίζει ένα $n$ -διαστάσεων διανυσματικό χώρο ως προς την πρόσθεση και τον κλιμακωτό πολλαπλασιασμό. Ο χώρος αυτός μπορεί να ερμηνευτεί ως ο χώρος των συναρτήσεων στην κυκλική ομάδα τάξης $n$ , $C_{n}$ , ή ισοδύναμα ως ο δακτύλιος της ομάδας $C_{n}$ .
Οι κυκλοτερείς πίνακες σχηματίζουν μια αντιμεταθετική άλγεβρα, αφού για δύο οποιουσδήποτε δεδομένους κυκλοτερούς πίνακες $A$ και $B$ , το άθροισμα $A + B$ είναι κυκλοτερές, το γινόμενο $A B$ είναι κυκλοτερές και $A B = B A$ .
Για έναν Αντιστρέψιμο κυκλοτερή πίνακα $A$ , ο αντίστροφός του $A^{- 1}$ είναι επίσης κυκλοτερής. Για έναν Αντιστρέψιμο κυκλοτερή πίνακα, ο ψευδοαντίστροφός του Μουρ-Πένροουζ $A^{+}$ είναι κυκλοτερή. $F_{n} είναι μοναδιαίο, όπου F_{n} = [v_{0}, v_{1}, \dots, v_{n - 1}] = \frac{1}{\sqrt{n}} (f_{k j}) με f_{k j} = e^{2 π i / n \cdot k j}, για 0 \leq k, j \leq n - 1 .$
Ο πίνακας $F_{n}$ που αποτελείται από τα ιδιοδιανύσματα ενός κυκλοτερούς πίνακα σχετίζεται με τον διακριτό μετασχηματισμό Φουριέ και τον αντίστροφο μετασχηματισμό του:Συνεπώς, ο πίνακας $U_{n}$ διαγωνοποιεί τον $C$ . Στην πραγματικότητα, έχουμε $C = F_{n} diag (\sqrt{n} \cdot F_{n}^{†} c) F_{n}^{†},$ όπου $c$ είναι η πρώτη στήλη του $C$ . Οι ιδιοτιμές του $C$ δίνονται από το γινόμενο $F_{n}^{†} c$ . Αυτό το γινόμενο μπορεί εύκολα να υπολογιστεί με γρήγορο μετασχηματισμό Φουριέ.^[6] Αντίστροφα, για κάθε διαγώνιο πίνακα $D$ , το γινόμενο $F_{n} D F_{n}^{†}$ είναι κυκλοτερές.
Έστω $p (x)$ το (μονικό) χαρακτηριστικό πολυώνυμο ενός $n \times n$ κυκλοτερούς πίνακα $C$ . Τότε η κλιμακωτή παράγωγος $\frac{1}{n} p^{'} (x)$ είναι το χαρακτηριστικό πολυώνυμο του ακόλουθου $(n - 1) \times (n - 1)$ υποπίνακα του $C$ :

$C_{n - 1} = [\begin{matrix} c_{0} & c_{n - 1} & \dots & c_{3} & c_{2} \\ c_{1} & c_{0} & c_{n - 1} & c_{3} \\ ⋮ & c_{1} & c_{0} & ⋱ & ⋮ \\ c_{n - 3} & ⋱ & ⋱ & c_{n - 1} \\ c_{n - 2} & c_{n - 3} & \dots & c_{1} & c_{0} \end{matrix}]$

(Δείτε ^[7] για την απόδειξη)

Αναλυτική ερμηνεία

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

Ας θεωρήσουμε τα διανύσματα στο $ℝ^{n}$ ως συναρτήσεις στους ακέραιους αριθμούς με περίοδο $n$ , (δηλαδή, ως περιοδικές δι-άπειρες ακολουθίες: $\dots, a_{0}, a_{1}, \dots, a_{n - 1}, a_{0}, a_{1}, \dots$ ) ή ισοδύναμα, ως συναρτήσεις στην κυκλική ομάδα τάξης $n$ (συμβολίζεται $C_{n}$ ή $ℤ / n ℤ$ ) γεωμετρικά, πάνω (στις κορυφές) του [[κανονικό πολύγωνο|κανονικού Πρότυπο:Nowrap]]: αυτό είναι ένα διακριτό ανάλογο των περιοδικών συναρτήσεων στην πραγματική γραμμή ή στον κύκλο.

Τότε, από την άποψη της θεωρίας τελεστών, ένας κυκλοτερής πίνακας είναι ο πυρήνας ενός διακριτού ολοκληρωτικού μετασχηματισμού, δηλαδή ο τελεστής συνέλιξης για τη συνάρτηση $(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^{*}$ -άλγεβρα της $ℤ / n ℤ .$

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

Για έναν συμμετρικό κυκλοτερή πίνακα $C$ έχουμε την επιπλέον συνθήκη ότι $c_{n - i} = c_{i}$ . Έτσι καθορίζεται από $⌊ n / 2 ⌋ + 1$ στοιχεία.

$C = [\begin{matrix} c_{0} & c_{1} & \dots & c_{2} & c_{1} \\ c_{1} & c_{0} & c_{1} & c_{2} \\ ⋮ & c_{1} & c_{0} & ⋱ & ⋮ \\ c_{2} & ⋱ & ⋱ & c_{1} \\ c_{1} & c_{2} & \dots & c_{1} & c_{0} \end{matrix}] .$

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

$\begin{matrix} λ_{k} & = & c_{0} + c_{n / 2} e^{- π i \cdot k} + 2 \sum_{j = 1}^{\frac{n}{2} - 1} c_{j} \cos (- \frac{2 π}{n} \cdot k j) \\ = & c_{0} + c_{n / 2} ω_{k}^{n / 2} + 2 c_{1} ℜ ω_{k} + 2 c_{2} ℜ ω_{k}^{2} + \dots + 2 c_{n / 2 - 1} ℜ ω_{k}^{n / 2 - 1} \end{matrix}$

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

$\begin{matrix} λ_{k} & = & c_{0} + 2 \sum_{j = 1}^{\frac{n - 1}{2}} c_{j} \cos (- \frac{2 π}{n} \cdot k j) \\ = & c_{0} + 2 c_{1} ℜ ω_{k} + 2 c_{2} ℜ ω_{k}^{2} + \dots + 2 c_{(n - 1) / 2} ℜ ω_{k}^{(n - 1) / 2} \end{matrix}$

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

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

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

Η μιγαδική εκδοχή του κυκλικού πίνακα, πανταχού παρούσα στη θεωρία επικοινωνιών, είναι συνήθως Ερμιτιανή. Στην περίπτωση αυτή $c_{n - i} = c_{i}^{*}, i \leq n / 2$ και η ορίζουσα και όλες οι ιδιοτιμές του είναι πραγματικές.

Εάν το n είναι άρτιο, οι δύο πρώτες σειρές παίρνουν αναγκαστικά τη μορφή

$[\begin{matrix} 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{matrix}] .$

στην οποία το πρώτο στοιχείο $r_{3}$ στην πάνω δεύτερη ημισειρά είναι πραγματικό.

Αν το n είναι περιττό έχουμε

$[\begin{matrix} r_{0} & z_{1} & z_{2} & z_{2}^{*} & z_{1}^{*} \\ z_{1}^{*} & r_{0} & z_{1} & z_{2} & z_{2}^{*} \\ \dots \end{matrix}] .$

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

Εφαρμογές

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

Δεδομένης μιας εξίσωσης πίνακα

C 𝐱 = 𝐛,

όπου $C$ είναι ένας κυκλικός πίνακας μεγέθους $n$ , μπορούμε να γράψουμε την εξίσωση ως κυκλική συνέλιξη

$𝐜 ⋆ 𝐱 = 𝐛,$

όπου $𝐜$ είναι η πρώτη στήλη του $C$ , και τα διανύσματα $𝐜$ , $𝐱$ και $𝐛$ επεκτείνονται κυκλικά προς κάθε κατεύθυνση. Χρησιμοποιώντας το θεώρημα της κυκλικής συνέλιξης, μπορούμε να χρησιμοποιήσουμε τον διακριτό μετασχηματισμό Φουριέ για να μετατρέψουμε την κυκλική συνέλιξη σε πολλαπλασιασμό κατά συνιστώσες

$ℱ_{n} (𝐜 ⋆ 𝐱) = ℱ_{n} (𝐜) ℱ_{n} (𝐱) = ℱ_{n} (𝐛)$

έτσι ώστε

$𝐱 = ℱ_{n}^{- 1} {[{(\frac{(ℱ_{n} (𝐛))_{ν}}{(ℱ_{n} (𝐜))_{ν}})}_{ν \in ℤ}]}^{T} .$

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

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

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

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

Δείτε επίσης

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

Παραπομπές

Πρότυπο:Authority control Πρότυπο:Portal bar

[1] Πρότυπο:Cite book

[2] Πρότυπο:Cite web

[3] Πρότυπο:Cite web

[4] Πρότυπο:Cite web

[5] Πρότυπο:Cite journal

[6] Πρότυπο:Citation

[7] Πρότυπο:Citation

[8] Πρότυπο:Cite journal

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

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

Περιεχόμενα

Ορισμός

Ιδιότητες

Ιδιοδιανύσματα και ιδιοτιμές

Ορίζουσα

Βαθμός

Άλλες ιδιότητες

Αναλυτική ερμηνεία

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

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

Εφαρμογές

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

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

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

Δείτε επίσης

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

Παραπομπές

Μενού πλοήγησης

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

Ορισμός

Ιδιότητες

Ιδιοδιανύσματα και ιδιοτιμές

Ορίζουσα

Βαθμός

Άλλες ιδιότητες

Αναλυτική ερμηνεία

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

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

Εφαρμογές

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

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

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

Δείτε επίσης

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

Παραπομπές

Μενού πλοήγησης

Αναζήτηση