Arquivo da tag: Álgebra

As pontes de Konigsberg

Rookie

Quando eu era garoto, conheci um problema de lógica e desenho que deve ser famoso. Apresentaram-me a seguinte figura:

Sendo o objetivo do problema desenhar essa figura sem tirar o lápis do papel e sem repetir os caminhos. Após algumas tentativas, cheguei a um caminho correto, desenhava feliz a casa com o X segundo as regras. Foi então que me foi apresentado uma variante do problema, “mais difícil” segundo aquele que me passou. Fui desafiado a desenhar essa outra figura:

Passei anos tentando, vez ou outra, resolver esse problema. Deixei de dar atenção a ele depois dos treze anos e, aos dezoito, descobri que todas aquelas tentativas fúteis de desenhar essa estranha flor foram justificadas: o problema não tem solução, é impossível encontrar um caminho que desenhe essa figura sem tirar o lápis do papel e sem repetir caminhos.

Mal sabia eu que esse mesmo problema, ou quase, havia sido resolvido por Leonhard Euler na cidade de Konigsberg, Prússia, em 1735. Euler garante com tranquilidade um lugar no top 3 da matemática, ostentando ainda hoje o título de matemático com maior número de publicações, tendo passado os dez últimos anos de sua vida cego (e publicando matemática, claro) e, segundo dizem, foi um excelente pai de seus cinco filhos. Ao passar pela cidade de Konigsberg na Prússia, Euler foi desafiado com um problema típico da cidade. Ela possuía duas ilhas no rio ligadas entre si e com a terra por sete pontes, como mostra a figura descaradamente roubada da Wikipédia:

E o desafio era atravessar as sete pontes sem repetir nenhuma. Você pode se divertir tentando, como os habitantes da cidade faziam, mas Euler decidiu pensar no problema de maneira mais profunda. A primeira coisa que fez foi se livrar do que estava sobrando: prédios, ilhas, estradas, apenas as pontes importavam:

Numerei as massas de terra para que a identificação com o desenho seguinte fique mais clara. Não contente, Euler percebeu que podia simplificar ainda mais o diagrama escrevendo-o da seguinte forma:

A vantagem desse formato, minimalista ao extremo, é nos permitir focarmos apenas no que realmente importa. E esse foi o raciocínio de Euler: quero atravessar todas essas linhas sem jamais repetir nenhuma. Rapidamente, ele notou que, para não repetir linhas, todo ponto a que ele chegasse deveria permitir uma saída, exceto, claro, pelos pontos inicial e final. Ou seja, para todo o ponto, exceto os de começo e fim, cada entrada deve possuir uma saída correspondente: ele deve possuir um número par de conexões. Se ele possui um número ímpar, digamos, 3; eu entrarei nele, sairei dele e, na próxima entrada, não terei como sair, eu travei e, ao menos que ele seja meu ponto final, perdi o jogo.

Olhe agora o diagrama das pontes de Konigsberg. Todos os pontos possuem um número ímpar de linhas, quando o número máximo é dois (entrada e saída). Assim, Euler concluiu de uma vez por todas que não é possível atravessar as sete pontes de Konigsberg sem jamais repetir nenhuma.

E Euler também responde a meu problema da flor estranha. Enquanto a casa com o X possui todos os vértices com um número par de linhas exceto pelos dois na “base” da casa, eu consigo criar o caminho e desenhá-la sem repetir linhas. E mais: sei sempre que os pontos de começo e fim serão os da base, é impossível fazer o caminho sem começar por eles, são os únicos com um número ímpar de conexões. Quanto à flor, todos os vértices do quadrado central possuem cinco conexões, qualquer caminho leva ao fracasso e meu problema está resolvido.

Curiosamente, quando trabalhava na usina nuclear, um colega propôs-me esse problema da flor, alegando que seria interessante já que eu “gostava dessas coisas” e que ele não conseguia resolver. Vingando-me daquele que em minha infância apresentou-me o problema, disse triunfante ser impossível e, naquela mesma lousa, contei as linhas de cada vértice. Porque matemáticos não levam muito bem a ideia de “não conseguirem algo” e, não conseguindo, ao menos provam que ninguém no mundo consegue.

24 respostas

Aniversários

Rookie

Hoje é meu aniversário, celebro vinte e quatro anos de vida. E essa data, além de me fazer sentir especial, costuma me lembrar de um problema fascinante de combinatória, que levou a um igualmente interessante estudo econômico. Como não achei referência ao estudo, nem lembro onde o li, repeti-o eu mesmo, na medida do possível. O problema é conhecido como paradoxo do aniversário, que de paradoxal não tem nada.

