Re: [obm-l] Auto-valores de grafos

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 24.08.04 16:38, Domingos Jr. at dopikas@uol.com.br wrote:

> hmmm, lendo melhor o que vc escreveu, tem uma falha:
> 
> "Seja u_j a componente de maior valor absoluto de u.
> Entao a j-esima componente de Au serah igual a uma soma de d componentes u_i
> e tambem serah igual a d*u_j (pois u eh autovetor de A associado a d).
> Dada a escolha de u_j, isso soh poderah ocorrer se todos os u_i's forem
> iguais..."
> 
> 
> acontece que você descobriu que esses "d" u_i's são iguais, mas isso não
> prova imediatamente que todos os u_i's são iguais...
> eu tenho uma demonstração interessante, mas vou deixar você pensar um
> pouco mais.
> 
> [ ]'s
>
Verdade! Eu trabalhei com o exemplo de um grafo completo (para o qual o
raciocinio estah correto) e nao atentei para este detalhe.

A primeira ideia que me ocorreu foi tomar tambem a menor componente do
autovetor associado a d.
Como A eh simetrica e real, os seus autovalores sao reais e, portanto, os
autovetores tem componentes reais.
Seja v = (x_1,...,x_n)^t um autovetor associado a d e sejam x_r e x_s a
menor e a maior componente de v, respectivamente.

d*x_s = SOMA(i adjacente a s) x_i = x_i1 + ... + x_id
e   
d*x_r = SOMA(j adjacente a s) x_j = x_j1 + ... + x_jd

Logo, v deve ter pelo menos d+1 componentes iguais a x_r (incluindo x_r) e
pelo menos d+1 componentes iguais a x_s (incluindo x_s).

Isso prova o resultado para o caso em que n <= 2d+1, pois nesse caso os dois
(multi)conjuntos de d+1 componentes se intersectam.

Outra ideia que me ocorreu foi olhar para a matriz A - d*I.
Fazendo a operacao elementar L_n <- L_1 + L_2 + ... + L_n (ou seja, somando
cada uma das linhas a ultima linha dessa matriz) obtemos uma linha de zeros.
Isso prova que A - d*I eh singular e, portanto, que d eh um autovalor de A.
Se, alem disso, tivermos que posto(A - d*I) = n-1, entao acabou, pois nesse
caso, nulidade(A - d*I) = dimensao do autoespaco associado a d = 1.
Eu estou convencido de que isso eh verdade, mas nao consegui provar.

Enfim, qual a sua solucao?

[]s,
Claudio.


=========================================================================
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
=========================================================================