[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Determinante de 0s e 1s
Acabei de lembrar da enciclopédia de sequências de inteiros, aliás um site extremamente interessante, especialmente pra quem gosta de problemas do tipo "qual o próximo termo da sequência...".
A página relevante é:
e lá você encontra diversos links com mais informações sobre o problema.
Num desses links eu vi um resultado que dá um problema bonitinho:
Dada uma matriz complexa A, nxn e com entradas de módulo <= 1, prove que |det(A)| <= raiz(n^n) e exiba uma matriz A para a qual vale a igualdade.
Dica e problema correlato: Calcule o produto dos comprimentos de todos os lados e todas as diagonais de um n-gono regular convexo inscrito no círculo unitário (o produto tem n(n-1)/2 termos).
[]s,
Claudio.
| De: |
owner-obm-l@mat.puc-rio.br |
| Para: |
obm-l@mat.puc-rio.br |
| 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"
> To: "obm-l"
> 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.
>