Πίνακας μεταθέσεων

Στα μαθηματικά, ιδιαίτερα στη θεωρία πινάκων, ένας πίνακας μεταθέσεων είναι ένας τετραγωνικός δυαδικός πίνακας που έχει ακριβώς μία εγγραφή 1 σε κάθε γραμμή και σε κάθε στήλη με όλες τις άλλες εγγραφές 0.Πρότυπο:Rp Ένας πίνακας μεταθέσεων Πρότυπο:Math μπορεί να αναπαραστήσει μια μετάθεση Πρότυπο:Mvar στοιχείων. Ο προπολλαπλασιασμός ενός πίνακα Πρότυπο:Mvar-γραμμών Πρότυπο:Mvar με έναν πίνακα μεταθέσεων Πρότυπο:Mvar, σχηματίζοντας τον Πρότυπο:Mvar, έχει ως αποτέλεσμα τη μεταστοιχείωση των γραμμών του Πρότυπο:Mvar, ενώ ο μεταπολλαπλασιασμός ενός πίνακα Πρότυπο:Mvar-στηλών Πρότυπο:Mvar, σχηματίζοντας τον Πρότυπο:Mvar, μεταστοιχειώνει τις στήλες του Πρότυπο:Mvar.

Κάθε πίνακας μεταθέσεων P είναι ορθογώνιος, με τον αντίστροφό του να ισούται με τον αντιμεταθέτη του:$P^{-1}=P^{𝖳}$.Πρότυπο:Rp Πράγματι, οι πίνακες μεταθέσεων μπορούν να χαρακτηριστούν ως οι ορθογώνιοι πίνακες των οποίων οι καταχωρήσεις είναι όλες μη αρνητικές.

Οι δύο αντιστοιχίες μεταθέσεων/πίνακα

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

$\begin{array}{ccc}\pi :\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 2& 4& 1\end{array}\right)& ⟷& R_{\pi }:\left(\begin{array}{cccc}0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right)\\ \updownarrow & & \updownarrow \\ C_{\pi }:\left(\begin{array}{cccc}0& 0& 0& 1\\ 0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 1& 0\end{array}\right)& ⟷& {\pi }^{-1}:\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 2& 1& 3\end{array}\right)\end{array}$

Η αντιστοιχία με βάση τη γραμμή παίρνει την αντιμετάθεση Πρότυπο:Pi στον πίνακα $R_{\pi }$ στην πάνω δεξιά πλευρά. Η πρώτη γραμμή του $R_{\pi }$ έχει το 1 στην τρίτη στήλη επειδή $\pi (1)=3$. Γενικότερα, έχουμε $R_{\pi }=(r_{ij})$ όπου $r_{ij}=1$ όταν $j=\pi (i)$ και $r_{ij}=0$ διαφορετικά.

Η αντιστοιχία με βάση τις στήλες οδηγεί Πρότυπο:Pi στον πίνακα $C_{\pi }$ κάτω αριστερά. Η πρώτη στήλη του $C_{\pi }$ έχει το 1 στην τρίτη γραμμή επειδή $\pi (1)=3$. Γενικότερα, έχουμε $C_{\pi }=(c_{ij})$ όπου $c_{ij}$ είναι 1 όταν $i=\pi (j)$ και 0 αλλιώς. Δεδομένου ότι οι δύο συνταγές διαφέρουν μόνο με την αντικατάσταση του i με το j, ο πίνακας $C_{\pi }$ είναι η μεταφορά του $R_{\pi }$ και, δεδομένου ότι ο $R_{\pi }$ είναι ένας πίνακας μετατροπής, έχουμε $C_{\pi }=R_{\pi }^{𝖳}=R_{\pi }^{-1}$. Ανιχνεύοντας τις άλλες δύο πλευρές του μεγάλου τετραγώνου, έχουμε $R_{{\pi }^{-1}}=C_{\pi }=R_{\pi }^{-1}$ και $C_{{\pi }^{-1}}=R_{\pi }$.

Οι πίνακες μεταβολής μεταθέτουν γραμμές ή στήλες

Ο πολλαπλασιασμός ενός πίνακα M είτε με $R_{\pi }$ είτε με $C_{\pi }$ είτε στα αριστερά είτε στα δεξιά θα μεταβάλει είτε τις γραμμές είτε τις στήλες του M κατά Πρότυπο:Pi ή Πρότυπο:Pi⁻¹. Οι λεπτομέρειες είναι λίγο περίπλοκες.

