Artigos

4.4: Quadrados latinos


Definição: quadrado latino

UMA Quadrado latino de ordem (n ) é uma grade (n times n ) preenchida com (n ) símbolos para que cada símbolo apareça uma vez em cada linha e coluna.

Exemplo ( PageIndex {1} )

Aqui está um quadrado latino de ordem 4:

Normalmente usamos os inteiros (1 ldots n ) para os símbolos. Existem muitos, muitos quadrados latinos de ordem (n ), então vale a pena limitar o número concordando em não contar os quadrados latinos que são "realmente iguais" e diferentes. A maneira mais simples de fazer isso é considerar reduzido Quadrados latinos. Um quadrado latino reduzido é aquele em que a primeira linha é (1 ldots n ) (em ordem) e a primeira coluna é da mesma forma (1 ldots n ).

Exemplo ( PageIndex {2} )

Considere este quadrado latino:

4231
2413
1342
3124

A ordem das linhas e colunas não é muito importante para a ideia de um quadrado latino. Se reordenarmos as linhas e colunas, podemos considerar o resultado como sendo essencialmente o mesmo quadrado latino. Reordenando as colunas, podemos transformar o quadrado acima neste:

1234
3412
2341
4123

Então, podemos trocar as linhas dois e três:

1234
2341
3412
4123

Este quadrado latino está em forma reduzida e é essencialmente igual ao original.

Outra maneira simples de mudar a aparência de um quadrado latino sem mudar sua estrutura essencial é trocar os símbolos.

Exemplo ( PageIndex {3} )

Começando com o mesmo quadrado latino de antes:

4231
2413
1342
3124

podemos trocar os símbolos 1 e 4 para obter:

1234
2143
4312
3421

Agora, se trocarmos as linhas três e quatro, obteremos:

1234
2143
3421
4312

Observe que este quadrado latino está em forma reduzida, mas não é igual à forma reduzida do exemplo anterior, embora tenhamos começado com o mesmo quadrado latino. Portanto, podemos considerar alguns quadrados latinos reduzidos iguais entre si.

Definição: classes isotópicas e isotópicas

Dois quadrados latinos são isotópico se cada um pode ser transformado no outro permutando as linhas, colunas e símbolos. Esta relação de isotopia é uma relação de equivalência; as classes de equivalência são isotopia Aulas.

Os quadrados latinos são aparentemente muito difíceis de contar sem um poder de computação substancial. O número de quadrados latinos é conhecido apenas até (n = 11 ). Aqui estão os primeiros valores para todos os quadrados latinos, quadrados latinos reduzidos e quadrados latinos não isotópicos (ou seja, o número de classes de isotopia):

(n )TudoReduzidoNão isotópico
1111
2211
31211
457642
5161280562

Como podemos produzir um quadrado latino? Se você sabe o que é um grupo, você deve saber que a tabuada de qualquer grupo finito é um quadrado latino. (Além disso, qualquer quadrado latino é a tabuada de uma quasigrupo.) Mesmo se você não encontrou grupos com esse nome, você pode saber de alguns. Por exemplo, considerando o módulo de inteiros (n ) sob adição, a tabela de adição é um quadrado latino.

Exemplo ( PageIndex {4} )

Exemplo 4.3.6 Aqui está a tabela de adição para o módulo 6 de inteiros:

012345
123450
234501
345012
450123
501234

Exemplo 4.3.7 Aqui está outra maneira de gerar potencialmente muitos quadrados latinos. Comece com a primeira linha (1, ldots, n ). Considere os conjuntos (A_i = [n] barra invertida {i } ). De exercício 1 na seção 4.1 sabemos que este sistema de conjuntos tem muitos sdrs; if (x_1, x_2, ldots, x_n ) é um sdr, podemos usá-lo para a linha dois. Em geral, depois de escolhermos as linhas (1, ldots, j ), deixamos (A_i ) ser o conjunto de inteiros que ainda não foram escolhidos para a coluna (i ). Este sistema de conjunto tem um sdr, que usamos para a linha (j + 1 ).

