[obm-l] Re: [obm-l] Determinante Anti-Simétrico

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

Bom, eu tenho tentado tirar alguma conclusão através da definição de
determinante a partir de permutações...

já vou avisando que a mensagem é um pouco longa e eu não cheguei na
resposta, mas talvez seja interessante dar uma lida, a idéia parece ser boa.

se X é n x n, então
det(X) = somatório{f permutação} sign(f)*[produtório{i=1..n} X(i, f(i))]

onde sign(f) é 1 se a permutação é par ou -1 se ela é ímpar...
bom, eu não lembrava muito dessas coisas sobre permutações então encontrei
uma referência legal:

http://www.maths.lancs.ac.uk/dept/coursenotes/m225ril99/chapter5/chap5/node3.html

pra quem está enferrujado e não lembra o que é um ciclo:
http://www.maths.lancs.ac.uk/dept/coursenotes/m225ril99/chapter5/chap5/node2.html

Ok, agora vamos ao fato que eu quero chegar:

p é uma permutação
Defina
I(p) := {conjunto dos ciclos de comprimento ímpar de p}
P(p) := {conjunto dos ciclos de comprimento par de p}
p^(-1) := inversa de p, ou seja p^(-1)(p(i)) = i para todo i

Considere a relação ~ entre permutações, definida a seguir
p ~ q <=> [P(p) = P(q) e c está em I(p) <=> c ou c^(-1) está em I(q)]

ou seja, definimos que duas permutações estão relacionadas se seus ciclos
pares são iguais e se os ciclos ímpares são iguais ou inversos.

dá pra ver que p ~ p, p ~ q => q ~ p e p ~ q, q ~ u => p ~ u, ou seja ~ é
uma relação de equivalência.

podemos então particionar o conjunto de permutações utilizando a relação ~.

algumas observações:
há classes solitárias, representadas por permutações que só tem permutações
pares e portanto só possuem um elemento.
numa mesma classe o sinal de cada permutação é o mesmo já que o que importa
é o tamanho dos ciclos e estes são iguais dentro da classe.

ok, agora a parte legal, uma classe não solitária colabora com 0 na soma do
determinante de uma matriz anti-simétrica.

para ver isso tome p um representante de uma classe C não solitária, ou
seja, p tem k > 0 ciclos de tamanho ímpar.

Defina Prod(f) := [produtório{i=1..n} X(i, f(i))]
somatório{f permutação, f ~ p} sign(f)*Prod(f) =
sign(p) * somatório{f permutação, f ~ p} Prod(f)

note que, como p tem k ciclos ímpares, podemos obter todas as permutações
equivalentes a p invertendo esses ciclos.
ao inverter um ciclo ímpar, por exemplo (a_1 a_2 ... a_{2m+1}), temos
(a_{2m+1}  a_{2m-1} ... a_2 a_1).

como X é anti-simétrica A(a_i, a_{i+1}) = -A(a_{i+1}, a_i).

se p possui um ponto fixo então há um ciclo de tamanho 1, toda permutação f
equivalente a p tem Prod(f) = 0 e não há nada para provar.

 quando invertemos exatamente um ciclo (ímpar) de p para obter uma
permutação f, |Prod(f)| permanece o mesmo, mas o sinal é trocado (estamos
trocando o sinal de um número ímpar de fatores do produtório), ou seja
Prod(f) = -Prod(p).

dessa forma se invertermos um número ímpar de ciclos ímpares de p
obtemos -Prod(p), se invertermos um número par de ciclos ímpares de p
obtemos Prod(p).

podemos inverter um número ímpar de ciclos ímpares de
Binomial[k, 1] + Binomial[k, 3] + Binomial[k, 5] + ...
maneiras, e um nr. par de ciclos ímpares de
Binomial[k, 0] + Binomial[k, 2] + Binomial[k, 4] + ...
maneiras.

sabemos que Binomial[k-1, i] + Binomial[k-1, i+1] = Binomial[k, i+1].
logo,
Binomial[k, 1] + Binomial[k, 3] + Binomial[k, 5] + ... =
(Binomial[k-1, 0] + Binomial[k-1, 1]) +
(Binomial[k-1, 1] + Binomial[k-1, 2]) + ... = 2^(k-1),

logo Binomial[k, 0] + Binomial[k, 2] + Binomial[k, 4] + ... = 2^(k-1)

isso nos diz que o número de termos Prod(p) na soma das permutações da
classe C é 2^(k-1) e o número de termos -Prod(p) também é 2^(k-1) e então a
soma final é 0.

para calcular o determinante podemos restringir a soma de Prod(f) onde f só
possui ciclos de tamanho par, será que isso ajuda no problema?

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