Αρχικά, όταν μεταβάλλουμε τις καταχωρήσεις ενός διανύσματος $(v_1,\dots ,v_n)$ με κάποια αντιμετάθεση Πρότυπο:Pi, μετακινούμε την $i^{\text{th}}$ καταχώρηση $v_i$ του διανύσματος εισόδου στη θέση $\pi (i{)}^{\text{th}}$ του διανύσματος εξόδου. Ποια είσοδος καταλήγει τότε, ας πούμε, στην πρώτη σχισμή της εξόδου; Απάντηση: Η είσοδος που εμφανίζεται στην είσοδο του πίνακα, η οποία είναι η τελευταία που θα εισέλθει στο σύστημα: Η είσοδος $v_j$ για την οποία ισχύει $\pi (j)=1$, και συνεπώς $j={\pi }^{-1}(1)$. Επιχειρηματολογώντας με παρόμοιο τρόπο για κάθε μία από τις υποδοχές, βρίσκουμε ότι το διάνυσμα εξόδου είναι

$(v_{{\pi }^{-1}(1)},v_{{\pi }^{-1}(2)},\dots ,v_{{\pi }^{-1}(n)}),$

παρόλο που κάνουμε αντιμετάθεση κατά $\pi$ και όχι κατά ${\pi }^{-1}$. Έτσι, για να αντιμεταθέσουμε τις εγγραφές κατά $\pi$, πρέπει να αντιμεταθέσουμε τους δείκτες κατά ${\pi }^{-1}$.Πρότυπο:Rp (Η αντιμετάθεση των καταχωρήσεων κατά $\pi$ ονομάζεται μερικές φορές λήψη της άποψης του άλλοθι, ενώ η αντιμετάθεση των δεικτών κατά $\pi$ θα έπαιρνε την alias άποψη.)

Τώρα, ας υποθέσουμε ότι προ-πολλαπλασιάζουμε κάποιον πίνακα n σειρών $M=(m_{i,j})$ με τον πίνακα μεταθέσεων $C_{\pi }$. Σύμφωνα με τον κανόνα για τον πολλαπλασιασμό πινάκων, η καταχώρηση $(i,j{)}^{\text{th}}$ στο γινόμενο $C_{\pi }M$ είναι

$\sum _{k=1}^n{c}_{i,k}{m}_{k,j},$

Οι άλλες δύο επιλογές είναι ο προ-πολλαπλασιασμός με $R_{\pi }$ ή ο μετα-πολλαπλασιασμός με $C_{\pi }$, και πολλαπλασιάζουν τις γραμμές ή τις στήλες αντίστοιχα με Πρότυπο:Pi^-1, αντί με Πρότυπο:Pi.

όπου $c_{i,k}$ είναι 0 εκτός από την περίπτωση που $i=\pi (k)$, οπότε είναι 1. Έτσι, ο μόνος όρος στο άθροισμα που επιβιώνει είναι ο όρος στον οποίο $k={\pi }^{-1}(i)$, και το άθροισμα ανάγεται σε $m_{{\pi }^{-1}(i),j}$. Εφόσον έχουμε μεταθέσει τον δείκτη των γραμμών κατά ${\pi }^{-1}$, έχουμε μεταθέσει τις ίδιες τις γραμμές του M κατά Πρότυπο:Pi.Πρότυπο:Rp} Ένα παρόμοιο επιχείρημα δείχνει ότι ο μεταπολλαπλασιασμός ενός n πίνακα M με $R_{\pi }$ μετατρέπει τις στήλες του κατά Πρότυπο:Pi.

Η μετάθεση είναι επίσης το αντίστροφο

Ένα σχετικό επιχείρημα αποδεικνύει ότι, όπως ισχυριστήκαμε παραπάνω, η μεταφορά οποιουδήποτε πίνακα μεταθέσεων P ενεργεί επίσης ως το αντίστροφό του, το οποίο συνεπάγεται ότι ο P είναι αντιστρέψιμος. (Ο Αρτίν αφήνει αυτή την απόδειξη ως άσκηση,Πρότυπο:Rp την οποία εδώ επιλύουμε). Αν $P=(p_{i,j})$, τότε η $(i,j{)}^{\text{th}}$ είσοδος της αντιμετάθεσής του $P^{𝖳}$ είναι $p_{j,i}$. Η $(i,j{)}^{\text{th}}$ είσοδος του γινομένου $P{P}^{𝖳}$ είναι τότε

