Cuadrado latino

Mostrando un 7 × 7 plaza latina, esta ventana de vidrio manchado en Gonville y Caius College, Cambridge honró a Ronald Fisher, cuyo Diseño de Experimentos discutidos cuadrados latinos. La ventana de Sir Ronald Fisher fue removida en 2020 debido a la conexión de Fisher con eugenesia.

En combinatoria y en diseño experimental, un cuadrado latino es una matriz n × n llena de n símbolos diferentes, cada uno de los cuales aparece exactamente una vez en cada fila y exactamente una vez en cada columna. Un ejemplo de un cuadrado latino de 3×3 es

El nombre "cuadrado latino" se inspiró en los artículos matemáticos de Leonhard Euler (1707–1783), quien usó caracteres latinos como símbolos, pero se puede usar cualquier conjunto de símbolos: en el ejemplo anterior, la secuencia alfabética A, B, C se puede reemplazar por la secuencia entera 1, 2, 3. Euler comenzó la teoría general de los cuadrados latinos.

Historia

El matemático coreano Choi Seok-jeong fue el primero en publicar un ejemplo de cuadrados latinos de orden nueve, para construir un cuadrado mágico en 1700, anterior a Leonhard Euler por 67 años.

Forma reducida

Se dice que un cuadrado latino está reducido (también, normalizado o en forma estándar) si tanto su primera fila como su primera columna están en su orden natural. Por ejemplo, el cuadrado latino anterior no se reduce porque su primera columna es A, C, B en lugar de A, B, C.

Cualquier cuadrado latino se puede reducir permutando (es decir, reordenando) las filas y las columnas. Aquí, al cambiar la segunda y la tercera fila de la matriz anterior, se obtiene el siguiente cuadrado:

Este cuadrado latino se reduce; tanto su primera fila como su primera columna están ordenadas alfabéticamente A, B, C.

Propiedades

Representación de matriz ortogonal

Si cada entrada de un cuadrado latino n × n se escribe como un triple (r,c,s), donde r es la fila, c es la columna y s es el símbolo, obtener un conjunto de n² triples denominado representación de matriz ortogonal del cuadrado. Por ejemplo, la representación de matriz ortogonal del cuadrado latino

es

(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) },

donde, por ejemplo, el triple (2, 3, 1) significa que en la fila 2 y la columna 3 está el símbolo 1. Los arreglos ortogonales generalmente se escriben en forma de matriz donde los triples son las filas, como:

La definición de un cuadrado latino se puede escribir en términos de matrices ortogonales:

• Un cuadrado latino es un conjunto de n² triples (r, c, s), donde 1 ≤ r, c, s ≤ n, tal que todos los pares ordenados (r, c) son distintos, todos los pares ordenados (r, s) son distintos, y todos los pares ordenados (c, s) son distintos.

Esto significa que los n² pares ordenados (r, c) son todos los pares (i, j) con 1 ≤ i, j ≤ n, una vez cada uno. Lo mismo ocurre con los pares ordenados (r, s) y los pares ordenados (c, s).

La representación de matriz ortogonal muestra que las filas, las columnas y los símbolos desempeñan funciones bastante similares, como se aclarará a continuación.

Clases de equivalencia de cuadrados latinos

Muchas operaciones en un cuadrado latino producen otro cuadrado latino (por ejemplo, darle la vuelta).

Si permutamos las filas, permutamos las columnas y permutamos los nombres de los símbolos de un cuadrado latino, obtenemos un nuevo cuadrado latino que se dice que es isotópico al primero. El isotopismo es una relación de equivalencia, por lo que el conjunto de todos los cuadrados latinos se divide en subconjuntos, llamados clases de isotopía, de modo que dos cuadrados de la misma clase son isotópicos y dos cuadrados de clases diferentes no son isotópicos.

