Potenze di matrici in Z

[orecchia]

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]

Se l'ipotesi è che A sia invertibile, è difficile che sia la matrice 0...

[ma_go]

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]

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

[orecchia]

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]

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