Quadrado latino

FIGURA 1: Quadrado latino de ordem 10 preenchido com números de 0 a 9.

Um quadrado latino de ordem (ou lado) n é uma matriz Predefinição:Math preenchida com um conjunto de n símbolos diferentes, cada um ocorrendo exatamente uma vez em cada linha e em cada coluna. Abaixo seguem dois exemplos:

$\left[\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\\ 3& 1& 2\end{array}\right]\left[\begin{array}{cccc}a& b& d& c\\ b& c& a& d\\ c& d& b& a\\ d& a& c& b\end{array}\right]$

Os quadrados latinos são objetos muito relevantes no estudo da combinatória e da teoria do design em geral. Suas primeiras ocorrências remontam a amuletos e ritos orientais do ano 1000, com outras aparições sistemáticas nos textos de Al-Buni (ano 1200, aproximadamente), Choi Seok-Jeong (por volta de 1710) e Euler (década de 1780), a maioria inicialmente relacionada ao estudo dos quadrados mágicos. O nome "quadrado latino" foi escolhido por inspiração nos artigos matemáticos de Leonhard Euler (1707-1783), que se aprofundou no tema e usava caracteres do alfabeto latino como símbolos nos seus estudos desses dispositivos. Apesar do nome, qualquer conjunto de símbolos pode ser usado para formar um quadrado latino (como observado nos exemplos acima).

História

FIGURA 2: Medalhão de liga de cobre, provavelmente datado do século XVI-XVIII, gravado com um quadrado mágico 4x4.

Na Europa, os quadrados latinos são conceitos matemáticos atribuídos a Euler e seus estudos sobre a construção de quadrados mágicos, no século XVIII. Contudo, apesar de ter sido essa relação que impulsionou a pesquisa e sistematização da teoria dos quadrados latinos, com Euler sendo o primeiro a defini-los, formalizá-los e investigá-los matematicamente, existem registros desses objetos espalhados pelo mundo, especialmente no Oriente, datados de séculos antes. As primeiras ocorrências, na verdade, remontam a amuletos e rituais de algumas comunidades árabes e indianas, por volta do ano 1000 (ainda que nesses registros também se encontrem quadrados mágicos, em maior quantidade, inclusive), usados para combater espíritos malignos, reverenciar os deuses, celebrar o sol e os planetas, entre outros fins místicos.

Seguindo os registros, agora por volta de 1200, a história dos quadrados latinos leva ao livro Shams al-Ma'arif al-Kubra (O sol do grande conhecimento), famosa obra do sufi Ahmad ibn 'Ali ibn Yusuf Al-Buni. Ao longo do texto, o autor apresenta diversas figuras de quadrados latinos, ainda relacionadas ao misticismo, descrevendo, por exemplo, 7 quadrados associados, respectivamente, a um dia da semana e a um planeta. É importante ressaltar, contudo, que a maioria dos quadrados está incorreta, isto é, alguma das entradas se repete por linha e/ou coluna, embora fique evidente a estruturação como um quadrado latino. Além disso, há fortes evidências de que Al-Buni também estudava métodos para a construção de quadrados mágicos a partir de quadrados latinos, antecipando (em parte) os estudos formalizados de Euler, bem como outros matemáticos fizeram. Quanto a estes últimos, os registros conhecidos incluem escritos de matemática indiana (1356), trabalhos do místico e filósofo espanhol Ramón Lull(focados no aspecto combinatório desses objetos), artigos de La Loubère (1691), Poignard (1704), La Hire (1705) e Sauveur (1710), ainda que a maioria deles tenha abordado o tema de formas abstratas e indiretas. Contudo, ao menos 67 anos antes da publicação do primeiro artigo de Euler, já existia um trabalho na área mais contundente e mais formalizado que os anteriormente citados: a monografia Koo-Soo-Ryak, escrita pelo coreano Choi Seok-Jeong (1646–1715), no qual ele, pela primeira vez no mundo, detalha um método para construir um quadrado mágico usando dois quadrados latinos de ordem 9, acrescentando, também, que não consegue fazer o mesmo com quadrados de ordem 10.

