Mas porque depois de riscar algumas colunas nunca vai ficar uma linha só com zeros?
Gabriel Dalalio Em 16 de fevereiro de 2011 12:12, Rogerio Ponce <abrlw...@gmail.com> escreveu: > 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 =========================================================================