En matemáticas, una matriz ortogonal es una "tabla" (matriz) cuyas entradas provienen de un conjunto finito fijo de símbolos (típicamente, {1,2, ..., n }), organizados de tal manera que hay un número entero t para que para cada selección de t columnas de la tabla, todas las t - tuplas ordenadas de los símbolos, formadas tomando las entradas en cada fila restringidas a estas columnas, aparezcan el mismo número de veces. El número t se llama fuerza de la matriz ortogonal. Aquí hay un ejemplo simple de una matriz ortogonal con el conjunto de símbolos {1,2} y fuerza 2:
1 1 1 2 2 1 1 2 2 2 1 2
Observe que los cuatro pares ordenados (2-tuplas) formados por las filas restringidas a la primera y tercera columnas, a saber (1,1), (2,1), (1,2) y (2,2), son todos los posibles pares ordenados del conjunto de dos elementos y cada uno aparece exactamente una vez. La segunda y tercera columnas darían, (1,1), (2,1), (2,2) y (1,2); de nuevo, todos los pares ordenados posibles aparecen cada uno una vez. La misma declaración se mantendría si se hubieran utilizado la primera y la segunda columna. Por tanto, se trata de una matriz ortogonal de fuerza dos.
Los arreglos ortogonales generalizan, en forma tabular, la idea de cuadrados latinos mutuamente ortogonales . Estos arreglos tienen muchas conexiones con otros diseños combinatorios y tienen aplicaciones en el diseño estadístico de experimentos , teoría de codificación , criptografía y varios tipos de pruebas de software .
Definición
Una matriz ortogonal t - ( v , k , λ) ( t ≤ k ) es una matriz λ v t × k cuyas entradas se eligen de un conjunto X con v puntos de modo que en cada subconjunto de t columnas de la matriz, cada t -tupla de puntos de X aparece exactamente en filas λ.
En esta definición formal, se prevé la repetición de las t- tuplas (λ es el número de repeticiones) y el número de filas está determinado por los otros parámetros.
En muchas aplicaciones, estos parámetros reciben los siguientes nombres:
- v es el número de niveles ,
- k es el número de factores ,
- λ v t es el número de corridas experimentales ,
- t es la fuerza , y
- λ es el índice .
Una matriz ortogonal es simple si no contiene filas repetidas.
Una matriz ortogonal es lineal si X es un campo finito F q de orden q ( q una potencia prima) y las filas de la matriz forman un subespacio del espacio vectorial ( F q ) k . [1]
Cada arreglo ortogonal lineal es simple.
Ejemplos de
Un ejemplo de una matriz ortogonal 2- (4, 5, 1); un diseño de nivel 2, 4 de índice 1 con 16 carreras.
1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 2 | 2 |
1 | 3 | 3 | 3 | 3 |
1 | 4 | 4 | 4 | 4 |
2 | 1 | 4 | 2 | 3 |
2 | 2 | 3 | 1 | 4 |
2 | 3 | 2 | 4 | 1 |
2 | 4 | 1 | 3 | 2 |
3 | 1 | 2 | 3 | 4 |
3 | 2 | 1 | 4 | 3 |
3 | 3 | 4 | 1 | 2 |
3 | 4 | 3 | 2 | 1 |
4 | 1 | 3 | 4 | 2 |
4 | 2 | 4 | 3 | 1 |
4 | 3 | 1 | 2 | 4 |
4 | 4 | 2 | 1 | 3 |
Un ejemplo de una matriz ortogonal 2- (3,5,3) (escrita como su transposición para facilitar la visualización): [2]
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 |
0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 0 | 0 | 0 |
0 | 1 | 2 | 1 | 2 | 0 | 2 | 0 | 1 | 0 | 1 | 2 | 1 | 2 | 0 | 2 | 0 | 1 | 0 | 1 | 2 | 1 | 2 | 0 | 2 | 0 | 1 |
Ejemplos triviales
Cualquier matriz ortogonal t - ( v , t , λ) se consideraría trivial ya que se construyen fácilmente simplemente enumerando todas las t -tuplas del v -set λ veces.
Cuadrados latinos mutuamente ortogonales
Una matriz ortogonal 2- ( v , k , 1) es equivalente a un conjunto de k - 2 cuadrados latinos mutuamente ortogonales de orden v .
Las matrices ortogonales de índice uno, fuerza 2 también se conocen como diseños cuadrados hiper-grecolatinos en la literatura estadística.
Sea A una matriz ortogonal de fuerza 2, índice 1 en un conjunto v de elementos, identificado con el conjunto de números naturales {1, ..., v }. Elija y corrija, en orden, dos columnas de A , llamadas columnas de indexación . Todos los pares ordenados ( i , j ) con 1 ≤ i , j ≤ v aparecen exactamente una vez en las filas de las columnas de indexación. Tome cualquier otra columna de A y crear una matriz cuadrada cuya entrada en la posición ( i , j ) es la entrada de A en esta columna en la fila que contiene ( i , j ) en las columnas de indexación de la A . El cuadrado resultante es un cuadrado latino de orden v . Por ejemplo, considere la matriz ortogonal 2- (3,4,1):
1 | 1 | 1 | 1 |
1 | 2 | 2 | 2 |
1 | 3 | 3 | 3 |
2 | 1 | 2 | 3 |
2 | 2 | 3 | 1 |
2 | 3 | 1 | 2 |
3 | 1 | 3 | 2 |
3 | 2 | 1 | 3 |
3 | 3 | 2 | 1 |
Al elegir las columnas 3 y 4 (en ese orden) como columnas de indexación, la primera columna produce el cuadrado latino,
1 | 2 | 3 |
3 | 1 | 2 |
2 | 3 | 1 |
mientras que la segunda columna produce el cuadrado latino,
1 | 3 | 2 |
3 | 2 | 1 |
2 | 1 | 3 |
Los cuadrados latinos producidos de esta manera a partir de una matriz ortogonal serán cuadrados latinos ortogonales, por lo que las k - 2 columnas distintas de las columnas de indexación producirán un conjunto de k - 2 cuadrados latinos mutuamente ortogonales .
Esta construcción es completamente reversible y, por lo tanto, las matrices ortogonales de fuerza 2, índice 1 se pueden construir a partir de conjuntos de cuadrados latinos mutuamente ortogonales. [3]
Cuadrados latinos, cubos latinos e hipercubos latinos
Las matrices ortogonales proporcionan una forma uniforme de describir estos diversos objetos que son de interés en el diseño estadístico de experimentos .
Cuadrados latinos
Como se mencionó en la sección anterior, un cuadrado latino de orden n se puede considerar como una matriz ortogonal 2- ( n , 3, 1). En realidad, la matriz ortogonal puede dar lugar a seis cuadrados latinos, ya que cualquier par ordenado de columnas distintas se puede utilizar como columnas de indexación. Sin embargo, todos estos son isotópicos y se consideran equivalentes. En aras de la concreción, siempre asumiremos que las dos primeras columnas en su orden natural se utilizan como columnas de indexación.
Cubos latinos
En la literatura estadística, un cubo latino es una matriz tridimensional de n × n × n que consta de n capas, cada una de las cuales tiene n filas yn columnas de manera que los n elementos distintos que aparecen se repiten n 2 veces y se ordenan de manera que en cada capa paralela a cada uno de los tres pares de caras opuestas del cubo aparecen todos los n elementos distintos y cada uno se repite exactamente n veces en esa capa. [4]
Tenga en cuenta que con esta definición una capa de un cubo latino no necesita ser un cuadrado latino. De hecho, ninguna fila, columna o archivo (las celdas de una posición particular en las diferentes capas) necesita ser una permutación de los n símbolos. [5]
Un cubo latino de orden n es equivalente a una matriz ortogonal 2- ( n , 4, n ). [2]
Dos cubos latinos de orden n son ortogonales si, entre los n 3 pares de elementos elegidos de las celdas correspondientes de los dos cubos, cada par ordenado distinto de los elementos ocurre exactamente n veces.
Un conjunto de k - 3 cubos latinos mutuamente ortogonales de orden n es equivalente a una matriz ortogonal 2- ( n , k , n ). [2]
Se dio un ejemplo de un par de cubos latinos mutuamente ortogonales de orden tres como la matriz ortogonal 2- (3,5,3) en la sección de Ejemplos anterior.
A diferencia del caso de los cuadrados latinos, en el que no hay restricciones, las columnas de indexación de la representación de matriz ortogonal de un cubo latino deben seleccionarse para formar una matriz ortogonal 3- ( n , 3,1).
Hipercubos latinos
Un hipercubo latino m -dimensional de orden n de la clase r- ésima es una matriz n × n × ... × n m -dimensional que tiene n r elementos distintos, cada uno repetido n m - r veces, y tal que cada elemento ocurre exactamente n m - r - 1 veces en cada uno de sus m conjuntos de n subespacios lineales paralelos ( m - 1) dimensionales (o "capas"). Dos hipercubos latinos del mismo orden n y clase r con la propiedad de que, cuando uno se superpone al otro, cada elemento del uno ocurre exactamente n m - 2 r veces con cada elemento del otro, se dice que son ortogonales. . [6]
Un conjunto de k - m hipercubos latinos m - dimensionales mutuamente ortogonales de orden n es equivalente a una matriz ortogonal 2- ( n , k , n m - 2 ), donde las columnas de indexación forman una m - ( n , m , 1) matriz ortogonal.
Historia
Los conceptos de cuadrados latinos y cuadrados latinos mutuamente ortogonales fueron generalizados a cubos e hipercubos latinos, y cubos e hipercubos latinos ortogonales por Kishen (1942) . [7] Rao (1946) generalizó estos resultados a la fuerza t . La noción actual de arreglo ortogonal como generalización de estas ideas, debida a CR Rao , aparece en Rao (1947) . [8]
Otras construcciones
Matrices de Hadamard
Si existe una matriz de Hadamard de orden 4 m , entonces existe una matriz ortogonal 2- (2, 4 m - 1, m ).
Sea H una matriz de Hadamard de orden 4 m en forma estandarizada (las entradas de la primera fila y columna son todas +1). Elimine la primera fila y tome la transposición para obtener la matriz ortogonal deseada. [9]
El orden 8 matriz de Hadamard estandarizada a continuación (± 1 entradas indicadas solo por signo),
+ | + | + | + | + | + | + | + |
+ | + | + | + | - | - | - | - |
+ | + | - | - | + | + | - | - |
+ | + | - | - | - | - | + | + |
+ | - | + | - | + | - | + | - |
+ | - | + | - | - | + | - | + |
+ | - | - | + | + | - | - | + |
+ | - | - | + | - | + | + | - |
produce la matriz ortogonal 2- (2,7,2): [10]
+ | + | + | + | + | + | + |
+ | + | + | - | - | - | - |
+ | - | - | + | + | - | - |
+ | - | - | - | - | + | + |
- | + | - | + | - | + | - |
- | + | - | - | + | - | + |
- | - | + | + | - | - | + |
- | - | + | - | + | + | - |
Usando las columnas 1, 2 y 4 como columnas de indexación, las columnas restantes producen cuatro cubos latinos mutuamente ortogonales de orden 2.
Codigos
Sea C ⊆ ( F q ) n , un código lineal de dimensión m con distancia mínima d . Entonces C ⊥ (el complemento ortogonal del subespacio vectorial C ) es una matriz ortogonal (lineal) ( d - 1) - ( q , n , λ) donde
λ = q n - m - d + 1 . [11]
Aplicaciones
Esquemas de umbral
El intercambio de secretos (también llamado división de secretos ) consiste en métodos para distribuir un secreto entre un grupo de participantes, a cada uno de los cuales se le asigna una parte del secreto. El secreto sólo puede reconstruirse cuando se combinan un número suficiente de acciones, posiblemente de diferentes tipos; las acciones individuales no sirven de nada por sí mismas. Un esquema de intercambio de secretos es perfecto si cada grupo de participantes que no cumple con los criterios para obtener el secreto, no tiene un conocimiento adicional de cuál es el secreto que un individuo sin compartir.
En un tipo de esquema de compartición de secretos no es uno de concesionarios y n jugadores . El crupier comparte un secreto con los jugadores, pero solo cuando se cumplan las condiciones específicas, los jugadores podrán reconstruir el secreto. El crupier logra esto dando a cada jugador una parte de tal manera que cualquier grupo de t (para el umbral ) o más jugadores puedan reconstruir juntos el secreto, pero ningún grupo de menos de t jugadores puede. Este sistema se denomina esquema de umbral ( t , n ).
Se puede usar una matriz ortogonal t - ( v , n + 1, 1) para construir un esquema de umbral perfecto ( t , n ). [12]
- Sea A la matriz ortogonal. Las primeras n columnas se utilizarán para proporcionar acciones a los jugadores, mientras que la última columna representa el secreto a compartir. Si el crupier desea compartir una S secreta , solo se utilizan en el esquema las filas de A cuya última entrada es S. El crupier selecciona aleatoriamente una de estas filas y entrega al jugador i la entrada en esta fila en la columna i como acciones.
Diseños factoriales
Un experimento factorial es un experimento estructurado estadísticamente en el que se aplican varios factores (niveles de riego, antibióticos, fertilizantes, etc.) a cada unidad experimental en niveles variables (pero integrales) (alto, bajo o varios niveles intermedios). [13] En un experimento factorial completo, es necesario probar todas las combinaciones de niveles de los factores, pero para minimizar las influencias de confusión, los niveles deben variarse dentro de cualquier ejecución experimental.
Se puede usar una matriz ortogonal de fuerza 2 para diseñar un experimento factorial. Las columnas representan los diversos factores y las entradas son los niveles en los que se pueden aplicar los factores (suponiendo que todos los factores se pueden aplicar en el mismo número de niveles). Una corrida experimental es una fila de la matriz ortogonal, es decir, aplicar los factores correspondientes en los niveles que aparecen en la fila. Cuando se utiliza uno de estos diseños, las unidades de tratamiento y el orden del ensayo deben ser aleatorizados tanto como lo permita el diseño. Por ejemplo, una recomendación es que se seleccione aleatoriamente una matriz ortogonal de tamaño apropiado entre las disponibles, y luego aleatorice el orden de ejecución.
Control de calidad
Los arreglos ortogonales jugaron un papel central en el desarrollo de los métodos de Taguchi por Genichi Taguchi , que tuvo lugar durante su visita al Instituto de Estadística de la India a principios de la década de 1950. Sus métodos fueron aplicados y adoptados con éxito por las industrias japonesa e india y, posteriormente, también fueron adoptados por la industria estadounidense, aunque con algunas reservas.
Pruebas
La prueba de matriz ortogonal es una técnica de prueba de caja negra que es una forma sistemática y estadística de prueba de software . [14] [15] Se utiliza cuando el número de entradas al sistema es relativamente pequeño, pero demasiado grande para permitir una prueba exhaustiva de todas las posibles entradas a los sistemas . [14] Es particularmente eficaz para encontrar errores asociados con la lógica defectuosa dentro de los sistemas de software de computadora . [14] Las matrices ortogonales se pueden aplicar en pruebas de interfaz de usuario, pruebas de sistemas , pruebas de regresión y pruebas de rendimiento . Las permutaciones de los niveles de factor que comprenden un solo tratamiento se eligen de manera que sus respuestas no están correlacionadas y por lo tanto cada tratamiento da una pieza única de información . El efecto neto de organizar el experimento en tales tratamientos es que se recopila la misma información en el número mínimo de experimentos .
Ver también
- Diseño combinatorio
- Muestreo de hipercubo latino
- Cuadrados grecolatinos
Notas
- ^ Stinson 2003 , pág. 225
- ↑ a b c Dénes y Keedwell 1974 , pág. 191
- ^ Stinson 2003 , págs. 140-141, sección 6.5.1
- ^ Dénes y Keedwell 1974 , pág. 187 atribuye la definición a Kishen (1950 , pág.21)
- ^ En la definición preferida del combinatorio, cada fila, columna y archivo contendría una permutación de los símbolos, pero este es solo un tipo especial de cubo latino llamado cubo de permutación .
- ^ Dénes y Keedwell 1974 , pág. 189
- ^ Raghavarao 1988 , pág. 9
- ^ Raghavarao 1988 , pág. 10
- ^ Stinson 2003 , pág. 225, Teorema 10.2
- ^ Stinson 2003 , pág. 226, ejemplo 10.3
- ^ Stinson 2003 , pág. 231, Teorema 10.17
- ^ Stinson 2003 , pág. 262, Teorema 11.5
- ^ Calle y calle 1987 , pág. 194, Sección 9.2
- ↑ a b c Pressman, Roger S (2005). Ingeniería de software: el enfoque de un practicante (6ª ed.). McGraw – Hill. ISBN 0-07-285318-2.
- ^ Phadke, Madhav S. "Planificación de pruebas de software eficientes" . Phadke Associates, Inc.
Numerosos artículos sobre la utilización de matrices ortogonales para pruebas de software y sistemas.
Referencias
- Caja, GEP; Hunter, WG; Hunter, JS (1978). Estadísticas para experimentadores: una introducción al diseño, análisis de datos y construcción de modelos . John Wiley e hijos.
- Dénes, J .; Keedwell, AD (1974), cuadrados latinos y sus aplicaciones , Nueva York-Londres: Academic Press, ISBN 0-12-209350-X, MR 0351850
- Hedayat, AS; Sloane, NJA; Stufken, J. (1999), matrices ortogonales, teoría y aplicaciones , Nueva York: Springer
- Kishen, K. (1942), "Sobre cubos e hipercubos latinos e hipergraecos", Current Science , 11 : 98–99
- Kishen, K. (1950), "Sobre la construcción de cubos e hipercubos latinos e hiper-grecolatinos", J. Indian Soc. Agric. Estadísticas , 2 : 20–48
- 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.
- Raghavarao, Damaraju y Padgett, LV (2005). Diseños de bloques: análisis, combinatoria y aplicaciones . World Scientific.CS1 maint: varios nombres: lista de autores ( enlace )
- Rao, CR (1946), "Hipercubos de fuerza '' d '' que conducen a diseños confusos en experimentos factoriales", Boletín de la Sociedad Matemática de Calcuta , 38 : 67–78
- Rao, CR (1947), "Experimentos factoriales derivables de arreglos combinatorios de matrices", Suplemento del Journal of the Royal Statistical Society , 9 (1): 128-139, doi : 10.2307 / 2983576 , JSTOR 2983576
- Stinson, Douglas R. (2003), Diseños combinatorios: Construcciones y análisis , Nueva York: Springer, ISBN 0-387-95487-2
- Street, Anne Penfold y Street, Deborah J. (1987). Combinatoria de Diseño Experimental . Oxford UP [Clarendon]. ISBN 0-19-853256-3.
enlaces externos
- Diseños cuadrados hiper-grecolatinos
- Un ejemplo de SAS usando PROC FACTEX
- Kuhfeld, Warren F. "Matrices ortogonales". SAS Institute Inc. SAS ofrece un catálogo de más de 117.000 matrices ortogonales.
Este artículo incorpora material de dominio público del sitio web del Instituto Nacional de Estándares y Tecnología https://www.nist.gov .