Articulo de referencia

Matriz ortogonal

En matemáticas, una matriz ortogonal (más específicamente, una matriz ortogonal de nivel fijo ) es una tabla ("matriz") cuyas entradas provienen de un conjunto finito fijo de sí...

En matemáticas, una matriz ortogonal (más específicamente, una matriz ortogonal de nivel fijo ) es una tabla ("matriz") cuyas entradas provienen de un conjunto finito fijo de símbolos (por ejemplo, {1,2,..., v }), dispuestas de tal manera que existe un entero t tal que, para cada selección de t columnas de la tabla, todas las t - tuplas ordenadas de los símbolos, formadas al tomar las entradas de cada fila restringidas a estas columnas, aparecen el mismo número de veces. El número t se denomina fuerza de la matriz ortogonal. He aquí dos ejemplos:

El ejemplo de la izquierda corresponde a una matriz ortogonal con el conjunto de símbolos {1,2} y fuerza 2. Nótese que los cuatro pares ordenados (tuplas de 2) formados por las filas restringidas a la primera y tercera columna, a saber, (1,1), (2,1), (1,2) y (2,2), son todos los pares ordenados posibles del conjunto de dos elementos y cada uno aparece exactamente una vez. La segunda y tercera columna darían como resultado (1,1), (2,1), (2,2) y (1,2); de nuevo, todos los pares ordenados posibles aparecen una vez cada uno. La misma afirmación sería válida si se hubieran utilizado la primera y la segunda columna. Por lo tanto, se trata de una matriz ortogonal de fuerza dos.

En el ejemplo de la derecha, [ 1 ] las filas restringidas a las tres primeras columnas contienen las 8 posibles ternas ordenadas formadas por 0 y 1, cada una apareciendo una vez. Lo mismo ocurre con cualquier otra elección de tres columnas. Por lo tanto, se trata de una matriz ortogonal de fuerza 3.

Una matriz ortogonal de niveles mixtos es aquella en la que cada columna puede tener un número diferente de símbolos. A continuación se muestra un ejemplo.

Las matrices ortogonales generalizan, en forma tabular, la idea de los cuadrados latinos mutuamente ortogonales . Estas matrices tienen muchas conexiones con otros diseños combinatorios y aplicaciones en el diseño estadístico de experimentos , la teoría de la codificación , la criptografía y diversos tipos de pruebas de software .

Definición

Un OA(18, 7, 3, 2) en el lado derecho. Cualquier par de columnas (extraídas al lado izquierdo) contiene cada par ordenado dos veces como su fila. Aquí se reproduce la animación SVG que varía el par de columnas.

Para tk , una matriz ortogonal de tipo ( N, k, v, t ) –una OA ( N, k, v, t ) para abreviar– es una matriz N × k cuyas entradas se eligen de un conjunto X con v puntos (un v -conjunto ) de tal manera que en cada subconjunto de t columnas de la matriz, cada t -tupla de puntos de X se repite el mismo número de veces. El número de repeticiones se suele denotar como λ.  

En muchas aplicaciones, a estos parámetros se les asignan los siguientes nombres:

N es el número de ensayos experimentales ,
k es el número de factores ,
v es el número de niveles ,
t es la fuerza y
λ es el índice .

La definición de fuerza conduce a la relación de parámetros

N = λ v t .

Una matriz ortogonal es simple si no contiene filas repetidas. ( Las submatrices de t columnas pueden tener filas repetidas, como en el ejemplo OA(18, 7, 3, 2) que se muestra en esta sección).

Una matriz ortogonal es lineal si X es un cuerpo 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 . [ 2 ] El ejemplo de la derecha en la introducción es lineal sobre el cuerpo F 2 . Toda matriz ortogonal lineal es simple.

En una matriz ortogonal de niveles mixtos, los símbolos en las columnas pueden elegirse de diferentes conjuntos que tienen diferentes números de puntos, como en el siguiente ejemplo: [ 3 ]

Esta matriz tiene fuerza 2:

  • Cualquier par de las primeras cuatro columnas contiene cada uno de los pares ordenados (0, 0), (0, 1), (1, 0) y (1, 1) dos veces.
  • Las columnas 4 y 5 , o la columna 5 junto con cualquiera de las otras columnas , contienen cada par ordenado ( i , j ) una vez, donde i = 0 o 1 y j = 0, 1, 2 o 3.  

