Re: [obm-l] Problema de matrizes

["F�bio Dias Moreira" <fabio.dias.moreira@xxxxxxxxxxxx>]

---------- Cabe�alho inicial  -----------

De: owner-obm-l@sucuri.mat.puc-rio.br
Para: obm-l@mat.puc-rio.br
C�pia: 
Data: Mon, 21 Jul 2003 19:16:47 -0300 (EST)
Assunto: Re: [obm-l] Problema de matrizes

> Nao eh dificil dar uma solu�ao usando autovalores. Veja a solu�ao enviada pelo Stabel, que eh otima, e que consegue usar autovalores de forma compreensivel a (bons) alunos do ensino medio. Mas, sei la, continuo desconfiado que deve haver uma solu�ao que nao va alem de determinantes e sistemas de equa�oes lineares. Algo que provasse diretamente que A anti-simetrica real implicaria det(A+I) diferente de 0.
> [...]

Eu acho que tenho uma solu��o elementar parcial para o problema:

Seja nxn o tamanho da matriz A. Seja P o conjunto das permuta��es de comprimento n). Seja p uma permuta��o de P. Se p n�o for uma involu��o, tome sua inversa q. Olhe para os termos associados a p e q no determinante da matriz A+I. Como pq = i, onde i � a identidade de P, p e q t�m a mesma paridade, logo os termos associados t�m, a priori, o mesmo sinal. Mas se x aparece num dos termos, ent�o -x aparece no termo oposto; logo um dos termos � (-1)^k o outro, onde k � o n�mero de pontos n�o-fixos, i.e. x tais que p(x) != x.

Caso pp = i, eu afirmo que o termo associado � certamente n�o-negativo. Note que ent�o que os ciclos de p t�m comprimento no m�ximo 2. Logo o termo pode ser constru�do do termo associado � identidade (que vale 1) se fizermos invers�es disjuntas. Cada invers�o troca um 1*1 por um -x*x = -x^2, mas tamb�m multiplica por -1 por causa da invers�o da paridade. Logo o termo � multiplicado por x^2, certamente n�o-negativos.

Se uma permuta��o p n�o-involutiva tem um n�mero �mpar de pontos n�o-fixos, ent�o sua inversa q gera um termo que � igual em m�dulo ao termo gerado por p, mas tem sinal oposto, logo os dois termos se cancelam. Agora considere todas as permuta��es com k pontos n�o fixos, k par. Ent�o os termos gerados por essas permuta��es s�o da forma 2*(-1)^m*P, onde m � 0 ou 1 e P � um produt�rio de um n�me
s associados � permuta��o que n�o s�o 1 e que est�o na metade superior da matriz -- escolher os termos daqui � sempre poss�vel se mexermos no m apropriadamente).

Eu acho que n�o sei passsar muito daqui. A minha id�ia era agrupar esses �ltimos termos com os termos quadrados perfeitos de mesmo grau para formar novos quadrados perfeitos maiores, assim retirando os termos que podem ser negativos de circula��o.

Pergunta 1: � sempre poss�vel agrupar os termos dessa forma?

Pergunta 2: m depende s� de k (ou melhor ainda, n�o depende de nada)? Se sim, a resposta � pergunta 1 parece ser bem mais f�cil.

Pergunta 3 (ao Morgado): Na sua opini�o, isso est� no n�vel do ITA?

Se eu tiver alguma id�ia interessante sobre as perguntas 1 e 2, eu mando para a lista.

[]s,

-- 
F�bio "ctg \pi" Dias Moreira

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