4.4: Cuadrados latinos
- Page ID
- 117113
Definición\(\PageIndex{1}\): Latin Square
Un cuadrado latino de orden\(n\) es una\(n\times n\) cuadrícula llena de\(n\) símbolos para que cada símbolo aparezca una vez en cada fila y columna.
Ejemplo\(\PageIndex{1}\)
Aquí hay un cuadrado latino de orden 4:
| ♥ | ♣ | ♠ | ♦ |
| ♣ | ♠ | ♦ | ♥ |
| ♠ | ♦ | ♥ | ♣ |
| ♦ | ♥ | ♣ | ♠ |
Por lo general, usamos los enteros\(1\ldots n\) para los símbolos. Hay muchos, muchos cuadrados latinos de orden\(n\), por lo que vale la pena limitar el número al acordar no contar cuadrados latinos que son “realmente iguales” que diferentes. La forma más sencilla de hacerlo es considerar cuadrados latinos reducidos. Un cuadrado latino reducido es aquel en el que la primera fila está\(1\ldots n\) (en orden) y la primera columna es igualmente\(1\ldots n\).
Ejemplo\(\PageIndex{2}\)
Considera este cuadrado latino:
| 4 | 2 | 3 | 1 |
| 2 | 4 | 1 | 3 |
| 1 | 3 | 4 | 2 |
| 3 | 1 | 2 | 4 |
El orden de las filas y columnas no es realmente importante para la idea de un cuadrado latino. Si reordenamos las filas y columnas, podemos considerar que el resultado es en esencia el mismo cuadrado latino. Al reordenar las columnas, podemos convertir el cuadrado de arriba en esto:
| 1 | 2 | 3 | 4 |
| 3 | 4 | 1 | 2 |
| 2 | 3 | 4 | 1 |
| 4 | 1 | 2 | 3 |
Entonces podemos intercambiar las filas dos y tres:
| 1 | 2 | 3 | 4 |
| 2 | 3 | 4 | 1 |
| 3 | 4 | 1 | 2 |
| 4 | 1 | 2 | 3 |
Este cuadrado latino está en forma reducida, y es esencialmente el mismo que el original.
Otra forma sencilla de cambiar la apariencia de un cuadrado latino sin cambiar su estructura esencial es intercambiar los símbolos.
Ejemplo\(\PageIndex{3}\)
Comenzando con el mismo cuadrado latino que antes:
| 4 | 2 | 3 | 1 |
| 2 | 4 | 1 | 3 |
| 1 | 3 | 4 | 2 |
| 3 | 1 | 2 | 4 |
podemos intercambiar los símbolos 1 y 4 para obtener:
| 1 | 2 | 3 | 4 |
| 2 | 1 | 4 | 3 |
| 4 | 3 | 1 | 2 |
| 3 | 4 | 2 | 1 |
Ahora si intercambiamos las filas tres y cuatro obtenemos:
| 1 | 2 | 3 | 4 |
| 2 | 1 | 4 | 3 |
| 3 | 4 | 2 | 1 |
| 4 | 3 | 1 | 2 |
Observe que este cuadrado latino está en forma reducida, pero no es lo mismo que la forma reducida del ejemplo anterior, aunque empezamos con el mismo cuadrado latino. Por lo tanto, tal vez queramos considerar que algunos cuadrados latinos reducidos son iguales entre sí.
Definición\(\PageIndex{2}\): Isotopic and Isotopy Classes
Dos cuadrados latinos son isotópicos si cada uno se puede convertir en el otro permutando las filas, columnas y símbolos. Esta relación de isotopía es una relación de equivalencia; las clases de equivalencia son las clases de isotopía.
Al parecer, los cuadrados latinos son bastante difíciles de contar sin una potencia de cálculo sustancial. El número de cuadrados latinos se conoce sólo hasta\(n=11\). Estos son los primeros valores para todos los cuadrados latinos, cuadrados latinos reducidos y cuadrados latinos no isotópicos (es decir, el número de clases de isotopía):
| \(n\) | Todos | Reducida | No isotópico |
|---|---|---|---|
| \ (n\) ">1 | 1 | 1 | 1 |
| \ (n\) ">2 | 2 | 1 | 1 |
| \ (n\) ">3 | 12 | 1 | 1 |
| \ (n\) ">4 | 576 | 4 | 2 |
| \ (n\) ">5 | 161280 | 56 | 2 |
¿Cómo podemos producir un cuadrado latino? Si sabes lo que es un grupo, debes saber que la tabla de multiplicar de cualquier grupo finito es un cuadrado latino. (También, cualquier cuadrado latino es la tabla de multiplicación de un cuasigrupo.) Incluso si no has encontrado grupos con ese nombre, quizás conozcas algunos. Por ejemplo, considerando el módulo de enteros\(n\) en adición, la tabla de suma es un cuadrado latino.
Ejemplo \(\PageIndex{4}\)
Aquí está la tabla de suma para los enteros módulo 6:
| 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 2 | 3 | 4 | 5 | 0 |
| 2 | 3 | 4 | 5 | 0 | 1 |
| 3 | 4 | 5 | 0 | 1 | 2 |
| 4 | 5 | 0 | 1 | 2 | 3 |
| 5 | 0 | 1 | 2 | 3 | 4 |
Ejemplo \(\PageIndex{5}\)
Aquí hay otra forma de generar potencialmente muchos cuadrados latinos. Comienza con la primera fila\(1,\ldots, n\). Considera los conjuntos\(A_i=[n]\backslash\{i\}\). Del Ejercicio 4.E.1.1 en la Sección 4.E sabemos que este sistema de conjunto tiene muchos sdr s; si\(x_1,x_2,\ldots,x_n\) es un sdr, podemos usarlo para la fila dos. En general, después de haber elegido filas\(1,\ldots,j\), dejamos\(A_i\) ser el conjunto de enteros que aún no han sido elegidos para columna\(i\). Este sistema de conjunto tiene un sdr, que utilizamos para fila\(j+1\).
Definición\(\PageIndex{3}\): Orthogonal
Supongamos\(A\) y\(B\) son dos cuadrados latinos de orden\(n\), con entradas\(A_{i,j}\) y\(B_{i,j}\) en fila\(i\) y columna\(j\). Formar la matriz\(M\) con entradas\(M_{i,j}=(A_{i,j},B_{i,j})\); denotaremos esta operación como\(M=A\cup B\). Decimos eso\(A\) y\(B\) son ortogonales si\(M\) contiene todos los pares\(n^2\) ordenados\((a,b)\)\(1\le a\le n\),,\(1\le b\le n\), es decir, todos los elementos de\(\{0,1,\ldots,n-1\}\times\{0,1,\ldots,n-1\}\).
Como veremos, es fácil encontrar cuadrados latinos ortogonales de orden\(n\) si\(n\) es impar; no demasiado difícil encontrar cuadrados latinos ortogonales de orden\(4k\), y difícil pero posible encontrar cuadrados latinos ortogonales de orden\(4k+2\), con la excepción de órdenes\(2\) y\(6\). En la década de 1700, Euler demostró que existen cuadrados latinos ortogonales de todos los órdenes excepto de orden\(4k+2\), y conjeturó que no hay cuadrados latinos ortogonales de orden\(6\). En 1901, el matemático aficionado Gaston Tarry demostró que efectivamente no hay nada de orden\(6\), al demostrar que todas las posibilidades para tales cuadrados latinos no lograron ser ortogonales. En 1959 finalmente se demostró que hay cuadrados latinos ortogonales de todos los demás órdenes.
Teorema \(\PageIndex{1}\)
Hay pares de cuadrados latinos ortogonales de orden\(n\) cuando\(n\) es impar.
- Prueba
-
Esta prueba se puede acortar utilizando ideas de teoría de grupos, pero presentaremos una versión autónoma. Considere la tabla de adición para el mod de adición\(n\):
0 \(\cdots\) \(j\) \(\cdots\) \(n-1\) 0 0 \(\cdots\) \(j\) \(\cdots\) \(n-1\) \(\vdots\) \(i\) \(i\) \(\cdots\) \(i+j\) \(\cdots\) \(n+i-1\) \(\vdots\) \(n-1\) \(n-1\) \(\cdots\) \(n+j-1\) \(\cdots\) \(n-2\) Afirmamos primero que esta (sin la primera fila y columna, por supuesto) es un cuadrado latino con símbolos\(0,1,\ldots,n-1\). Considera dos entradas en fila\(i\), digamos\(i+j\) y\(i+k\). Si\(i+j\equiv i+j \pmod{n}\), entonces\(j\equiv k\), así\(j=k\). Así, todas las entradas de fila\(i\) son distintas, por lo que cada una de\(0,1,\ldots,n-1\) aparece exactamente una vez en fila\(i\). La prueba de que cada uno aparece una vez en cualquier columna es similar. Llama a esta plaza latina\(A\). (Tenga en cuenta que hasta el momento todo es cierto ya sea\(n\) impar o par.)
Ahora formamos un nuevo cuadrado\(B\) con entradas\(B_{i,j}=A_{2i,j}=2i+j\), donde por\(2i\) y\(2i+j\) nos referimos a esos valores mod\(n\). Así fila\(i\) de\(B\) es lo mismo que fila\(2i\) de\(A\). Ahora afirmamos que de hecho las filas de\(B\) son exactamente las filas de\(A\), en un orden diferente. Para ello, basta con demostrar que si\(2i\equiv 2k\pmod{n}\), entonces\(i=k\). Esto implica que todas las filas de\(B\) son distintas, y por lo tanto deben ser todas las filas de\(A\).
Supongamos que sin pérdida de generalidad eso\(i\ge k\). Si\(2i\equiv 2k\pmod{n}\) entonces\(n| 2(i-k)\). Ya que\(n\) es impar,\(n| (i-k)\). Desde\(i\) y\(k\) están en\(0,1,\ldots,n-1\),\(0\le i-k\le n-1\). De estos valores, sólo\(0\) es divisible por\(n\), así\(i-k=0\). Así también\(B\) es un cuadrado latino.
Para mostrar que\(A\cup B\) contiene todos los\(n^2\) elementos de\(\{0,1,\ldots,n-1\}\times\{0,1,\ldots,n-1\}\), basta con mostrar que no hay dos elementos de\(A\cup B\) iguales. Supongamos que\((i_1+j_1,2i_1+j_1)=(i_2+j_2,2i_2+j_2)\) (la aritmética es mod\(n\)). Entonces restando ecuaciones,\(i_1=i_2\); con la primera ecuación esto implica\(j_1=j_2\).
Ejemplo \(\PageIndex{6}\)
Cuando\(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]. \nonumber \]
Un enfoque obvio para construir cuadrados latinos, y pares de cuadrados latinos ortogonales, es comenzar con cuadrados latinos más pequeños y usarlos para producir cuadrados más grandes. Produciremos un cuadrado latino de orden\(mn\) a partir de un cuadrado latino de orden\(m\) y uno de orden\(n\).
\(A\)Sea un cuadrado latino de orden\(m\) con símbolos\(1,\ldots,m\), y\(B\) uno de orden\(n\) con símbolos\(1,\ldots,n\). Que\(c_{i,j}\),\(1\le i\le m\),\(1\le j\le n\), sean\(mn\) nuevos símbolos. Formar una\(mn\times mn\) cuadrícula reemplazando cada entrada de\(B\) con una copia de\(A\). Después reemplace cada entrada\(i\) en este ejemplar de\(A\) por\(c_{i,j}\), donde\(j\) está la entrada de la\(B\) que fue reemplazada. Denotamos este nuevo cuadrado latino\(A\times B\). Aquí hay un ejemplo, combinando un cuadrado\(4\times 4\) latino con un cuadrado\(3\times 3\) latino para formar un cuadrado\(12\times 12\) latino:}
\ [\ begin {array} {llll}
1 & 2 & 3 & 4\\
2 & 3 & 4 & 1\\
3 & 4 & 1 & 2 & 2 & 3
\ end {array}\ times\ begin {array} {lll}
1 & 2 & 3\\
2 & 3 &
1\\
3 & 1 y 2
\ end {array} =\ begin {array} {llllllllll}
c_ {1,1} & c_ {2,1} & c_ {3,1} & c_ {4,1} & c_ {1,2} & c_ {2,2} & c_ {3,2} & c_ {4,2} & c_ {1,3} & c_ {2,3} & c_ {3,3} & c_ {3,3} & c_ {3,3} & _ {4,3}\\
c_ {2,1} & c_ {3,1} & amp; c_ {4,1} & c_ {1,1} & c_ {2,2} & c_ {3,2} & c_ {4,2} & c_ {1,2} & c_ {2,3} & c_ {3,3} & c_ {4,3} & c_ {1,3}\
c_ {3,1} & c_ {4,1} & c_ {1,1} & c_ {2,1} & c_ {3,2} & c_ {4,2} & c_ {1,2} & c_ {2,2} & c_ {3,3} & c_ {4,3} & c_ {1,3} & c_ {2,3}\\
c_ {4,1} & c_ {1,1} & c_ {2,1} & c_ {3,1} & c_ {4,2} & c_ {1,2} & c_ {2,2} & c_ {3,2} & c_ {4,3} & c_ {1,3} & c_ {2,3} & c_ {3,3}\ c_ {1,2} & c_ {2,2} & c_ {2,2} & c_ {2,2} &
c_ {2,3} & c_ {3,3}\ c_ {1,2} & c_ {2,2} 3,2} & c_ {4,2} & c_ {1,3} & c_ {2,3} & c_ {3,3} & c_ {4,3} & c_ {4,3} & amp; c_ {1,1} & c_ {2,1} & c_ {3,1} & c_ {4,1}\\
c_ {2,2} & c_ {3,2} & c_ {4,2} & c_ {1,2} & c_ {2,3} & c_ {3,3} & c_ {4,3} & c_ {1,3} & c_ {2,1} & c_ {3,1} & c_ {4,1} & c_ {1,1}\\
c_ {3,2} & c_ {4,2} & c_ {1,2} & c_ {2,2} & c_ { 3,3} & c_ {4,3} & c_ {1,3} & c_ {2,3} & c_ {3,1} & c_ {4,1} & c_ {1,1} & c_ {2,1}\ c_ {4,2} &
c_ {1,2} & c_ {2,2} & c_ {3,2} & c_ {4,3} & c_ {4,3} & c_ {1,3} & c_ {2,3} y c_ {3,3} & c_ {3,3} & c_ {4,1} & c_ {1,1} & c_ {2,1} & c_ {3,1}\\
c_ {1,3} & amp; c_ {2,3} & c_ {3,3} & c_ {4,3} & c_ {1,1} & c_ {2,1} & c_ {3,1} & c_ {4,1} & c_ {1,2} & c_ {2,2} & c_ {3,2} & c_ {4,2}\\
c_ {2,3} & c_ {3,3} & c_ {4,3} & c_ {1,3} & c_ {1,3} & c_ {2,1} & c_ {3,1} & c_ {4,1} & c_ {1,1} & c_ {2,2} & c_ {3,2} & c_ {4,2} & c_ {1,2}\\
c_ {3,3} & c_ {4,3} & c_ {1,3} & c_ {2,3} & c_ {3,1} & c_ {4,1} & c_ {1,1} & c_ {2,1} & c_ {3,2} & c_ {4,2} & c_ {1,2} & c_ {2,2}\\ c_ {4,3} y
c_ {4,3} & c_ {4,2} 1,3} & c_ {2,3} & c_ {3,3} & c_ {4,1} & c_ {1,1} & c_ {2,1} & c_ {2,1} & amp; c_ {3,1} & c_ {4,2} & c_ {1,2} & c_ {2,2} & c_ {3,2}\
\ final {array}\ nonumber\]
Teorema \(\PageIndex{2}\)
Si\(A\) y\(B\) son cuadrados latinos, así es\(A\times B\).
- Prueba
-
Considera dos símbolos\(c_{i,j}\) y\(c_{k,l}\) en la misma fila. Si las posiciones que contienen estos símbolos están en la misma copia de\(A\), entonces\(i\not=k\), ya que\(A\) es un cuadrado latino, y así los símbolos\(c_{i,j}\) y\(c_{k,l}\) son distintos. De lo contrario\(j\not=l\),, ya que\(B\) es un cuadrado latino. El argumento es el mismo para las columnas.
Notablemente, esta operación preserva la ortogonalidad:
Teorema \(\PageIndex{3}\)
Si\(A_1\) y\(A_2\) son cuadrados latinos de orden\(m\),\(B_1\) y\(B_2\) son cuadrados latinos de orden\(n\),\(A_1\) y\(A_2\) son ortogonales, y\(B_1\) y\(B_2\) son ortogonales, entonces\(A_1\times B_1\) es ortogonal a\(A_1\times B_2\).
- Prueba
-
Denotamos el contenido de\(A_i\times B_i\) by\(C_i(w,x,y,z)\), es decir, la entrada en fila\(w\) y columna\(x\) de la copia de\(A_i\) que reemplazó la entrada en fila\(y\) y columna\(z\) de\(B_i\), que denotamos\(B_i(y,z)\). Utilizamos\(A_i(w,x)\) para denotar la entrada en fila\(w\) y columna\(x\) de\(A_i\).
Supongamos 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'))\), dónde\((w,x,y,z)\not=(w',x',y',z')\). \((w,x)\not=(w',x')\)O bien\((y,z)\not=(y',z')\). Si este último, entonces\((B_1(y,z),B_2(y,z))= (B_1(y',z'),B_2(y',z'))\), una contradicción, ya que\(B_1\) es ortogonal a\(B_2\). De ahí\((y,z)=(y',z')\) y\((w,x)\not=(w',x')\). Pero esto implica eso\((A_1(w,x),A_2(w,x))=(A_1(w',x'),A_2(w',x'))\), una contradicción. De ahí\(A_1\times B_1\) que sea ortogonal a\(A_1\times B_2\).
Queremos construir cuadrados ortogonales latinos de orden\(4k\). Escribir\(4k=2^m\cdot n\), donde\(n\) es impar y\(m\ge 2\). Sabemos que hay cuadrados ortogonales latinos de orden\(n\), por teorema\(\PageIndex{1}\). Si hay cuadrados latinos ortogonales de orden\(2^m\), entonces por Teorema\(\PageIndex{3}\) podemos construir cuadrados latinos ortogonales de orden\(4k=2^m\cdot n\).
Para obtener un cuadrado latino de orden\(2^m\), también utilizamos Teorema\(\PageIndex{3}\). Baste encontrar dos cuadrados latinos ortogonales de orden\(4=2^2\) y dos de orden\(8=2^3\). Entonces la aplicación repetida del Teorema nos\(\PageIndex{3}\) permite construir ortogonales cuadrados latinos de orden\(2^m\),\(m\ge 2\).
Dos cuadrados latinos ortogonales de orden 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], \nonumber \]
y dos del orden 8:
\[ \left[\matrix{ 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 }\right] \left[\matrix{ 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]. \nonumber \]