Definizione di matrici di permutazione e permutazioni associate

Messaggioda marco2132k » 10/03/2019, 20:26

Ciao. Mi devo vedere qualcosa sulle permutazioni, e ho voluto andare incontro a questa cosa che ora segue.

Una matrice di permutazione, a quanto pare, è "una matrice \( P \) per cui la moltiplicazione a sinistra è una permutazione delle righe di una matrice \( X \)".

Sia \( X \) ad esempio la matrice \( \begin{pmatrix}x_1&x_2& x_3\end{pmatrix}^\intercal \); una matrice di permutazione dovrebbe essere una matrice \( P \) di dimensioni \( 3\times 3 \) tale che \( PX \) sia la matrice \( \begin{pmatrix}x_2&x_3& x_1\end{pmatrix}^\intercal \): abbiamo che l'elemento \( x_1 \) è mandato nell'elemento \( (PX)_3 \), l'elemento \( x_2 \) in \( (PX)_1 \) e \( x_3 \) in \( (PX)_2 \).
Allora è la permutazione
\[
p\colon 1\mapsto 3\mapsto 2\mapsto 1
\] e si può scrivere \( x_i=(PX)_{p(i)} \), oppure \( (PX)_i=x_{p^{-1}(i)} \).

Domanda 0.
Vorrei chiarirmi il fatto che ogni volta che una matrice di permutazione agisce, mentre l'elemento \( i \)-esimo è mandato nella posizione \( p(i) \)-esima, gli indici sono permutati con l'inversa della permutazione associata. Perché succede questo? :-D

Domanda 1 (secondaria).
Testo nascosto, fai click qui per vederlo
Wikipedia mi dice che una matrice di permutazione è una matrice quadrata che ha per ogni colonna e per ogni riga un'unica entrata accesa, uguale \( 1 \). Voglio provare l'uguaglianza delle due definizioni.

Ogni matrice \( P \) "di Wikipedia" ha una permutazione associata. Data \( P \), possiamo definire una permutazione \( p \) (tenendo a mente il caso \( X=\begin{pmatrix}x_1 & \dots & x_n\end{pmatrix}^\intercal\) per semplificare) come quella funzione che manda \( i \) in \( j \) tale che \( x_i=(PX)_j \). Allora dovrei provare semplicemente che, se \( P \) è costruita come da ipotesi, per ogni \( (PX)_j \) esiste un unico \( x_i \) tale che \( (PX)_j=x_j \): non so farlo. O meglio, intuisco che si debba un attimo giocare con la moltiplicazione tra matrici, magari per induzione. Non vorrei perderci del tempo, magari accetto qualche suggerimento, tanto che la cosa è così "si vede".

Ogni matrice \( P \) per a cui sia possibile associare una permutazione nel modo indicato in apertura è della forma espressa prima (binaria, un unico \( 1 \) per ogni riga e colonna). Evito. \( \square \)

Domanda 2.
Data una permutazione \( p\colon\{1,\dots, n\}\to\{1,\dots, n\} \), voglio provare che ad essa è associata una matrice di permutazione. (Che ad ogni matrice di permutazione sia associata una permutazione è assodato dalla roba in spoiler ormai, sia per definizione o per via della "dimostrazione" precedente).

Data una permutazione "di indici" \( p \), dovrebbe essere possibile ristabilire la matrice \( P \) tale che \( PX \) abbia (penso sempre a \( X=\begin{pmatrix}x_1&\dots&x_n\end{pmatrix}^\intercal \) per semplicità, ma la cosa non cambia con una matrice \( n\times p \)) per oggetto \( i \)-esimo il numero \( (X)_{p^{-1}(i)} \) (oppure tale che sia \( x_i=(PX)_{p(i)} \), come detto prima). Qui la mia idea è di provare che esiste un insieme di matrici elementari \( e_{ij} \) tali che la loro somma sia proprio una matrice \( P \) cercata, domani la sviluppo, se riesco.

Intanto sono riuscito a formulare meglio il problema, domani se ho qualcosa in mente edito di nuovo.
marco2132k
Advanced Member
Advanced Member
 
Messaggio: 219 di 2053
Iscritto il: 18/02/2018, 23:52

Re: Definizione di matrici di permutazione e permutazioni associate

Messaggioda Bokonon » 11/03/2019, 09:07

