[algebra lineare] matrice irriducibile non-negativa

da **alvinlee88** » 05/11/2010, 13:09

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

da **alvinlee88** » 09/11/2010, 01:54

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

Testo nascosto, fai click qui per vederlo

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

da **Mathematico** » 09/11/2010, 17:45

Testo nascosto, fai click qui per vederlo

Mi chiedo se partire da
$ \displaystyle (I+A)^{n-1}= \sum_{k=0}^{n-1}{n-1\choose k} A^k\quad\text{ con } A^0:= I $
sia una cosa furba ... :-k

, 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

da **alvinlee88** » 09/11/2010, 18:24

@mathematico
ho corretto, grazie.

Testo nascosto, fai click qui per vederlo

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

da **Mathematico** » 12/11/2010, 10:42

@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 :-D

.

(La mia difficoltà è sorta perchè ho lavorato poco con questo tipo di matrici :roll:

). L'esercizio non è difficile, bisogna essere furbi, evidentemente io non lo sono abbastanza :lol:

da **alvinlee88** » 13/11/2010, 03:17

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.

da **Mathematico** » 14/11/2010, 17:34

Ok scriverò la dimostrazione.

Testo nascosto, fai click qui per vederlo

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

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

Consideriamo una matrice $ \displaystyle P $ che trasformi il vettore $ \displaystyle x $ in $ \displaystyle Px=\left (\begin{matrix} \alpha \\ o\end{matrix} \right) $ dove $ \displaystyle \alpha $ è il sottovettore costituito dagli elementi positivi di $ \displaystyle x $ , mentre $ \displaystyle o $ è un sottovettore che ha per elementi tutti e soli elementi nulli di $ \displaystyle x $ . Ricordando inoltre che la matrice di permutazione $ \displaystyle P $ gode della seguente proprietà $ \displaystyle PP^T= I $ si scopre che:
$ \displaystyle (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) $ .
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:
$ \displaystyle Py=\left (\begin{matrix} \omega\\ o\end{matrix} \right) $ , con $ \displaystyle \omega $ della stessa lunghezza di $ \displaystyle \alpha $ .

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

Sostituendo nella equazione $ \displaystyle (1.3) $ abbiamo:
$ \displaystyle \omega= \alpha+A_{11}\alpha $
$ \displaystyle o= A_{21} \alpha $

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

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

Pertanto $ \displaystyle y_{n-1}=(I+A)^{n-1}x >0 $

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..... :roll:

da **alvinlee88** » 14/11/2010, 18:28

@mathematico
E esattamente la stessa dimostrazione che conosco io, 8-)

Testo nascosto, fai click qui per vederlo

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$

[algebra lineare] matrice irriducibile non-negativa

[algebra lineare] matrice irriducibile non-negativa

Chi c’è in linea