Definição 4.3.8 Suponha que (A ) e (B ) sejam dois quadrados latinos de ordem (n ), com entradas (A_ {i, j} ) e (B_ {i, j} ) na linha (i ) e coluna (j ). Forme a matriz (M ) com entradas (M_ {i, j} = (A_ {i, j}, B_ {i, j}) ); vamos denotar esta operação como (M = A xícara B ). Dizemos que (A ) e (B ) são ortogonal se (M ) contém todos os (n ^ 2 ) pares ordenados ((a, b) ), (1 le a le n ), (1 le b le n ) , isto é, todos os elementos de ( {0,1, ldots, n-1 } times {0,1, ldots, n-1 } ).

Como veremos, é fácil encontrar quadrados latinos ortogonais de ordem (n ) se (n ) for ímpar; não é muito difícil encontrar quadrados latinos ortogonais de ordem (4k ), e difícil, mas é possível encontrar quadrados latinos ortogonais de ordem (4k + 2 ), com exceção das ordens (2 ) e (6 ) No século XVIII, Euler mostrou que existem quadrados latinos ortogonais de todas as ordens, exceto da ordem (4k + 2 ) e conjecturou que não há quadrados latinos ortogonais de ordem (6 ). Em 1901, o matemático amador Gaston Tarry mostrou que de fato não há nenhuma ordem (6 ), mostrando que todas as possibilidades para tais quadrados latinos falharam em ser ortogonais. Em 1959, foi finalmente mostrado que existem quadrados latinos ortogonais de todas as outras ordens.

Teorema 4.3.9

Existem pares de quadrados latinos ortogonais de ordem (n ) quando (n ) é ímpar.

Prova

Esta prova pode ser resumida usando idéias da teoria dos grupos, mas apresentaremos uma versão independente. Considere a tabela de adição para o mod de adição (n ):

0 ( cdots ) (j ) ( cdots ) (n-1 )
00 ( cdots ) (j ) ( cdots ) (n-1 )
( vdots )
(eu)(eu) ( cdots ) (i + j ) ( cdots ) (n + i-1 )
( vdots )
(n-1 ) (n-1 ) ( cdots ) (n + j-1 ) ( cdots ) (n-2 )

Afirmamos primeiro que este (sem a primeira linha e coluna, é claro) é um quadrado latino com símbolos (0,1, ldots, n-1 ). Considere duas entradas na linha (i ), digamos (i + j ) e (i + k ). Se (i + j equiv i + j pmod {n} ), então (j equiv k ), então (j = k ). Assim, todas as entradas da linha (i ) são distintas, então cada um de (0,1, ldots, n-1 ) aparece exatamente uma vez na linha (i ). A prova de que cada um aparece uma vez em qualquer coluna é semelhante. Chame isso de quadrado latino (A ). (Observe que até agora tudo é verdade, seja (n ) ímpar ou par.)

Agora forme um novo quadrado (B ) com entradas (B_ {i, j} = A_ {2i, j} = 2i + j ), onde por (2i ) e (2i + j ) nós significa esses valores mod (n ). Assim, a linha (i ) de (B ) é igual à linha (2i ) de (A ). Agora, afirmamos que de fato as linhas de (B ) são exatamente as linhas de (A ), em uma ordem diferente. Para fazer isso, basta mostrar que se (2i equiv 2k pmod {n} ), então (i = k ). Isso implica que todas as linhas de (B ) são distintas e, portanto, devem ser todas as linhas de (A ).

Suponha, sem perda de generalidade, que (i ge k ). Se (2i equiv 2k pmod {n} ) então (n divide 2 (i-k) ). Como (n ) é ímpar, (n divide (i-k) ). Uma vez que (i ) e (k ) estão em (0,1, ldots, n-1 ), (0 le i-k le n-1 ). Destes valores, apenas (0 ) é divisível por (n ), então (i-k = 0 ). Assim, (B ) também é um quadrado latino.