Moltiplicare un qualsiasi vettore riga per una matrice significa significa creare un nuovo vettore riga che è la combinazione lineare delle righe della matrice....esattamente come moltiplicare una matrice per un qualsiasi vettore colonna significa creare un nuovo vettore colonna che è la combinazione lineare delle colonne della matrice.
Questo segue dalla definizione di prodotto matriciale che a sua volta segue dalla definizione di prodotto scalare fra vettori.
Non c'è nulla da dimostrare.

Quindi se si vuole permutare le righe (o estrarne una a piacere) basta usare zeri e un 1 e indicizzare solo le righe.
$( ( 0 , 1 , 0 ),( 0 , 0 , 1 ),( 1 , 0 , 0 ) )( ( x_1 ),( x_2 ),( x_3 ) ) = ( ( 0*x_1+1*x_2+0*x_3 ),( 0*x_1+0*x_2+1*x_3 ),( 1*x_1+0*x_2+0x_3 ) ) =( ( x_2 ),( x_3 ),( x_1 ) ) $

Dove $x_i$ i=1,2,3 è una riga composta da n elementi.

Quali caratteristiche dovrà avere una matrice di permutazione? Definiamola.
Dovrà avere solo zeri e un 1 in ogni colonna/riga.
Dovrà essere quadrata e invertibile, altrimenti si perdono/aggiungono/duplicano delle righe.

Da cui segue che:
a) il determinante sarà sempre 1
b) il numero di permutazioni possibile è n! (disposizioni semplici di n elementi)
c) il prodotto di due matrici di permutazione è ancora una matrice di permutazione...perchè sarà ancora una matrice di zeri e "uni".
Avatar utente
Bokonon
Cannot live without
Cannot live without
 
Messaggio: 891 di 5942
Iscritto il: 25/05/2018, 20:22

Re: Definizione di matrici di permutazione e permutazioni associate

Messaggioda fmnq » 11/03/2019, 13:28

Facciamo un po' di ordine?

Se \(G\) è un gruppo, una azione di \(G\) su un insieme \(X\) consta di un omomorfismo di gruppi \(G \to Aut(X)\), dove \(AUt(X)\) è l'insieme degli automorfismi di \(X\) (le biiezioni di \(X\)); più in particolare, una rappresentazione di un gruppo \(G\) è un omomorfismo di gruppi \(r : G \to GL(V)\), dove \(GL(V)\) è il gruppo delle applicazioni lineari invertibili di uno spazio vettoriale \(V\).

Consideriamo, ora, \(V = k^n\), lo spazio vettoriale ovvio delle \(n\)-uple di scalari in un campo \(k\).

Claim. Esiste una rappresentazione del gruppo simmetrico \(S(n)\) (il gruppo delle permutazioni di un insieme di \(n\) elementi) su \(V\), che è definito nel modo seguente: la mappa \(r(g) : V \to V\) deve essere una applicazione lineare invertibile, e la definiamo facendola agire su una base \(\{v_1,...,v_n\}\) mandando \(v_i\) in \(v_{g(i)}\). Questo significa che \(g\) agisce linearmente sui vettori di una base permutandone gli indici, e il vettore generico \(v = \sum a_i v_i\) viene mandato in \(\sum a_i v_{g(i)}\).

Ora, data una base di \(V\), come si scrive la matrice di \(r(g)\)? Semplice: al posto \((i,j)\) c'è un 1 se \(j = g(i)\), e zero in ogni altro caso. Questa costruzione ti dà le "matrici di permutazione" che cerchi.
fmnq
Average Member
Average Member
 
Messaggio: 281 di 764
Iscritto il: 03/10/2017, 23:14

Re: Definizione di matrici di permutazione e permutazioni associate

Messaggioda marco2132k » 12/03/2019, 00:41

Vi ringrazio intanto per le risposte che, insieme, rispondono più o meno alla mia domanda.

Parto dall'ultima, a cui ha risposto @fmnq.
Un'idea di come associare ad una permutazione una matrice ora ce l'ho; forse mi sono dimenticato di esplicitare - e avrei dovuto farlo - che avrei preferito operare "sulle matrici", evitando costruzioni più generali.

Provo per esercizio a "ricostruirmi" la matrice: considerando la base canonica, una permutazione \( g \) è mandata nell'applicazione lineare \( r(g)\colon {\sum_{j}x_je_j}\mapsto{\sum_{j}x_je_{g(j)}} \). Abbiamo ovviamente \( GL\left(K^n\right)\cong GL_n(K) \) (col secondo termine indico il gruppo delle matrici \( x\times n \) invertibili), mandando \( r(g) \) nella matrice che ha per colonne i coefficienti di \( r(g)(e_i) \), i.e., i coefficienti di \( e_{g(i)} \).