Finalmente, a história desembarca no século XVIII, quando Leonhard Euler publica oficialmente o problema dos 36 oficiais: como alinhar em um quadrado 36 oficiais de 6 graus diferentes e 6 regimentos diferentes, de tal forma que em cada linha e coluna haja 6 oficiais de diferentes patentes e diferentes regimentos? Embora não pudesse provar, Euler pensou se tratar de um acordo impossível e, na tentativa de esclarecer essa questão, começou a generalizar esse problema, usando letras gregas e latinas (produzindo o que hoje chamamos de quadrados greco-latinos e formalizando o conceito de ortogonalidade de dois quadrados latinos). Dada essa propriedade recém observada, Euler construiu seu principal trabalho na área, o artigo “Pesquisas sobre uma nova espécie de quadrados mágicos”, de 1782, no qual, a priori, são expostos métodos de construção de quadrados mágicos por meio de dois quadrados latinos ortogonais, algoritmos dos quais os hindus se aproximaram à sua época, assim como Al-Buni e Choi Seok-Jeong. Apesar do nome, esse e outros textos de Euler são focados, em sua maioria, nos quadrados latinos e, além da ortogonalidade, exploram também outras caracterizações desses objetos, como a transversal, a ciclicidade e a enumeração, enunciando, por fim, diversos resultados e desafios sobre a existência (ou não) de tais relações. Dentre esses enunciados, alguns ainda em aberto, cabe mencionar a famosa conjectura de Euler sobre quadrados latinos ortogonais, que envolveu a comunidade matemática por quase 200 anos:

“para n congruente com 2 (módulo 4), não existe par de quadrados latinos ortogonais de ordem n”

Euler provou a veracidade da afirmação para n = 2. No século XIX, diversos artigos sobre a conjectura foram publicados, sem, contudo, representarem avanço concreto, até que, em 1900, Tarry encontrou uma prova para n = 6, demonstrando que, de fato, o problema dos oficiais é um problema impossível. Apesar disso, durante um terço de século, a conjectura continuou aberta, até que, por fim, em 1958-59, Bose, Parker e Shrikhande deram uma conclusão ao mistério: a conjectura foi refutada para todo n>6, em uma das primeiras resoluções de problemas combinatórios obtidas por meio de um computador digital. A essa altura, inclusive, o problema era tão famoso que sua solução foi anunciada na primeira página do The New York Times, em 26 de abril de 1959..

Propriedades e Características

Forma Reduzida

Um quadrado latino é dito ser reduzido (normalizado ou na forma padrão) se tanto a primeira linha quanto a primeira coluna estão na ordem natural dos símbolos. Todo quadrado latino pode ser reduzido através da permutação (isto é, reordenação) de linhas e colunas. Por exemplo, o primeiro quadrado latino abaixo não é reduzido, pois sua primeira linha é A, C, B, ao invés de A, B, C. Contudo, trocando a segunda coluna com a terceira, produzimos um quadrado reduzido, já que tanto sua primeira linha quanto sua primeira coluna são alfabeticamente ordenadas: A, B, C (segundo exemplo).

$\left[\begin{array}{ccc}A& C& B\\ B& A& C\\ C& B& A\end{array}\right]\left[\begin{array}{ccc}A& B& C\\ B& C& A\\ C& A& B\end{array}\right]$

Quadrados Latinos Cíclicos

Um quadrado latino cíclico padrão pode ser definido para qualquer ordem n, construindo-o de forma que cada entrada (i,j), i sendo a linha e j a coluna, seja preenchida com o número i + j - 1 (módulo n). Eles se provaram muito úteis para a investigação dos quadrados latinos transversais e para os estudos sobre ortogonalidade, sendo extensamente abordados nos trabalhos de Euler. Um exemplo simples de quadrado latino cíclico é o seguinte:

$\left[\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\\ 3& 1& 2\end{array}\right]$

