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