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