$\sum _{k=1}^n{p}_{i,k}{p}_{j,k}.$

Όποτε $i\ne j$, ο όρος $k^{\text{th}}$ σε αυτό το άθροισμα είναι το γινόμενο δύο διαφορετικών καταχωρήσεων στη στήλη $k^{\text{th}}$ του P, οπότε όλοι οι όροι είναι 0 και το άθροισμα είναι 0. Όταν $i=j$, αθροίζουμε τα τετράγωνα των καταχωρήσεων στη $i^{\text{th}}$ γραμμή του P, οπότε το άθροισμα είναι 1. Το γινόμενο $P{P}^{𝖳}$ είναι επομένως ο Ταυτοτικός πίνακας. Ένα συμμετρικό επιχείρημα δείχνει το ίδιο για τον $P^{𝖳}P$, που σημαίνει ότι ο P είναι αντιστρέψιμος με $P^{-1}=P^{𝖳}$.

Πολλαπλασιασμός πινάκων μεταθέσεων

Δεδομένων δύο μεταθέσεων των Πρότυπο:Math στοιχείων σ και τ, το γινόμενο των αντίστοιχων πινάκων μεταθέσεων με βάση τις στήλες Πρότυπο:Math και Πρότυπο:Math δίνεται,Πρότυπο:Rp όπως είναι αναμενόμενο, από τη σχέση

$C_{\sigma }{C}_{\tau }=C_{\sigma \circ \tau },$

όπου η σύνθετη μετάθεση $\sigma \circ \tau$ εφαρμόζει πρώτα τ και στη συνέχεια σ, δουλεύοντας από τα δεξιά προς τα αριστερά:

$(\sigma \circ \tau )(k)=\sigma (\tau (k)).$

Αυτό προκύπτει επειδή ο προπολλαπλασιασμός κάποιου πίνακα με τον Πρότυπο:Math και στη συνέχεια ο προπολλαπλασιασμός του προκύπτοντος γινομένου με τον Πρότυπο:Math δίνει το ίδιο αποτέλεσμα με τον προπολλαπλασιασμό μόνο μία φορά με το συνδυασμένο $C_{\sigma \circ \tau }$.

Για τους πίνακες με βάση τις γραμμές, υπάρχει μια ανατροπή: Το γινόμενο των Πρότυπο:Math και Πρότυπο:Math δίνεται από τη σχέση

$R_{\sigma }{R}_{\tau }=R_{\tau \circ \sigma },$

με το 𝜎 να εφαρμόζεται πριν από το 𝜏 στη στη σύνθετη μετάθεση. Αυτό συμβαίνει επειδή πρέπει να κάνουμε μεταπολλαπλασιασμό για να αποφύγουμε αντιστροφές σύμφωνα με την επιλογή με βάση τη σειρά, οπότε θα κάναμε μεταπολλαπλασιασμό πρώτα με το Πρότυπο:Math και μετά με το Πρότυπο:Math.

Μερικοί άνθρωποι, όταν εφαρμόζουν μια συνάρτηση σε ένα όρισμα, γράφουν τη συνάρτηση μετά το όρισμα (Αντίστροφη πολωνική σημειογραφία), αντί για πριν από αυτό. Όταν κάνουν γραμμική άλγεβρα, εργάζονται με γραμμικούς χώρους διανυσμάτων γραμμής και εφαρμόζουν έναν γραμμικό χάρτη σε ένα όρισμα χρησιμοποιώντας τον πίνακα του χάρτη για να πολλαπλασιάσουν μετά το διάνυσμα γραμμής του επιχειρήματος. Συχνά χρησιμοποιούν έναν τελεστή σύνθεσης από αριστερά προς τα δεξιά, τον οποίο εδώ συμβολίζουμε χρησιμοποιώντας μια άνω τελεία- έτσι η σύνθεση $\sigma ;\tau$ ορίζεται είτε ως εξής

$(\sigma ;\tau )(k)=\tau (\sigma (k)),$

ή, πιο εύστοχα, με

$(k)(\sigma ;\tau )=((k)\sigma )\tau ,$

με το σ να εφαρμόζεται πρώτα. Αυτός ο συμβολισμός μας δίνει έναν απλούστερο κανόνα για τον πολλαπλασιασμό πινάκων μετατροπής με βάση τις γραμμές:

