Potenze di matrici in Z

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
orecchia
Messaggi: 4
Iscritto il: 02 lug 2007, 09:17

Potenze di matrici in Z

Messaggio da orecchia » 02 lug 2007, 09:42

l'algebra lineare non è argomento olimpico: thread spostato in matematica non elementare,
ma_go

-------------------------------------------------

Sia A una matrice quadrata i cui elementi sono interi nonnegativi. Se A e' invertibile e se esiste C tale per tutti gli n interi positivi ogni elemento di A^n e' minore di C, dimostrare che A e' la matrice 0 o una permutazione.


La collocazione di questo problema sotto combinatorica e' un piccolo suggerimento.
Una dimostrazione non completamente combinatorica mi risulterebbe abbastanza sorprendente.

fph
Site Admin
Messaggi: 3625
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 02 lug 2007, 13:39

Se l'ipotesi è che A sia invertibile, è difficile che sia la matrice 0... ;)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 02 lug 2007, 14:33

wow, usiamo le parolone? :p
la mia idea, molto poco non elementare...
supponiamo che ci sia una riga con almeno due elementi (di conseguenza, per invertibilità, anche una colonna ne avrà almeno due) oppure un elemento maggiore di 1: allora la somma degli elementi della matrice sarà *strettamente* crescente (per stupidi conticini), quindi gli elementi non possono essere equilimitati.
---------
EDIT: fph ha cancellato il suo messaggio intermedio...

fph
Site Admin
Messaggi: 3625
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 02 lug 2007, 15:51

ma_go ha scritto:EDIT: fph ha cancellato il suo messaggio intermedio...
mm sì, mi sono accorto che la soluzione non è semplice da scrivere come pensavo. Anche la tua idea in effetti richiede un po' di lavoro se vuoi farla senza barare ;)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

orecchia
Messaggi: 4
Iscritto il: 02 lug 2007, 09:17

Messaggio da orecchia » 02 lug 2007, 19:54

Certo, non sara' la matrice 0.
La dimostrazione che conosco considera il digrafo indotto dalla matrice A.
Alcuni lemma non difficili sono:
- se A e' invertibile, ogni vertice appartiene ad almeno un circolo diretto.
- se un vertice i appartiene a piu' di un circolo diretto, allora (A^m)_ii va all'infinito con m.
Quindi il grafo viene decomposto in cicli disconessi, che corrispondo alla decomposizione in cicli della permutazione.

le parisien
Messaggi: 15
Iscritto il: 05 giu 2007, 11:08
Località: parigi

Messaggio da le parisien » 05 set 2007, 17:24

per prima cosa il fatto che C limiti tutti i coefficienti di A^n ci dice che l' insieme delle A^n continene solo matrici a coeff. naturali limitati e dunque un numero finito di matrici per cui esistono n e m differenti tali che A^n=A^m e dunque l'invertibilità di A ci fa concludere che esiste d tale che A^d=Id.
due modi per concludere
1,rapido con le mani
sia B=A^d-1 (1)
allora B è a coefficienti naturali e AB=id
è facile verificare che per due matrici M e N a coefficienti naturali INVERTIBILI la somma dei coefficienti persenti nella matriceMN è più grande di quella di M( o N)
applicando questo alla (1) si conclude.
2,astuto e teorico(questo è del mio amico Yohan)
ad ogni matrice a coefficienti naturali si può associare un grafo orientato:
sia n la taglia della matrice. costruiamo un grafo a n vertici che numeriamo.
il coefficiente nella posizone i,j indicherà il numero di cammini diretti da i a j.
a questo punto il coefficiente i,j della matrice A^k indica il numero di passagi da i a j di lunghezza k(rifletterci un attimo).
una volta interpretata così la situazione è facile capire che se c'è un solo percorso di lunghezza n che parte da i allora ce n'è anche uno solo di lunghezza 1 che parte da i...
se non riuscite a concludere da qua scrivo bene i dettagli
G
se Parigi avesse il mare sarebbe una piccola Bari

Rispondi