Por lo tanto, se puede denotar como OA(8, 5, 2 4 4 1 , 2), como se explica más adelante. La expresión 2 4 4 1 indica que cuatro factores tienen 2 niveles y uno tiene 4 niveles.

Como en este ejemplo, no hay un único "índice" o número de repetición λ en una matriz ortogonal de niveles mixtos de fuerza t : cada submatriz de t columnas puede tener un λ diferente.

Terminología y notación

Los términos simétrico y asimétrico se utilizan a veces para referirse a niveles fijos y niveles mixtos . Aquí, la simetría se refiere a la propiedad de que todos los factores tienen el mismo número de niveles, no a la "forma" de la matriz: una matriz ortogonal simétrica casi nunca es una matriz simétrica .

La notación OA( N, k, v, t ) a veces se contrae de modo que se puede escribir, por ejemplo, simplemente OA( k, v ), [ 4 ] siempre que el texto aclare los valores de los parámetros no declarados. En el otro sentido, se puede expandir para matrices de niveles mixtos. Aquí se escribiría OA( N, k, v 1 ···v k , t ), donde la columna i tiene v i niveles. Esta notación generalmente se acorta cuando los valores v se repiten, de modo que se escribe OA(8, 5, 2 4 4 1 , 2) para el ejemplo al final de la última sección, en lugar de OA(8, 5, 2·2·2·2·4, 2). De manera similar, se puede acortar OA( N, k, v, t ) a OA( N, v k , t ) para matrices de nivel fijo.

Esta notación OA no incluye explícitamente el índice λ, pero este se puede recuperar a partir de los demás parámetros mediante la relación N = λ v t . Esto resulta eficaz cuando todos los parámetros tienen valores numéricos específicos, pero no tanto cuando se pretende definir una clase de arreglos ortogonales. Por ejemplo, al indicar la clase de arreglos con fuerza t = 2 e índice λ = 1, la notación OA( N, k, v, 2 ) es insuficiente para determinar λ por sí sola. Esto se suele solucionar escribiendo OA( v 2 , k, v, 2) en su lugar. Si bien las notaciones que incluyen explícitamente el parámetro λ no presentan este problema, no se pueden extender fácilmente para denotar arreglos de niveles mixtos.

Algunos autores definen un OA( N, k, v, t ) como k × N en lugar de N × k . En tales casos, la fuerza de la matriz se define en términos de un subconjunto de t filas en lugar de columnas.

Excepto por el prefijo OA, la notación OA( N, k, v, t ) es la misma que la introducida por Rao. [ 5 ] Si bien esta notación es muy común, no es universal. Hedayat, Sloane y Stufken [ 6 ] la recomiendan como estándar, pero enumeran ocho alternativas encontradas en la literatura, y existen otras. [ 8 ]

Ejemplos

Un ejemplo de un OA(16, 5, 4, 2); un diseño de fuerza 2, 4 niveles de índice 1 con 16 ensayos:

Un ejemplo de OA(27, 5, 3, 2) (escrito como su transpuesta para facilitar la visualización): [ 9 ]

Este ejemplo tiene índice λ = 3.

Ejemplos triviales

Un arreglo que consta de todas las k -tuplas de un v -conjunto, dispuestas de manera que las k -tuplas sean filas, tiene automáticamente ( de forma trivial ) fuerza k , y por lo tanto es un OA( v k , k, v, k ). Cualquier OA( N, k, v, k ) se consideraría trivial ya que tales arreglos se construyen fácilmente simplemente enumerando todas las k -tuplas del v -conjunto λ veces.

Cuadrados latinos mutuamente ortogonales

Un OA( n² , 3, n , 2) es equivalente a un cuadrado latino de orden n . Para kn + 1, un OA( n² , k, n , 2) es equivalente a un conjunto de k  2 cuadrados latinos mutuamente ortogonales de orden n . Estos arreglos ortogonales de índice uno y fuerza 2 también se conocen como diseños de cuadrados hiper-graeco-latinos en la literatura estadística.

Sea A una matriz ortogonal de fuerza 2 e índice 1 sobre un conjunto de n elementos, identificado con el conjunto de números naturales {1,..., n }. Elija y fije, en orden, dos columnas de A , llamadas columnas de indexación . Debido a que la fuerza es 2 y el índice es 1, todos los pares ordenados ( i , j ) con 1 ≤ i , jn aparecen exactamente una vez en las filas de las columnas de indexación. Aquí, i y j indexarán a su vez las filas y columnas de un cuadrado n × n . Tome cualquier otra columna de A y rellene la celda ( i , j ) de este cuadrado con la entrada que se encuentra en esta columna de A y en la fila de A cuyas columnas de indexación contienen ( i , j ). El cuadrado resultante es un cuadrado latino de orden n . Por ejemplo, considere este OA(9, 4, 3, 2):

