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

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

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

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

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

:\begin{matrix} 
\pi\colon\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}
& \longleftrightarrow &
R_\pi\colon\begin{pmatrix}
0&0&1&0\\
0&1&0&0\\
0&0&0&1\\
1&0&0&0\end{pmatrix}\\[5pt]
\Big\updownarrow && \Big\updownarrow\\[5pt]
C_\pi\colon\begin{pmatrix}
0&0&0&1\\
0&1&0&0\\
1&0&0&0\\
0&0&1&0\end{pmatrix}
& \longleftrightarrow &
\pi^{-1}\colon\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}\end{matrix}

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

Η αντιστοιχία με βάση τις στήλες οδηγεί  στον πίνακα 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^\mathsf{T}=R_\pi^{-1}. Ανιχνεύοντας τις άλλες δύο πλευρές του μεγάλου τετραγώνου, έχουμε R_{\pi^{-1}}=C_\pi=R_\pi^{-1} και C_{\pi^{-1}}=R_\pi.

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

Ο πολλαπλασιασμός ενός πίνακα *M* είτε με R_\pi είτε με C_\pi είτε στα αριστερά είτε στα δεξιά θα μεταβάλει είτε τις γραμμές είτε τις στήλες του *M* κατά  ή −1. Οι λεπτομέρειες είναι λίγο περίπλοκες.

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

: \big(v_{\pi^{-1}(1)},v_{\pi^{-1}(2)},\ldots,v_{\pi^{-1}(n)}\big),

παρόλο που κάνουμε αντιμετάθεση κατά \pi και όχι κατά \pi^{-1}. Έτσι, για να αντιμεταθέσουμε τις εγγραφές κατά \pi, πρέπει να αντιμεταθέσουμε τους δείκτες κατά \pi^{-1}. (Η αντιμετάθεση των καταχωρήσεων κατά \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, και πολλαπλασιάζουν τις γραμμές ή τις στήλες αντίστοιχα με -1, αντί με .

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

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

:\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. Το γινόμενο PP^\mathsf{T} είναι επομένως ο Ταυτοτικός πίνακας. Ένα συμμετρικό επιχείρημα δείχνει το ίδιο για τον P^\mathsf{T}P, που σημαίνει ότι ο *P* είναι αντιστρέψιμος με P^{-1}=P^\mathsf{T}.

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

C_{\sigma} C_{\tau} = C_{\sigma\,\circ\,\tau}, 

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

(\sigma\circ\tau) (k) = \sigma \left(\tau (k) \right).

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

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

:R_{\sigma} R_{\tau} = R_{\tau\,\circ\,\sigma}, 

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

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

:(\sigma\,;\,\tau)(k) = \tau\left(\sigma(k)\right),
ή, πιο εύστοχα, με
:(k)(\sigma\,;\,\tau) = \left((k)\sigma \right)\tau,
με το *σ* να εφαρμόζεται πρώτα. Αυτός ο συμβολισμός μας δίνει έναν απλούστερο κανόνα για τον πολλαπλασιασμό πινάκων μετατροπής με βάση τις γραμμές:
:R_{\sigma} R_{\tau} = R_{\sigma\,;\,\tau}. 

## Ομάδα πίνακα

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

Υπάρχουν  πίνακες μεταθέσεων, αφού υπάρχουν  μεταθέσεις και ο χάρτης C\colon\pi\mapsto C_\pi είναι μια αντιστοιχία ένα προς ένα μεταξύ μεταθέσεων και πινάκων μεταθέσεων. (Ο χάρτης R είναι μια άλλη τέτοια αντιστοιχία.) Σύμφωνα με τους παραπάνω τύπους, αυτοί οι  πίνακες μεταθέσεων σχηματίζουν μια ομάδα τάξης  υπό πολλαπλασιασμό πινάκων, με τον πίνακα ταυτότητας ως στοιχείο ταυτότητας, μια ομάδα που συμβολίζουμε \mathcal{P}_n. Η ομάδα \mathcal{P}_n είναι μια υποομάδα της γενικής γραμμικής ομάδας GL_n(\mathbb{R}) των αντιστρέψιμων  πινάκων πραγματικών αριθμών. Πράγματι, για οποιοδήποτε σώμα *F*, η ομάδα \mathcal{P}_n είναι επίσης μια υποομάδα της ομάδας GL_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,.... ,} όπου η πράξη της ομάδας είναι η τυπική, από δεξιά προς τα αριστερά σύνθεση «\circ»- και ας συμβολίσουμε με S_n^\rightarrow την αντίθετη ομάδα, η οποία χρησιμοποιεί τη σύνθεση από αριστερά προς τα δεξιά «\,;\,». Ο χάρτης C\colon S_n^\leftarrow\to GL_n(\mathbb{R}) που παίρνει *π* στον πίνακα με βάση τις στήλες του C_\pi είναι μια πιστή αναπαράσταση, και ομοίως για το χάρτη R\colon S_n^\rightarrow\to GL_n(\mathbb{R}) που παίρνει *π* στο R_\pi.

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

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

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

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

:\begin{matrix} 
\rho_P\colon\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}
& \longleftrightarrow &
P\colon\begin{pmatrix}
0&0&1&0\\
0&1&0&0\\
0&0&0&1\\
1&0&0&0\end{pmatrix}\\[5pt]
\Big\updownarrow && \Big\updownarrow\\[5pt]
P^{-1}\colon\begin{pmatrix}
0&0&0&1\\
0&1&0&0\\
1&0&0&0\\
0&0&1&0\end{pmatrix}
& \longleftrightarrow &
\kappa_P\colon\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}\end{matrix}

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

Ένα σημείο είναι σταθερό από το \kappa_P ακριβώς όταν είναι σταθερό από το \rho_P, και το ίχνος του *P* είναι ο αριθμός των κοινών σταθερών σημείων. Εάν ο ακέραιος *k* είναι ένας από αυτούς, τότε το τυπικό διάνυσμα βάσης  είναι ένα ιδιοδιάνυσμα του *P*.

Για να υπολογίσουμε τις μιγαδικές ιδιοτιμές του *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*. (Εφόσον κάθε πίνακας μεταθέσεων είναι κανονικός και κάθε κανονικός πίνακας είναι διαγωνοποιήσιμος πάνω στους μιγαδικούς αριθμούς, η αλγεβρική και η γεωμετρική πολλαπλότητα μιας ιδιοτιμής v είναι η ίδια).

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

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

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

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

* 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

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


* 
* 

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