En combinatoria y en diseño experimental , un cuadrado latino es una matriz n × n llena de n símbolos diferentes, cada uno exactamente una vez en cada fila y exactamente una vez en cada columna. Un ejemplo de un cuadrado latino de 3x3 es:
| UNA | si | do |
| do | UNA | si |
| si | do | UNA |
El nombre "cuadrado latino" se inspiró en los documentos matemáticos de Leonhard Euler (1707–1783), que usó caracteres latinos como símbolos, [1] pero se puede usar cualquier conjunto de símbolos: en el ejemplo anterior, la secuencia alfabética A, B , C puede ser reemplazado por la secuencia entera 1, 2, 3. Euler comenzó la teoría general de los cuadrados latinos.
Historia [ editar ]
El matemático coreano Choi Seok-jeong fue el primero en publicar un ejemplo de cuadrados latinos de orden nueve, con el fin de construir un cuadrado mágico en 1700, anterior a Leonhard Euler por 67 años. [2]
Forma reducida [ editar ]
Se dice que un cuadrado latino se reduce (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 de arriba 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 columnas. Aquí, cambiar las filas segunda y tercera de la matriz anterior produce el siguiente cuadrado:
| UNA | si | do |
| si | do | UNA |
| do | UNA | si |
Este cuadrado latino se reduce; Tanto su primera fila como su primera columna están ordenadas alfabéticamente A, B, C.
Propiedades [ editar ]
Representación de matriz ortogonal [ editar ]
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, obtenemos un conjunto de n 2 triples llamado representación de matriz ortogonal del cuadrado. Por ejemplo, la representación de matriz ortogonal del siguiente cuadrado latino es:
| 1 | 2 | 3 |
| 2 | 3 | 1 |
| 3 | 1 | 2 |
- {(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. La definición de un cuadrado latino se puede escribir en términos de matrices ortogonales:
- Un cuadrado latino es un conjunto de n 2 triples ( r , c , s ), donde 1 ≤ r , c , s ≤ n , de modo 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 2 pares ordenados ( r , c ) son todos los pares ( i , j ) con 1 ≤ i , j ≤ n , una vez cada uno. Lo mismo es cierto para los pares ordenados ( r , s ) y los pares ordenados ( c , s ).
La representación de matriz ortogonal muestra que las filas, columnas y símbolos juegan roles bastante similares, como se aclarará a continuación.
Clases de equivalencia de cuadrados latinos [ editar ]
Muchas operaciones en un cuadrado latino producen otro cuadrado latino (por ejemplo, al revés).
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 en la misma clase son isotópicos y dos cuadrados en diferentes clases 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 en cada triple, se obtiene otra matriz ortogonal (y, por lo tanto, otro cuadrado latino). Por ejemplo, podemos reemplazar cada triple ( r , c , s ) por ( c , r , s ) que corresponde a la transposición del cuadrado (reflejando su diagonal principal), o podríamos reemplazar 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 paratrophes ) 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 la clase principal , si uno de ellos es isotópico a un conjugado del otro. Esto es nuevamente una relación de equivalencia, con las clases de equivalencia llamadas clases principales , especies o clases de paratopia . Cada clase principal contiene hasta 6 clases de isotopía.
Número [ editar ]
No se conoce una fórmula fácil de calcular 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 [3] es que
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
donde B n es el conjunto de todos los n × n {0, 1} matrices, σ 0 ( A ) es el número de entradas cero en la matriz A , y por ( A ) es la permanente de la matriz A . [4]
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 total de cuadrados latinos (secuencia A002860 en el OEIS ) es n ! ( n -1)! multiplicado por el número de cuadrados latinos reducidos (secuencia A000315 en el OEIS ).
| norte | cuadrados latinos reducidos de tamaño n | todos los cuadrados latinos de tamaño n |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 3 | 1 | 12 |
| 4 4 | 4 4 | 576 |
| 5 5 | 56 | 161,280 |
| 6 6 | 9,408 | 812,851,200 |
| 7 7 | 16.942.080 | 61,479,419,904,000 |
| 8 | 535,281,401,856 | 108,776,032,459,082,956,800 |
| 9 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 × 10 44 | ? |
| 13 | 2.51 × 10 56 | ? |
| 14 | 2.33 × 10 70 | ? |
| 15 | 1.50 × 10 86 | ? |
Para cada n , cada clase de isotopía (secuencia A040082 en el OEIS ) contiene hasta ( n !) 3 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.
| norte | clases principales | clases de isotopia |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 1 |
| 3 | 1 | 1 |
| 4 4 | 2 | 2 |
| 5 5 | 2 | 2 |
| 6 6 | 12 | 22 |
| 7 7 | 147 | 564 |
| 8 | 283,657 | 1,676,267 |
| 9 9 | 19,270,853,541 | 115,618,721,533 |
| 10 | 34,817,397,894,749,939 | 208,904,371,354,363,006 |
| 11 | 2,036,029,552,582,883,134,196,099 | 12,216,177,315,369,229,261,482,540 |
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 [ editar ]
Damos un ejemplo de un cuadrado latino de cada clase principal hasta el orden 5.
Presentan, respectivamente, las tablas de multiplicar de los siguientes grupos:
- {0} - el grupo trivial de 1 elemento
- - el grupo binario
- - grupo cíclico de orden 3
- - los cuatro grupos de Klein
- - grupo cíclico de orden 4
- - grupo cíclico de orden 5
- el último es un ejemplo de un cuasigrupo , o más bien un bucle , que no es asociativo.
Algoritmos [ editar ]
Para cuadrados pequeños es posible generar permutaciones y probar si se cumple la propiedad del cuadrado latino. Para cuadrados más grandes, el algoritmo de Jacobson y Matthews permite el muestreo a partir de una distribución uniforme sobre el espacio de n × n cuadrados latinos. [5]
Aplicaciones [ editar ]
Estadística y matemática [ editar ]
- En el diseño de experimentos , los cuadrados latinos son un caso especial de diseños de fila-columna para dos factores de bloqueo : [6] Muchos diseños de fila-columna se construyen mediante la concatenación de cuadrados latinos. [7]
- En álgebra , los cuadrados latinos son generalizaciones de grupos ; de hecho, los cuadrados latinos se caracterizan por ser tablas de multiplicación ( tablas de Cayley ) de cuasigrupos . Se dice que una operación binaria cuya tabla de valores forma un cuadrado latino obedece a la propiedad del cuadrado latino .
Error al corregir códigos [ editar ]
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. [8] [9] [10]
En primer lugar, el mensaje se envía usando 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 en el mensaje a enviar se codifica enviando una serie de señales a diferentes frecuencias en intervalos de tiempo sucesivos. En el siguiente ejemplo, las letras A a L se codifican enviando señales a cuatro frecuencias diferentes, en cuatro intervalos de tiempo. La letra C, por ejemplo, se codifica enviando primero a la frecuencia 3, luego 4, 1 y 2.
La codificación de las doce letras se forman a partir de tres cuadrados latinos que son ortogonales entre sí. Ahora imagine que hay ruido adicional en los canales 1 y 2 durante toda la transmisión. La letra A se recogería como:
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 fueron 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 en la tabla anterior, la letra A. Del mismo modo, podemos imaginar una explosión de estática en todas las frecuencias en el tercer espacio:
Nuevamente, podemos deducir de la tabla de codificaciones que debe haber sido la letra A transmitida. 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.
Rompecabezas matemáticos [ editar ]
El problema de determinar si un cuadrado parcialmente lleno se puede completar para formar un cuadrado latino es NP-complete . [11]
Los populares rompecabezas de Sudoku son un caso especial de cuadrados latinos; Cualquier solución para un rompecabezas de Sudoku es un cuadrado latino.
Sudoku impone la restricción adicional de que nueve subcuadros adyacentes 3 × 3 particulares también deben contener los dígitos 1–9 (en la versión estándar). Los rompecabezas KenKen más recientes también son ejemplos de cuadrados latinos.
Juegos de mesa [ editar ]
Los cuadrados latinos se han utilizado como base para varios juegos de mesa, especialmente el popular juego de estrategia abstracta Kamisado .
Investigación agronómica [ editar ]
Los cuadrados latinos se utilizan en el diseño de experimentos de investigación agronómica para minimizar los errores experimentales.
No hay comentarios:
Publicar un comentario