Al elegir las columnas 3 y 4 (en ese orden) como columnas de indexación, la primera columna produce el cuadrado latino.

mientras que la segunda columna produce el cuadrado latino

Además, estos dos cuadrados son mutuamente ortogonales. En general, 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, por lo que se pueden construir matrices ortogonales de fuerza 2 e índice 1 a partir de conjuntos de cuadrados latinos mutuamente ortogonales. [ 10 ]

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 puede considerarse como un OA( n² , 3, n , 2). De hecho, la matriz ortogonal puede generar seis cuadrados latinos , ya que cualquier par ordenado de columnas distintas puede usarse como columnas de indexación. Sin embargo, todas son isotópicas y se consideran equivalentes. Para mayor claridad, 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 n × n × n que consta de n capas, cada una con n filas y n columnas, de manera que los n elementos distintos que aparecen se repiten n 2 veces y están dispuestos de tal forma que en cada capa, paralela a cada uno de los tres pares de caras opuestas del cubo, aparecen los n elementos distintos y cada uno se repite exactamente n veces en esa capa. [ 11 ]

Nótese que, según esta definición, una capa de un cubo latino no tiene por qué ser un cuadrado latino. De hecho, ninguna fila, columna o archivo (las celdas de una posición particular en las diferentes capas) tiene por qué ser una permutación de los n símbolos. [ 12 ]

Un cubo latino de orden n es equivalente a un OA( n 3 , 4 ,n , 2). [ 9 ]

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 aparece exactamente n veces. Un conjunto de k  3 cubos latinos mutuamente ortogonales de orden n es equivalente a un OA( n 3 , k, n , 2). [ 9 ] Un ejemplo de un par de cubos latinos mutuamente ortogonales de orden tres se dio como el OA(27, 5, 3, 2) en la sección de Ejemplos anterior.

A diferencia del caso de los cuadrados latinos, en los que no hay restricciones, las columnas de indexación de la representación de matriz ortogonal de un cubo latino deben seleccionarse de manera que formen un OA( n 3 , 3, n , 3).

hipercubos latinos

Un hipercubo latino m -dimensional de orden n de la clase r es una matriz m -dimensional n × n × ... × n que tiene n r elementos distintos, cada uno repetido n mr veces, y tal que cada elemento aparece exactamente n mr1 veces en cada uno de sus m conjuntos de n subespacios lineales paralelos ( m − 1)-dimensionales (o "capas"). Dos hipercubos latinos de este tipo, del mismo orden n y clase r, con la propiedad de que, cuando uno se superpone al otro, cada elemento de uno aparece exactamente n m2 r veces con cada elemento del otro, se denominan ortogonales . [ 13 ]          

Un conjunto de k m hipercubos latinos m -dimensionales mutuamente ortogonales de orden n es equivalente a un OA( n m , k, n, 2 ), donde las columnas de indexación forman un OA( n m , m, n, m ). 

Historia

Los conceptos de cuadrados latinos y cuadrados latinos mutuamente ortogonales fueron generalizados a cubos latinos e hipercubos, y cubos latinos ortogonales e hipercubos por Kishen (1942) . [ 14 ] Rao (1946) generalizó estos resultados a arreglos de fuerza t . La noción actual de arreglo ortogonal como una generalización de estas ideas, debida al legendario científico CR Rao , aparece en Rao (1947) , [ 15 ] y su generalización a arreglos de niveles mixtos apareció en 1973. [ 16 ]

Rao utilizó inicialmente el término "matriz" sin ningún modificador y lo definió simplemente como un subconjunto de todas las combinaciones de tratamientos : una matriz simple . La posibilidad de matrices no simples surgió de forma natural al convertir las combinaciones de tratamientos en las filas de una matriz. Hedayat, Sloane y Stufken [ 17 ] atribuyen a K. Bush [ 18 ] el término "matriz ortogonal". 

Otras construcciones

Matrices de Hadamard

