[algebra lineare] matrice irriducibile non-negativa

[alvinlee881]

Sia [tex]A \in \mathbb R^{n \times n}[/tex] una matrice irriducibile a entrate non-negative, i.e. [tex]a_{ij}\geq0[/tex] per ogni [tex]i,j=1,\cdots,n[/tex]. Dimostrare che allora la matrice [tex](I+A)^{n-1}[/tex] è a entrate strettamente positive.

[alvinlee881]

Post scriptum: una matrice [tex]M[/tex]è irriducibile se non esiste una matrice di permutazione [tex]P[/tex] tale che [tex]PMP^t=\left[
\begin{array}{c|c}
A & B \\ \hline
0 & C
\end{array}\right][/tex], con [tex]A[/tex] matrice quadrata di ordine [tex]m
Hint:

dimostrare che se [tex]x[/tex] è a componenti [tex]\ge0[/tex], allora [tex](I+A)^{n-1}x[/tex] è a componenti [tex]>0[/tex]

[salvozungri]

Mi chiedo se partire da
[tex]$(I+A)^{n-1}= \sum_{k=0}^{n-1}{n-1\choose k} A^k\quad\text{ con } A^0:= I[/tex]
sia una cosa furba ... , questa strada però mi sembra piena di calcoli e mi scoraggia
p.s: Attento che nella definizione hai utilizzato A per indicare due matrici distinte

[alvinlee881]

@mathematico
ho corretto, grazie.

Si, quello sviluppo aiuta, ma servono molti meno conti di quanto pensi...

[salvozungri]

@alvinlee88: purtroppo non sono riuscito da solo a risolvere il quesito. Sono andato a chiedere chiarimenti ad un mio amico dottorando, il quale mi ha risolto l'esercizio (senza chiedergli tra l'altro la soluzione ) rovinandomi la "sorpresa". Non riporto la dimostrazione perchè mi spiace rovinare un così bell'esercizio .

(La mia difficoltà è sorta perchè ho lavorato poco con questo tipo di matrici ). L'esercizio non è difficile, bisogna essere furbi, evidentemente io non lo sono abbastanza

[alvinlee881]

Questo esercizio è uno dei vari lemmi che servono per dimostrare un teorema piuttosto grosso di algebra lineare, quindi non è questione di essere furbi o meno, ma di aver già visto come si lavora con questo tipo di matrici.
Quindi la dim postala pure, magari in spoiler, così vedo se è la stessa che conosco io.

[salvozungri]

Ok scriverò la dimostrazione.

Prendiamo un vettore [tex]x\in\mathbb{R}^n[/tex] tale che [tex]x\ge0[/tex](1.1) con almeno un elemento non nullo.
Definiamo
[tex](1.2) \qquad y=(I+A)x = x+Ax[/tex].

Per ipotesi , la matrice [tex]A\ge 0[/tex] e dunque [tex]Ax\ge0[/tex], questo perchè nel prodotto matrice-vettore abbiamo somme di prodotti di numeri reali non negativi. Per come è definito il vettore [tex]y[/tex] esso avrà almeno lo stesso numero di elementi nulli di [tex]x[/tex]. Si dimostra in realtà che il numero di zeri di [tex]y[/tex] è inferiore al numero di zeri di [tex]x[/tex], è quello che faremo .

Consideriamo una matrice [tex]P[/tex] che trasformi il vettore [tex]x[/tex] in [tex]Px=\left (\begin{matrix} \alpha \\ o\end{matrix} \right)[/tex] dove [tex]\alpha[/tex] è il sottovettore costituito dagli elementi positivi di [tex]x[/tex], mentre [tex]o[/tex] è un sottovettore che ha per elementi tutti e soli elementi nulli di [tex]x[/tex]. Ricordando inoltre che la matrice di permutazione [tex]P[/tex] gode della seguente proprietà [tex]PP^T= I[/tex] si scopre che:
[tex](1.3)\qquad Py= Px+PAP^T P x =\left (\begin{matrix} \alpha \\ o\end{matrix} \right)+PAP^T \left (\begin{matrix} \alpha \\ o\end{matrix} \right)[/tex].
Utilizziamo la notazioni a blocchi compatibili, (leggi in questo modo, per non avere problemi con indici e pedici, lavoreremo con matrici a blocchi e vettori a blocchi di modo che il prodotto sia compatibile).

Supponiamo per assurdo che Px e Py abbiano lo stesso numero di zeri, ciò implica che:
[tex]Py=\left (\begin{matrix} \omega\\ o\end{matrix} \right)[/tex], con [tex]\omega[/tex] della stessa lunghezza di [tex]\alpha[/tex].

Scomponiamo in blocchi la matrice [tex]PAP^T[/tex]
[tex]PAP^T=\left(\begin{matrix}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{matrix}\right)[/tex]

Sostituendo nella equazione [tex](1.3)[/tex] abbiamo:
[tex]\omega= \alpha+A_{11}\alpha[/tex]
[tex]o= A_{21} \alpha[/tex]

Poichè per ipotesi [tex]\alpha>0\implies A_{21}=0[/tex] che comporta un assurdo in quanto A è irriducibile. Possiamo quindi costruire una successione:

[tex]y_k:= (I+A)^k x[/tex] con [tex]y_k[/tex] vettore di [tex]\mathbb{R}^n[/tex] che ha almeno k zeri in meno rispetto ad [tex]x[/tex]

Pertanto [tex]y_{n-1}=(I+A)^{n-1}x >0[/tex]

Se riscontrate errori la colpa è mia, la dimostrazione spiegatami non l'ho riportata su foglio, ho ricostruito la dimostrazione a casa... magari malamente
_________
(1.1): con questa dicitura si intende un vettore che ha le entrate non negative.

PS: sono ancora alla ricerca di una dimostrazione che non utilizzi questa cosa. Io sospetto che ce ne sia una che sfrutti l'uguaglianza riportata nel mio spoiler precedente.....

[alvinlee881]

@mathematico
E esattamente la stessa dimostrazione che conosco io,

la formula binomiale serve solo per fare il caso $x>0$, poiche, con le tue notazioni, se $\alpha=x$, ossia se non ci sono componenti nulle, non e assurdo che $y$ abbia lo stesso numero di zeri di $x$ (ossia tutte), anzi e proprio cio che ti serve e che devi dimostrare a parte: $(I+A)^{n-1}x=(I+\mbox{matrice a entrate non negative})x=x+(\mbox{vettore a entrate non negative})>0$