Otro tipo de operación es más fácil de explicar utilizando la representación de matriz ortogonal del cuadrado latino. Si reordenamos sistemática y consistentemente los tres elementos de cada terna (es decir, permutamos las tres columnas en forma de matriz), se obtiene otra matriz ortogonal (y, por tanto, otro cuadrado latino). Por ejemplo, podemos reemplazar cada triple (r,c,s) por (c, r,s) que corresponde a trasponer el cuadrado (reflejándose sobre su diagonal principal), o podríamos sustituir cada triple (r,c,s) por (c,s,r), que es una operación más complicada. En total, hay 6 posibilidades que incluyen "no hacer nada", lo que nos da 6 cuadrados latinos llamados conjugados (también parástrofes) del cuadrado original.

Finalmente, podemos combinar estas dos operaciones de equivalencia: se dice que dos cuadrados latinos son paratópicos, también isotópicos de clase principal, si uno de ellos es isotópico a un conjugado del otro. Esta es nuevamente una relación de equivalencia, con las clases de equivalencia llamadas clases principales, especies o clases de paratopía. Cada clase principal contiene hasta seis clases de isotopía.

Número de n × n cuadrados latinos

No existe una fórmula fácil de calcular conocida para el número L_n de n × n Cuadrados latinos con símbolos 1, 2,..., n. Los límites superior e inferior más precisos conocidos para grandes n están muy separados. Un resultado clásico es que

∏ ∏ k=1n()k!)n/k≥ ≥ Ln≥ ≥ ()n!)2nnn2.{displaystyle prod _{k=1}n}left(k!right)^{n/k}geq ¿Qué?

En 1992 se publicó una fórmula simple y explícita para el número de cuadrados latinos, pero aún no es fácil de calcular debido al aumento exponencial en el número de términos. Esta fórmula para el número L_n de n × n cuadrados latinos es

