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