Para mostrar que (A cup B ) contém todos os elementos (n ^ 2 ) de ( {0,1, ldots, n-1 } times {0,1, ldots, n -1 } ), é suficiente mostrar que não há dois elementos de (A cup B ) iguais. Suponha que ((i_1 + j_1,2i_1 + j_1) = (i_2 + j_2,2i_2 + j_2) ) (a aritmética é mod (n )). Então, subtraindo as equações, (i_1 = i_2 ); com a primeira equação, isso implica (j_1 = j_2 ).

(quadrado)

Exemplo 4.3.10 Quando (n = 3 ), $$ left [ matrix {0 & 1 & 2 cr 1 & 2 & 0 cr 2 & 0 & 1 cr} right] cup left [ matrix {0 & 1 & 2 cr 2 & 0 & 1 cr 1 & 2 & 0 cr} right] = left [ matrix {(0,0) & (1,1) & (2,2) cr (1,2) & (2,0) & (0,1) cr (2,1) & (0,2) & (1,0) cr} right]. $$

Uma abordagem óbvia para construir quadrados latinos, e pares de quadrados latinos ortogonais, é começar com quadrados latinos menores e usá-los para produzir quadrados maiores. Vamos produzir um quadrado latino de ordem (mn ) a partir de um quadrado latino de ordem (m ) e outro de ordem (n ).

Seja (A ) um quadrado latino de ordem (m ) com símbolos (1, ldots, m ) e (B ) um quadrado de ordem (n ) com símbolos (1, ldots, n ). Sejam (c_ {i, j} ), (1 le i le m ), (1 le j le n ), ser (mn ) novos símbolos. Forme uma grade (mn times mn ) substituindo cada entrada de (B ) por uma cópia de (A ). Em seguida, substitua cada entrada (i ) nesta cópia de (A ) por (c_ {i, j} ), onde (j ) é a entrada de (B ) que foi substituída. Denotamos este novo quadrado latino (A vezes B ). Aqui está um exemplo, combinando um quadrado latino (4 vezes 4 ) com um quadrado latino (3 vezes 3 ) para formar um quadrado latino (12 vezes 12 ):}

(1)(2)(3)(4)
(2)(3)(4)(1)
(3)(4)(1)(2)
(4)(1)(2)(3)
( vezes )
(1)(2)(3)
(2)(3)(1)
(3)(1)(2)
(=)
(c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} )
(c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} )
(c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} )
(c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} )
(c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} )
(c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} )
(c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} )
(c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} )
(c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} )
(c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} )
(c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} )
(c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} )
(c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} )
(c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} )
(c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} )
(c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} )
(c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} )
(c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} )
(c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} )
(c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} )
(c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} )
(c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} )
(c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} )
(c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} )
(c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} )
(c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} )
(c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} )
(c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} )
(c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} )
(c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} )
(c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} )
(c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} )
(c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} )
(c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} )
(c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} )
(c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} )

Teorema 4.3.11

f (A ) e (B ) são quadrados latinos, assim como (A vezes B ).

Prova

Considere dois símbolos (c_ {i, j} ) e (c_ {k, l} ) na mesma linha. Se as posições contendo esses símbolos estão na mesma cópia de (A ), então (i not = k ), uma vez que (A ) é um quadrado latino, e assim os símbolos (c_ {i, j} ) e (c_ {k, l} ) são distintos. Caso contrário, (j not = l ), uma vez que (B ) é um quadrado latino. O argumento é o mesmo para colunas.

(quadrado)

Notavelmente, esta operação preserva ortogonalidade:

Teorema 4.3.12

Se (A_1 ) e (A_2 ) são quadrados latinos de ordem (m ), (B_1 ) e (B_2 ) são quadrados latinos de ordem (n ), (A_1 ) e (A_2 ) são ortogonais, e (B_1 ) e (B_2 ) são ortogonais, então (A_1 vezes B_1 ) é ortogonal a (A_1 vezes B_2 ).

Prova

