Re: [obm-l] RE: [obm-l] Quadrado M�gico

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 06.04.05 22:14, kleinad2@globo.com at kleinad2@globo.com wrote:

> Oi, Cl�udio
> 
> '>'-- Mensagem Original --
> '>'Date: Wed,  6 Apr 2005 17:46:51 -0300
> '>'Subject: [obm-l] Quadrado M�gico
> '>'From: "claudio.buffara" <claudio.buffara@terra.com.br>
> '>'To: "obm-l" <obm-l@mat.puc-rio.br>
> '>'Reply-To: obm-l@mat.puc-rio.br
> '>'
> '>'
> '>'Acho que sei como demonstrar que L_i (1<=i<=n), C_j (1<=j<=n-1), T e
> S s�o
> '>'funcionais lineares L.I.
> '>'
> '>'Suponhamos que existam escalres a_i (1<=i<=n), b_j (1<=j<=n), c e d
> tais
> '>'que o funcional linear:
> '>'F = SOMA(1...n) a_i*L_i + SOMA(1...n-1) b_j*C_j + c*T + d*S
> '>'seja identicamente nulo.
> '>'
> '>'Seja A(i,j) a matriz cujo coeficiente (i,j) � 1 e todos os demais s�o
> 0.
> '>'
> '>'F(A(1,n)) = 0 ==> a_1 + d = 0
> '>'F(A(n,n)) = 0 ==> a_n + c = 0
> '>'F(A(k,n)) = 0 para 2 <= k <= n-1 ==>  a_k = 0.
> '>'
> '>'Ou seja, j� podemos escrever:
> '>'F = -d*L_1 - c*L_n + SOMA(1..n-1) b_j*C_j + c*T + d*S.
> '>'
> '>'F(A(1,1)) = 0 ==> -d + b_1 + c = 0
> '>'F(A(2,1)) = 0 ==> b_1 = 0 ==> c = d
> '>'F(A(k+1,k)) = 0 para 2 <= k <= n-2 ==> b_k = 0
> '>'F(A(n,n-1)) = 0 ==> -c + b_(n-1) = 0
> '>'
> '>'Assim:
> '>'F = c*(-L_1 - L_n + C_(n-1) + T + S).
> '>'
> '>'Finalmente, F(A(2,2)) = 0 ==> c = 0.
> '>'
> '>'Logo, a_i = b_j = c = d = 0 e, portanto, os 2n+1 funcionais acima s�o
> L.I.
> '>'e, portanto, o espa�o dos quadrados m�gicos nxn tem dimens�o n^2 - (2n+1)
> '>'= n^2 - 2n - 1.
> '>'
> '>'[]s,
> '>'Claudio.
> 
> A demonstra��o da independ�ncia dos funcionais est� ok, mas isso mostra
> que se Z � o conjunto das matrizes n x n tais que todos esses funcionais
> se anulam, ent�o Z (na verdade um subespa�o de M(nxn)) � tal que dim Z =
> dim M(nxn) - dim(F), onde por F � o subespa�o gerado pelos 2n + 2 funcionais
> em quest�o no dual de M(nxn), isto �, dim Z = n^2 - (2n + 1) = n^2 - 2n
> - 1. Este resultado � mais geral: Se Z � o espa�o dos zeros dos funcionais
> f_1, ..., f_k, que est�o no dual de V, ent�o dim Z = dim V - dim (f_1, ...,
> f_k).
> 
> Mas claramente a matriz A com todas as coordenadas 1 satisfaz L_1(A) = ...
> = L_n(A) = C_1(A) = ... = C_n(A) = T(A) = S(A) = n <> 0, assim dim Q >=
> dim Z + 1 (Q = conjunto das matrizes A que satisfazem L_1(A) = ... = L_n(A)
> = C_1(A) = ... = C_n(A) = T(A) = S(A), ou seja, dos quadrados m�gicos, um
> subespa�o vetorial). D� para provar que dim Q <= dim Z + 1 (naturalmente
> um resultado mais geral v�lido para quaisquer funcionais), logo dim Q =
> dim Z + 1 = n^2 - 2n.
> 
> []s,
> Daniel
> 
Claro!

Eu esqueci justamente de levar em conta a condicao de quadrado magico...

Uma forma mais elementar de ver isso eh observar que o espaco dos quadrados
magicos eh justamente o espaco-solucao do seguinte sistema de 2n equacoes
lineares homogeneas (e linearmente independentes, como demonstrado acima) em
n^2 incognitas:
L_1 - T = 0
L_2 - T = 0
...
L_n - T = 0
C_1 - T = 0
C_2 - T = 0
...
C_(n-1) - T = 0
S - T = 0
Logo, o espaco solucao do sistema (igual a Q) tem dimensao n^2 - 2n.

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