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 ocurre exactamente una vez en cada fila y exactamente una vez en cada columna. Un ejemplo de un cuadrado latino de 3 × 3 es
A | B | C |
C | A | B |
B | C | A |
El nombre "cuadrado latino" se inspiró en artículos matemáticos de Leonhard Euler (1707-1783), quien 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 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 en 67 años. [2]
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. [3] 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 columnas. Aquí, cambiar la segunda y tercera filas de la matriz anterior produce el siguiente cuadrado:
A | B | C |
B | C | A |
C | A | B |
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, obtenemos un conjunto de n 2 triples llamado Representación de matriz ortogonal del cuadrado. Por ejemplo, la representación de matriz ortogonal del cuadrado latino
1 | 2 | 3 |
2 | 3 | 1 |
3 | 1 | 2 |
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. Las matrices ortogonales generalmente se escriben en forma de matriz donde las triples son las filas, como por ejemplo:
r | C | s |
---|---|---|
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 |
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 ocurre con los pares ordenados ( r , s ) y los pares ordenados ( c , s ).
La representación de la matriz ortogonal muestra que las filas, columnas y 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, dándole 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 del 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 diferentes clases no son isotópicos.
Otro tipo de operación es más fácil de explicar usando la representación de matriz ortogonal del cuadrado latino. Si reordenamos sistemática y consistentemente los tres elementos en cada triple (es decir, permutamos las tres columnas en la forma de matriz), 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, incluido "no hacer nada", lo que nos da 6 cuadrados latinos llamados conjugados (también parastrofes ) del cuadrado original. [4]
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 paratopia . [4] Cada clase principal contiene hasta seis clases de isotopías.
Número
No existe 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 n grandes están muy separados. Un resultado clásico [5] es que
En 1992 se publicó una fórmula simple y explícita para el número de cuadrados latinos, pero todavía no es fácil de calcular debido al aumento exponencial del 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 . [6]
La siguiente tabla contiene todos los valores exactos conocidos. Se puede ver que los números crecen muy rápidamente. Para cada n , el número de cuadrados latinos en total (secuencia A002860 en la OEIS ) es n ! ( n -1)! multiplicado por el número de cuadrados latinos reducidos (secuencia A000315 en la OEIS ).
norte | cuadrados latinos reducidos de tamaño n (secuencia A000315 en la OEIS ) | todos los cuadrados latinos de tamaño n (secuencia A002860 en la 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 × 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 la OEIS ) contiene hasta ( n !) 3 cuadrados latinos (el número exacto varía), mientras que cada clase principal (secuencia A003090 en la OEIS ) contiene 1, 2, 3 o 6 clases de isotopías.
norte | clases principales | clases de isotopía | cuadrados estructuralmente distintos |
---|---|---|---|
1 | 1 | 1 | 1 |
2 | 1 | 1 | 1 |
3 | 1 | 1 | 1 |
4 | 2 | 2 | 12 |
5 | 2 | 2 | 192 |
6 | 12 | 22 | 145,164 |
7 | 147 | 564 | 1,524,901,344 |
8 | 283.657 | 1,676,267 | |
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 mediante 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 la OEIS ).
Ejemplos de
Damos un ejemplo de un cuadrado latino de cada clase principal hasta el orden cinco.
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
- - el grupo de cuatro 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.
Transversales y emparejamientos de arco iris
Una transversal en un cuadrado latino es una opció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 gráfico 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 un borde (entre su fila y su columna) y los símbolos son colores. Las reglas de los cuadrados latinos implican que este es un color de borde adecuado . Con esta definición, una transversal latina es un emparejamiento en el que cada borde tiene un color diferente; tal emparejamiento se llama emparejamiento del arco iris .
Por lo tanto, muchos resultados sobre cuadrados / rectángulos latinos están contenidos en artículos con el término "coincidencia de arco iris" en su título, y viceversa. [7]
Algunos cuadrados latinos no tienen transversal. Por ejemplo, cuando n es par, un n- por- n cuadrado latino en el que el valor de la celda i, j es ( i + j ) mod n no tiene transversal. A continuación, se muestran dos ejemplos:
En 1967, HJ Ryser conjeturó que, cuando n es impar , cada n- por- n cuadrado latino tiene una transversal. [8]
En 1975, SK Stein y Brualdi conjeturaron que, cuando n es par , cada n- por- n cuadrado latino tiene una transversal parcial de tamaño n -1. [9]
Una conjetura más general de Stein es que existe una transversal de tamaño n -1 no sólo en los cuadrados latinos, sino también en cualquier matriz n- por- n de n símbolos, siempre que cada símbolo aparezca exactamente n veces. [8]
Se han probado algunas versiones más débiles de estas conjeturas:
- Cada n- por- n cuadrado latino tiene una transversal parcial de tamaño 2 n / 3. [10]
- Cada n- por- n cuadrado latino tiene una transversal parcial de tamaño n - sqrt ( n ). [11]
- Cada n- por- n cuadrado latino tiene una transversal parcial de tamaño n - 11 log 2 2 ( n ). [12]
Algoritmos
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 tomar muestras de una distribución uniforme en el espacio de n × n cuadrados latinos. [13]
Aplicaciones
Estadística y matemática
- En el diseño de experimentos , los cuadrados latinos son un caso especial de diseños de filas y columnas para dos factores de bloqueo : [14] [15]
- En álgebra , los cuadrados latinos están relacionados con generalizaciones de grupos ; en particular, los cuadrados latinos se caracterizan por ser las tablas de multiplicar ( tablas de Cayley ) de los 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
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. [16] [17] [18]
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 que se va a enviar se codifica enviando una serie de señales a diferentes frecuencias en intervalos de tiempo sucesivos. En el siguiente ejemplo, las letras de la A a la 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 a la 4, 1 y 2.
La codificación de las doce letras se forma 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 entonces 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 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 una ráfaga de estática en todas las frecuencias en la tercera ranura:
Nuevamente, podemos inferir de la tabla de codificaciones que debe haber sido la letra A que se estaba 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 comprobado que si el número de frecuencias es un número primo o una potencia de un número 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 . [19]
Los populares rompecabezas de Sudoku son un caso especial de 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). Consulte también Matemáticas del Sudoku .
Los rompecabezas KenKen 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 abstracta 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. [20]
Heráldica
El cuadrado latino también figura en los brazos de la Sociedad de Estadística de Canadá , [21] siendo mencionado específicamente en su blasón . Además, aparece en el logo de la International Biometric Society . [22]
Generalizaciones
- Un rectángulo latino es una generalización de un cuadrado latino en el que hay n columnas yn valores posibles, pero el número de filas puede ser menor que n . Cada valor sigue apareciendo como máximo una vez en cada fila y columna.
- Un cuadrado grecolatino es un par de dos cuadrados latinos de modo que, cuando uno se coloca encima del otro, cada par ordenado de símbolos aparece exactamente una vez.
- Un hipercubo latino es una generalización de un cuadrado latino de dos dimensiones a múltiples dimensiones.
Ver también
- Diseño de bloque
- Diseño combinatorio
- Rompecabezas de las ocho reinas
- Futoshiki
- cuadrado mágico
- Problemas en cuadrados latinos
- Gráfico de Rook , un gráfico que tiene cuadrados latinos como colorantes
- Plaza Sator
- Plaza védica
- Palabra cuadrada
Notas
- ^ Wallis, WD; George, JC (2011), Introducción a la combinatoria , CRC Press, p. 212, ISBN 978-1-4398-0623-4
- ^ Colbourn, Charles J .; Dinitz, Jeffrey H. (2 de noviembre de 2006). Manual de diseños combinatorios (2ª ed.). Prensa CRC. pag. 12. ISBN 9781420010541. Consultado el 28 de marzo de 2017 .
- ^ Dénes y Keedwell 1974 , p. 128
- ↑ a b Dénes y Keedwell , 1974 , p. 126
- ^ van Lint y Wilson 1992 , págs. 161-162
- ^ Jia-yu Shao; Wan-di Wei (1992). "Una fórmula para el número de cuadrados latinos". Matemáticas discretas . 110 (1-3): 293-296. doi : 10.1016 / 0012-365x (92) 90722-r .
- ^ Gyarfas, Andras; Sarkozy, Gabor N. (2012). "Emparejamientos de arco iris y transversales parciales de cuadrados latinos". arXiv : 1208.5670 [ CO math. CO ].
- ^ a b Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (4 de enero de 2017). "Sobre una conjetura de Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 87 (2): 203–211. doi : 10.1007 / s12188-016-0160-3 . ISSN 0025-5858 . S2CID 119139740 .
- ^ Stein, Sherman (1 de agosto de 1975). "Transversales de cuadrados latinos y sus generalizaciones" . Pacific Journal of Mathematics . 59 (2): 567–575. doi : 10.2140 / pjm.1975.59.567 . ISSN 0030-8730 .
- ^ Koksma, Klaas K. (1 de julio de 1969). "Un límite inferior para el orden de una transversal parcial en un cuadrado latino" . Revista de teoría combinatoria . 7 (1): 94–95. doi : 10.1016 / s0021-9800 (69) 80009-8 . ISSN 0021-9800 .
- ^ Woolbright, David E (1 de marzo de 1978). "Un cuadrado latino n × n tiene una transversal con al menos n − n símbolos distintos". Revista de Teoría Combinatoria, serie A . 24 (2): 235–237. doi : 10.1016 / 0097-3165 (78) 90009-2 . ISSN 0097-3165 .
- ^ Hatami, Pooya; Shor, Peter W. (1 de octubre de 2008). "Un límite inferior para la longitud de una transversal parcial en un cuadrado latino". Revista de Teoría Combinatoria, serie A . 115 (7): 1103-1113. doi : 10.1016 / j.jcta.2008.01.002 . ISSN 0097-3165 .
- ^ Jacobson, MT; Matthews, P. (1996). "Generación de cuadrados latinos aleatorios distribuidos uniformemente". Revista de diseños combinatorios . 4 (6): 405–437. doi : 10.1002 / (sici) 1520-6610 (1996) 4: 6 <405 :: aid-jcd3> 3.0.co; 2-j .
- ^ Bailey, RA (2008), "6 diseños de columnas de filas y 9 más sobre cuadrados latinos" , Diseño de experimentos comparativos , Cambridge University Press, ISBN 978-0-521-68357-9, MR 2422352
- ^ Shah, Kirti R .; Sinha, Bikas K. (1989), "4 Row-Column Designs", Theory of Optimal Designs , Lecture Notes in Statistics , 54 , Springer-Verlag, págs. 66-84, ISBN 0-387-96991-8, MR 1016151
- ^ Colbourn, CJ ; Kløve, T .; Ling, ACH (2004). "Matrices de permutación para comunicación powerline". IEEE Trans. Inf. Teoría . 50 : 1289-1291. doi : 10.1109 / tit.2004.828150 . S2CID 15920471 .
- ^ Revolución de Euler , New Scientist, 24 de marzo de 2007, págs. 48–51
- ^ Huczynska, Sophie (2006). "La comunicación por línea eléctrica y el problema de los 36 agentes". Philosophical Transactions de la Royal Society A . 364 (1849): 3199–3214. doi : 10.1098 / rsta.2006.1885 . PMID 17090455 . S2CID 17662664 .
- ^ C. Colbourn (1984). "La complejidad de completar cuadrados latinos parciales". Matemáticas aplicadas discretas . 8 : 25-30. doi : 10.1016 / 0166-218X (84) 90075-1 .
- ^ http://joas.agrif.bg.ac.rs/archive/article/59 | La aplicación del cuadrado latino en la investigación agronómica
- ^ "Cartas Patentes que confieren las armas SSC" . ssc.ca . Archivado desde el original el 21 de mayo de 2013.
- ^ La Sociedad Biométrica Internacional Archivado el 7 de mayo de 2005 en la Wayback Machine.
Referencias
- Bailey, RA (2008). "6 diseños de columnas de filas y 9 más sobre cuadrados latinos" . Diseño de Experimentos Comparativos . Prensa de la Universidad de Cambridge. ISBN 978-0-521-68357-9. Señor 2422352 .
- Dénes, J .; Keedwell, AD (1974). Cuadrados latinos y sus aplicaciones . Nueva York-Londres: Academic Press. pag. 547. ISBN 0-12-209350-X. Señor 0351850 .
- Shah, Kirti R .; Sinha, Bikas K. (1989). "Diseños de 4 filas y columnas". Teoría de los diseños óptimos . Notas de conferencias en estadística . 54 . Springer-Verlag. págs. 66–84. ISBN 0-387-96991-8. Señor 1016151 .
- van Lint, JH; Wilson, RM (1992). Un curso de combinatoria . Prensa de la Universidad de Cambridge. pag. 157 . ISBN 0-521-42260-4.
Otras lecturas
- Dénes, JH; Keedwell, AD (1991). Cuadrados latinos: Nuevos desarrollos en la teoría y aplicaciones . Annals of Discrete Mathematics. 46 . Paul Erdős (prólogo). Amsterdam: Prensa académica. ISBN 0-444-88899-3. Señor 1096296 .
- Hinkelmann, Klaus; Kempthorne, Oscar (2008). Diseño y Análisis de Experimentos . I, II (Segunda ed.). Wiley. ISBN 978-0-470-38551-7. Señor 2363107 .
- Hinkelmann, Klaus; Kempthorne, Oscar (2008). Diseño y Análisis de Experimentos, Volumen I: Introducción al Diseño Experimental (Segunda ed.). Wiley. ISBN 978-0-471-72756-9. Señor 2363107 .
- Hinkelmann, Klaus; Kempthorne, Oscar (2005). Diseño y Análisis de Experimentos, Volumen 2: Diseño Experimental Avanzado (Primera ed.). Wiley. ISBN 978-0-471-55177-5. Señor 2129060 .
- Knuth, Donald (2011). El arte de la programación informática, volumen 4A: algoritmos combinatorios, parte 1 . Reading, Massachusetts: Addison-Wesley. ISBN 978-0-201-03804-0.
- Laywine, Charles F .; Mullen, Gary L. (1998). Matemáticas discretas usando cuadrados latinos . Serie Wiley-Interscience en matemáticas discretas y optimización. Nueva York: John Wiley & Sons, Inc. ISBN 0-471-24064-8. Señor 1644242 .
- Shah, KR; Sinha, Bikas K. (1996). "Diseños fila-columna". En S. Ghosh y CR Rao (ed.). Diseño y análisis de experimentos . Manual de Estadística. 13 . Amsterdam: North-Holland Publishing Co. págs. 903–937. ISBN 0-444-82061-2. Señor 1492586 .
- Raghavarao, Damaraju (1988). Construcciones y problemas combinatorios en el diseño de experimentos (reimpresión corregida de la edición de Wiley de 1971). Nueva York: Dover. ISBN 0-486-65685-3. Señor 1102899 .
- Calle, Anne Penfold ; Calle, Deborah J. (1987). Combinatoria de Diseño Experimental . Nueva York: Oxford University Press. ISBN 0-19-853256-3. Señor 0908490 .
- Berger, Paul D .; Maurer, Robert E .; Celli, Giovana B. (28 de noviembre de 2017). Diseño experimental con aplicaciones en administración, ingeniería y ciencias (2a edición (28 de noviembre de 2017) ed.). Saltador. págs. 267-282.
enlaces externos
- Weisstein, Eric W. "Cuadrado latino" . MathWorld .
- Cuadrados latinos en la enciclopedia de las matemáticas
- Cuadrados latinos en la enciclopedia en línea de secuencias enteras