Allora posso definirmi direttamente la matrice associata a \( g \), come quella matrice che ha, nella posizione \( (i,j) \)-esima, \( \delta_{jg(i)} \). In effetti sarebbe stato un casino arrivarci pensando solo alle matrici grezze, ma era a questo risultato finale a cui miravo.

@Bokonon
Quello che mi interessava provare era proprio che per ogni permutazione, le matrici che dessero l'effetto di permutazione sulle righe di un vettore \( X \) in accordo con quella permutazione, fossero tutte e sole quelle della forma che hai descritto. Ossia, non riuscivo a formalizzarmi il "basta mettere zeri e un 1 e indicizzare solo le righe": e se ce ne fossero di altri tipi?. Sì diciamo che avrei potuto risparmiarmelo 'sto thread (come molti altri). :-D
marco2132k
Advanced Member
Advanced Member
 
Messaggio: 220 di 2053
Iscritto il: 18/02/2018, 23:52

Re: Definizione di matrici di permutazione e permutazioni associate

Messaggioda fmnq » 12/03/2019, 10:21

L'unica cosa che è importante realizzare è che le matrici di permutazione hanno quell'espressione semplice nelle basi fissate; in una base diversa in partenza o in arrivo, sono completamente diverse (ma in modo prevedibile, note le matrici di cambio di base).

Detto meglio, rappresentazioni che differiscono per un cambio di coordinate sono considerate equivalenti.
fmnq
Average Member
Average Member
 
Messaggio: 282 di 764
Iscritto il: 03/10/2017, 23:14

Re: Definizione di matrici di permutazione e permutazioni associate

Messaggioda dissonance » 12/03/2019, 10:30

marco2132k ha scritto:@Bokonon
Quello che mi interessava provare era proprio che per ogni permutazione, le matrici che dessero l'effetto di permutazione sulle righe di un vettore \( X \) in accordo con quella permutazione, fossero tutte e sole quelle della forma che hai descritto. Ossia, non riuscivo a formalizzarmi il "basta mettere zeri e un 1 e indicizzare solo le righe": e se ce ne fossero di altri tipi?. Sì diciamo che avrei potuto risparmiarmelo 'sto thread (come molti altri). :-D

A me piace vedere la cosa in questo modo facile da ricordare: la matrice di permutazione associata alla permutazione \(\sigma\) è quella che si ottiene permutando le righe della matrice identica secondo \(\sigma\).

Infatti, sia \(A\) una matrice generica e sia \(A_\sigma\) la matrice con le righe permutate. Vogliamo trovare la matrice \(P\) tale che
\[
PA=A_\sigma.\]
Ora, ovviamente, \(A=IA\), quindi il membro sinistro diventa
\[
(PI)A=A_\sigma.\]
D'altra parte,
\[
P=PI=I_\sigma.\]
Concludiamo che \(P=I_\sigma\), ovvero, che per costruire \(P\) bisogna applicare la permutazione voluta alla matrice identità.
dissonance
Moderatore
Moderatore
 
Messaggio: 15111 di 27757
Iscritto il: 24/05/2008, 19:39
Località: Nomade

Re: Definizione di matrici di permutazione e permutazioni associate

Messaggioda marco2132k » 13/03/2019, 00:31

@dissonance
Sì in pratica un altro modo ancora di vedere la cosa credo sia ricordare che una permutazione è sempre un prodotto di \( n \) trasposizioni; tenendo a mente i soliti risultati, un matrice di permutazione \( P \) è sempre data da un prodotto del tipo \( P=\prod_k{E_k} \), dove \( E_k \) è una matrice del tipo \( I+e_{ij}+e_{ji}-e_{ii}-e_{ij} \). In effetti questo è utile per far vedere che \( \det{P}=(-1)^n \), dove \( n \) è il numero di trasposizioni.

Detto in altro modo, per ogni matrice di permutazione \( P \) e per ogni matrice \( X \), per definizione (dato che \( (PX)_{p(i)}=X_i \)) esistono \( E_1,\dots,E_k \) matrici di trasposizione tali che \( PX=E_k\cdots E_1X \).

Allora è anche vero che \( P=E_k\cdots E_1I \).

Credo possa andare.
marco2132k
Advanced Member
Advanced Member
 
Messaggio: 221 di 2053
Iscritto il: 18/02/2018, 23:52


Torna a Geometria e algebra lineare

Chi c’è in linea

Visitano il forum: Google Adsense [Bot] e 1 ospite