A pergunta é: quantas pessoas eu preciso colocar em uma sala para que a chance de haver naquela sala pessoas com o aniversário repetido seja maior que a chance de não haver pessoas com o aniversário repetido? Formulado de outra maneira, eu tenho $N$ pessoas em uma sala e uma probabilidade $P(N)$ de que essas pessoas possuam aniversário repetidos, qual o primeiro valor de $N$ para o qual $P(N)>0,5$?

E a resposta é um número surpreendentemente baixo: 23. A partir desse valor de pessoas, é mais provável encontrar pessoas com aniversários repetidos que não encontrar, a probabilidade de que duas pessoas tenham nascido no mesmo dia do ano passa a 50,7% para esse valor de $N$. A razão do número ser pequeno é o grande crescimento da função fatorial, usada para calcular o número de combinações possíveis para a comparação de cada par de pessoas. Ou seja, apesar de haver muitos dias no ano, o número de comparações possíveis entre o aniversário de 23 pessoas é suficientemente grande para tornar essa probabilidade maior que 50%.

Interessados nesse resultado, podemos testar os aniversários de partidas de futebol. Sendo 11 para cada lado e o juiz, teremos 23 pessoas a cada partida, e podemos comparar um número grande de partidas para perceber que há mais partidas com aniversários repetidos que partidas sem aniversários repetidos.

No entanto, o resultado não será o que esperamos. De fato, há muitas partidas com aniversários repetidos, mas um número muito maior que o esperado! As partidas com aniversários repetidos ocorrem em número muito maior que as que não possuem aniversários em comum, quando a diferença não deveria estar muito longe de 51% contra 49%. Esse fato foi-me apresentado há algum tempo, foi-me até dito que um estudo foi feito, jamais achei o estudo, fi-lo eu mesmo com a ajuda da Wikipédia e sua excelente página da escalação de cada seleção de futebol.

Pus-me a anotar os meses de nascimento dos jogadores de futebol das seguintes seleções: Brasil, Paraguai, Chile e Argentina. Tomei a escalação mais atual possível, para não haver privilégio de uma época ou outra. A razão de pegar apenas países do hemisfério sul ficará clara com os resultados.

Enquanto o Paraguai não apresenta uma distribuição de nascimento de seus jogadores ao decorrer do ano que chame a atenção, Brasil, Chile e Argentina impressionaram-me e comprovaram, em termos nada rigorosos, a teoria que eu havia ouvido a respeito do estudo. Organizei um histograma em três camadas, as barras menores são os nascimentos no mês, as intermediárias representam nascimentos em um trimestre e as grandes são os nascimentos no semestre. O resultado do Paraguai, analisados 83 jogares, foi:

Nada impressionante até aqui, os aniversários parecem razoavelmente bem distribuídos em todos os níveis e não consigo perceber uma tendência evidente. No entanto, a distribuição do Brasil já começa a apresentar um fenômeno interessante:

Temos na seleção brasileira, analisados os 69 últimos convocados de Mano Menezes, uma concentração clara de nascimentos no primeiro semestre, em especial uma forte ausência de nascidos no último trimestre do ano. Claro, isso pode ser uma improbabilidade realizada, não um indício de variável escondida. Se analisarmos com cuidado, podemos calcular a probabilidade de, jogando aniversários aleatoriamente no ano, ter essa diferença entre o primeiro e o segundo semestre; é improvável, mas nem de longe impossível.

No entanto, os resultados do Chile, analisados 77 jogadores, revelaram-se:

E essa diferença entre primeiro e segundo semestre já não pode mais ser explicada como uma anomalia estatística, há algo estranho nesse país que faz jogadores de futebol nascerem no começo do ano e não no final. Para confirmar a teoria, podemos avançar no estudo da seleção Argentina, analisando 92 jogadores:

Esse gráfico não pode, de maneira alguma, ser justificado como coincidência. A albiceleste possui o dobro de jogadores nascidos no primeiro semestre em relação ao segundo semestre. Entrementes, notamos que em todas as seleções dezembro é sistematicamente o pior mês, ou o segundo pior, no caso do Chile.

Podemos nos divertir calculando a probabilidade de obter uma configuração como a da Argentina se os aniversários fossem distribuídos de maneira uniforme no ano. Temos 92 jogadores e queremos saber a chance de, distribuindo aleatoriamente no ano, ter uma diferença de 30 nascimentos entre os dois semestres, sendo o primeiro semestre o favorecido. Calculando com cuidado, essa probabilidade não passa do valor 0,08%, extremamente baixa, ela precisa de uma explicação.

