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