Matriz Ortogonal Associada

Se cada entrada de um quadrado latino Predefinição:Math é escrita como uma tripla ordenada (linha, coluna, símbolo), obtemos um conjunto de n² triplas ordenadas chamado matriz ortogonal associada ao quadrado. Por exemplo, a matriz ortogonal associada ao quadrado latino acima é {(1,1,1), (1,2,2), (1,3,3), (2,1,2), (2,2,3), (2,3,1), (3,1,3), (3,2,1), (3,3,2)}, na qual a tripla ordenada (2,3,1) indica que na linha 2 e coluna 3 está o símbolo 1.

As matrizes ortogonais podem ser utilizadas para escrever outra definição de um quadrado latino nesses termos:

Um quadrado latino é um conjunto de n² triplas ordenadas (linha, coluna, símbolo), no qual todos os pares ordenados (linha, coluna), (linha, símbolo) e (coluna, símbolo) são distintos.

Ortogonalidade

Dois quadrados latinos de ordem n são ortogonais se, dada a união deles em um mesmo quadrado, com cada entrada formando um par ordenado (símbolo no primeiro quadrado, símbolo no segundo quadrado), não haja células com o mesmo par. A título de exemplo, os quadrados latinos 1 e 2 abaixo são ortogonais, enquanto os quadrados 1 e 3 não são.

$1)\left[\begin{array}{cccc}1& 2& 3& 4\\ 3& 4& 1& 2\\ 4& 3& 2& 1\\ 2& 1& 4& 3\end{array}\right]2)\left[\begin{array}{cccc}1& 2& 3& 4\\ 4& 3& 2& 1\\ 2& 1& 4& 3\\ 3& 4& 1& 2\end{array}\right]3)\left[\begin{array}{cccc}1& 2& 3& 4\\ 2& 3& 4& 1\\ 3& 4& 1& 2\\ 4& 1& 2& 3\end{array}\right]$

$1+2=\left[\begin{array}{cccc}(1,1)& (2,2)& (3,3)& (4,4)\\ (3,4)& (4,3)& (1,2)& (2,1)\\ (4,2)& (3,1)& (2,4)& (1,3)\\ (2,3)& (1,4)& (4,1)& (3,2)\end{array}\right]1+3=\left[\begin{array}{cccc}(1,1)& (2,2)& (3,3)& (4,4)\\ (3,2)& (4,3)& (1,4)& (2,1)\\ (4,3)& (3,4)& (2,1)& (1,2)\\ (2,4)& (1,1)& (4,2)& (3,3)\end{array}\right]$

De certa forma, podemos ver essa união de quadrados como um novo quadrado latino, agora com respeito a dois conjuntos de símbolos, e, a ele, damos o nome de quadrado greco-latino, em homenagem aos estudos de Euler sobre essa propriedade por meio de letras gregas e letras latinas. Por fim, podemos estender esse conceito da seguinte forma: uma coleção de quadrados latinos é dita mutuamente ortogonal se, dados dois quadrados latinos quaisquer desta coleção, eles são ortogonais entre si.

Alguns resultados interessantes envolvendo ortogonalidade são:

• Para n par, o cíclico de um quadrado latino de ordem n não tem ortogonal (demonstrado por Euler);
• Existem quadrados latinos ortogonais de todas as ordens ímpares (demonstrado por Euler);
• Existem quadrados latinos ortogonais de todas as ordens n divisíveis por 4 (demonstrado por Euler);
• Conjectura de Euler: para n congruente a 2 (módulo 4), não existem quadrados latinos ortogonais de lado n (verdadeira para n=2 (Euler), n=6 (Tarry) e refutada para n>6 (Bose, Parker e Shrikhande));
• O número N(n) de quadrados latinos ortogonais de ordem n tende ao infinito quando n tende ao infinito (demonstrado por Chowla, Erdös e Straus);
• Dado n uma potência prima, existem n-1 quadrados latinos de ordem n mutuamente ortogonais entre si (demonstrado por Moore).