$R_{\sigma }{R}_{\tau }=R_{\sigma ;\tau }.$

Ομάδα πίνακα

Όταν το π είναι η μετάθεση ταυτότητας, η οποία έχει $\pi (i)=i$ για όλα τα i, τόσο ο Πρότυπο:Math όσο και ο Πρότυπο:Mathείναι ο Ταυτοτικός πίνακας.

Υπάρχουν Πρότυπο:Math πίνακες μεταθέσεων, αφού υπάρχουν Πρότυπο:Math μεταθέσεις και ο χάρτης $C:\pi \mapsto C_{\pi }$ είναι μια αντιστοιχία ένα προς ένα μεταξύ μεταθέσεων και πινάκων μεταθέσεων. (Ο χάρτης $R$ είναι μια άλλη τέτοια αντιστοιχία.) Σύμφωνα με τους παραπάνω τύπους, αυτοί οι Πρότυπο:Math πίνακες μεταθέσεων σχηματίζουν μια ομάδα τάξης Πρότυπο:Math υπό πολλαπλασιασμό πινάκων, με τον πίνακα ταυτότητας ως στοιχείο ταυτότητας, μια ομάδα που συμβολίζουμε ${𝒫}_n$. Η ομάδα ${𝒫}_n$ είναι μια υποομάδα της γενικής γραμμικής ομάδας $G{L}_n(ℝ)$ των αντιστρέψιμων Πρότυπο:Math πινάκων πραγματικών αριθμών. Πράγματι, για οποιοδήποτε σώμα F, η ομάδα ${𝒫}_n$ είναι επίσης μια υποομάδα της ομάδας $G{L}_n(F)$, όπου οι καταχωρήσεις του πίνακα ανήκουν στο F. (Κάθε σώμα περιέχει 0 και 1 με $0+0=0,$ $0+1=1,$ $0*0=0,$ $0*1=0,$ και $1*1=1;$ και αυτό είναι το μόνο που χρειαζόμαστε για να πολλαπλασιάσουμε τους πίνακες μετάθεσης. Διαφορετικά πεδία διαφωνούν για το αν $1+1=0$, αλλά αυτό το άθροισμα δεν προκύπτει).

Έστω $S_n^{\leftarrow }$ η συμμετρική ομάδα, ή ομάδα μεταθέσεων, στο {1,2,.... ,Πρότυπο:Math} όπου η πράξη της ομάδας είναι η τυπική, από δεξιά προς τα αριστερά σύνθεση «$\circ$»- και ας συμβολίσουμε με $S_n^{\to }$ την αντίθετη ομάδα, η οποία χρησιμοποιεί τη σύνθεση από αριστερά προς τα δεξιά «$;$». Ο χάρτης $C:S_n^{\leftarrow }\to G{L}_n(ℝ)$ που παίρνει π στον πίνακα με βάση τις στήλες του $C_{\pi }$ είναι μια πιστή αναπαράσταση, και ομοίως για το χάρτη $R:S_n^{\to }\to G{L}_n(ℝ)$ που παίρνει π στο $R_{\pi }$.

Διπλά στοχαστικοί πίνακες

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

Γραμμικές-αλγεβρικές ιδιότητες

Ακριβώς όπως κάθε μετάθεση σχετίζεται με δύο πίνακες μεταθέσεων, κάθε πίνακας μεταθέσεων σχετίζεται με δύο μεταθέσεις, όπως μπορούμε να δούμε επανασημασιοδοτώντας το παράδειγμα στο μεγάλο τετράγωνο παραπάνω ξεκινώντας με τον πίνακα P πάνω δεξιά:

$\begin{array}{ccc}{\rho }_P:\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 2& 4& 1\end{array}\right)& ⟷& P:\left(\begin{array}{cccc}0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right)\\ \updownarrow & & \updownarrow \\ P^{-1}:\left(\begin{array}{cccc}0& 0& 0& 1\\ 0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 1& 0\end{array}\right)& ⟷& {\kappa }_P:\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 2& 1& 3\end{array}\right)\end{array}$

