[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Problema sobre matrizes de permutação
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.comescreveu:
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 01 0 01 0 0
0 1 0 + 0 0 1 + 0 0 1
0 0 10 1 00 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
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Problema sobre matrizes de permutação
Li as provas do teorema, bem legal, estou começando a saber um pouco
mais de fluxo agora.
E me deparei com esse artigo do Onofre que explica esse teorema de
Hall e que foi bem útil para eu entender as provas:
http://www.obm.org.br/export/sites/default/semana_olimpica/docs/2005/maxflow_onofre.pdf
Gabriel Dalalio
Em 16 de fevereiro de 2011 14:58, Gabriel Dalalio
gabrieldala...@gmail.com escreveu:
Legal, vou ler agora esses links ae sobre o teorema.
Obrigado ae Ralph.
Gabriel Dalalio
Em 16 de fevereiro de 2011 13:52, Ralph Teixeira ralp...@gmail.com escreveu:
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
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Problema sobre matrizes de permutação
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
=
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Problema sobre matrizes de permutação
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
=
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Problema sobre matrizes de permutação
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
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Problema sobre matrizes de permutação
Legal, vou ler agora esses links ae sobre o teorema.
Obrigado ae Ralph.
Gabriel Dalalio
Em 16 de fevereiro de 2011 13:52, Ralph Teixeira ralp...@gmail.com escreveu:
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
=