Transversais

A transversal em um quadrado latino é uma escolha de n entradas distintas ocorrendo em linhas distintas e em colunas distintas. Observe que isso é possível se, e somente se, existem quadrados latinos ortogonais de ordem n. Além disso, dizemos que um quadrado latino é simétrico se sua diagonal principal for uma transversal. Note que, nos exemplos da seção acima, os quadrados latinos 1 e 2 são simétricos, ao passo que o quadrado 3 não possui transversal. Abaixo, seguem mais dois exemplos: o primeiro não possui transversal, enquanto o segundo possui, mas não é simétrico. É interessante observar que, no primeiro quadrado, cada célula (i,j) vale i+j (mod n) e, sempre que n é par, esse quadrado latino Predefinição:Math não possui transversal (é o caso do quadrado 3 da seção acima, com n=4).

$\left[\begin{array}{cc}1& 2\\ 1& 1\end{array}\right]\left[\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\\ 2& 3& 1\end{array}\right]$

Outra possível definição de uma transversal latina utiliza de conceitos da Teoria dos Grafos: tome um quadrado latino como um grafo bipartido completo, no qual as linhas são vértices de uma parte, as colunas são vértices da outra parte, cada célula é uma aresta (entre sua linha e sua coluna) e os símbolos são cores. Sendo assim, as regras de construção do quadrado latino implicam que essa é uma coloração própria das arestas do grafo, logo, uma transversal é um emparelhamento no qual cada aresta tem uma cor diferente, chamado de emparelhamento arco-íris. Por conseguinte, é possível encontrar muitos artigos que apresentam resultados sobre quadrados latinos sob o termo “emparelhamento arco-íris” no título e vice e versa.

Como observado nos exemplos, alguns quadrados latinos não têm transversal, o que motivou Euler (e outros matemáticos depois dele) a estudar possíveis métodos para a procura dessas estruturas. Segue um dos resultados que vieram desses estudos, bem como algumas conjecturas em aberto:

• Para n par, o cíclico de um quadrado latino de ordem n não tem transversal (demonstrado por Euler);
• Todo quadrado latino de ordem ímpar tem uma transversal (conjectura em aberto, proposta por H.J. Ryser, em 1967);
• Todo quadrado latino de ordem n tem uma transversal parcial de tamanho n-1 (conjectura em aberto, proposta por S.K. Stein e Brualdi, em 1975. É provada apenas para n suficientemente grande (2023) e, para todo n, a cota mais aproximada já encontrada é n − O(log n/loglog n) (2022), embora outras cotas mais fracas tenham sido provadas anteriormente).

Enumeração

Euler pontuou em seus trabalhos que considerava o problema da enumeração dos quadrados latinos uma questão muito complicada. De fato, mais de 200 anos depois, não se sabe uma fórmula computacional simples para calcular o número Predefinição:Math de quadrados latinos Predefinição:Math, ao passo que as cotas superiores e inferiores mais precisas conhecidas (para n grande) são muito distantes. Apesar disso, segue abaixo um resultado clássico.

$$\prod _{k=1}^n{(k!)}^{n/k}\ge L_n\ge \frac{{(n!)}^{2n}}{n^{n^2}}.$$

Ademais, uma fórmula explícita para o número de quadrados latinos foi publicada em 1992, entretanto, não é facilmente computável, em razão do aumento exponencial no número de termos. Tal fórmula para o número Predefinição:Math de quadrados latinos Predefinição:Math é

$$L_n=n!\sum _{A\in B_n}^{}(-1{)}^{{\sigma }_0(A)}(\genfrac{}{}{0ex}{}{\mathrm{per}A}{n}),$$

na qual Predefinição:Math é o conjunto de todas as (0,1)-matrizes Predefinição:Math, Predefinição:Math é o número de entradas 0 da matriz Predefinição:Mvar e Predefinição:Math é o permanente da matriz Predefinição:Mvar.