Ln=n!.. A▪ ▪ Bn()− − 1)σ σ 0()A)()per⁡ ⁡ An),{displaystyle ¡No! ¿Qué?

La siguiente tabla contiene todos los valores exactos conocidos. Se puede ver que los números crecen extremadamente rápido. Para cada n, el número de cuadrados latinos en total (secuencia A002860 en la OEIS) es n! (n − 1)! veces el número de cuadrados latinos reducidos (secuencia A000315 en el OEIS).

Para cada n, cada clase de isotopía (secuencia A040082 en la OEIS) contiene hasta (n!)³ cuadrados latinos (el número exacto varía), mientras que cada clase principal (secuencia A003090 en el OEIS) contiene 1, 2, 3 o 6 clases de isotopía.

El número de cuadrados latinos estructuralmente distintos (es decir, los cuadrados no pueden hacerse idénticos por medio de rotación, reflexión y/o permutación de los símbolos) para n = 1 hasta 7 es 1, 1, 1, 12, 192, 145164, 1524901344 respectivamente (secuencia A264603 en el OEIS).

Ejemplos

Damos un ejemplo de un cuadrado latino de cada clase principal hasta el orden cinco.

[1][1221][123231312]{displaystyle {begin{bmatrix}1end{bmatrix}quad {begin{bmatrix}1⁄222end{bmatrix}quad {begin{bmatrix}1 tendrían una relación32}

[1234214334124321][1234241331424321]{displaystyle {begin{bmatrix}1 tendría2 segundos3 tendría42}}quad {begin{bmatrix}1 tendrían una relación32}}

[1234523514354214125354132][1234524153354214153253214]{displaystyle {begin{bmatrix}1 tendría2 segundos3 tarde52 tendría52 punto3 tendría43 diez43 limitaciones4 limitada2 limitada14 limitada14 limitada14 con 3 péndulo35 péndulo1 3 péndulo 2end{bmatrix}quad {begin{bmatrix}1 tendría2 segundos3 tendría4 resultados52 tendría4 afectados1 tendrían 3 años 33 limitada5 limitada4 limitada2 correspond14 limitada14 reducida14 con 3 resultados25 con 3 pacientes2 afectados1 con 3 púlpitos 1 péndulo.

Presentan, respectivamente, las tablas de multiplicar de los siguientes grupos:

• {0} – el grupo trivial de 1 elemento
• Z2{displaystyle mathbb {Z} _{2} – el grupo binario
• Z3{displaystyle mathbb {Z} _{3} – grupo cíclico de orden 3
• Z2× × Z2{displaystyle mathbb {Z} _{2}times mathbb {Z} _{2} – el grupo Klein
• Z4{displaystyle mathbb {Z} _{4} – grupo cíclico de orden 4
• Z5{displaystyle mathbb {Z} _{5} – grupo cíclico de orden 5
• el último es un ejemplo de un cuasigrupo, o más bien un bucle, que no es asociativo.

Correspondencias transversales y arcoiris

Un transversal en un cuadrado latino es una elección de n celdas, donde cada fila contiene una celda, cada columna contiene una celda y hay una celda que contiene cada símbolo.

Se puede considerar un cuadrado latino como un grafo bipartito completo en el que las filas son vértices de una parte, las columnas son vértices de la otra parte, cada celda es una arista (entre su fila y su columna), y los símbolos son colores Las reglas de los cuadrados latinos implican que esta es una coloración de borde adecuada. Con esta definición, una transversal latina es un emparejamiento en el que cada arista tiene un color diferente; tal combinación se llama combinación de arco iris.

Por lo tanto, muchos resultados sobre cuadrados/rectángulos latinos están contenidos en documentos con el término "coincidencia arcoíris" en su título, y viceversa.

Algunos cuadrados latinos no tienen transversal. Por ejemplo, cuando n es par, un cuadrado latino n-by-n en el que el valor de la celda i,j es (i+j) mod n no tiene transversal. He aquí dos ejemplos:

[1221][1234234134124123]{displaystyle {begin{bmatrix}1 tendría22 limit1end{bmatrix}quad {begin{bmatrix}1}1 tendría2 ventaja42 con 3 contacto13 coincidiendo13 con 4 con 3 con 3 con 3 con 3 con 3 con 3 con 3 con 3 con 3 con 3 con 3 con 3 con 3 con 3 con 3 y 2 con 3 con 3.

En 1975, S. K. Stein y Brualdi conjeturaron que, cuando n es par, cada n-por-n El cuadrado latino tiene una transversal parcial de tamaño n−1.

Una conjetura más general de Stein es que una transversal de tamaño n−1 existe no solo en cuadrados latinos sino también en cualquier n-por-n matriz de n símbolos, siempre que cada símbolo aparezca exactamente n veces.

Se han probado algunas versiones más débiles de estas conjeturas:

• Cada uno n-por-n Plaza latina tiene una transversal parcial de tamaño 2n/3.
• Cada uno n-por-n Plaza latina tiene una transversal parcial de tamaño n − sqrt(n).
• Cada uno n-por-n Plaza latina tiene una transversal parcial de tamaño n − 11 troncos²
  ₂()n).

Algoritmos

Para cuadrados pequeños es posible generar permutaciones y probar si se cumple la propiedad del cuadrado latino. Para cuadrados más grandes, Jacobson y Matthews' El algoritmo permite muestrear a partir de una distribución uniforme sobre el espacio de n × n cuadrados latinos.

Aplicaciones

Estadística y matemáticas

• En el diseño de experimentos, los cuadrados latinos son un caso especial de diseños de columna para dos factores de bloqueo.
• En álgebra, los cuadrados latinos están relacionados con generalizaciones de grupos; en particular, los cuadrados latinos se caracterizan por ser las tablas de multiplicación (Cayley tablas) de cuasigrupos. Una operación binaria cuya tabla de valores forma una plaza latina se dice que obedece la propiedad cuadrada latina.

Códigos de corrección de errores

Los conjuntos de cuadrados latinos que son ortogonales entre sí han encontrado una aplicación como códigos de corrección de errores en situaciones en las que la comunicación se ve perturbada por más tipos de ruido que el simple ruido blanco, como cuando se intenta transmitir Internet de banda ancha a través de líneas eléctricas.

En primer lugar, el mensaje se envía utilizando varias frecuencias o canales, un método común que hace que la señal sea menos vulnerable al ruido en cualquier frecuencia específica. Una letra del mensaje a enviar se codifica mediante el envío de una serie de señales a diferentes frecuencias en intervalos de tiempo sucesivos. En el siguiente ejemplo, las letras A a L se codifican mediante el envío de señales en cuatro frecuencias diferentes, en cuatro intervalos de tiempo. La letra C, por ejemplo, se codifica enviando primero en la frecuencia 3, luego 4, 1 y 2.

ABCD[1234214334124321]EFGH[1342243131244213]IJKL[1423231432414132]{begin{begin{matrix}AB\c\c\c\c\d\d\dd\ddd\dcH}{begin{bmatrix}1}1⁄4c}dcH0}ccH0}ccH3c}c}c}c}c}c}cc}cc}c}c}c}c}cc}c}c}ccc}ccccccc}cccccccc}c}cc}c}cccccccccc}cccccccccccccccc}ccc {begin{matrix}EF\G\\H\\end{matrix}{begin{bmatrix}1 implica3 implica22 implica4 implica3 implica13 implica1}3 implicados14 implicados2 conciliados1 con 3\\\4}quad {begin{matrix}IJ\K\\\fn}{begin{bmatrix}1 tendría4 consecuencias32 implica32 implica3 implica1 implica43 implica2 implica14 implica14 simultáneamente1}}}}}}}}}