Antes que os astrólogos saiam em defesa de alguma correlação entre estrelas e seres humanos, comento a conclusão a que chegaram os estatísticos. Essa predominância de nascimentos em um semestre não ocorre em países europeus, curiosamente, analisei França e Inglaterra e os resultados não são nada impressionantes. Esses três países do sul, Brasil, Argentina e Chile, apresentam sistematicamente jogadores nascidos em um semestre, e a razão disso, muito provavelmente, é o ano letivo.

No mesmo argumento que usou Malcolm Gladwell em seu livro Outliers para explicar jogadores de hóquei, nesses países, as escolas de futebol organizam os alunos de acordo com o ano letivo, e os jogadores profissionais enfrentam peneiras desde cedo para seguir na carreira. Os nascidos no começo do ano são, por isso, os mais velhos de suas turmas e, ao enfrentam peneiras desde crianças, são também os mais fortes e mais rápidos. Os nascidos no primeiro trimestre são quase um ano mais velhos que os nascidos no último, e são selecionados em uma idade em que um ano é muito para o desenvolvimento corporal. Esse resultado é ausente nos times europeus porque as escolas de futebol não seguem um ano específico, algumas tomam o escolar como base e outras o ano de nascimento, não havendo consenso, há equilíbrio na distribuição.

Falta, claro, explicar o caso do Paraguai. Tendo em vista os outros países, o mais natural é supor, ou que o Paraguai é a anomalia estatística, ou que o sistema de escola de futebol e peneira desde muito cedo não é tão rigoroso no Paraguai.

Tudo o que eu acabo de fazer, aviso, consiste em estatística de péssima qualidade. Eu precisaria tomar vergonha na cara, analisar mais jogadores de mais times, informar-me sobre o sistema de avaliação do Paraguai e não me ater a essa tese com muito afinco, ela pode muito bem estar furada. Contudo, os 0,08% chamam a atenção, e confirmam que o estudo do paradoxo do aniversário não pode ser realizado com jogadores de futebol.

Claro que a hipótese feita, a distribuição igual de nascimentos ao redor do ano pela população normal, precisa ser justificada. Redireciono-os ao trabalho desse site, enquanto aponto ao curioso fato do grande número de nascimentos em setembro-agosto, provavelmente resultado das férias de natal, quando a chance de se estar em casa é alta e a programação da televisão cai de qualidade vertiginosamente.

Se o futebol sul-americano já apresenta esse fenômeno, podemos encontrá-lo de forma ainda mais acentuada em esportes cuja dependência da disposição física (e, logo, da idade) seja maior, o hóquei é um bom exemplo. Um grande estudo nesse aspecto foi realizado no Canadá em 1988 e os resultados do estudo são impressionantes, o mês de nascimento parece ter implicação direta no sucesso do jogador. Atualmente, parece que as ligas americanas e canadenses adaptaram um calendário diferente, mais próximo daquele europeu de futebol, e a diferença não é mais gritante.

E esses gráficos nos inspiram a questionar o quanto do sucesso de alguém em uma carreira é fruto de sucesso inicial, de ter se dado bem no começo, gostado, continuado, se esforçado e se dado ainda melhor, um círculo vicioso positivo vindo apenas do fato de ter sido bem sucedido no começo. Extrapolando, podemos nos perguntar se fazemos o que fazemos pelo sucesso inicial, e me pergunto quanto da matemática que faço não vem de uma primeira nota alta na matéria. As coisas talvez tivessem sido diferentes se eu tivesse errado mais questões, se minha professora fosse uma carrasca, se a ponta de meu lápis tivesse quebrado naquela primeira prova ou, quem sabe, se eu tivesse nascido em junho.

19 respostas

A pior forma de governo

Rookie

As eleições na França tiveram há pouco sua conclusão, com a vitória do socialista François Hollande, e logo as eleições americanas começarão. Eu conversava com um amigo francês a respeito, ele, em um não raro surto nacionalista, dizia ser raro encontrar um país com uma democracia tão funcional quanto a francesa, em que candidatos em igualdade de condições (mesmo tempo de propaganda eleitoral, por exemplo) são avaliados de forma justa e o escolhido é o favorito da população. Comparava esse sistema ao confuso método americano de eleições indiretas, que pode gerar aberrações estatísticas como a estranha eleição de Bush sem a maioria absoluta da população. Ainda, argumentei que o escrutínio francês não é perfeito, o método de eleição em dois turnos não é ideal. Ele perguntou qual seria, então; e a resposta é simples, e longe de intuitiva: nenhum método é justo.