A tabela abaixo contém todos os valores conhecidos de Predefinição:Math, os quais, inclusive, Euler calculou até n = 5. É perceptível que os números crescem extremamente rápido. Para cada n, o número total de quadrados latinos de ordem n Predefinição:OEIS é Predefinição:Math vezes o número de quadrados latinos reduzidos Predefinição:OEIS.

O número Predefinição:Math de quadrados latinos Predefinição:Math

Predefinição:Mvar	quadrados latinos reduzidos de ordem Predefinição:Mvar Predefinição:OEIS	todos os quadrados latinos de ordem Predefinição:Mvar Predefinição:OEIS
1	1	1
2	1	2
3	1	12
4	4	576
5	56	161,280
6	9,408	812,851,200
7	16,942,080	61,479,419,904,000
8	535,281,401,856	108,776,032,459,082,956,800
9	377,597,570,964,258,816	5,524,751,496,156,892,842,531,225,600
10	7,580,721,483,160,132,811,489,280	9,982,437,658,213,039,871,725,064,756,920,320,000
11	5,363,937,773,277,371,298,119,673,540,771,840	776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000
12	1.62 × 1044
13	2.51 × 1056
14	2.33 × 1070
15	1.50 × 1086

Aplicações

FIGURA 3: Janela do Colégio Caius, em Cambridge, exibindo um quadrado latino 7x7, em homenagem a Ronald Fisher, autoria da artista McClafferty. A janela foi removida em 2020, devido às conexões de Fisher com eugenia.

Os quadrados latinos encontram aplicações em diversas áreas, por vezes sem a nomenclatura oficial, em especial dentro da matemática, da estatística e do design de experimentos.

Estatística e Design de Experimentos

O uso dos quadrados latinos para otimizar a organização e apresentação de experimentos e dados estatísticos não é uma conquista exclusiva do século XX. O exemplo mais antigo conhecido é do investigador agrícola francês François Cretté de Palluel, que, em 31 de Julho de 1788, apresentou um artigo à Real Sociedade Agrícola de Paris, com objetivo de argumentar pelas vantagens de alimentar ovelhas com raízes no inverno, por meio de um experimento de alimentação com 16 ovelhas em dietas diferentes. O layout dos resultados do experimento, apesar da falta de intenção do autor, forma claramente um quadrado latino 4x4, com quatro raças de ovinos em linhas, quatro dietas diferentes em colunas e quatro tempos de abate diferentes como símbolos.

Apesar disso, foi somente em 1920 que o uso de quadrados latinos em projetos experimentais foi extensamente impulsionado, liderado pelos trabalhos do estatístico R.A. Fisher, em especial o artigo "Design de Experimentos", de 1926, que trata exclusivamente do uso de quadrados latinos mutuamente ortogonais.

Matemática

Dentro da Matemática, os quadrados latinos são associados tanto à áreas da Matemática Pura, quanto ao âmbito da Matemática Recreativa. Quanto à esta primeira, esses objetos estão presentes, por exemplo, nos caminhos da álgebra, por meio da generalização de grupos e da correlação deles com as tabelas de Cayley, homem que, inclusive, fez importantes contribuições para a teoria dos quadrados latinos em seus estudos. Além disso, ainda dentro da álgebra, quadrados latinos mutuamente ortogonais são uma das ferramentas utilizadas pelos códigos corretores de erros, especificamente em situações onde há perturbação generalizada de ruídos na transmissão da mensagem. Por fim, as aplicações e aparições dos quadrados latinos na Combinatória e na Teoria dos Grafos também são extensas, englobando principalmente os emparelhamentos arco-íris e problemas relacionados, como citado anteriormente.

FIGURA 4: Tabuleiro de Kamisado, no qual o movimento do próximo jogador é restrito pelo movimento do jogador anterior (e pela cor onde ele finalizou sua jogada).

FIGURA 5: Quadrado Mágico de Aniversário de Ramanujan, que nada mais é do que um quadrado latino 4x4.

