En matemáticas combinatorias , se dice que dos cuadrados latinos del mismo tamaño ( orden ) son ortogonales si, cuando se superponen, las entradas emparejadas ordenadas en las posiciones son todas distintas. Un conjunto de cuadrados latinos, todos del mismo orden, cuyos pares son ortogonales se llama 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. Por tanto, "ortogonal" es 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 un par de cuadrados latinos ortogonales es cuadrado grecolatino , que se encuentra en la literatura más antigua.
Un cuadrado grecolatino o un cuadrado de Euler o un par de cuadrados latinos ortogonales de orden n sobre dos conjuntos S y T (que pueden ser iguales), cada uno de los cuales consta de n símbolos, es una disposición de celdas de n × n , donde cada celda contiene 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 caracteres latinos) y de las coordenadas t (los caracteres griegos) forma cada una un cuadrado latino . Por 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 ve como un par de cuadrados latinos ortogonales, se dice que cada uno de los cuadrados latinos tiene una pareja 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 denomina transversal de ese cuadrado. [1] Considere un símbolo en un cuadrado grecolatino. Todas las posiciones que contienen este símbolo deben estar en filas y columnas diferentes y, además, el otro símbolo en estas posiciones debe ser distinto. Por lo tanto, cuando se ven 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 relación de pareja ortogonal si y sólo si tiene n transversales disjuntas. [2]
La tabla Cayley (sin bordes) de cualquier grupo de orden impar forma un cuadrado latino que posee una relación de pareja ortogonal. [2]
Por lo tanto, existen cuadrados grecolatinos para todos los órdenes impares, ya que existen grupos de estos órdenes. Se dice que estos cuadrados grecolatinos están basados en grupos .
Euler pudo construir cuadrados grecolatinos de órdenes que son múltiplos de cuatro, [2] y parecía ser consciente del siguiente resultado.
No puede existir ningún cuadrado grecolatino basado 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 reconocido por su original tratamiento matemático del tema, los cuadrados latinos ortogonales son anteriores a Euler. En forma de un antiguo rompecabezas de naipes , [4] la construcción de un juego de 4 x 4 fue publicada por Jacques Ozanam en 1725. [5] El problema era tomar todos los ases, reyes, reinas y jotas de una baraja estándar. de cartas y colóquelas en una cuadrícula de 4 x 4 de manera que cada fila y cada columna contenga los cuatro palos, así como uno de cada valor nominal. Este problema tiene varias soluciones.
Una variante común de este problema era ordenar las 16 cartas de manera que, además de las restricciones de fila y columna, cada diagonal contuviera los cuatro valores nominales y también los cuatro palos.
Según Martin Gardner , quien presentó esta variante del problema en su columna de Juegos Matemáticos 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, dando un total de 1152 soluciones. Las soluciones 144×8 se pueden clasificar en las dos clases de equivalencia siguientes :
Para cada una de las dos soluciones, se pueden derivar 24 × 24 = 576 soluciones permutando los cuatro palos y los cuatro valores nominales, de forma independiente. Ninguna permutación convertirá las dos soluciones entre sí, porque los palos y los valores nominales son diferentes.
Un problema similar al problema de las cartas anterior circulaba en San Petersburgo a finales del siglo XVIII y, según la leyenda, 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 desde hace tiempo ejercita 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 organizar 36 oficiales provenientes de 6 regimientos diferentes, de modo que estén alineados en un cuadrado de modo que en cada línea (tanto horizontal como vertical) haya 6 oficiales de diferentes rangos y 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 múltiplo de 4. Al observar que no existe ningún cuadrado de orden dos y al no poder construir un cuadrado de orden seis, conjeturó que no existe ninguno para ningún número imparmente par n ≡ 2 ( mod 4). La inexistencia del orden de seis cuadrados fue confirmada en 1901 por Gaston Tarry mediante 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 importantes trabajos en combinatoria . [13]
En 1959, RC Bose y SS Shrikhande construyeron algunos contraejemplos (denominados spoilers de Euler ) de orden 22 utilizando conocimientos matemáticos. [14] Luego, ET Parker encontró un contraejemplo de orden 10 utilizando una búsqueda informática 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 de combinatoria resueltos en una computadora digital ).
En abril de 1959, Parker, Bose y Shrikhande presentaron su artículo demostrando que la conjetura de Euler era falsa para todo n ≥ 7. [15] Por lo tanto, los cuadrados grecolatinos existen para todos los órdenes n > 1 excepto n = 2, 6. En el 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.
Desde 2017 se han estudiado extensiones de cuadrados latinos mutuamente ortogonales al dominio cuántico. [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 serie de estados cuánticos que proporciona un ejemplo de cuadrados latinos cuánticos mutuamente ortogonales de tamaño 6; o, equivalentemente, un arreglo de 36 oficiales que se enredan [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 niveles de 6 que certifica la ocurrencia de un error.
Un conjunto de cuadrados latinos del mismo orden tal 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 anterior de MOLS(5), es más típico representar de forma compacta los MOLS como una matriz ortogonal (ver más abajo). [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 muestran 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 cuatro dimensiones diferentes en sólo 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 tipos de letra y combinaciones de colores diferentes.
La propiedad de ortogonalidad mutua de un conjunto de MOLS no se ve afectada por
Usando estas operaciones, cualquier conjunto de MOLS se puede poner en forma estándar , lo que significa que la primera fila de cada cuadrado es idéntica y normalmente se coloca 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 conjunto completo de MOLS . Se sabe que existen conjuntos completos cuando n es un número primo o una potencia de un primo (consulte Construcción de campos 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 se puede expresar en términos de la existencia de estos planos proyectivos. [25]
Como se mencionó anteriormente, existen conjuntos completos de MOLS( n ) si n es una potencia prima o prima, por lo que existen planos proyectivos de tales órdenes. No se sabe que existan planos proyectivos finitos con un orden diferente a estos y, por lo tanto, conjuntos completos de MOLS de tales órdenes. [10]
El único resultado general sobre la inexistencia 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 lo demostró una búsqueda informática 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 pedido 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 número entero n en potencias de números 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 números compuestos generales, se desconoce 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 el 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, no son menos de nueve. Sin embargo, nunca se ha encontrado ningún conjunto de tres MOLS(10), a pesar de que muchos investigadores han intentado descubrir dicho conjunto. [29]
Para n lo suficientemente grande , el número de MOLS es mayor que , por lo tanto, para cada k , solo hay un número finito de n tal 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 una potencia prima o prima. Esto se desprende de una construcción que se basa en un campo finito GF ( q ), que sólo 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 α 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 campo sea un campo primo ( q = p a prime), donde los elementos del campo se representan de la forma habitual, como los números enteros módulo p , se puede eliminar la convención de nomenclatura anterior 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 juegos completos de MOLS surgen de esta construcción. El plano proyectivo que está asociado al conjunto completo de MOLS obtenidos de esta construcción de campo es de un tipo especial, un plano proyectivo desarguesiano . Existen planos proyectivos no desarguesianos y sus correspondientes conjuntos completos de MOLS no se pueden obtener a partir de campos finitos. [32]
Una matriz ortogonal , OA( k,n ), de fuerza dos e índice uno es una matriz A n 2 × k ( k ≥ 2 y n ≥ 1, enteros) con entradas de un conjunto de tamaño n tal 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 como r y c denotan la fila y la columna de una posición en un cuadrado y el resto de la fila para valores fijos de r y c se completa 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 roles r y c y luego complete los cuadrados latinos con las entradas de 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 cruzan en como máximo un punto. Además, las líneas se pueden dividir en k clases paralelas (no se encuentran dos de sus líneas), cada una de las cuales contiene n líneas. [34]
Una red ( n + 1, n ) es un plano afín de orden n .
Un conjunto de k MOLS( n ) es equivalente a una ( k + 2, n ) -net. [10]
Para construir una red ( k + 2, n ) 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 como r y c se considerarán las coordenadas de los n 2 puntos de la red. Cada otra columna (es decir, el cuadrado latino) se utilizará para definir las líneas en una clase paralela. Las n líneas determinadas por la columna denominada Li se indicarán como li j . Los puntos sobre l ij serán aquellos con coordenadas correspondientes a las filas donde la entrada en la columna Li es j . Hay dos clases paralelas adicionales, correspondientes a las columnas r y c . Las líneas r j y c j constan de 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 en 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 una T[ k ,1; n ] diseño 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 )-net. Es decir, tiene nk puntos yn 2 bloques. Cada punto está en n bloques; cada bloque contiene k puntos. Los puntos se dividen en k clases de equivalencia (grupos) de tamaño n , de modo que dos puntos del mismo grupo no están contenidos en un bloque, mientras que dos puntos de 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á por bij . Los puntos del diseño se obtendrán del siguiente esquema: r i ↔ i , c j ↔ 5 j , y l ij ↔ 5 i + j . Los puntos del diseño se indican así con 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 borde del gráfico 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 , programación de torneos y 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 de 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)
