[obm-l] Re: [obm-l] Convergência de uma seqüência de matrizes

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Thu, Dec 05, 2002 at 12:39:43AM -0200, Artur Costa Steiner wrote:
> Olá a todos
>  
> Estou trabalhando em um programa ligado a energia elétrica e tenho uma
> matriz quadrada A, de ordem p, na qual cada termo a_i,j está em [0,1].
> Além disto, tenho que a soma de cada coluna da matriz é 1. Embora não
> seja exatamente isto, é como se A fosse uma matriz de probabilidades de
> transição de estado, conforme aparece em processos estocásticos. 
>  
> Com algum algebrismo verificamos que a soma de cada coluna de A2 também
> é 1, do que concluímos imediatamente que esta mesma condição vale para
> qualquer potência inteira de A.

De fato. Dizer que as colunas de A somam 1 significa que XA = X onde
X é a matriz linha (1 1 1 ... 1) e portanto de XA = X então XAA = XA = X.
Dizer que as linhas somam 1 significa que AY = Y onde Y = X^t é o vetor
coluna com todas as entradas iguais a 1 e se AY = Y então AAY = AY = Y.

>                                 Não consegui provar matematicamente,
> mas, com uma planilha Excel, verifico que, se A não contiver zeros ou
> 1s, então a seqüência (An) converge para uma matriz na qual todas as
> colunas são idênticas e correspondem a um auto vetor de A associado ao
> auto valor 1.

De fato, considere T o conjunto de vetores coluna (x1,x2,...,xn)
com x1+x2+...+xn = 1, 0 <= xi <= 1. Este conjunto T é invariante
pela transformação linear A e é homeomorfo a um disco. Pelo
teorema do ponto fixo de Brower deve existir um ponto fixo de A em T
que claramente é um autovetor correspondente ao autovalor 1.

Se existisse mais de um ponto fixo então por linearidade
o subespaço contendo esses dois pontos seria todo de pontos
fixos logo haveria um ponto fixo no bordo do nosso conjunto T,
ou seja, haveria um ponto fixo v com uma ou mais coordenadas
iguais a 0 e as demais maiores que 0. Se todos os coeficientes
de A forem positivos devemos ter todas as coordenadas de Av
estritamente positivas, o que é um absurdo. Assim o ponto fixo
é único.

Acabamos de provar que a multiplicidade geométrica do autovalor
1 é igual a 1. A multiplicidade algébrica também é igual a 1
pois se existisse nilpotência associada ao autovalor 1 haveria
um vetor v para o qual o limite de |A^n v| seria infinito
o que é claramente falso: o conjunto dos vetores (x1,x2,...,xn)
com |x1| + |x2| + ... + |xn| <= 1 é invariante por A.

> Podemos provar matematicamente que isto, de fato, sempre se verifica? Se
> a matriz contiver zeros (logo, também 1s) então pode não haver
> converg6encia, certo?

Claro, basta considerar a matriz

(0 0 1)
(1 0 0)
(0 1 0)

ou outra matrix de permutação qualquer.

Os resultados que você quer são os teoremas de Perron-Frobenius.
Você pode achar em livros de álgebra linear um pouco mais avançados
do que os livros texto que você deve conhecer. Uma boa referência é:

Theory of matrices, Gantmacher, F. R., Chelsea Publishing Co.,
New York, 1977.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================