Se Churchill disse que a democracia é a pior forma de governo, exceto todas as outras que já foram tentadas, o post de hoje é para convencê-los de que até em um caso bem simples a democracia não possui resposta fácil, a justiça nem sempre é evidente e uma eleição possui fatores que vão além de músicas contagiantes, propagandas elaboradas e discursos violentos.

Somos confrontados diversas vezes com situações em que uma eleição deve ser realizada, não damos a devida atenção ao método do escrutínio. Digo que não apenas ele amplifica ou ajuda um resultado, muitas vezes a forma de escrutínio determina o vencedor. Para não forçar meu argumento, vou listar os métodos mais tradicionais de escrutínio, todos baseados em sistemas existentes:

1º Método: eleições em um único turno. Inspirados em sistemas de democracia pequena, como a eleição para “chefe do grupo” ou para o diretório de estudantes de uma universidade, podemos apenas contar, em uma votação com uma opção apenas, quem tem mais votos e decidir que ele será o escolhido.

2º Método: eleições em dois turnos. Inspirados nas eleições francesas e brasileiras, podemos realizar uma primeira votação e, selecionados os dois melhores, podemos realizar um segundo turno e eleger vencedor o que obtiver então mais votos.

3º Método: atribuição de pontos. Inspirados nas eleições legislativas australianas, podemos atribuir pontos a suas preferências: 5 pontos ao favorito, 3 ao segundo favorito, 1 ao terceiro lugar e 0 ao que não querem de jeito nenhum. O candidato que ganhar mais pontos é eleito.

4º Método: contagem de confrontos. Inspirados nas eleições americanas, com um sistema um pouco diferente, podemos pensar em um sistema de “confronto” entre candidatos. Quantas vezes o A é preferido em relação ao B? E ao C? E ao D? Após todas essas comparações, ou confrontos, somamos o “placar” de cada candidato e o que tiver vencido mais confrontos é o eleito. Em outras palavras, é como simular todos os “segundos turnos” possíveis e eleger o candidato que vencer mais segundos turnos.

Todos esses métodos são usados em algum sistema democrático de comparação na vida real, não inventei nada. Ainda, digo a vocês que é impossível estabelecer um vencedor único, aliás, consigo situações em que é impossível encontrar um vencedor “justo” da eleição. Se você considera esses quatro métodos válidos, sigo contando a história de um país bem pequeno.

Apresento a vocês Pequenolândia, um país de dez habitantes que quer eleger seu presidente (não confundir com Pequenópolis, oficialmente cidade natal de Clark Kent). Quatro candidatos se apresentam, A, B, C e D. Cada cidadão possui para si uma ordem de prioridade na escolha dos candidatos, e eu apresento essa ordem em forma de tabela:

Eleitor 1 2 3 4 5 6 7 8 9 10
1º A A A A B B B C C D
2º D C D D C C C D D C
3º B D B B D D D B B B
4º C B C C A A A A A A

A constituição de Pequenolândia, contudo, não está escrita, eles precisam de um presidente para isso. Sem saber como realizar as votações, os habitantes de Pequenolândia se inspiram nas diferentes formas de classificação eleitoral pelo mundo, e, decididos a exercerem plenamente a democracia, realizam as eleições com os quatro métodos acima, e comparam resultados.

O primeiro método dá vitória ao A, preferido de quatro habitantes, vence os demais, cujas preferências são três, dois e um. O segundo método selecionaria o A e o B para um segundo turno, e podemos ver que o B vence o A na preferência dos eleitores que não votariam inicialmente neles, o que daria a vitória ao B em uma eleição a dois turnos.

Contando os pontos pelo terceiro método, teríamos o A com 20 pontos, o B com 21 pontos, o C com 25 pontos e o D com 24 pontos, sendo a vitória por pontos corridos claramente do candidato C. Se contarmos os confrontos, o A vence apenas 12 confrontos (4 vezes cada candidato), o B vence 15 (6 vezes o A, 6 vezes o C e 3 vezes o D), o C vence 16 (6 o A, 4 o B, 6 o D) e o candidato D vence 17 (6 o A, 7 o B e 4 o C) confrontos, sendo claro que a vitória pertence ao candidato D. Pequenolândia terá, como resultado de sua eleição, anarquia completa.

