Re: [obm-l] Determinante de 0s e 1s

["Marcelo Salhab Brogliato" <k4ss@xxxxxxxxxx>]

Olá,

vamos propor o seguinte lema: det(A) <= n!, onde n é a dimensao da matriz 
quadrada.

para n=1, temos: det(A) <= 1, ok!
para n=2, temos: det(A) = ab - cd <= ab <= 1 <= 2!

vamos supor que vale para k, e vamos mostrar que vale para k+1.
Seja A uma matriz quadrada de dimensao k+1, entao, aplicando o teorema de 
laplace em uma fila qualquer, ficamos com:
det(A) = Somatório(i=1 até k+1, a_i * det(B_i)), onde a_i sao os elementos 
da fila, e det(B_i) os determinantes, conforme o teorema.
mas, por hipotese, det(B_i) <= k! (pois B_i tem dimensao k), logo: det(A) <= 
Somatório(i=1 até k+1, k!*a_i) <= Somatório(i=1 até k+1, k!) = (k+1) * k! = 
(k+1)! (cqd)

portanto, esta provado que qualquer matriz quadrada de dimensao nxn com 
entradas pertencentes a {0, 1} tem determinante <= n!

tem como melhorar essa desigualdade?
inicialmente eu pensei <= 1, mas nao saiu a demonstracao e me induziu a 
tentar <= n, mas tb nao saiu e me induziu a mostrar <= n!, e saiu!

abraços,
Salhab


----- Original Message ----- 
From: "claudio.buffara" <claudio.buffara@terra.com.br>
To: "obm-l" <obm-l@mat.puc-rio.br>
Sent: Wednesday, December 06, 2006 9:55 AM
Subject: [obm-l] Determinante de 0s e 1s


Vi esse aqui num site sobre curiosidades numericas:

Qual o valor maximo do determinante de uma matriz 10x10 cujas entradas 
pertencem a {0,1}?
Generalize para uma matriz nxn.

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


-- 
No virus found in this incoming message.
Checked by AVG Free Edition.
Version: 7.1.409 / Virus Database: 268.15.3/562 - Release Date: 1/12/2006


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