Maratona problemi algebra lineare

[Dorian1]

Dato il successo che ha ottenuto recentemente la maratona sui problemi di 'Teoria dei gruppi', ho pensato che fosse il caso di aprire un topic simile, nel quale esporre problemi di algebra lineare.
Valgono le stesse regole, quindi: chi risolve per primo esibisce un nuovo problema, oppure cede la mano... Nella speranza che qualcuno voglia partecipare, posto il primo problema... Pronti, via!

Si consideri lo spazio vettoriale $M_(n,m)(K)$ (matrici con $n$ righe ed $m$ colonne a coefficienti in un campo $K$) (*) sul quale definiamo la seguente relazione (d'equivalenza):

$A sim B <=> EE P in GL_n(K), EE Q in GL_m(K): B=PAQ$

(1) Dare una condizione necessaria e sufficiente affinchè, date due matrici $A$,$B in M_(n,m)(K)$, sia $A sim B$;
(2) Dire quanti elementi ha l'insieme $M_(n,m)(K)$ / $sim$;

Buon lavoro!

EDIT: (*) Sarebbe più corretto, date le richieste del problema, vedere $M_(n,m)(K)$ come $K$-algebra con le operazioni di somma, prodotto per scalare, prodotto di matrici.

[NightKnight1]

Io avevo in mente un'altra dimostrazione del fatto che se $q$ è relativamente primo con $m$ allora $q(f)$ è un'automorfismo:
per l'identità di Bezout, esistono dei polinomi $a,b \in K[t]$ tali che $a(t) \ q(t) + b(t) \ m(t) = 1$ e valutando nell'endomorfismo $f$ si ha:
$Id_V = a(f) \circ q(f) + b(f) \circ m(f) = a(f) \circ q(f)$ e quindi $q(f)$ è invertibile.

E poi si fa vedere il caso generale: Se $d(t)= MCD \ (q(t) \ , \ m(t))$ allora $Ker \ q(f) = Ker \ d(f)$:
infatti allora $q(t) = a(t) \ d(t)$ dove $a(t)$ è primo con $m(t)$, allora per quanto visto sopra $a(f)$ è un isomorfismo e quindi $Ker \ q(f) = Ker \ a(f) \circ d(f) = Ker \ d(f)$.

Non ho ben capito perché K dovrebbe essere iniettiva. Comunque l'idea è giusta.

[dissonance]

Voglio dire che a ogni fattore monico di $p$ corrisponde un sottospazio distinto di $V$. Infatti il teorema di decomposizione ci dice anche di più: e cioè che non solo i $"ker"\ p(f)$ sono distinti, ma addirittura la loro somma è diretta.

[NightKnight1]

Si si, ok....
Se q(t) e p(t) sono due polinomi monici e divisori di m(t) e distinti allora i ker relativi sono diversi. ok!

Dissonance, ti passo il testimone!

[dissonance]

Mi piacerebbe se rispolverassimo il problema proposto da Martino. Finora l'abbiamo snobbato perché il testo è troppo lungo, ci vuole tempo solo per leggerlo. Perciò io direi che possiamo provare a spezzarlo in due: la costruzione dell'algebra esterna, e la caratterizzazione del determinante. Più tardi provo a riscrivere la prima parte del testo (adesso devo andare) per vedere se ci spaventa di meno.

Naturalmente se vedo che non arrivano risposte poi proporrò io un esercizio più standard. O se pensate che debba farlo subito, ditemelo.

[dissonance]

Ci ho ripensato. Evidentemente l'esercizio di Martino è troppo istruttivo per essere svolto davanti ad uno schermo!
Provo a proporne un altro più da Settimana Enigmistica: calcolare il determinante di
$[[1,1,0,0, ldots, 0, 0],[1,1,1,0, ldots, 0,0],[0,1,1,1,ldots, 0,0],[0,0,1,1,ddots,0,0],[vdots, vdots, vdots, ddots, ddots,ddots,vdots], [0,0,0,0,ddots,1,1], [0,0,0,0,ldots, 1,1]]$
in funzione della dimensione della matrice.

[NightKnight1]

Sia $x_n$ il determinante della matrice n x n del tipo considerato. Sviluppiamo il determinante della matrice n x n rispetto alla prima colonna:
$x_n = det ([1,1,0,ldots,0,0],[1,1,1,ldots,0,0],[0,1,1,ddots,0,0],[vdots,vdots,ddots,ddots,ddots,vdots],[0,0,0,ddots,1,1],[0,0,0,ldots,1,1]) - det([1,0,0,ldots,0,0],[1,1,1,ldots,0,0],[0,1,1,ddots,0,0],[vdots,vdots,ddots,ddots,ddots,vdots],[0,0,0,ddots,1,1],[0,0,0,ldots,1,1])$.
Si vede subito che il primo determinante è $x_(n-1)$; sviluppiamo il secondo determinante rispetto alla prima riga e otteniamo $x_(n-2)$.
Quindi per ogni $n > 2, \ x_n=x_(n-1)-x_(n-2)$.
Inoltre si vede facilmente che $x_1=1$ e che $x_2=det([1,1],[1,1])=0$.

Per trovare un formula esplicita, cioè non ricorsiva, della successione $x_n$ troviamo le soluzioni dell'equazione $x^2=x-1$, cioè le radici del polinomio $x^2-x+1$.
Si vede che le radici di questo polinomio sono $\omega , -\omega$ dove $\omega=e^((2i\pi)/6)$ è la radice sesta dell'unità.
Allora la successione $x_n$ è una combinazione lineare delle due successioni $\omega^n \ , \ (-\omega)^n$. Imponendo le condizioni iniziali per $n=1,2$ si trovano i due coefficienti della combinazione lineare e si trova che:
$x_n = 1/(2\omega) \omega^n - 1/(2\omega) (-\omega)^n$.

[dissonance]

Ah quindi tu hai risolto la ricorrenza... Ma come hai fatto? (Non dubito che sia corretto, è che per ignoranza mia davvero non capisco che procedimento hai seguito).

Io avevo pensato, una volta trovata la relazione ${(x_n=x_{n-1}-x_{n-2}),(((x_2),(x_1))=((0),(1))):}$ di riscriverla come ${(((x_n), (x_{n-1}))=((1,-1), (1,0))((x_{n-1}), (x_{n-2}))),(((x_2),(x_1))=((0),(1))):}$. Calcolando qualche valore di $x_n$ viene il dubbio che la successione si ripeta dopo un certo numero di passi, e infatti la matrice $((1,-1),(1,0))$ ha periodo finito 6. Perciò basta calcolare $x_3, x_4, x_5, x_6, x_7$ ovvero le potenze da 1 a 5 di quella matrice 2 x 2 per il vettore $((0),(1))$, dopodiché i valori si ripeteranno.

[Studente Anonimo]

"NightKnight":Per trovare un formula esplicita, cioè non ricorsiva, della successione $x_n$ troviamo le soluzioni dell'equazione $x^2=x-1$, cioè le radici del polinomio $x^2-x+1$.
Si vede che le radici di questo polinomio sono $\omega , -\omega$ dove $\omega=e^((2i\pi)/6)$ è la radice sesta dell'unità.

Forse volevi dire che le radici sono $omega$, $bar{omega}$ ?

A me viene: $x_n = (bar{omega}^{n-2}-omega^{n-2})/(i sqrt{3})$.

Torna anche con la verifica dato che:

$i sqrt{3} (x_{n-1}-x_{n-2}) = bar{omega}^{n-3}-omega^{n-3} - (bar{omega}^{n-4} - omega^{n-4}) = bar{omega}^{n-2}-omega^{n-2} = i sqrt{3} x_n$

infatti portando tutto a sinistra nella seconda uguaglianza risulta:

$bar{omega}^{n-4} (bar{omega}-1-bar{omega}^2)+omega^{n-4}(-omega+1+omega^2) = 0$

e questo è vero perché $omega$ e $bar{omega}$ sono proprio gli zeri di $x^2-x+1$.

@dissonance: il metodo per passare da una formula ricorsiva ad una formula chiusa in questo tipo di problemi è "standard" quando applicabile. Se ti interessa posso mandarti un pvt in merito.

[dissonance]

"Martino":
@dissonance: il metodo per passare da una formula ricorsiva ad una formula chiusa in questo tipo di problemi è "standard" quando applicabile. Se ti interessa posso mandarti un pvt in merito.

si certo se ne hai voglia...ma che cos'è un pvt?

[dissonance]

ah se può servire... il risultato che ottengo io è:
$x_[1] = 1, x_[2] = 0, x_[3] = -1, x_[4] = -1, x_[5] = 0, x_[6] = 1, x_[7] = 1, x_[8] = 0, x_[9] = -1,ldots$
(penso sia giusto...l'ho verificato fino all'ordine 30 con Maple).

[dissonance]

@Martino: Aaaaaahhhh...adesso ho capito... $x^2-x+1$ è il polinomio caratteristico della matrice $((1,-1), (1,0))$... Vabbé, comunque sicuramente le due radici sono coniugate.
@N.K.: Quando vuoi proponi un altro problema!

[NightKnight1]

Hai ragione Martino! Ho commesso un errore... le radici del polinomio $x^2-x+1$ sono $\omega \ , bar(\omega)$ dove
$\omega=e^((2\pi i)/6)=cos((2\pi)/6)+i sen((2\pi)/6)=1/2 + i sqrt(3)/2$ è la radice sesta dell'unità.

Allora la nostra successione $x_n$ deve essere una combinazione lineare delle due successioni $\omega^n \ , bar(\omega)^n$, cioè:
$x_n=\alpha \omega^n + \beta bar(\omega)^n$ e allora imponendo le condizioni iniziali per $n=1,2$ si ottiene il sistema lineare di due equazioni in due incognite:
$\alpha \omega + \beta bar(\omega) = 1$
$\alpha \omega^2 + \beta (bar(\omega))^2 = 0$
Se risolviamo questo sistema otteniamo:
$\alpha = - \omega^4/(i sqrt(3))$
$\beta = \omega^2/(i sqrt(3))$
Allora risistemando un po' le cose, otteniamo:
$x_n = i/sqrt(3) [\omega^(n-2) - bar(\omega)^(n-2)]$
come aveva detto Martino.

Oppure si può usare anche il ragionamento proposto da dissonance:
$[[x_2],[x_1]]=[[0],[1]]$
$[[x_n],[x_(n-1)]]=[[1,-1],[1,0]] \ [[x_(n-1)],[x_(n-2)]]$
Allora si vede che per ogni $ n >= 2$, si ha
$[[x_n],[x_(n-1)]] = A^(n-2) e_2 = [[1,-1],[1,0]]^(n-2) [[0],[1]]$. Cioè $[[x_n],[x_(n-1)]]$ è la seconda colonna della matrice $A^(n-2)$.
Quindi si tratta di calcolare le potenze della matrice $A$.
Si vede che la matrice $A$ ha come polinomio caratteristico $x^2-x+1$ che ha come radici $\omega \ , \ bar(\omega)$; poichè la matrice $A$ ha due autovalori distinti essa è diagonalizzabile.
Una base di autovettori è ad esempio ${ ((\omega),(1)) \ , \ ((bar(\omega)),(1)) }$
Allora chiamando $M=((\omega,bar(\omega)),(1,1))$
$D=((\omega,0),(0,bar(\omega)))$
si vede che $M^(-1) = 1/(\omega - bar(\omega)) ((1,-bar(\omega)),(-1,\omega))$
e che $A=M \ D \ M^(-1)$.
Allora per ogni $k$ naturale si ha $A^k=(M \ D \ M^(-1))^k=M \ D^k \ M^(-1)=1/(\omega - bar(\omega)) ((\omega,bar(\omega)),(1,1)) ((\omega^k,0),(0,bar(\omega)^k)) ((1,-bar(\omega)),(-1,\omega)) = 1/(\sqrt(3) i) ((\omega^(k+1)-bar(\omega)^(k+1),-\omega^k+bar(\omega)^k),(\omega^k-bar(\omega)^k,-\omega^(k-1)+bar(\omega)^(k-1)))$.
Allora ricordando che $[[x_n],[x_(n-1)]]$ è la seconda colonna della matrice $A^(n-2)$ e ponendo $k=n-2$, si ha che:
$[[x_n],[x_(n-1)]] = 1/(sqrt(3) i) \ [[-\omega^(n-2)+bar(\omega)^(n-2)],[-\omega^(n-3)+bar(\omega)^(n-3)]]$
e allora $x_n = (-\omega^(n-2) + bar(\omega)^(n-2))/(sqrt(3) i) = i (\omega^(n-2) - bar(\omega)^(n-2))/sqrt(3)$ come visto prima.

[NightKnight1]

"dissonance":@Martino: Aaaaaahhhh...adesso ho capito... $x^2-x+1$ è il polinomio caratteristico della matrice $((1,-1), (1,0))$...

Quel polinomio è sì il polinomio caratteristico della matrice, ma io l'avevo trovato in un altro modo. Infatti, io due metodi che ho proposto per esplicitare le successioni definite per ricorrenza sono indipendenti tra loro.
Ti faccio vedere la cosa in generale: sia $x_n$ una successione a valori complessi così definita:
$x_(n+1) = a x_n + b x_(n-1) \ \ \ \forall n >= 2$. E si supponga di aver fissato già $x_0 \ , \ x_1$.
Allora supponiamo che la successione $x_n$ sia della forma $\lambda^n$ per qualche $\lambda \in CC$. [Questo procedimento assomiglia molto al metodo di risoluzione delle eq. differenziali lineari a coefficienti costanti omogenee, dove si considerano le soluzioni del tipo $e^(\lambda x)$ e si trova così l'equazione caratteristica dell'equazione differenziale] Allora sostituendo $x_n = \lambda^n$ si ottiene:
$\lambda^(n+1) = a \lambda^n + b \lambda^(n-1)$ e dividendo per $\lambda^(n-1)$ si ottiene l'equazione:
$\lambda^2 = a \lambda + b$.
Se quest'equazione ha due soluzioni distinte $\lambda_1 \ , \lambda_2$ allora $x_n$ è una combinazione lineare di $\lambda_1^n \ , \ \lambda_2^n$.
Se invece l'equazione caratteristica ha due soluzioni uguali $\lambda_0$ allora $x_n$ è una combinazione lineare di $\lambda_0^n \ , \ n*\lambda_0^n$.
Per trovare i coefficienti di questa combinazione lineare basta imporre le condizioni iniziali per $n=0,1$ e si ottiene in questo modo un sistema lineare.

Questo procedimento per esplicitare le successioni definite per ricorrenza si può fare per tutte quelle in cui:
$x_(n+1) = a_0 x_n + a_1 x_(n-1) + a_2 x_(n-2) + ... + a_k x_(n-k)$
cioè quando il termine generale $x_n$ è una combinazione lineare di un numero finito di termini precedenti.
In questo caso il polinomio che si ottiene è:
$\lambda^(k+1) - a_0 \lambda^k - a_1 \lambda^(k-1) - ... - a_(k-1) \lambda - a_k$.
Anche il tuo metodo delle matrici può essere applicato a successioni di questo tipo che coinvolgono più di due termini precedenti.
Allora si ottiene:
$[[x_(n+1)],[x_n],[x_(n-1)],[vdots],[x_(n-k+2)],[x_(n-k+1)]] \ = \ [[a_0,a_1,a_2,ldots,a_(k-1),a_k],[1,0,0,ldots,0,0],[0,1,0,ldots,0,0],[vdots,vdots,ddots, ,vdots,vdots],[0,0,0,ddots,0,0],[0,0,0,ldots,1,0]] \ * \ [[x_n],[x_(n-1)],[x_(n-2)],[vdots],[x_(n-k+1)],[x_(n-k)]]$
E si verifica che il polinomio caratteristico della matrice sopra è proprio il polinomio caratteristico della successione per ricorrenza definito sopra.
Infatti una matrice di questo tipo si dice matrice compagna del polinomio sopra, e matrici di questo tipo sono fondamentali nella forma canonica razionale.
In realtà nelle matrici compagne vere e proprie che si usano nella forma canonica razionale gli uni stanno nella sovradiagonale mentre i coefficienti $a_i$ stanno nell'ultima riga in ordine inverso. Mi spiego meglio:
dato un polinomio monico $q(t) = c_0 + c_1 t + c_2 t^2 + ... + c_(k-1) t^(k-1) + t^k \ \in \mathbbK[t]$ allora la sua matrice compagna è:
$[[0,1,0,ldots,0],[0,0,1,ldots,0],[vdots,vdots, ,ddots, ],[0,0,0,ldots,1],[-c_0,-c_1,-c_2,ldots,-c_(k-1)]]$.
Quest'ultima parte sulle matrici compagne l'ho un po' buttata lì, perché a lezione non abbiamo fatto la forma canonica razionale e quello che ho detto l'ho letto alla meno peggio sull'Herstein e quindi può darsi che abbia detto qualche castroneria. Correggetemi!

[Dorian1]

@Martino: perdonami l'ennesima richiesta di delucidazioni!

"Martino":- Osservare che $f(u_i)^2=0$ per ogni $i=1,...,n$, e dedurre che $f(v)^2=0$ per ogni $v in V$. Dedurre che $(j,E)$ appartiene a $Omega$.

Volevi scrivere $j$ al posto di $f$, giusto?

[Studente Anonimo]

"Dorian":@Martino: perdonami l'ennesima richiesta di delucidazioni!

[quote="Martino"]- Osservare che $f(u_i)^2=0$ per ogni $i=1,...,n$, e dedurre che $f(v)^2=0$ per ogni $v in V$. Dedurre che $(j,E)$ appartiene a $Omega$.

Volevi scrivere $j$ al posto di $f$, giusto?[/quote]

Giusto, scusa, ho corretto.

[Dorian1]

"Martino":- Mostrare che se $eta:V to V$ è un $k$-endomorfismo di $V$ allora resta definito un endomorfismo di $E(V)$ come $eta(L):E(V) to E(V)$, $eta(L)(u_{i_1}...u_{i_t})=L(u_{i_1})...L(u_{i_t})$ (dove $i_1<...

Non capisco la parte in grassetto... Cos'è $L$?

[Studente Anonimo]

"Dorian":[quote="Martino"]- Mostrare che se $eta:V to V$ è un $k$-endomorfismo di $V$ allora resta definito un endomorfismo di $E(V)$ come $eta(L):E(V) to E(V)$, $eta(L)(u_{i_1}...u_{i_t})=L(u_{i_1})...L(u_{i_t})$ (dove $i_1<...

Non capisco la parte in grassetto... Cos'è $L$?[/quote]

Madonna scusa hai ragione, quanti errori di trascrizione!

$L$ è il morfismo $V to V$ che ho erroneamente chiamato $eta$.

[Dorian1]

"Martino": Mostrare che $eta(L_1 L_2) = eta(L_1) eta(L_2)$, che $eta(1)=1$.

$L_1$ ed $L_2$ sono elementi di $E(V)$ oppure con $eta(L_1L_2)$ denoti l'endomorfismo indotto su $E(V)$ dall'endomorfismo $L_1 circ L_2$?

$eta(1)$ è l'endomorfismo indotto dall'identità di $V$?

[Dorian1]

"Martino":
- $eta(L)(u_{i_1}...u_{i_t})$=$L(u_{i_1})...L(u_{i_t})$ (dove $i_1<...

Ma non abbiamo definito un prodotto tra gli elementi di $V$...Volevi forse scrivere $eta(L)$ in luogo di $L$?

[Studente Anonimo]

"Dorian":con $eta(L_1L_2)$ denoti l'endomorfismo indotto su $E(V)$ dall'endomorfismo $L_1 circ L_2$?

Esatto.

$eta(1)$ è l'endomorfismo indotto dall'identità di $V$?

Sì.

Ma non abbiamo definito un prodotto tra gli elementi di $V$...Volevi forse scrivere $eta(L)$ in luogo di $L$?

No, lì ho scritto giusto: il prodotto $L(u_{i_1})...L(u_{i_t})$ viene fatto in $E(V)$, non in $V$ (cioè è un prodotto di elementi di $V$ pensati in $E(V)$).