Denotamos o conteúdo de (A_i times B_i ) por (C_i (w, x, y, z) ), significando a entrada na linha (w ) e coluna (x ) da cópia de (A_i ) que substituiu a entrada na linha (y ) e coluna (z ) de (B_i ), que denotamos (B_i (y, z) ). Usamos (A_i (w, x) ) para denotar a entrada na linha (w ) e coluna (x ) de (A_i ).

Suponha que ((C_1 (w, x, y, z), C_2 (w, x, y, z)) = (C_1 (w ', x', y ', z'), C_2 (w ', x ', y', z ')) ), onde ((w, x, y, z) não = (w', x ', y', z ') ). Ou ((w, x) not = (w ', x') ) ou ((y, z) not = (y ', z') ). Se for o último, então ((B_1 (y, z), B_2 (y, z)) = (B_1 (y ', z'), B_2 (y ', z')) ), uma contradição, uma vez que (B_1 ) é ortogonal a (B_2 ). Portanto, ((y, z) = (y ', z') ) e ((w, x) não = (w ', x') ). Mas isso implica que ((A_1 (w, x), A_2 (w, x)) = (A_1 (w ', x'), A_2 (w ', x')) ), uma contradição. Portanto, (A_1 vezes B_1 ) é ortogonal a (A_1 vezes B_2 ).

(quadrado)

Queremos construir quadrados latinos ortogonais de ordem (4k ). Escreva (4k = 2 ^ m cdot n ), onde (n ) é ímpar e (m ge 2 ). Sabemos que existem quadrados latinos ortogonais de ordem (n ), por teorema 4.3.9. Se houver quadrados latinos ortogonais de ordem (2 ^ m ), então por teorema 4.3.12 podemos construir quadrados latinos ortogonais de ordem (4k = 2 ^ m cdot n ).

Para obter um quadrado latino de ordem (2 ^ m ), também usamos o teorema 4.3.12. Basta encontrar dois quadrados latinos ortogonais de ordem (4 = 2 ^ 2 ) e dois de ordem (8 = 2 ^ 3 ). Em seguida, aplicação repetida do teorema 4.3.12 nos permite construir quadrados latinos ortogonais de ordem (2 ^ m ), (m ge 2 ).

Dois quadrados latinos ortogonais de ordem 4:

$$ left [ matrix {1 & 2 & 3 & 4 cr 2 & 1 & 4 & 3 cr 3 & 4 & 1 & 2 cr 4 & 3 & 2 & 1 cr} right] left [ matrix {1 & 2 & 3 & 4 cr 3 & 4 & 1 & 2 cr 4 & 3 & 2 & 1 cr 2 & 1 & 4 & 3 cr} right], $$

e dois da ordem 8:

$$ esquerda [ matriz {1 & 3 & 4 & 5 & 6 & 7 & 8 & 2 cr 5 & 2 & 7 & 1 & 8 & 4 & 6 & 3 cr 6 & 4 & 3 & 8 & 1 & 2 & 5 & 7 cr 7 & 8 & 5 & 4 & 2 & 1 & 3 & 6 cr 8 & 7 & 2 & 6 & 5 & 3 & 1 & 4 cr 2 & 5 & 8 & 3 & 7 & 6 & 4 & 1 cr 3 & 1 & 6 & 2 & 4 & 8 & 7 & 5 cr 4 & 6 & 1 & 7 & 3 & 5 & 2 & 8 cr} direita] esquerda [ matriz {1 & 4 & 5 & 6 & 7 & 8 & 2 & 3 cr 8 & 2 & 6 & 5 & 3 & 1 & 4 & 7 cr 2 & 8 & 3 & 7 & 6 & 4 & 1 & 5 cr 3 & 6 & 2 & 4 & 8 & 7 & 5 & 1 cr 4 & 1 & 7 & 3 & 5 & 2 & 8 & 6 cr 5 & 7 & 1 & 8 & 4 & 6 & 3 & 2 cr 6 & 3 & 8 & 1 & 2 & 5 & 7 & 4 cr 7 & 5 & 4 & 2 & 1 & 3 & 6 & 8 cr} right]. $$


Assista o vídeo: - Princípio do Método dos Mínimos Quadrados (Dezembro 2021).