on 24.08.04 16:38, Domingos Jr. at [EMAIL PROTECTED] 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 =========================================================================