Έτσι, εδώ συμβολίζουμε το αντίστροφο του C ως $\kappa$ και το αντίστροφο του R ως $\rho$. Μπορούμε στη συνέχεια να υπολογίσουμε τις γραμμικές-αλγεβρικές ιδιότητες του P από κάποιες συνδυαστικές ιδιότητες που μοιράζονται οι δύο μεταθέσεις ${\kappa }_P$ και ${\rho }_P={\kappa }_P^{-1}$.

Ένα σημείο είναι σταθερό από το ${\kappa }_P$ ακριβώς όταν είναι σταθερό από το ${\rho }_P$, και το ίχνος του P είναι ο αριθμός των κοινών σταθερών σημείων.Πρότυπο:Rp Εάν ο ακέραιος k είναι ένας από αυτούς, τότε το τυπικό διάνυσμα βάσης Πρότυπο:Math είναι ένα ιδιοδιάνυσμα του P.Πρότυπο:Rp

Για να υπολογίσουμε τις μιγαδικές ιδιοτιμές του P, γράφουμε την μετάθεση ${\kappa }_P$ ως μια σύνθεση διαχωρισμένων κύκλων, ας πούμε ${\kappa }_P=c_1{c}_2\cdots c_t$. (Οι μεταθέσεις ασύζευκτων υποσυνόλων αντιμετατίθενται, οπότε δεν έχει σημασία εδώ αν συνθέτουμε από δεξιά προς τα αριστερά ή από αριστερά προς τα δεξιά). Για $1\le i\le t$, έστω ότι το μήκος του κύκλου $c_i$ είναι ${\ell }_i$, και έστω $L_i$ το σύνολο των μιγαδικών λύσεων του $x^{{\ell }_i}=1$, οι οποίες λύσεις είναι οι ${\ell }_i^{\text{th}}$ ρίζες μονάδας. Η ένωση των πολλαπλών συνόλων των $L_i$ είναι τότε το πολλαπλό σύνολο των ιδιοτιμών του P. Εφόσον γράφοντας το ${\rho }_P$ ως γινόμενο κύκλων θα έδινε τον ίδιο αριθμό κύκλων ίδιου μήκους, η ανάλυση του ${\rho }_p$ θα έδινε το ίδιο αποτέλεσμα. Η πολλαπλότητα κάθε ιδιοτιμής v είναι ο αριθμός των i για τα οποία ο $L_i$ περιέχει την v. (Εφόσον κάθε πίνακας μεταθέσεων είναι κανονικός και κάθε κανονικός πίνακας είναι διαγωνοποιήσιμος πάνω στους μιγαδικούς αριθμούς,Πρότυπο:Rp η αλγεβρική και η γεωμετρική πολλαπλότητα μιας ιδιοτιμής v είναι η ίδια).

Από τη θεωρία των ομάδων γνωρίζουμε ότι κάθε μετάθεση μπορεί να γραφτεί ως σύνθεση μεταφοράς. Επομένως, οποιοσδήποτε πίνακας μετατροπής παραγοντοποιείται ως γινόμενο στοιχειωδών πινάκων με μεταθέσεις στη σειρά, καθένας από τους οποίους έχει ορίζουσα −1. Έτσι, η ορίζουσα του πίνακα μεταθέσεων P είναι το πρόσημο της μετάθεσης ${\kappa }_P$, που είναι επίσης το πρόσημο του ${\rho }_P$.

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

• Πρότυπο:Cite journal
• Πρότυπο:Cite book
• Πρότυπο:Cite journal
• Πρότυπο:Citation
• Πρότυπο:Citation
• Diodorus Siculus, Bibliotheca Historica. Vol. 1–2. Immanel Bekker. Ludwig Dindorf. Friedrich Vogel. in aedibus B. G. Teubneri. Leipzig. 1888–1890. Greek text available at the Perseus Digital Library.
• Πρότυπο:Citation
• Πρότυπο:Citation
• Πρότυπο:Cite journal

Δείτε επίσης

• 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
• Fourier Transforms: Approach to Scientific Principles
• Euclidean Distance Matrices and Their Applications in Rigidity Theory.
• Physics and Combinatorics 2000: Proceedings of the Nagoya 2000 International ...
• Matrix Calculus and Kronecker Product: A Practical Approach to Linear and ...
• Matrix Riccati Equations in Control and Systems Theory ...
• Matrix Algebra: Theory, Computations, and Applications in Statistics.
• Lectures on the Combinatorics of Free Probability, Τόμος 13

Παραπομπές

• Πρότυπο:Cite book
• Πρότυπο:Citation