Existe una OA( 4λ, 4λ  1, 2, 2) si y solo si existe una matriz de Hadamard de orden 4λ . [ 19 ] Para proceder en una dirección, sea H una matriz de Hadamard de orden 4m en forma estandarizada (las entradas de la primera fila y columna son todas +1). Elimine la primera fila y tome la transpuesta para obtener la matriz ortogonal deseada. [ 20 ] El siguiente ejemplo ilustra esto. (La construcción inversa es similar).

La matriz de Hadamard estandarizada de orden 8 que se muestra a continuación (±1 entradas indicadas solo por el signo),

produce el OA(8, 7, 2, 2): [ 21 ]

Utilizando las columnas 1, 2 y 4 como columnas de indexación, las columnas restantes producen cuatro cubos latinos mutuamente ortogonales de orden 2.

Códigos

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 un OA( q n-m , n, q, d  1) (lineal) donde λ  = q nmd + 1 . [ 22 ]       

Aplicaciones

Esquemas de umbral

El reparto 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 mismo. El secreto solo puede reconstruirse cuando se combinan suficientes partes, posiblemente de diferentes tipos; las partes individuales no sirven por sí solas. Un sistema de reparto de secretos es perfecto si ningún grupo de participantes que cumpla los criterios para obtener el secreto posee información adicional sobre el mismo que la que posee un individuo sin ninguna parte.

En un tipo de esquema de compartición de secretos, hay un distribuidor y n jugadores . El distribuidor reparte partes de un secreto entre los jugadores, pero estos solo podrán reconstruirlo si se cumplen ciertas condiciones. El distribuidor logra esto asignando a cada jugador una parte de tal manera que cualquier grupo de t (donde t es el umbral ) o más jugadores pueda reconstruir el secreto, pero ningún grupo de menos de t jugadores podrá hacerlo. Este sistema se denomina esquema de umbral ( t , n ). 

Se puede utilizar un OA( v t , n+1, v, t ) para construir un esquema de umbral ( t , n ) perfecto. [ 23 ]

Sea A la matriz ortogonal. Las primeras n columnas se usarán para distribuir las participaciones entre los jugadores, mientras que la última columna representa el secreto a compartir. Si el crupier desea compartir un secreto S , solo se usarán en el esquema las filas de A cuya última entrada sea S. El crupier selecciona aleatoriamente una de estas filas y entrega al jugador i la entrada de dicha fila en la columna i como participación.

Diseños factoriales

Un experimento factorial es un experimento con estructura estadística en el que se aplican varios factores (niveles de riego, antibióticos, fertilizantes, etc.) a cada unidad experimental en un número finito de niveles , que pueden ser cuantitativos o cualitativos. [ 24 ] En un experimento factorial completo, es necesario probar todas las combinaciones de niveles de los factores. En un diseño factorial fraccionado, solo se utiliza un subconjunto de combinaciones de tratamientos.

Se puede utilizar una matriz ortogonal para diseñar un experimento factorial fraccionado. Las columnas representan los distintos factores y las entradas, los niveles en los que se observan dichos factores. Una ejecución experimental es una fila de la matriz ortogonal, es decir, una combinación específica de niveles de los factores. La robustez de la matriz determina la resolución del diseño fraccionado. Al utilizar uno de estos diseños, las unidades de tratamiento y el orden de las ejecuciones deben aleatorizarse en la medida en que el diseño lo permita. Por ejemplo, se recomienda seleccionar aleatoriamente una matriz ortogonal de tamaño adecuado entre las disponibles y, posteriormente, aleatorizar el orden de las ejecuciones.

Los diseños de niveles mixtos surgen de forma natural en el ámbito estadístico.

Control de calidad

Las matrices ortogonales desempeñaron un papel fundamental en el desarrollo de los métodos de Taguchi por Genichi Taguchi , durante su visita al Instituto Estadístico Indio 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 por la industria estadounidense, aunque con ciertas reservas . El catálogo de Taguchi [ 25 ] contiene matrices de nivel fijo y mixto.

Pruebas

Las pruebas de matrices ortogonales son una técnica de prueba de caja negra que es una forma sistemática y estadística de prueba de software . [ 26 ] [ 27 ] Se utiliza cuando el número de entradas al sistema es relativamente pequeño, pero demasiado grande para permitir una prueba exhaustiva de cada posible entrada a los sistemas . [ 26 ] Es particularmente eficaz para encontrar errores asociados con lógica defectuosa dentro de los sistemas de software de computadora . [ 26 ] Las matrices ortogonales se pueden aplicar en pruebas de interfaz de usuario , pruebas de sistema , pruebas de regresión y pruebas de rendimiento . Las permutaciones de los niveles de factor que componen un solo tratamiento se eligen de tal manera que sus respuestas no estén correlacionadas y, por lo tanto, cada tratamiento da una pieza de información única . El efecto neto de organizar el experimento en tales tratamientos es que la misma pieza de información se recopila en el número mínimo de experimentos .

