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