Ihnnn, Ihonnn!!!
E' verdade, Ralph!
Ei Gabriel, voce tambem tem razao!
...de volta 'a prancheta...
[]'s
Rogerio Ponce
Em 16 de fevereiro de 2011 13:02, Ralph Teixeira <ralp...@gmail.com>escreveu:
> Oi, Ponce.
>
> Concordo que, por indução, basta mostrar que existe UMA matriz de
> permutação "dentro" da matriz dada. Acho que existe sim. Mas
> demonstrar a presença desta escolha parece ser sutil....
>
> Por exemplo, começando por:
>
> 1 0 1 0
> 0 1 1 0
> 1 1 0 0
> 0 0 0 2
>
> Se você pegar o 1 em a_11, e em seguida pegar o 1 em a_22... de
> repente você fica sem opções para completar a matriz de permutação com
> as linhas e colunas não riscadas... Daria certo usando a_11, a_23,
> a_32 e a_44, mas como provar isto em geral?
>
> Abraço,
> Ralph
>
>
> 2011/2/16 Rogerio Ponce <abrlw...@gmail.com>:
> > Ola' Gabriel,
> > voce sempre pode decompor a matriz original NxN, com soma K nas linhas e
> > colunas, em matrizes de permutacao.
> > Veja uma forma de se obter um conjunto de matrizes de permutacao que
> > satisfaz ao problema:
> >
> > Escolha um elemento qualquer, maior que zero, da 1a linha da matriz
> > original.
> > Diminua este elemento de 1, e "risque" , na matriz original, a linha e
> > coluna a que ele pertence.
> > Coloque "1" na matriz de permutacao, na mesma posicao (linha e coluna).
> >
> > Considere apenas as linhas e colunas "nao riscadas" da matriz original,
> e
> > repita mais N-1 vezes o processo acima.
> >
> > Pronto! Aqui, neste ponto, voce acabou de montar uma matriz de
> permutacao, e
> > a matriz original foi transformada em outra, com soma K-1 nas linhas e
> > colunas.
> >
> > Depois de executar K vezes todo o processo acima, voce obtem uma
> > decomposicao que satisfaz ao problema.
> >
> > []'s
> > Rogerio Ponce
> >
> > PS: e' facil verificar que todos os passos sao possiveis.
> >
> >
> >
> > Em 15 de fevereiro de 2011 04:07, Gabriel Dalalio <
> gabrieldala...@gmail.com>
> > escreveu:
> >>
> >> Concordo, o produto de duas matrizes de permutação é uma matriz de
> >> permutação.
> >> Mas não consegui ver como usar isso no problema que eu falei.
> >> O que eu quero saber é se toda matriz quadrada de números inteiros não
> >> negativos em que a soma de todas as linhas e colunas são iguais pode
> >> ser escrita como uma soma
> >> de matrizes de permutação, por exemplo a matriz:
> >> 3 0 0
> >> 0 1 2
> >> 0 2 1
> >> tem soma nas linhas e nas colunas igual a 3, e ela pode ser escrita
> como:
> >> 1 0 0 1 0 0 1 0 0
> >> 0 1 0 + 0 0 1 + 0 0 1
> >> 0 0 1 0 1 0 0 1 0
> >>
> >> Se o produto de duas matrizes de permutação tem a ver com o problema
> >> mesmo explica melhor ai que eu não entendi.
> >>
> >> Abraço,
> >> Gabriel Dalalio
> >>
> >> Em 14 de fevereiro de 2011 19:47, Marcelo Salhab Brogliato
> >> <msbro...@gmail.com> escreveu:
> >> > Olá, Gabriel,
> >> > estou com a impressão que o produto de duas matrizes de permutação é
> uma
> >> > matriz de permutação.
> >> > Isto é, a operação de multiplicação é fechada nas matrizes de
> >> > permutação.
> >> > Se isso for verdade, então, sempre teremos apenas 1's.
> >> > O que invalida sua idéia.
> >> > Vamos tentar:
> >> > C = AB, onde A e B são permutações.
> >> > Então:
> >> > c_ij = Sum{k=1..n} a_ik * b_kj
> >> > Para cada linha (isto é, analisando para i fixo):
> >> > Veja que com i fixo, estamos vendo sempre a mesma linha de A.
> >> > Esta linha tem apenas um 1.
> >> > Ao mesmo tempo, estamos passando por colunas de B, que também possuem
> um
> >> > 1.
> >> > Quando os "uns" se casarem, temos c_ij = 1.
> >> > Logo, provamos que cada linha de C tem apenas um 1.
> >> > Falta provarmos que isso também ocorre para cada coluna.
> >> > Usando a mesma argumentação anterior, mostramos que cada coluna tem
> >> > apenas
> >> > um 1.
> >> > Desta maneira, a operação de multiplicação é fechada em matrizes
> >> > simétricas.
> >> > Abraços,
> >> > Salhab
> >> >
> >> > 2011/2/14 Gabriel Dalalio <gabrieldala...@gmail.com>
> >> >>
> >> >> Matriz de permutação é uma matriz quadrada binária contendo
> exatamente
> >> >> uma vez o numero 1 em cada linha e coluna.
> >> >> Toda matriz quadrada de números inteiros não negativos em que a soma
> >> >> de todas as linhas e colunas são iguais pode ser escrita como uma
> soma
> >> >> de matrizes de permutação?
> >> >>
> >> >> Eu tava pensando nisso esses dias por causa de um problema de
> >> >> programação e achei que isso poderia ser verdade, mas não conseguir
> >> >> concluir nada ainda.
> >> >> Se alguém conseguir provar ou achar um contra-exemplo comenta ai,
> >> >> obrigado.
> >> >>
> >> >> Gabriel Dalalio
> >> >>
> >> >>
> >> >>
> =========================================================================
> >> >> Instruções para entrar na lista, sair da lista e usar a lista em
> >> >> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> >> >>
> >> >>
> =========================================================================
> >> >
> >> >
> >>
> >>
> =========================================================================
> >> Instruções para entrar na lista, sair da lista e usar a lista em
> >> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> >>
> =========================================================================
> >
> >
>
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =========================================================================
>
