Los cuadrados latinos y los cuasigrupos son objetos matemáticos equivalentes, aunque el primero tiene una naturaleza combinatoria mientras que el segundo es más algebraico . La lista a continuación considerará los ejemplos de algunos órdenes muy pequeños , que es la longitud del lado del cuadrado o el número de elementos en el cuasigrupo equivalente.
Dado un cuasigrupo Q con n elementos, su tabla de Cayley (casi universalmente llamada su tabla de multiplicación ) es una tabla ( n + 1) × ( n + 1) que incluye bordes; una fila superior de encabezados de columna y una columna izquierda de encabezados de fila. Al eliminar los bordes, queda una matriz n × n que es un cuadrado latino. Este proceso se puede invertir, comenzando con un cuadrado latino, introduciendo una fila y una columna de borde para obtener la tabla de multiplicación de un cuasigrupo. Si bien existe una total arbitrariedad en cómo se realiza este borde, los cuasigrupos obtenidos con diferentes elecciones a veces son equivalentes en el sentido que se da a continuación.
Dos cuadrados latinos, L 1 y L 2 de tamaño n son isotópicos si hay tres biyecciones de las filas, columnas y símbolos de L 1 sobre las filas, columnas y símbolos de L 2 , respectivamente, que asignan L 1 a L 2 . [1] La isotopía es una relación de equivalencia y las clases de equivalencia se denominan clases de isotopía .
Existe una forma más fuerte de equivalencia. Dos cuadrados latinos, L 1 y L 2 de lado n con conjunto de símbolos común S que es también el conjunto de índices para las filas y columnas de cada cuadrado, son isomorfos si hay una biyección g:S → S tal que g ( L 1 ( i , j )) = L 2 ( g ( i ), g ( j )) para todo i , j en S . [1] Una forma alternativa de definir cuadrados latinos isomorfos es decir que un par de cuadrados latinos isotópicos son isomorfos si las tres biyecciones utilizadas para mostrar que son isotópicos son, de hecho, iguales. [2] El isomorfismo es también una relación de equivalencia y sus clases de equivalencia se denominan clases de isomorfismo .
Una representación alternativa de un cuadrado latino se da mediante una matriz ortogonal . Para un cuadrado latino de orden n, se trata de una matriz n 2 × 3 con columnas etiquetadas r , c y s y cuyas filas corresponden a una única posición del cuadrado latino, es decir, la fila de la posición, la columna de la posición y el símbolo en la posición. Por lo tanto, para el cuadrado latino de orden tres,
La matriz ortogonal viene dada por:
La condición para que una matriz de tamaño apropiado represente un cuadrado latino es que para dos columnas cualesquiera , los n 2 pares ordenados determinados por las filas en esas columnas sean todos los pares ( i , j ) con 1 ≤ i , j ≤ n , una vez cada uno.
Esta propiedad no se pierde al permutar las tres columnas (pero no las etiquetas), por lo que se obtiene otra matriz ortogonal (y, por lo tanto, otro cuadrado latino). Por ejemplo, al permutar las dos primeras columnas, lo que corresponde a la transposición del cuadrado (reflexionando sobre su diagonal principal), se obtiene otro cuadrado latino, que puede ser isotópico o no al original. En este caso, si el cuasigrupo correspondiente a este cuadrado latino satisface la ley conmutativa , el nuevo cuadrado latino es el mismo que el original. En total, hay seis posibilidades, incluida la de "no hacer nada", lo que da como máximo seis cuadrados latinos llamados conjugados (también parastrofes ) del cuadrado original. [3]
Se dice que dos cuadrados latinos son paratópicos , también isotópicos de clase principal , si uno de ellos es isotópico con respecto a un conjugado del otro. Esta es también una relación de equivalencia, y las clases de equivalencia se denominan clases principales , especies o clases de paratopía . [3] Cada clase principal contiene hasta seis clases de isotopía.
Una clase principal es una unión disjunta de clases de isotopía y una clase de isotopía es una unión disjunta de clases de isomorfismo. [4]
Sean ( Q ,∘) y ( R ,∗) dos cuasigrupos. Un triple ordenado ( f , g , h ) de biyecciones de Q sobre R se denomina isotopismo de ( Q ,∘) sobre ( R ,∗) si f ( x ) ∗ g ( y ) = h ( x ∘ y ) para todo x, y en G . Se dice que tales cuasigrupos son isotópicos . [5]
Si en la definición anterior f = g = h entonces se dice que los cuasigrupos son isomorfos . [2]
A diferencia de la situación con los cuadrados latinos, cuando dos cuasigrupos isotópicos se representan mediante tablas de Cayley (cuadrados latinos con bordes), las permutaciones f y g operan solo en los encabezados de los bordes y no mueven columnas ni filas, mientras que h opera en el cuerpo de la tabla. [5]
La permutación de las filas y columnas de una tabla de Cayley (incluidos los encabezados) no cambia el cuasigrupo que define, sin embargo, el cuadrado latino asociado con esta tabla se permutará a un cuadrado latino isotópico. Por lo tanto, la normalización de una tabla de Cayley (poner los encabezados de los bordes en un orden predeterminado fijo mediante la permutación de filas y columnas, incluidos los encabezados) preserva la clase de isotopía del cuadrado latino asociado. Además, si dos tablas de Cayley normalizadas representan cuasigrupos isomorfos, entonces sus cuadrados latinos asociados también son isomorfos. Por lo tanto, el número de cuasigrupos distintos de un orden dado es el número de clases de isomorfismo de cuadrados latinos de ese orden. [6]
El conjunto de símbolos que se utiliza en un cuadrado latino (o cuasigrupo) es arbitrario y los símbolos individuales no tienen significado, aunque puedan tenerlo en otros contextos. Por lo tanto, dado que es más común ver los conjuntos de símbolos {1,2, ... , n } o {0,1, ... , n − 1 }, hay que recordar que estos símbolos no tienen significado numérico. Para enfatizar este punto, los cuadrados latinos pequeños a veces utilizan letras del alfabeto como conjunto de símbolos.
Como un cuadrado latino es un objeto combinatorio, el conjunto de símbolos que se utilice para escribir el cuadrado es irrelevante. Por lo tanto, como cuadrados latinos, estos deberían considerarse iguales:
De manera similar, y por la misma razón,
Deberían considerarse como lo mismo. Por lo tanto,
No pueden considerarse como cuadrados latinos diferentes.
Este argumento intuitivo se puede hacer más preciso. Los cuadrados latinos
son isotópicos, de varias maneras. Sea ( a,b ) la permutación involutiva en el conjunto S = { a , b }, enviando a a b y b a a . Entonces la isotopía {( a , b ), id , id } intercambiará las dos filas del primer cuadrado para dar el segundo cuadrado ( id es la permutación identidad). Pero, { id , ( a , b ), id } que intercambia las dos columnas también es una isotopía, como lo es { id , id , ( a , b ) } que intercambia los dos símbolos. Sin embargo, {( a , b ), ( a , b ), ( a , b ) } también es una isotopía entre los dos cuadrados, y por lo tanto, este par de cuadrados son isomorfos.
Encontrar la clase de isomorfismo de un cuadrado latino dado puede ser un problema computacional difícil para cuadrados de gran orden. Para reducir el problema un poco, un cuadrado latino siempre se puede poner en una forma estándar conocida como cuadrado reducido . Un cuadrado reducido tiene sus elementos de la fila superior escritos en algún orden natural para el conjunto de símbolos (por ejemplo, números enteros en orden creciente o letras en orden alfabético). Las entradas de la columna de la izquierda se colocan en el mismo orden. Como esto se puede hacer por permutaciones de fila y columna, cada cuadrado latino es isotópico a un cuadrado reducido. Por lo tanto, cada clase de isotopía debe contener un cuadrado latino reducido, sin embargo, un cuadrado latino puede tener más de un cuadrado reducido que sea isotópico a él. De hecho, puede haber más de un cuadrado reducido en una clase de isomorfismo dada. [7]
Por ejemplo, los cuadrados latinos reducidos de orden cuatro,
Ambos están en la clase de isomorfismo que también contiene el cuadrado reducido
Esto se puede demostrar mediante los isomorfismos {(3,4), (3,4), (3,4)} y {(2,3), (2,3), (2,3)} respectivamente. [8]
Como las clases de isotopía son disjuntas, el número de cuadrados latinos reducidos proporciona un límite superior para el número de clases de isotopía. Además, el número total de cuadrados latinos es n !( n − 1)! veces el número de cuadrados reducidos. [9]
Se puede normalizar una tabla de Cayley de un cuasigrupo de la misma manera que un cuadrado latino reducido. Entonces, el cuasigrupo asociado a un cuadrado latino reducido tiene un elemento de identidad (bilateral) (es decir, el primer elemento entre los encabezados de fila). Un cuasigrupo con una identidad bilateral se denomina bucle . Algunos bucles, pero no todos, son grupos. Para ser un grupo, también debe cumplirse la ley asociativa.
Los recuentos de varias subestructuras en un cuadrado latino pueden ser útiles para distinguirlas entre sí. Algunos de estos recuentos son los mismos para cada isótopo de un cuadrado latino y se conocen como invariantes de isotopía. Uno de estos invariantes es el número de subcuadrados de 2 × 2, llamados intercalados . Otro es el número total de transversales , un conjunto de n posiciones en un cuadrado latino de orden n , una en cada fila y una en cada columna, que no contienen ningún elemento dos veces. Los cuadrados latinos con diferentes valores para estos recuentos deben estar en diferentes clases de isotopía. El número de intercalados también es un invariante de clase principal.
Para el orden uno sólo hay un cuadrado latino con símbolo 1 y un cuasigrupo con conjunto subyacente {1}; es un grupo, el grupo trivial .
Sólo hay un cuadrado latino reducido de orden dos (y sólo dos en total), a saber:
Como sólo hay un cuadrado reducido de este orden, sólo hay una clase de isotopía. De hecho, esta clase de isotopía es también una clase de isomorfismo (como se muestra arriba). [8] [1]
Como sólo hay una clase de isomorfismo de cuadrados latinos, sólo hay un cuasigrupo de orden dos (hasta el isomorfismo) y es el grupo usualmente denotado por el grupo cíclico de orden dos.
También hay un solo cuadrado latino reducido de orden tres (de 12),
Por lo tanto, sólo hay una clase de isotopía. [8] Sin embargo, esta clase de isotopía es la unión de cinco clases de isomorfismo. [1]
Tres de las cinco clases de isomorfismo contienen tres cuadrados latinos cada una, una contiene dos y otra contiene sólo uno. El cuadrado reducido está en una clase de isomorfismo con tres elementos y, por lo tanto, el cuasigrupo correspondiente es un bucle, de hecho, es un grupo, el grupo cíclico de orden tres. Un cuadrado latino representativo de cada una de estas clases de isomorfismo viene dado por (el número debajo de cada una es el número de cuadrados en la clase de isomorfismo correspondiente):
Hay cuatro cuadrados latinos reducidos de orden cuatro (de un total de 576 cuadrados). Son los siguientes:
Los últimos tres de estos son isomorfos (ver arriba). Hay dos clases principales, dos clases de isotopía y 35 clases de isomorfismo. Entre los 35 cuasigrupos, solo dos son bucles, y de hecho son grupos. Correspondiente al primer cuadrado anterior está el grupo de cuatro de Klein , mientras que correspondiente a cualquiera de los otros tres cuadrados está el grupo cíclico. El primer cuadrado tiene ocho transversales y 12 intercalados, mientras que cada uno de los otros no tiene transversales y cuatro intercalados.
La clase de isomorfismo del grupo de cuatro de Klein tiene cuatro miembros, mientras que la clase de isomorfismo del grupo cíclico tiene 12 miembros. De los 576 cuadrados latinos, 288 son soluciones de la versión 4×4 del Sudoku , a veces llamada Shi Doku [1].
De los 161.280 cuadrados latinos de orden cinco, hay 56 cuadrados reducidos. Hay dos clases principales y sólo dos clases de isotopía, pero 1.411 clases de isomorfismo. Hay seis clases de isomorfismo que contienen cuadrados reducidos, es decir, hay seis bucles, de los cuales sólo uno es un grupo, el grupo cíclico de orden cinco. [1]
A continuación se muestran dos cuadrados latinos reducidos de orden cinco, uno de cada clase de isotopía. [10]
El primer cuadrado tiene 15 transversales, ningún intercalado y es la tabla de Cayley sin borde del grupo cíclico. El segundo cuadrado tiene tres transversales y cuatro intercalados. Representa un bucle que no es un grupo, ya que, por ejemplo, 2 + (3 + 4) = 2 + 0 = 2, mientras que (2 + 3) + 4 = 0 + 4 = 4, por lo que la ley asociativa no se cumple.
El número de cuadrados latinos, a medida que aumenta el orden, presenta el fenómeno conocido como explosión combinatoria ; a pequeños aumentos de tamaño corresponden enormes aumentos de variedades. Los recuentos básicos se dan en las dos tablas siguientes [1] , y no se sabe con exactitud mucho más allá de lo que se presenta aquí.
Este relato sigue a McKay, Meynert y Myrvold (2007, p. 100).
El conteo de cuadrados latinos tiene una larga historia, pero los relatos publicados contienen muchos errores. Euler en 1782, [11] y Cayley en 1890, [12] ambos conocían el número de cuadrados latinos reducidos hasta el orden cinco. En 1915, MacMahon [13] abordó el problema de una manera diferente, pero inicialmente obtuvo el valor incorrecto para el orden cinco. M. Frolov en 1890, [14] y Tarry en 1901, [15] [16] encontraron el número de cuadrados reducidos de orden seis. M. Frolov dio un recuento incorrecto de cuadrados reducidos de orden siete. RA Fisher y F. Yates , [17] sin conocer el trabajo anterior de E. Schönhardt, [18] dieron el número de clases de isotopía de órdenes hasta seis. En 1939, HW Norton encontró 562 clases de isotopía de orden siete, [19] pero reconoció que su método era incompleto. A. Sade, en 1951, [20] pero publicado privadamente antes en 1948, y PN Saxena [21] encontraron más clases y, en 1966, DA Preece notó que esto corrigió el resultado de Norton a 564 clases de isotopía. [22] Sin embargo, en 1968, JW Brown anunció un valor incorrecto de 563, [23] que se ha repetido a menudo. También dio el número incorrecto de clases de isotopía de orden ocho. El número correcto de cuadrados reducidos de orden ocho ya había sido encontrado por MB Wells en 1967, [24] y los números de clases de isotopía, en 1990, por G. Kolesova, CWH Lam y L. Thiel. [25] El número de cuadrados reducidos para el orden nueve fue obtenido por SE Bammel y J. Rothstein, [26] para el orden 10 por BD McKay y E. Rogoyski, [27] y para el orden 11 por BD McKay e IM Wanless. [28]