Esse pequeno exemplo ilustra como métodos reconhecidos e consagrados pelo uso na democracia não apenas geram resultados diferentes, eles determinam o vencedor. Cada método elegeu um candidato, e nenhum deles pode ser acusado de ser injusto, todos são usados em eleições, campeonatos e torneios.

Uma resposta otimista seria admitir que existe um método correto e justo, apenas que não é um desses que listei; mas os matemáticos já se encarregaram de arrasar esse otimismo com um sonoro não. O teorema da impossibilidade de Arrow afirma que quaisquer critérios justos que sejam escolhidos, com hipóteses matemáticas exatas de o que ele chama de justiça (todos os critérios acima satisfazem as hipóteses de Arrow), sempre é possível encontrar uma lista de preferências que eleja dois candidatos diferentes com métodos justos. De forma simplificada, nenhuma eleição é justa, Pequenolândia terá que escolher um método antes de escolher um presidente (diferentemente do Brasil em 1988). Em outras palavras, é impossível, de uma lista genérica de preferências, obter de forma inequívoca quem será o presidente.

Em um exemplo atual, e mais concreto, este artigo (agradecimentos a Guilherme Mazanti pelo link), infelizmente em francês, atesta um fato surpreendente. Nessas eleições francesas, o candidato François Bayrou, quinto colocado no primeiro turno, ganharia de qualquer oponente em um combate direito (4˚ método); se participasse, ele ganharia qualquer segundo turno! Ora, como pode um candidato preferido por toda a população a qualquer outra opção não apenas não ser o presidente, mas ser quinto lugar nas pesquisas? Eis um dos resultados impressionantes do teorema de Arrow, colocando em uma perspectiva diferente a afirmação de meu amigo, até que não deve ser tão difícil encontrar eleições mais justas que aquelas que não elegem o favorito da população frente a qualquer outra opção.

Ainda, quanto a meu amigo francês, ele pode ficar tranquilo. Diz-se que eleições justas são pleonasmo, pois se não fosse justa não seria eleição; Arrow nos garante, nada de pleonasmo, eleições justas são, na realidade, um paradoxo.

5 respostas

A raiz do problema

Rookie

O teorema de Pitágoras é o centro da geometria de nossa oitava série, agora nono ano. Nele, aprendemos que há uma relação simples e até bonita entre os lados de um triângulo retângulo, aquele com um ângulo de 90°. O que não nos contam é a quantidade de problema que esse teorema já deu, e até as mortes que causou, na época de seu descobrimento. Os número irracionais já foram muito mais interessantes, quando havia gente que daria a vida, e mataria, para manter certas verdades ocultas na antiguidade clássica.

Pitágoras é uma figura historicamente bem misteriosa. Tudo o que se sabe sobre ele provém de séculos depois de sua morte, há mesmo quem duvide de sua existência, e todos os dados sobre ele são carregados de misticismo. Isso porque Pitágoras não era apenas um matemático, um professor, um sábio, ele foi além: em sua busca por conhecimentos e verdades nos números, enxergou um pouco mais do que devia e fundou um culto religioso envolvendo as verdades geométricas do universo.

Neste culto secreto, ciência e religião não possuíam diferença alguma e a busca pela verdade era também a busca pelo divino. O culto possuía regras de alimentação, comportamento, ser pitagórico era muito mais que pesquisar matemática, era um estilo de vida, e seu seguidores reuniam-se em uma mistura de escola com monastério no sul da atual Itália, no século V a.C.

Essa mistura não podia terminar muito bem. Diz-se na boca pequena, nesses boatos da história da matemática, que um infortunado descobriu que a raiz quadrada no número dois era um número irracional. Horrorizados com a notícia, os pitagóricos, e talvez até o próprio Pitágoras, mandaram matar este matemático para silenciar o que colocaria em cheque muito das verdades divinas descobertas pelo grupo. A razão do choque é difícil entender, mas vamos tentar, ela reside na ideia que os gregos tinham da natureza de um número.

Toda a matemática grega repousava na geometria, sua álgebra era fraca, a escrita era sempre feita em termos geométricos e os grandes trabalhos gregos versavam teoremas avançados sobre elipses, cônicas, parábolas, mas a ideia de equação está ausente em todos esses textos. Os números, como eles entendiam, eram sempre dados por proporções. Eles escolhiam um comprimento de linha, uma barra, para ser o 1. Mas isso não era “apenas” o número 1, a própria noção de número não existia muito, o 1 da contagem de ovelhas e o 1 da barra eram coisas diferentes para os pitagóricos, e gregos em geral. Essa barra de tamanho 1 representava a unidade, o fundamental, o que gera todas as coisas. E a definição de número dos gregos estava atrelada a isso. Dizer o número 3, a eles, era a barra cujo comprimento era três vezes o da barra unidade. Na ideia deles, dizer 3 era dizer:

Os demais números eram compostos de maneira parecida. A fração 21/16, por exemplo, não era ensinada com pedaços de bolo como em nossas quarta-séries, mas com pedaços da unidade. Você quebra a unidade em 16 pedaços, junta 21 deles, cola e tem o número que deseja:

E assim eles faziam a matemática. Toda barra encontrada era “numerizada” quando se quebrava a unidade em partes pequenas o suficiente para, com um bom número delas, colar e formar a barra nova. E todo número novo era sempre pensado em forma de barra ou de pedaços de barra, toda a matemática eram intersecções, retas, circunferências e pontos. Até que, um dia, um homem, dizem Hipaso de Metaponto, descobriu uma barra que não era número. E, pior, ela estava o tempo todo bem embaixo do nariz de todos. Essa barra é a raiz quadrada de dois, uma barra tão facilmente obtida quanto alguém pode desenhar um quadrado:

Essa barra, a diagonal do quadrado, não pode ser composta com pequenos pedaços da lateral do quadrado, por menores que esses pedaços sejam. Isso não é nada evidente, você pode até tentar se enganar com a fração 141/100, mas ela ainda não é perfeitamente a diagonal do quadrado e nenhuma outra fração jamais será. Se antes eles apenas achavam que era uma barra cuja fração era complicada demais, isso é um abismo em relação à ideia de “não há fração para essa barra”. Em outras palavras, isso violava a própria noção de número dos gregos, algo alienígena à matemática deles, que estava profundamente atrelada ao religioso, à noção de proveniência da unidade, da formação do todo pelo pedaço primordial, ora, nada mais natural que silenciar o herege que descobriu esse pedaço de barra infiel.

A maneira como ele descobriu isso foi geométrica, mas posso dar um argumento algébrico legal de como nenhuma fração ao quadrado dá dois. Suponha que eu seja malandro, suponha que eu tenha encontrado dois números $p$ e $q$ tais que $\left(\frac{p}{q}\right)^2=2$. Como eu estou estudando a fração, é de bom tom que $p$ e $q$ não tenham divisores em comum pois, se tiverem, basta dividir a fração em cima e embaixo pelo número para ter uma fração equivalente (ou seja, 10/15 é o mesmo que 2/3, basta eu dividir os dois por 5).

Mas se $ \left(\frac{p}{q}\right)^2=2$, então $ \frac{p^2}{q^2} = 2$ e $ p^2 = 2q^2$. Até aqui sem surpresas, apenas apliquei o quadrado nos dois elementos e passei o de baixo multiplicando. No entanto, se $ p^2$ é duas vezes alguém, ele tem que ser par. Mas se $ p^2$ é par, então $ p$ é par, pois o quadrado de um número só é par se o próprio número for par, não tem como fazer um fator 2 “surgir” quando você multiplica um número por ele mesmo. Então $ p$ é par, e, como todo bom número par, é o dobro de alguém. Vamos chamar esse alguém de $ k$, então $ p=2k$. E se $ p^2 = 2q^2$, podemos substituir esse $ p$ por $ 2k$ e escrever $ (2k)^2=2q^2\implies 4k^2=2q^2\implies 2k^2=q^2$. De novo, sem surpresas, eu apliquei o quadrado nos dois caras da esquerda, percebi que podia dividir os dois lados da equação por dois e o fiz. Então eu provo que $ q^2$ é o dobro de alguém, o tal do $ k^2$, e, com isso, é par, o que faz o próprio $ q$ ser par também. Moral da história, se $ \frac{p^2}{q^2} = 2$, então tanto $ p$ quanto $ q$ são pares.

Contudo, eu havia suposto que $ p$ e $ q$ não possuíam divisores em comum! E acabo de provar que ambos são pares, então eles possuem um divisor em comum. Ora, posso dividir ambos por dois que a fração $ \frac{p}{q}$ ainda terá dois como quadrado, mas eu posso repetir o raciocínio acima e novamente provar que eles ainda são pares, então posso dividir de novo por dois e, aplicando o raciocínio acima, provar que ainda são pares! Ora, nenhum número é infinitamente par, está na cara que caímos em contradição nesse raciocínio e isso prova que nossa hipótese inicial é falha, pois ela nos conduz a um absurdo, que é um número infinitamente par. A verdadeira moral da história é: não existem números $ p$ e $ q$ tais que $ \frac{p^2}{q^2} = 2$.

