Matriz duplamente estocástica

Matriz duplamente estocástica (Redirecionado do teorema de Birkhoff-Von Neumann) Ir para a navegação Ir para a pesquisa Em matemática, especialmente em probabilidade e combinatória, uma matriz duplamente estocástica (também chamada de matriz bistocástica), é uma matriz quadrada {estilo de exibição X=(x_{eu j})} de números reais não negativos, cada uma de cujas linhas e colunas soma 1,[1] ou seja, {soma de estilo de exibição _{eu}x_{eu j}=soma _{j}x_{eu j}=1,} Desta forma, uma matriz duplamente estocástica é estocástica esquerda e estocástica direita.[1][2] De fato, qualquer matriz que seja estocástica à esquerda e à direita deve ser quadrada: se cada linha soma a um então a soma de todas as entradas na matriz deve ser igual ao número de linhas, e como o mesmo vale para colunas, o número de linhas e colunas deve ser igual.[1] Conteúdo 1 Politopo de Birkhoff 2 Teorema de Birkhoff-von Neumann 3 Outras propriedades 4 Prova do teorema de Birkhoff-von Neumann 4.1 Generalizações 5 Veja também 6 Referências 7 Links externos Politopo de Birkhoff Artigo principal: Politopo de Birkhoff A classe de {estilo de exibição n vezes n} matrizes duplamente estocásticas é um politopo convexo conhecido como politopo de Birkhoff {estilo de exibição B_{n}} . Usando as entradas da matriz como coordenadas cartesianas, encontra-se em um {estilo de exibição (n-1)^{2}} -subespaço afim dimensional de {estilo de exibição n^{2}} -espaço euclidiano dimensional definido por {estilo de exibição 2n-1} restrições lineares independentes especificando que as somas de linha e coluna são todas iguais. (Há {estilo de exibição 2n-1} restrições em vez de {estilo de exibição 2n} porque uma dessas restrições é dependente, pois a soma das somas das linhas deve ser igual à soma das somas das colunas.) Além disso, as entradas são todas restritas a serem não negativas e menores ou iguais a um.

Teorema de Birkhoff-von Neumann Teorema de Birkhoff-von Neumann (muitas vezes conhecido simplesmente como teorema de Birkhoff[3][4][5]) afirma que o politopo {estilo de exibição B_{n}} é o casco convexo do conjunto de {estilo de exibição n vezes n} matrizes de permutação, e ainda que os vértices de {estilo de exibição B_{n}} são precisamente as matrizes de permutação. Em outras palavras, E se {estilo de exibição X} é uma matriz duplamente estocástica, então existe {estilo de exibição teta _{1},ldots ,teta _{k}geq 0,soma _{i=1}^{k}teta _{eu}=1} e matrizes de permutação {estilo de exibição P_{1},ldots ,P_{k}} de tal modo que {estilo de exibição X = theta _{1}P_{1}+cdots +teta _{k}P_{k}.} (Tal decomposição de X é conhecida como uma 'combinação convexa'.) Uma prova do teorema com base no teorema do casamento de Hall é dada abaixo.

Esta representação é conhecida como a decomposição de Birkhoff-von Neumann, e pode não ser único. É frequentemente descrito como uma generalização de valor real do teorema de Kőnig, onde a correspondência é estabelecida através de matrizes de adjacência de grafos.

