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

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Vamos mostrar o caso em que o grafo é conexo.

Considere a matriz B = A + I. Note que B é simétrica e real também.
A coordenada (i, j) de B^k representa o número de passeios no grafo 
(onde podemos repetir arestas) do vértice i até o vértice j.
Como o grafo é conexo, para algum k, B^k tem todas as entradas positivas.
Agora note que se x não é múltiplo de (1, ..., 1) e Ax = dx, então Bx = 
(d+1)x e, portanto x é auto-vetor de B.
Seja m tal que x_m é mínimo. Defina y = x - x_m*(1, ..., 1). Veja que y 
é auto-vetor de B (com auto-valor correspondente d+1), cuja menor 
coordenada é 0 e todas as demais são não-negativas.
B^k y = (d+1)^k y, mas isso é absurdo pois y_m = 0 e, portanto, [(d+1)^k 
y]_m = 0, enquanto
[B^k y]_m > 0, pois este valor é a soma de valores não negativos (onde 
pelo menos um valor é estritamente positivo).

Se o grafo tem r componentes conexas, podemos formar explicitamente uma 
base de auto-vetores para a matriz de adjacência. Se há r componentes 
conexas, digamos C_1, ..., C_r, então os vetores {v_i} que possuem 0 nas 
coordenadas correspondentes a C_j com j != i e 1 nas coordenadas 
correspondentes a C_i formam uma base de auto-vetores da matriz de 
adjacência.

[ ]'s
=========================================================================
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
=========================================================================