stringtranslate.com

cuadrado latino

Con un cuadrado latino de 7 × 7, este vitral en Gonville and Caius College, Cambridge, rindió homenaje a Ronald Fisher , cuyo Diseño de experimentos analizó los cuadrados latinos. La ventana de Sir Ronald Fisher se eliminó en 2020 debido a la conexión de Fisher con la eugenesia. [1]

En combinatoria y diseño experimental , un cuadrado latino es una  matriz de 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 artículos matemáticos de Leonhard Euler (1707-1783), quien usó caracteres latinos como símbolos, [2] pero se puede usar cualquier conjunto de símbolos: en el ejemplo anterior, la secuencia alfabética A, B , C puede reemplazarse por la secuencia de números enteros 1, 2, 3. Euler inició 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, 67 años antes que Leonhard Euler. [3]

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. [4] 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í, al cambiar la segunda y tercera filas 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, 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

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 triplete (2, 3, 1) significa que en la fila 2 y columna 3 está el símbolo 1. Los arreglos ortogonales generalmente se escriben en forma de matriz donde los tripletes son las filas, como por ejemplo:

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

Esto significa que los n 2 pares ordenados ( r , c ) son todos los pares ( i , j ) con 1 ≤ i , jn , 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, columnas y símbolos desempeñan funciones bastante similares, como se aclarará a continuación.

Clases de equivalencia de cuadrados latinos

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

Si permutamos las filas, permutamos las columnas o 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 utilizando la representación de matriz ortogonal del cuadrado latino. Si reordenamos sistemática y consistentemente los tres elementos de cada tripleta (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 tripleta ( r , c , s ) por ( c , r , s ) que corresponde a transponer el cuadrado (reflexionando sobre su diagonal principal), o podríamos reemplazar cada tripleta ( 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 parástrofes ) del cuadrado original. [5]

Finalmente, podemos combinar estas dos operaciones de equivalencia: dos cuadrados latinos se dicen paratópicos , también isotópicos de clase principal , si uno de ellos es isotópico de 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 . [5] Cada clase principal contiene hasta seis clases de isotopías.

Número de n × n cuadrados latinos

No existe una fórmula conocida fácilmente computable 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 grande están muy separados. Un resultado clásico [6] 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ácilmente computable 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

B nn × n {0, 1}, σ 0 ( A )Aper () espermanenteA. [7]

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

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

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 el OEIS ).

Ejemplos

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

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

Transversales y coincidencias de arcoíris

Una 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 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 una arista (entre su fila y su columna) y los símbolos son colores. Las reglas de los cuadrados latinos implican que se trata de una coloración de borde adecuada . Con esta definición, una transversal latina es una coincidencia en la que cada borde tiene un color diferente; Esta combinación se llama coincidencia de arcoíris .

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. [8]

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

HJ Rysernimparnn[9]

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. [10]

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

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

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 muestrear a partir de una distribución uniforme en el espacio de n  ×  n cuadrados latinos. [dieciséis]

Aplicaciones

Estadística y matemáticas

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. [19] [20] [21]

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 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 en cuatro frecuencias diferentes, en cuatro intervalos de tiempo. La letra C, por ejemplo, se codifica enviándose primero en la frecuencia 3, luego en la 4, 1 y 2.

La codificación de las doce letras se forma a partir de tres cuadrados latinos ortogonales entre sí. Ahora imagina que hay ruido añadido en los canales 1 y 2 durante toda la transmisión. La letra A entonces se recogería como:

Es decir, en el primer slot 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 la que se transmitió. La cantidad de errores que este código puede detectar es uno menos que la cantidad de intervalos de tiempo. También se ha demostrado 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 lo más eficientes posible.

acertijos matemáticos

Construcción del cuadrado mágico del cumpleaños de Ramanujan a partir de un cuadrado latino de 4 × 4 con diagonales distintas y valores de día (D), mes (M), siglo (C) y año (Y), y ejemplo del cumpleaños de Ramanujan.

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

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

Los acertijos más recientes de KenKen y Strimko 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. [23]

Heráldica