Outras propriedades O produto de duas matrizes duplamente estocásticas é duplamente estocástico. No entanto, a inversa de uma matriz não singular duplamente estocástica não precisa ser duplamente estocástica (na verdade, a inversa é duplamente estocástica se tiver entradas não negativas). A distribuição estacionária de uma cadeia de Markov finita aperiódica irredutível é uniforme se e somente se sua matriz de transição for duplamente estocástica. O teorema de Sinkhorn afirma que qualquer matriz com entradas estritamente positivas pode ser duplamente estocástica por pré- e pós-multiplicação por matrizes diagonais. Por {estilo de exibição n=2} , todas as matrizes bistocásticas são unistocásticas e ortostocásticas, mas para maiores {estilo de exibição m} Este não é o caso. A conjectura de Van der Waerden de que o mínimo permanente entre todas as n × n matrizes duplamente estocásticas é {estilo de exibição m!/n^{n}} , alcançado pela matriz para a qual todas as entradas são iguais a {estilo de exibição 1/n} .[6] Provas desta conjectura foram publicadas em 1980 por B. Gyires[7] e em 1981 por G. P. Egorychev[8] e D. EU. Falikman;[9] para este trabalho, Egorychev e Falikman ganharam o Prêmio Fulkerson em 1982.[10] Prova do teorema de Birkhoff–von Neumann Seja X uma matriz duplamente estocástica. Então mostraremos que existe uma matriz de permutação P tal que xij ≠ 0 sempre que pij ≠ 0. Assim, se λ for o menor xij correspondente a um pij diferente de zero, a diferença X – λP será um múltiplo escalar de uma matriz duplamente estocástica e terá pelo menos uma célula zero a mais que X. Assim, podemos reduzir sucessivamente o número de células diferentes de zero em X removendo múltiplos escalares de matrizes de permutação até chegarmos à matriz zero, nesse ponto teremos construído uma combinação convexa de matrizes de permutação igual ao X original.[3] Por exemplo se {estilo de exibição X={fratura {1}{12}}{começar{pmatrix}7&0&5\2&6&4\3&6&3end{pmatrix}}} então {estilo de exibição P={começar{pmatrix}0&0&1\1&0&0\0&1&0end{pmatrix}}} , {estilo de exibição lambda ={fratura {2}{12}}} , e {estilo de exibição X-lambda P={fratura {1}{12}}{começar{pmatrix}7&0&3\0&6&4\3&4&3end{pmatrix}}} .

Prova: Construa um grafo bipartido no qual as linhas de X estão listadas em uma parte e as colunas na outra, e em qual linha i está conectado à coluna j iff xij ≠ 0. Seja A qualquer conjunto de linhas, e defina A' como o conjunto de colunas unidas a linhas em A no grafo. Queremos expressar os tamanhos |UMA| e |A'| dos dois conjuntos em função do xij.

Para cada i em A, a soma sobre j em A' de xij é 1, uma vez que todas as colunas j para as quais xij ≠ 0 estão incluídos em A', e X é duplamente estocástico; por isso |UMA| é a soma de todos os i ∈ A, j ∈ A' de xij.

Enquanto isso |A'| é a soma de tudo i (seja ou não em A) e todo j em A' de xij ; e esta é ≥ a soma correspondente na qual os i estão limitados a linhas em A. Por isso |A'| ≥ |UMA|.

Segue-se que as condições do teorema do casamento de Hall são satisfeitas, e que podemos, portanto, encontrar um conjunto de arestas no grafo que unem cada linha em X a exatamente uma (distinto) coluna. Essas arestas definem uma matriz de permutação cujas células diferentes de zero correspondem a células diferentes de zero em X. ∎ Generalizações Existe uma generalização simples para matrizes com mais colunas e linhas de modo que a i-ésima linha seja igual a ri (um número inteiro positivo), as somas das colunas são iguais a 1, e todas as células são não negativas (a soma das somas das linhas sendo igual ao número de colunas). Qualquer matriz nesta forma pode ser expressa como uma combinação convexa de matrizes na mesma forma composta de 0s e 1s. A prova é substituir a i-ésima linha da matriz original por ri linhas separadas, cada igual à linha original dividido por ri ; aplicar o teorema de Birkhoff à matriz quadrada resultante; e no final recombinar aditivamente as ri linhas em uma única linha i.