E isso prova de maneira definitiva que a diagonal do quadrado é um alienígena no mundo da matemática grega, um número que não pode ser colocado como razão entre dois outros e, nessa medida, justamente chamado de irracional. A existência de tais números foi mantida em segredo por um bom tempo, poucos queriam seguir o exemplo de Hipaso. Hoje, não apenas sabemos que eles estão por toda parte, mas que a maior parte dos números reais é, de fato, de número irracionais. Em outras palavras, se você tirar um número real ao acaso, a chance é zero de tirar um que pode ser colocado em forma de fração, mas uma definição com mais cuidado disso tudo levaria a outro post, mas um indício pode ser encontrado em um outro, mais antigo, sobre os infinitos, onde vocês podem comprovar que, se as frações entram em uma fila, o raiz de dois, este incompreendido, não entra em fila nenhuma.

4 respostas

O gás de Coulomb-Dyson

Hardcore

Esses dias trombei com um assunto bonito, uma parte do estudo de matrizes aleatórias que realmente achei interessante. Claro, trabalho com matrizes aleatórias, então é um pouco normal eu encontrar coisas bonitas aqui e ali, mas dificilmente algo tão bonito quanto o que achei outro dia em um desses livros de teoria espectral. Aviso, esse post é nível hardcore e provavelmente o mais intenso que já postei até agora, recomendo discrição. Se você não é um físico ou matemático, não vai pescar muita coisa do texto, não aconselho sua leitura.

As matrizes aleatórias servem para bastante coisa. Diversos modelos envolvendo um operador com perturbação aleatória e fora de nosso controle podem ser colocado em um formato de matriz aleatória, a transmissão de dados de um conjunto de antenas a outro com ruído pode ser modelizado por uma equação linear com uma matriz aleatória também, muita coisa entra nessa categoria e em cada um desses estudos a pergunta é recorrente: jogando entradas aleatórias em uma matriz, com uma densidade de probabilidade $ P(x)$ para as entradas, qual será a densidade de probabilidade de seus autovalores?

Porque, no fundo, é nisso que estamos interessados. Na quântica eles serão as medidas possíveis, nas equações diferenciais lineares eles nos darão a estabilidade do sistema, autovalores são a alma das matrizes. Mas se encontrar os autovalores de uma matriz $ n \times n$ bem definidas já não é tarefa tão fácil, resolver polinômios sempre dá preguiça, é difícil não sofrer só ao pensar como será com matrizes cuja única informação é a probabilidade de obter suas entradas entre dois valores.

Primeiro vamos estabelecer o que eu quero dizer com “probabilidade de uma matriz”. De forma civilizada, eu precisaria temperar esse texto com alguns detalhes da medida usada, do espaço em questão, mas isso é um blog e não um artigo; essa história está mais bem contada neste excelente artigo sobre matrizes aleatórias, ainda nas primeiras páginas. Tomemos um exemplo fácil, um vetor $ (x,y)$. Falar de sua densidade de probabilidade, é falar de uma função $ P(x,y)$ tal que, para descobrir a chance de encontrar esse vetor com as coordenadas $ 0\leq x \leq 3$ e $ 0 \leq y \leq 2$ será o resultado da integral $ \int_0^2 dy \int_0^3dx P(x,y)$, simples assim. Se $ x$ e $ y$ são independentes, certamente teremos $ P(x,y)=P(x)P(y)$, mas isso não será necessariamente verdade. Falar de densidade de probabilidade de uma matriz é falar da densidade conjunta de suas entradas, ou seja, sua j.p.d.f. (joint probability density function). Eu usaria o termo em português, mas não gosto de abreviar função densidade de probabilidade.

É claro que nem as matrizes nem as probabilidades podem ser quaisquer, problemas gerais demais não levam a lugar nenhum. Vou me restringir ao caso real, tudo pode ser generalizado para complexo com as devidas trocas. Listo dois tipos de matrizes cujo estudo das probabilidades é interessante: matrizes cujas probabilidades das entradas são independentes e matrizes que possuem a probabilidade invariante por conjugação.

Essa última propriedade é mais sutil, mas é simples. Dizer que a j.p.d.f. de uma matriz $ M$ é invariante por conjugação é dizer que, para toda $ U$ não singular, teremos que $ P(M)=P(UMU^{-1})=P(M’)$, ou seja, a chance de obter um elemento da classe de conjugação de $ M$ é a mesma chance de se obter $ M$.

