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

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

Bem, existe a desigualdade de Hadamard:
|det(A)| <= produto dos modulos dos vetores-linha (ou coluna) de A ==>
|det(A)| <= n^(n/2), o que eh uma pequena melhora, pois (n!)^2 >= n^n para todo n em N.
No nosso caso, levando em conta que existe no maximo uma linha ou coluna de modulo raiz(n) (caso contrario o determinante se 
anularia), ainda podemos escrever:
|det(A)| <= raiz(n*(n-1)^(n-1))
Mas ainda estamos longe. Pra n = 10 isso dah 62243,11, bem mais do que 320, que eh o que consta como maximo em:
http://tingilinde.typepad.com/starstuff/2005/11/significant_int.html

Outra ideia pra esse problema eh tentar encontrar o n-paralelepipedo de maior n-volume com um vertice na origem e com os n vertices 
adjacentes da forma (a_1,a_2,...,a_n) com a_i em {0,1}. Olhando pequenos casos, eu obtive:
n = 2 ==> Vmax = 1
n = 3 ==> Vmax = 2 (vertices (0,1,1), (1,0,1) e (1,1,0))
 
Pra n = 10 eu usei a funcao "Solver" do Excel e achei uma matriz 10x10 com determinante 320.
A matriz eh:
0	1	1	0	0	0	1	0	1	1
1	0	0	0	1	0	1	1	1	0
1	1	0	1	1	0	0	1	0	1
1	1	1	0	1	1	1	0	0	0
0	1	0	1	0	1	1	1	1	0
0	0	1	1	1	0	1	1	0	0
0	0	0	1	1	1	0	0	1	1
1	0	0	1	0	0	1	0	0	1
1	0	1	0	0	1	0	1	0	1
1	1	1	1	0	0	0	0	1	0

Talvez permutando linhas e colunas da matriz acima possamos achar uma matriz equivalente (com o mesmo determinante) que exiba 
algumas simetrias que nos permitam detectar uma lei de formacao e, com isso, dar uma prova por inducao.

[]s,
Claudio.

---------- Cabeçalho original -----------

De: owner-obm-l@mat.puc-rio.br
Para: obm-l@mat.puc-rio.br
Cópia: 
Data: Wed, 6 Dec 2006 18:27:52 -0200
Assunto: Re: [obm-l] Determinante de 0s e 1s

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


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