No mundo da Matemática Recreativa, por outro lado, os quadrados latinos encontraram aplicações muito mais populares: os quebra-cabeças sudoku, que nada mais são do que quadrados latinos de ordem 9, com a regra adicional de que cada um dos 9 subquadrados naturais Predefinição:Math também contenha todos os 9 símbolos. Além dele, outros jogos semelhantes também envolvem o contexto dos quadrados latinos, como KenKen, Futoshiki e Strimko, cujos objetivos consistem em preencher uma matriz Predefinição:Math como um quadrado latino, seguindo ainda outras regras adicionais relacionadas à operações matemáticas ou repetições de símbolos. Outro desafio é o chamado quebra cabeça do quadrado greco-latino, no qual é preciso encaixar as peças nos espaços disponíveis, evitando repetições de cor e formato por linha, coluna e diagonal, disponível em variadas ordens (o modelo 4x4 com 16 peças é o mais comum). Ademais, indo mais fundo, é possível encontrar até mesmo jogos de tabuleiro baseados na teoria dos quadrados latinos, como o jogo de conquista Kamisado. Finalmente, outra aplicação muito popular desses objetos matemáticos são os próprios quadrados mágicos, que fomentaram grande parte do avanço na teoria dos quadrados latinos. Evidentemente, estes também representam uma grande fatia da Matemática Recreativa, permeando desafios e matemágicas das mais variadas, a maioria envolvendo direta ou indiretamente a construção de um quadrado latino. O quadrado mágico de aniversário de Ramanujan é um exemplo clássico.

Quadrados Latinos nas Artes

O valor decorativo dos quadrados latinos parece ter inspirado alguns artistas ao longo da história, aparições que vão desde amuletos ancestrais (como os da Figura 2), até exibições arquitetônicas do século XX (janela da Figura 3). Além destes, no entanto, não faltam exemplos com outros propósitos e formatos, desde o acadêmico (Figura 6, ao lado), ao religioso. Esse último se caracteriza pelo curioso poema ode à Hanniball Basset, um camponês do condado de Mawgan, que foi enterrado em sua paróquia, a Igreja St. Mawgan, na Inglaterra, com o seguinte escrito sob sua lápide:

FIGURA 6: (Re)ilustração referente à capa da revista Scientific American de novembro de 1959, quando foram encontrados dois quadrados latinos de ordem 10, mostrando-os em cores (autoria de CMG Lee).

Hanniball Basset here Inter'd doth lye
Who dying lives to all Eternitye
hee departed this life the 17th of Ian
1709/8 in the 22th year of his age ~
A lover of learning

Shall wee all dye 
Wee shall dye all 
All dye shall wee 
Dye all wee shall

Cabe, ainda, mencionar dois exemplos de quadrados latinos presentes em símbolos atuais de Heráldica: o brasão da Sociedade de Estatística do Canadá e a logo da Sociedade Biométrica Internacional.

Ver também

• Amostragem por hipercubo latino, técnica de amostragem que se baseia em uma generalização do quadrado latino, para um número qualquer de dimensões.
• Quadrados Mágicos
• Problema das Oito Damas
• Sudoku

Referências

• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Cite book
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2 Novembro 2006). Handbook of Combinatorial Designs (2nd ed.). CRC Press. p. 12. ISBN 9781420010541.

Outras Leituras

• Predefinição:Cite journal
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Cite journal
• The application of Latin square in agronomic research
• Predefinição:Cite book
• Predefinição:Cite book
  • Predefinição:Cite book
  • Predefinição:Cite book
• Predefinição:Cite book
• Predefinição:Cite book
• Predefinição:Cite book
• Predefinição:Cite book
• Predefinição:Cite book
• Predefinição:Cite book

Ligações externas

• Predefinição:MathWorld
• Quadrado latino na Enciclopédia de matemática, em inglês.
• Quadrados Latinos na Enciclopédia Online dos Números Inteiros
• Latin Squares in Java no cut-the-knot
• Infinite Latin Square (Java) no cut-the-knot
• Quadrado mágico dentro do Quadrado latino