En matemáticas combinatorias , se dice que dos cuadrados latinos del mismo tamaño ( orden ) son ortogonales si, cuando se superponen, las entradas pareadas ordenadas en las posiciones son todas distintas. Un conjunto de cuadrados latinos, todos del mismo orden, cuyos pares son ortogonales, se denomina conjunto de cuadrados latinos mutuamente ortogonales . Este concepto de ortogonalidad en combinatoria está fuertemente relacionado con el concepto de bloqueo en estadística , que garantiza que las variables independientes sean verdaderamente independientes sin correlaciones de confusión ocultas. "Ortogonal" es, por lo tanto, sinónimo de "independiente" en el sentido de que conocer el valor de una variable no proporciona más información sobre el valor probable de otra variable.
Un término obsoleto para designar a un par de cuadrados latinos ortogonales es cuadrado grecolatino , que se encuentra en la literatura más antigua.
Un cuadrado grecolatino o cuadrado de Euler o par de cuadrados latinos ortogonales de orden n sobre dos conjuntos S y T (que pueden ser el mismo), cada uno de ellos compuesto por n símbolos, es una disposición n × n de celdas, cada celda conteniendo un par ordenado ( s , t ) , donde s está en S y t está en T , de modo que cada fila y cada columna contiene cada elemento de S y cada elemento de T exactamente una vez, y que no hay dos celdas que contengan el mismo par ordenado.
La disposición de las coordenadas s por sí mismas (que pueden considerarse como caracteres latinos) y de las coordenadas t (los caracteres griegos) forma cada una un cuadrado latino . Por lo tanto, un cuadrado grecolatino se puede descomponer en dos cuadrados latinos ortogonales. La ortogonalidad aquí significa que cada par ( s , t ) del producto cartesiano S × T ocurre exactamente una vez.
Los cuadrados latinos ortogonales fueron estudiados en detalle por Leonhard Euler , quien tomó los dos conjuntos como S = { A , B , C , ... }, las primeras n letras mayúsculas del alfabeto latino , y T = { α , β, γ, ... }, las primeras n letras minúsculas del alfabeto griego —de ahí el nombre de cuadrado grecolatino.
Cuando un cuadrado grecolatino se considera como un par de cuadrados latinos ortogonales, se dice que cada uno de los cuadrados latinos tiene un compañero ortogonal . En un cuadrado latino arbitrario, una selección de posiciones, una en cada fila y una en cada columna cuyas entradas son todas distintas se llama transversal de ese cuadrado. [1] Considere un símbolo en un cuadrado grecolatino. Las posiciones que contienen este símbolo deben estar todas en diferentes filas y columnas, y además el otro símbolo en estas posiciones debe ser todos distintos. Por lo tanto, cuando se ve como un par de cuadrados latinos, las posiciones que contienen un símbolo en el primer cuadrado corresponden a una transversal en el segundo cuadrado (y viceversa).
Un cuadrado latino dado de orden n posee una pareja ortogonal si y sólo si tiene n transversales disjuntas. [2]
La tabla de Cayley (sin bordes) de cualquier grupo de orden impar forma un cuadrado latino que posee una pareja ortogonal. [2]
Por lo tanto, los cuadrados grecolatinos existen para todos los órdenes impares, ya que existen grupos de estos órdenes. Se dice que estos cuadrados grecolatinos están basados en grupos .
Euler fue capaz de construir cuadrados grecolatinos de órdenes múltiplos de cuatro, [2] y parecía estar consciente del siguiente resultado.
No pueden existir cuadrados grecolatinos basados en grupos si el orden es un múltiplo impar de dos (es decir, igual a 4 k + 2 para algún entero positivo k ). [3]
Aunque se reconoce su tratamiento matemático original del tema, los cuadrados latinos ortogonales son anteriores a Euler. En 1725, Jacques Ozanam publicó la construcción de un conjunto de 4 x 4 en forma de un antiguo rompecabezas con naipes [ 4 ] . El problema consistía en tomar todos los ases, reyes, reinas y jotas de una baraja de cartas estándar y organizarlos en una cuadrícula de 4 x 4 de modo que cada fila y cada columna contuvieran los cuatro palos, así como una de cada valor nominal. Este problema tiene varias soluciones.
Una variante común de este problema era organizar las 16 cartas de modo que, además de las restricciones de filas y columnas, cada diagonal contuviera también los cuatro valores nominales y los cuatro palos.
Según Martin Gardner , que presentó esta variante del problema en su columna Mathematical Games de noviembre de 1959 , [6] Rouse Ball afirmó incorrectamente que el número de soluciones distintas era 72. Este error persistió durante muchos años hasta que Kathleen Ollerenshaw encontró el valor correcto de 144. Cada una de las 144 soluciones tiene ocho reflexiones y rotaciones, lo que da un total de 1152 soluciones. Las 144×8 soluciones se pueden clasificar en las siguientes dos clases de equivalencia :
Para cada una de las dos soluciones, se pueden obtener 24×24 = 576 soluciones permutando los cuatro palos y los cuatro valores nominales de forma independiente. Ninguna permutación convertirá las dos soluciones en la otra, porque los palos y los valores nominales son diferentes.
Un problema similar al problema de las cartas mencionado anteriormente circulaba en San Petersburgo a fines del siglo XVIII y, según el folclore, Catalina la Grande le pidió a Euler que lo resolviera, ya que él residía en su corte en ese momento. [7] Este problema se conoce como el problema de los treinta y seis oficiales , [8] y Euler lo presentó de la siguiente manera: [9] [10]
Una cuestión muy curiosa, que ha ejercitado durante algún tiempo el ingenio de muchas personas, me ha involucrado en los siguientes estudios, que parecen abrir un nuevo campo de análisis, en particular el estudio de las combinaciones. La cuestión gira en torno a la disposición de 36 oficiales que se extraerán de 6 regimientos diferentes de manera que se alineen en un cuadrado de modo que en cada línea (tanto horizontal como vertical) haya 6 oficiales de diferentes grados y de diferentes regimientos.
— Leonhard Euler
Euler no pudo resolver el problema, pero en este trabajo demostró métodos para construir cuadrados grecolatinos donde n es impar o un múltiplo de 4. Observando que no existe ningún cuadrado de orden dos y siendo incapaz de construir un cuadrado de orden seis, conjeturó que no existe ninguno para ningún número imparmente par n ≡ 2 ( mod 4). La no existencia de cuadrados de orden seis fue confirmada en 1901 por Gaston Tarry a través de una prueba por agotamiento . [11] [12] Sin embargo, la conjetura de Euler resistió la solución hasta finales de la década de 1950, pero el problema ha dado lugar a un importante trabajo en combinatoria . [13]
En 1959, RC Bose y SS Shrikhande construyeron algunos contraejemplos (llamados spoilers de Euler ) de orden 22 utilizando conocimientos matemáticos. [14] Luego, ET Parker encontró un contraejemplo de orden 10 utilizando una búsqueda de computadora de una hora en una computadora militar UNIVAC 1206 mientras trabajaba en la división UNIVAC de Remington Rand (este fue uno de los primeros problemas combinatorios resueltos en una computadora digital ).
En abril de 1959, Parker, Bose y Shrikhande presentaron su artículo que demostraba que la conjetura de Euler era falsa para todos los n ≥ 7. [15] Por lo tanto, los cuadrados grecolatinos existen para todos los órdenes n > 1 excepto n = 2, 6. En la edición de noviembre de 1959 de Scientific American, Martin Gardner publicó este resultado. [6] La portada es la refutación 10 × 10 de la conjetura de Euler.
Las extensiones de cuadrados latinos mutuamente ortogonales al dominio cuántico se han estudiado desde 2017. [17] En estos diseños, en lugar de la unicidad de los símbolos, los elementos de una matriz son estados cuánticos que deben ser ortogonales entre sí en filas y columnas. En 2021, un equipo indio-polaco de físicos (Rather, Burchardt, Bruzda, Rajchel-Mieldzioć, Lakshminarayan y Życzkowski ) encontró una matriz de estados cuánticos que proporciona un ejemplo de cuadrados latinos cuánticos mutuamente ortogonales de tamaño 6; o, equivalentemente, una disposición de 36 oficiales que están entrelazados. [16] [18] [19] Esta configuración resuelve una generalización del problema de los 36 oficiales de Euler, además de proporcionar un nuevo código de detección de errores cuánticos , que permite codificar un sistema de 6 niveles en un sistema de tres 6 niveles que certifica la ocurrencia de un error.
Un conjunto de cuadrados latinos del mismo orden tales que cada par de cuadrados son ortogonales (es decir, forman un cuadrado grecolatino) se denomina conjunto de cuadrados latinos mutuamente ortogonales (o cuadrados latinos ortogonales por pares ) y generalmente se abrevia como MOLS o MOLS( n ) cuando el orden se hace explícito.
Por ejemplo, un conjunto de MOLS(4) viene dado por: [20]
Y un conjunto de MOLS(5): [21]
Si bien es posible representar MOLS en una forma matricial "compuesta" similar a los cuadrados grecolatinos, por ejemplo,
Para el ejemplo MOLS(5) anterior, es más típico representar de forma compacta el MOLS como una matriz ortogonal (ver a continuación). [22]
En los ejemplos de MOLS dados hasta ahora, se ha utilizado el mismo alfabeto (conjunto de símbolos) para cada cuadrado, pero esto no es necesario como lo demuestran los cuadrados grecolatinos. De hecho, se pueden utilizar conjuntos de símbolos totalmente diferentes para cada cuadrado del conjunto de MOLS. Por ejemplo,
es una representación del ejemplo compuesto MOLS(5) anterior, donde los cuatro MOLS tienen los siguientes alfabetos, respectivamente:
Por lo tanto, la tabla anterior permite probar cinco valores en cada una de las cuatro dimensiones diferentes en solo 25 observaciones en lugar de las 625 (= 5 4 ) observaciones requeridas en un diseño factorial completo . Dado que las cinco palabras cubren las 26 letras del alfabeto entre ellas, la tabla permite examinar cada letra del alfabeto en cinco combinaciones de colores y tipos de letra diferentes.
La propiedad de ortogonalidad mutua de un conjunto de MOLS no se ve afectada por
Usando estas operaciones, cualquier conjunto de MOLS puede ponerse en forma estándar , lo que significa que la primera fila de cada cuadrado es idéntica y normalmente se pone en algún orden natural, y un cuadrado tiene su primera columna también en este orden. [23] Los ejemplos MOLS(4) y MOLS(5) al comienzo de esta sección se han puesto en forma estándar.
Al poner un conjunto de MOLS( n ) en forma estándar y examinar las entradas en la segunda fila y la primera columna de cada cuadrado, se puede ver que no pueden existir más de n − 1 cuadrados. [24] Un conjunto de n − 1 MOLS( n ) se llama un conjunto completo de MOLS . Se sabe que existen conjuntos completos cuando n es un número primo o una potencia de un primo (ver Construcción de cuerpos finitos a continuación). Sin embargo, el número de MOLS que pueden existir para un orden dado n no se conoce para n general , y es un área de investigación en combinatoria .
Un conjunto de n − 1 MOLS( n ) es equivalente a un plano afín finito de orden n (ver Redes a continuación). [10] Como cada plano afín finito es únicamente extensible a un plano proyectivo finito del mismo orden, esta equivalencia también puede expresarse en términos de la existencia de estos planos proyectivos. [25]
Como se mencionó anteriormente, existen conjuntos completos de MOLS( n ) si n es un primo o una potencia prima, por lo que existen planos proyectivos de tales órdenes. No se sabe que existan planos proyectivos finitos con un orden diferente de estos y, por lo tanto, conjuntos completos de MOLS de tales órdenes. [10]
El único resultado general sobre la no existencia de planos proyectivos finitos es el teorema de Bruck-Ryser , que dice que si existe un plano proyectivo de orden n y n ≡ 1 (mod 4) o n ≡ 2 (mod 4), entonces n debe ser la suma de dos cuadrados (enteros). [26] Esto descarta los planos proyectivos de órdenes 6 y 14, por ejemplo, pero no garantiza la existencia de un plano cuando n satisface la condición. En particular, n = 10 satisface las condiciones, pero no existe ningún plano proyectivo de orden 10, como se demostró mediante una búsqueda por computadora muy larga, [27] lo que a su vez implica que no existen nueve MOLS de orden 10.
No se conocen otros resultados de existencia. A partir de 2020, [actualizar]el orden más pequeño para el cual la existencia de un conjunto completo de MOLS es indeterminada es 12. [10]
Se sabe que el número mínimo de MOLS( n ) es 2 para todos los n excepto para n = 2 o 6, donde es 1. Sin embargo, se puede decir más, a saber, [28]
Teorema de MacNeish : Si es la factorización del entero n en potencias de primos distintos entonces
El teorema de MacNeish no da un límite inferior muy bueno, por ejemplo, si n ≡ 2 (mod 4), es decir, hay un solo 2 en la factorización prima, el teorema da un límite inferior de 1, que se supera si n > 6. Por otro lado, da el valor correcto cuando n es una potencia de un primo.
Para los números compuestos generales, no se conoce el número de MOLS. Los primeros valores que comienzan con n = 2, 3, 4... son 1, 2, 3, 4, 1, 6, 7, 8, ... (secuencia A001438 en la OEIS ).
El caso más pequeño para el cual no se conoce el número exacto de MOLS( n ) es n = 10. De la construcción del cuadrado grecolatino, debe haber al menos dos y de la inexistencia de un plano proyectivo de orden 10, hay menos de nueve. Sin embargo, nunca se ha encontrado un conjunto de tres MOLS(10) a pesar de que muchos investigadores han intentado descubrir un conjunto de ese tipo. [29]
Para un n suficientemente grande , el número de MOLS es mayor que , por lo tanto, para cada k , solo hay un número finito de n tales que el número de MOLS es k . [30] Además, el mínimo es 6 para todo n > 90.
Existe un conjunto completo de MOLS( q ) siempre que q sea un primo o una potencia prima. Esto se desprende de una construcción que se basa en un campo finito GF ( q ), que solo existe si q es un primo o una potencia prima. [31] El grupo multiplicativo de GF ( q ) es un grupo cíclico y, por lo tanto, tiene un generador, λ, lo que significa que todos los elementos distintos de cero del campo se pueden expresar como potencias distintas de λ. Nombra los q elementos de GF ( q ) de la siguiente manera:
Ahora, λ q -1 = 1 y la regla del producto en términos de los α es α i α j = α t , donde t = i + j -1 (mod q -1). Los cuadrados latinos se construyen de la siguiente manera, la ( i, j )ésima entrada en el cuadrado latino L r (con r ≠ 0) es L r ( i,j ) = α i + α r α j , donde todas las operaciones ocurren en GF ( q ). En el caso de que el cuerpo sea un cuerpo primo ( q = p un primo), donde los elementos del cuerpo se representan de la forma habitual, como los enteros módulo p , la convención de nomenclatura anterior se puede eliminar y la regla de construcción se puede simplificar a L r ( i,j ) = i + rj , donde r ≠ 0 e i , j y r son elementos de GF ( p ) y todas las operaciones están en GF ( p ). Los ejemplos MOLS(4) y MOLS(5) anteriores surgieron de esta construcción, aunque con un cambio de alfabeto.
No todos los conjuntos completos de MOLS surgen de esta construcción. El plano proyectivo que está asociado con el conjunto completo de MOLS obtenido a partir de esta construcción de campo es un tipo especial, un plano proyectivo desarguesiano . Existen planos proyectivos no desarguesianos y sus conjuntos completos correspondientes de MOLS no pueden obtenerse a partir de campos finitos. [32]
Una matriz ortogonal , OA( k,n ), de fuerza dos e índice uno es una matriz n 2 × k A ( k ≥ 2 y n ≥ 1, enteros) con entradas de un conjunto de tamaño n tales que dentro de dos columnas cualesquiera de A ( fuerza ), cada par ordenado de símbolos aparece exactamente en una fila de A ( índice ). [33]
Un OA( s + 2, n ) es equivalente a s MOLS( n ). [33] Por ejemplo, el ejemplo MOLS(4) dado anteriormente y repetido aquí,
se puede utilizar para formar un OA(5,4):
donde las entradas en las columnas etiquetadas r y c denotan la fila y columna de una posición en un cuadrado y el resto de la fila para valores fijos r y c se llena con la entrada en esa posición en cada uno de los cuadrados latinos. Este proceso es reversible; dado un OA( s , n ) con s ≥ 3, elija dos columnas cualesquiera para desempeñar los papeles r y c y luego complete los cuadrados latinos con las entradas en las columnas restantes.
Las matrices ortogonales más generales representan generalizaciones del concepto de MOLS, como los cubos latinos mutuamente ortogonales.
Una red (geométrica) ( k,n ) es un conjunto de n 2 elementos llamados puntos y un conjunto de kn subconjuntos llamados líneas o bloques , cada uno de tamaño n con la propiedad de que dos líneas distintas se intersecan en un punto como máximo. Además, las líneas se pueden dividir en k clases paralelas (no se cruzan dos de sus líneas) cada una de las cuales contiene n líneas. [34]
Una ( n + 1, n )-red es un plano afín de orden n .
Un conjunto de k MOLS( n ) es equivalente a una ( k + 2, n )-red. [10]
Para construir una ( k + 2, n )-red a partir de k MOLS( n ), represente los MOLS como una matriz ortogonal, OA( k + 2, n ) (ver arriba). Los pares ordenados de entradas en cada fila de la matriz ortogonal en las columnas etiquetadas r y c , se considerarán las coordenadas de los n 2 puntos de la red. Cada otra columna (es decir, cuadrado latino) se utilizará para definir las líneas en una clase paralela. Las n líneas determinadas por la columna etiquetada L i se denotarán por l ij . Los puntos en l ij serán aquellos con coordenadas correspondientes a las filas donde la entrada en la columna L i es j . Hay dos clases paralelas adicionales, correspondientes a las columnas r y c . Las líneas r j y c j consisten en los puntos cuyas primeras coordenadas son j , o segundas coordenadas son j respectivamente. Esta construcción es reversible. [35]
Por ejemplo, el OA(5,4) de la sección anterior se puede utilizar para construir una red (5,4) (un plano afín de orden 4). Los puntos de cada línea están dados por (cada fila a continuación es una clase paralela de líneas):
Un diseño transversal con k grupos de tamaño n e índice λ, denotado T[ k , λ; n ], es una tripleta ( X, G, B ) donde: [36]
La existencia de un diseño T[ k ,1; n ] es equivalente a la existencia de k -2 MOLS( n ). [37]
Un diseño transversal T[ k ,1; n ] es la estructura de incidencia dual de una ( k,n )-red. Es decir, tiene nk puntos y n 2 bloques. Cada punto está en n bloques; cada bloque contiene k puntos. Los puntos caen en k clases de equivalencia (grupos) de tamaño n de modo que dos puntos en el mismo grupo no están contenidos en un bloque mientras que dos puntos en diferentes grupos pertenecen exactamente a un bloque. [38]
Por ejemplo, utilizando la red (5,4) de la sección anterior podemos construir un diseño transversal T[5,1;4]. El bloque asociado al punto ( i, j ) de la red se denotará b ij . Los puntos del diseño se obtendrán a partir del siguiente esquema: r i ↔ i , c j ↔ 5 j , y l ij ↔ 5 i + j . Los puntos del diseño se denotan entonces por los números enteros 1, ..., 20. Los bloques del diseño son:
Los cinco "grupos" son:
Un conjunto de k MOLS( n ) es equivalente a una partición de aristas del grafo completo ( k + 2)-partito K n ,..., n en subgrafos completos de orden k + 2. [10]
Los cuadrados latinos mutuamente ortogonales tienen una gran variedad de aplicaciones. Se utilizan como punto de partida para construcciones en el diseño estadístico de experimentos , la programación de torneos y los códigos de detección y corrección de errores . El interés de Euler por los cuadrados grecolatinos surgió de su deseo de construir cuadrados mágicos . El escritor francés Georges Perec estructuró su novela de 1978 La vida: manual del usuario en torno a un cuadrado grecolatino de 10×10.
![{\displaystyle {\sqrt[{14.8}]{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c08db2066083d7a21d61eb8c265c14e6ade5a7e)