Da mesma forma, é possível replicar colunas e linhas, mas o resultado da recombinação não é necessariamente limitado a 0s e 1s. Uma generalização diferente (com uma prova significativamente mais difícil) foi apresentado por R. M. Carron et ai.[4] Veja também Matriz estocástica Matriz unistocástica Referências ^ Saltar para: a b c Gagniuc, Paul A. (2017). Cadeias de Markov: Da Teoria à Implementação e Experimentação. EUA, Nova Jersey: John Wiley & Sons. pp. 9-11. ISBN 978-1-119-38755-8. ^ Marechal, Olkin (1979). Desigualdades: Teoria da Majorização e Suas Aplicações. pp. 8. ISBN 978-0-12-473750-1. ^ Saltar para: a b teorema de Birkhoff, notas de Gabor Hetyei. ^ Saltar para: a b R. M. Carron et ai., 'Não quadrado "Duplamente Estocástico" Matrizes, 1996. ^ W. B. Jurkat e H. J. Arrepio, "Ranks de termos e permanentes de matrizes não negativas" (1967). ^ van der Waerden, B. eu. (1926), "tarefa 45", Jbr. Alemão. Clube de Matemática., 35: 117. ^ Gyires, B. (1980), "A fonte comum de várias desigualdades sobre matrizes duplamente estocásticas", Publicações Matemáticas Instituto de Matemática da Universidade de Debrecen, 27 (3-4): 291-304, SENHOR 0604006. ^ Egorychev, G. P. (1980), Solução problemática van-der-Vardena dlya permanenteov (em russo), Krasnoyarsk: Atrasos. Nauk SSSR Siberiano. Departamento. Inst. Fiz., p. 12, SENHOR 0602332. Egorychev, G. P. (1981), "Prova da conjectura de van der Waerden para permanentes", Akademiya Nauk SSSR (em russo), 22 (6): 65-71, 225, SENHOR 0638007. Egorychev, G. P. (1981), "A solução do problema de van der Waerden para permanentes", Avanços em Matemática, 42 (3): 299-305, doi:10.1016/0001-8708(81)90044-X, SENHOR 0642395. ^ Falikman, D. EU. (1981), "Prova da conjectura de van der Waerden sobre a permanente de uma matriz duplamente estocástica", Akademiya Nauk Soyuza SSR (em russo), 29 (6): 931–938, 957, SENHOR 0625097. ^ Prêmio Fulkerson, Sociedade de Otimização Matemática, recuperado 2012-08-19. Brualdi, Ricardo A. (2006). Classes de matrizes combinatórias. Enciclopédia de Matemática e Suas Aplicações. Volume. 108. Cambridge: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001. Links externos Página PlanetMath sobre o teorema de Birkhoff–von Neumann Página PlanetMath sobre a prova do teorema de Birkhoff–von Neumann ocultar classes vte Matrix Entradas explicitamente restritas AlternantAnti-diagonalAnti-HermitianAnti-simétricaArrowheadBandBidiagonalBisymmetricBlock-diagonalBlockBlock tridiagonalBooleanCauchyCentrometricConferenceComplex HadamardCopositivoDiagonalmente dominanteDiagonalDiscre te Fourier TransformadaElementarEquivalenteFrobeniusPermutação generalizadaHadamardHankelHermitianoHessenbergHollowIntegerLogicalUnidade matricialMetzlerMooreNãonegativoPentadiagonalPermutaçãoPersimétricoPolinômioQuaterniônicoAssinaturaSkew-HermitianoSkew-simétricoSkylineEsparsoSylvesterSimétricoToeplitzTriangularTridiagonalVandermondeWalshZ Troca constanteHilbert IdentityLehmerOf unsPascalPauliRedhefferShiftZero Condições em autovalores ou autovetores CompanionConvergentDefectiveDefiniteDiagonalizableHurwitzPositive-definiteStieltjes Condições satisfatórias em produtos ou inversos CongruentIdempotent ou ProjectionInvertibleInvolutoryNilpotentNormalOrthogonalUnimodularUnipotentUnitaryTotalmente unimodularPesagem Com aplicações específicasAdjugateAlternating signAugmentedBézout CarlemanCartanCirculanteCofatorComutaçãoConfusãoCoxeterDistânciaDuplicação e eliminaçãoDistância euclidianaFundamental (equação diferencial linear)GeradorGramHessianHouseholderJacobianMomentPayoffPickRandomRotationSeifertShearSimilaritySimplecticTotally PositiveTransformation Usado em estatística CenteringCorrelationCovarianceDesignDuply StochasticFisher informationHatPrecisionStochasticTransition Usado em teoria dos grafos AdjacencyBiadjacencyDegreeEdmondsIncidenceLaplacianSeidel adjacencyTutte Usado em ciência e engenharia Cabib bo–Kobayashi–MaskawaDensidadeFundamental (visão computacional)Fuzzy associativeGammaGell-MannHamiltonianIrregularSobreposiçãoSSTransição de estadoSubstituiçãoZ (química) Termos relacionados Forma normal de JordanIndependência linearMatriz exponencialRepresentação da matriz de seções cônicasMatriz perfeitaPseudoinversaForma escalonada de linhasWronskian Mathematics portalLista de matrizesCategoria:Categorias de matrizes: Matrizes