El cuadrado latino también figura en las armas de la Sociedad de Estadística de Canadá , [24] siendo mencionado específicamente en su blasón . Además, aparece en el logo de la Sociedad Internacional de Biometría . [25]

Generalizaciones

Un cubo latino de orden 4 explotó

Ver también

Notas

  1. ^ Busby, Mattha (27 de junio de 2020). "Cambridge College eliminará la ventana que conmemora al eugenista". El guardián . Consultado el 28 de junio de 2020 .
  2. ^ Wallis, WD; George, JC (2011), Introducción a la combinatoria, CRC Press, p. 212, ISBN 978-1-4398-0623-4
  3. ^ 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 .
  4. ^ Dénes y Keedwell 1974, pag. 128
  5. ^ ab Dénes y Keedwell 1974, pág. 126
  6. ^ van Lint y Wilson 1992, págs.161-162
  7. ^ 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 .
  8. ^ Gyarfas, András; Sarkozy, Gabor N. (2012). "Emparejamientos de arcoíris y transversales parciales de cuadrados latinos". arXiv : 1208.5670 [CO matemáticas. CO].
  9. ^ ab 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.
  10. ^ Stein, Sherman (1 de agosto de 1975). "Transversales de cuadrados latinos y sus generalizaciones". Revista Pacífico de Matemáticas . 59 (2): 567–575. doi : 10.2140/pjm.1975.59.567 . ISSN  0030-8730.
  11. ^ 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.
  12. ^ 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.
  13. ^ 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.
  14. ^ Keevash, Pedro; Pokrovskiy, Alexey; Sudakov, Benny; Yepremyan, Liana (15 de abril de 2022). "Nuevos límites para la conjetura de Ryser y problemas relacionados". Transacciones de la Sociedad Estadounidense de Matemáticas, Serie B. 9 (8): 288–321. doi : 10.1090/btran/92 . hdl : 20.500.11850/592212 . ISSN  2330-0000.
  15. ^ Montgomery, Richard (2023). "Una prueba de la conjetura de Ryser-Brualdi-Stein para n par grande". arXiv : 2310.19779 [math.CO].
  16. ^ 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.
  17. ^ Bailey, RA (2008), "6 diseños de filas y columnas y 9 más sobre cuadrados latinos", Diseño de experimentos comparativos , Cambridge University Press, ISBN 978-0-521-68357-9, SEÑOR  2422352
  18. ^ Shah, Kirti R.; Sinha, Bikas K. (1989), "Diseños de 4 filas y columnas", Teoría de los diseños óptimos , Apuntes de conferencias sobre estadística, vol. 54, Springer-Verlag, págs. 66–84, ISBN 0-387-96991-8, SEÑOR  1016151
  19. ^ Colbourn, CJ ; Kløve, T.; Ling, ACH (2004). "Matrices de permutación para comunicación por línea eléctrica". Traducción IEEE. inf. Teoría . 50 : 1289-1291. doi :10.1109/tit.2004.828150. S2CID  15920471.
  20. ^ La revolución de Euler , New Scientist, 24 de marzo de 2007, págs. 48–51
  21. ^ Huczynska, Sophie (2006). "La comunicación por línea eléctrica y el problema de los 36 agentes". Transacciones filosóficas de la Royal Society A. 364 (1849): 3199–3214. Código Bib : 2006RSPTA.364.3199H. doi :10.1098/rsta.2006.1885. PMID  17090455. S2CID  17662664.
  22. ^ C. Colbourn (1984). "La complejidad de completar cuadrados latinos parciales". Matemática Aplicada Discreta . 8 : 25–30. doi : 10.1016/0166-218X(84)90075-1 .
  23. ^ La aplicación del cuadrado latino en la investigación agronómica.
  24. ^ "Cartas de Patente que confieren las armas SSC". ssc.ca.Archivado desde el original el 21 de mayo de 2013.
  25. ^ La Sociedad Biométrica Internacional Archivado el 7 de mayo de 2005 en la Wayback Machine.

Referencias

Otras lecturas

enlaces externos