Bom, a conjectura do Gabriel é sim um teorema (Teorema de Birkhoff-von Neumann), mas parece que as demonstrações passam por teoria dos grafos. Uma delas está aqui:
http://math.uncc.edu/~ghetyei/courses/old/F07.3116/birkhofft.pdf (a parte mais chata, da qual falamos aqui, está no primeiro Lema, que usa o Teorema de Hall; o resto pode ser feito com o argumento do Ponce) outra aqui http://planetmath.org/encyclopedia/ProofOfBirkoffVonNeumannTheorem.html (a parte mais chata vem após "we now prove the more difficult direction") (Matrizes cujas linhas e colunas têm a mesma soma 1 são "Double Stochastic"; para conectar uma coisa coma outra, divida todos os elementos da nossa matriz aqui por S=soma de uma coluna ou linha) Abraço, Ralph 2011/2/16 Ralph Teixeira <ralp...@gmail.com>: > 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 =========================================================================