La codificación de las doce letras se forma a partir de tres cuadrados latinos que son ortogonales entre sí. Ahora imagine que se agrega ruido en los canales 1 y 2 durante toda la transmisión. La letra A sería entonces recogida como:

1212123124{displaystyle {begin{matrix}12 implica123 implica124end{matrix}}

En otras palabras, en la primera ranura recibimos señales tanto de la frecuencia 1 como de la frecuencia 2; mientras que la tercera ranura tiene señales de las frecuencias 1, 2 y 3. Debido al ruido, ya no podemos saber si las dos primeras ranuras eran 1,1 o 1,2 o 2,1 o 2,2. Pero el caso 1,2 es el único que produce una secuencia que coincide con una letra de la tabla anterior, la letra A. De manera similar, podemos imaginar un estallido de estática en todas las frecuencias en la tercera ranura:

1212344{displaystyle {begin{matrix}1 ventaja2 limitada1234 implica4end{matrix}}

De nuevo, podemos inferir de la tabla de codificaciones que debe haber sido la letra A la que se está transmitiendo. El número de errores que este código puede detectar es uno menos que el número de intervalos de tiempo. También se ha demostrado que si el número de frecuencias es un primo o una potencia de un primo, los cuadrados latinos ortogonales producen códigos de detección de errores que son lo más eficientes posible.

Acertijos matemáticos

El problema de determinar si un cuadrado parcialmente lleno se puede completar para formar un cuadrado latino es NP-completo.

Los populares Sudoku son un caso especial de los cuadrados latinos; cualquier solución a un Sudoku es un cuadrado latino. Sudoku impone la restricción adicional de que nueve subcuadrados adyacentes particulares de 3 × 3 también deben contener los dígitos 1–9 (en la versión estándar). Ver también Matemáticas de Sudoku.

Los rompecabezas KenKen y Strimko más recientes también son ejemplos de cuadrados latinos.

Juegos de mesa

Los cuadrados latinos se han utilizado como base para varios juegos de mesa, en particular el popular juego de estrategia abstracto Kamisado.

Investigación agronómica

Los cuadrados latinos se utilizan en el diseño de experimentos de investigación agronómica para minimizar los errores experimentales.

Heráldica

El cuadrado latino también figura en los brazos de la Sociedad de Estadística de Canadá, y se menciona específicamente en su blasón. Además, aparece en el logo de la Sociedad Internacional de Biometría.

Generalizaciones

• Un rectángulo latino es una generalización de una plaza latina en la que hay n columnas y n valores posibles, pero el número de filas puede ser menor que n. Cada valor todavía aparece a la mayoría de una vez en cada fila y columna.
• Una plaza Graeco-Latin es un par de dos plazas latinas de tal manera que, cuando uno se coloca encima del otro, cada par de símbolos ordenados aparece exactamente una vez.
• Un hipercubo latino es una generalización de un cuadrado latino de dos dimensiones a múltiples dimensiones.