Véase también

Notas

  1. ^ Hedayat, Sloane y Stufken 1999 , Tabla 1.3
  2. Stinson 2003 , pág. 225
  3. ^ Hedayat, Sloane y Stufken 1999 , cuadro 9.10(b)
  4. Stinson 2003 , pág. 140 
  5. Rao 1947 , pág. 129 
  6. ^ Hedayat, Sloane y Stufken 1999 , pág. 2 
  7. Stinson 2003 , pág. 225
  8. Véase, por ejemplo, [ 7 ] .
  9. 1 2 3 Dénes y Keedwell 1974 , pág. 191
  10. Stinson 2003 , págs. 140–141, Sección 6.5.1
  11. Dénes & Keedwell 1974 , pág. 187 atribuyen la definición a Kishen (1950 , pág. 21)
  12. En la definición preferida del combinatorialista, cada fila, columna y archivo contendría una permutación de los símbolos, pero esto es solo un tipo especial de cubo latino llamado cubo de permutación .
  13. Dénes & Keedwell 1974 , pág. 189
  14. Raghavarao 1988 , pág. 9
  15. Raghavarao 1988 , pág. 10
  16. Rao 1973 , pág. 354 
  17. ^ Hedayat, Sloane y Stufken 1999 , pág. 4 
  18. Bush 1950
  19. ^ Hedayat, Sloane y Stufken 1999 , Teorema 7.5
  20. Stinson 2003 , pág. 225, Teorema 10.2
  21. Stinson 2003 , pág. 226, Ejemplo 10.3
  22. Stinson 2003 , pág. 231, Teorema 10.17
  23. Stinson 2003 , pág. 262, Teorema 11.5
  24. Street & Street 1987 , pág. 194, Sección 9.2
  25. Taguchi 1986
  26. 1 2 3 Pressman, Roger S (2005). Ingeniería de software: Un enfoque práctico (6.ª  ed.). McGraw-Hill. ISBN 0-07-285318-2.
  27. Phadke, Madhav S. "Planificación de pruebas de software eficientes" . Phadke Associates, Inc. Archivado del original el 25 de abril de 2012. Consultado el 6 de agosto de 2012. Numerosos artículos sobre la utilización de matrices ortogonales para pruebas de software y sistemas.

Referencias

  • Box, GEP; Hunter, WG; Hunter, JS (1978). Estadística para experimentadores: Introducción al diseño, análisis de datos y construcción de modelos . John Wiley and Sons. ISBN 9780471093152.
  • Bush, KA (1950). Matrices ortogonales (PhD). Universidad de Carolina del Norte.
  • Dénes, J.; Keedwell, AD (1974), Latin Squares and Their Applications , Nueva York-Londres: Academic Press, ISBN 0-12-209350-X, MR 0351850 
  • Hedayat, AS; Sloane, Nueva Jersey; Stufken, J. (1999), Matrices ortogonales, teoría y aplicaciones , Nueva York: Springer
  • Kishen, K. (1942), "Sobre cubos latinos e hipergriegos e hipercubos", Current Science , 11 : 98–99
  • Kishen, K. (1950), "Sobre la construcción de cubos e hipercubos latinos e hipergrecolatinos", J. Indian Soc. Agric. Statistics , 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.{{cite book}}: 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 a partir de arreglos combinatorios de matrices", Suplemento del Journal of the Royal Statistical Society , 9 (1): 128– 139, doi : 10.2307/2983576 , JSTOR 2983576 
  • Rao, CR (1973). «Algunos problemas combinatorios de arreglos y aplicaciones al diseño de experimentos». En Srivastava, Jagdish N. (ed.). Un estudio de la teoría combinatoria . North Holland. ISBN 0-7204-22620.
  • 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 del diseño experimental . Oxford UP [Clarendon]. ISBN 0-19-853256-3.
  • Taguchi, Genichi (1986). Arreglos ortogonales y grafos lineales . Dearborn, MI: American Supplier Institute.
  • Diseños de cuadrados hipergreco-latinos
  • 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.

Dominio público Este artículo incorpora material de dominio público del Instituto Nacional de Estándares y Tecnología.