E essa propriedade serve para uma manobra bem útil. Se a j.p.d.f. é invariante por conjugação, e se eu consigo diagonalizar a matriz, a probabilidade da matriz será a mesma probabilidade de sua forma diagonal, com seus autovalores como entradas, o que me permite de maneira fácil obter a distribuição de probabilidade de seus autovalores. Por vários motivos, físicos e matemáticos, gostamos de estudar matrizes simétricas, ou hermitianas se complexas. Isso vai garantir a diagonalização por matrizes unitárias e a existência de um alegre conjunto de autovalores bem reais.

Teorema: O único grupo de matrizes aleatórias invariantes por conjugação unitária e cujas entradas possuem p.d.f. independentes é o grupo das matrizes gaussianas, cujas entradas possuem como p.d.f. uma distribuição normal.

Nem arrisco tentar demonstrar isso, tomaria este post e mais outros três. Esse teorema nos inspira a aprofundar nosso estudo das matrizes gaussianas. Como elas são invariantes por conjugação unitária (estamos ainda com matrizes simétricas se reais e hermitianas se complexas, então elas são diagonalizáveis por uma matriz unitária), podemos escrever que $ P(M) = P(D)$, onde $ D$ é sua forma diagonalizada. Para que isso seja possível, vamos nos restringir às matrizes gaussianas simétricas (hermitianas se são complexas). Como em $ P(M)$ as probabilidades das entradas individuais são independentes, nosso instinto nos diz que em $ P(D)$ as coisas serão parecidas, que os autovalores terão probabilidades independentes, e não poderíamos estar mais errados. Porque escrever $ P(D)$ é escrever $ P(\lambda_1,\lambda_2,ldots,\lambda_n)$, uma probabilidade que depende dos autovalores, isso é uma mudança de variável e, como a probabilidade sempre se dá integrando essa densidade de probabilidade, precisamos levar em conta o jacobiano dessa transformação que, para nosso desespero, acopla todos os autovalores. Tal probabilidade já é conhecida há algum tempo, a j.p.d.f. dos autovalores da matriz gaussiana:

\[P(\lambda_1,ldots,\lambda_n) = C_k e^{-\beta \sum_k \lambda_k^2} \prod_{j<k}|\lambda_k-\lambda_j|^\beta \]

E o último termo da direita, a parte do jacobiano relativa aos autovalores, não é ninguém menos que o determinante de Vandemonde. O $ \beta$ é um valor referente ao tipo da matriz gaussiana, vale 1 se ela é real, 2 se é complexa e 4 se estamos nos quatérnions. E agora vem a parte bonita: Dyson (nisso fui corrigido, disseram ser Wigner, deixo a polêmica) percebeu que essa j.p.d.f. poderia ser colocada de uma forma mais familiar, bastava apenas jogarmos o determinante de Vandermonde para o expoente como $ \prod_{j<k}|\lambda_k-\lambda_j|^\beta = e^{\beta \sum_{j<k} \log |\lambda_k-\lambda_j|}$, teremos que a probabilidade será um múltiplo de uma grande exponencial. Chamar aquele número de $ \beta$ é extremamente sugestivo. Um leitor atento já deve ter percebido, contemplamos um peso de Boltzmann, em uma analogia perfeita a uma j.p.d.f. do sistema canônico:

\[P(\lambda_1,ldots,\lambda_n) = C_k e^{-\beta\left(\sum_k\lambda_k^2-sum_{j<k}\log |\lambda_k-\lambda_j|\right)} = \frac{1}{Z}e^{-\beta H}.\]

A magia dessa interpretação é poder importar todas as ferramentas da física estatística para resolver esse intrincado problema de álgebra linear. Se imaginarmos que cada autovalor representa a posição de um elétron confinado a uma linha (que representará o eixo real), atraídos ao centro por um potencial harmônico (o termo em $ \sum_k\lambda_k^2$ ) e submetidos à repulsão coulombiana mútua (que em sua forma bidimensional é $ \log |x_i-x_j|$), teremos um sistema físico cujas posições dos elétrons são equivalentes às posições dos autovalores da matriz gaussiana. E, caramba!, isso é muito bonito.

A analogia não é apenas formal, podemos extrair diversas propriedades dessa distribuição com técnicas do ensemble canônico (meu orientador, aliás, fez a carreira dele nisso). E este é um de meus exemplos favoritos de física ajudando matemática, ainda que, se fôssemos contar pontos nisso, a competição seria injusta, estaríamos perdendo por uma boa margem.

1 resposta