La teoría de los esquemas de asociación surgió en estadística, en la teoría del diseño experimental para el análisis de varianza . [1] [2] [3] En matemáticas , los esquemas de asociación pertenecen tanto al álgebra como a la combinatoria . En la combinatoria algebraica , los esquemas de asociación proporcionan un enfoque unificado para muchos temas, por ejemplo, diseños combinatorios y teoría de codificación . [4] [5] En álgebra, los esquemas de asociación generalizan grupos y la teoría de esquemas de asociación generaliza la teoría del carácter.de representaciones lineales de grupos. [6] [7] [8]
Definición
Un esquema de asociación de clase n consiste en un conjunto X junto con una partición S de X × X en n + 1 relaciones binarias , R 0 , R 1 , ..., R n que satisfacen:
- y se llama relación de identidad .
- Definiendo , si R en S , entonces R * en S
- Si , el número de tal que y es una constante Dependiendo de , , pero no en la elección particular de y .
Un esquema de asociación es conmutativo si para todos , y . La mayoría de los autores asumen esta propiedad.
Un esquema de asociación simétrico es aquel en el que cada relaciónes una relación simétrica . Es decir:
- si ( x , y ) ∈ R i , entonces ( y , x ) ∈ R i . (O equivalentemente, R * = R. )
Todo esquema de asociación simétrico es conmutativo.
Sin embargo, tenga en cuenta que mientras que la noción de esquema de asociación generaliza la noción de grupo, la noción de esquema de asociación conmutativo solo generaliza la noción de grupo conmutativo.
Dos puntos x e y son llamados i th asociados si. La definición establece que si X e Y son i th asociados también lo son y y x . Cada par de puntos es i ésimo asociado para exactamente uno. Cada punto es su propio asociado cero, mientras que los puntos distintos nunca son asociados cero. Si x y y son k th asociados a continuación, el número de puntosque son ambos i- ésimo asociados dey j th asociados de es una constante .
Interpretación de gráficos y matrices de adyacencia
Un esquema de asociación simétrico se puede visualizar como un gráfico completo con bordes etiquetados. El gráfico tiene vértices, uno por cada punto de , y el borde que une los vértices y está etiquetado Si y están th asociados. Cada borde tiene una etiqueta única y la cantidad de triángulos con una base fija etiquetada tener los otros bordes etiquetados y es una constante , Dependiendo de pero no en la elección de la base. En particular, cada vértice incide exactamente bordes etiquetados ; es la valencia de la relación . También hay bucles etiquetados en cada vértice , correspondiente a .
Las relaciones se describen por sus matrices de adyacencia .es la matriz de adyacencia de por y es una matriz v × v con filas y columnas etiquetadas por los puntos de.
La definición de un esquema de asociación simétrico equivale a decir que el son v × v (0,1) - matrices que satisfacen
- I. es simétrico,
- II. (la matriz de todos unos),
- III. ,
- IV. .
El ( x , y ) de entrada-ésimo de la parte izquierda de (IV) es el número de caminos de longitud dos entre x y y con etiquetas I y J en el gráfico. Tenga en cuenta que las filas y columnas de Contiene 's:
Terminología
- Los números se llaman los parámetros del esquema. También se denominan constantes estructurales .
Historia
El término esquema de asociación se debe a ( Bose & Shimamoto 1952 ) pero el concepto ya es inherente a ( Bose & Nair 1939 ). [9] Estos autores estaban estudiando lo que los estadísticos han llamado diseños de bloques incompletos parcialmente equilibrados (PBIBD). El tema se convirtió en objeto de interés algebraico con la publicación de ( Bose & Mesner 1959 ) y la introducción del álgebra de Bose-Mesner . La contribución más importante a la teoría fue la tesis de P. Delsarte ( Delsarte 1973 ) quien reconoció y utilizó plenamente las conexiones con la teoría de la codificación y la teoría del diseño. [10] Las generalizaciones han sido estudiadas por la DG Higman (configuraciones coherentes) y B. Weisfeiler ( gráficos regulares de distancia ).
Hechos básicos
- , es decir, si luego y el único tal que es
- , esto se debe a que dividir .
El álgebra de Bose-Mesner
Las matrices de adyacencia de las gráficas generar una conmutativa y asociativa álgebra (más de los reales o números complejos ) tanto para el producto de matriz y el producto puntual . Este asociativa , álgebra conmutativa se llama el álgebra Bose-Mesner del esquema de asociación.
Dado que las matrices enson simétricos y se conmutan entre sí, se pueden diagonalizar simultáneamente. Por lo tanto,es semi-simple y tiene una base única de idempotentes primitivos .
Hay otra álgebra de matrices que es isomorfa ay, a menudo, es más fácil trabajar con él.
Ejemplos de
- El esquema de Johnson , denotado J ( v, k ), se define como sigue. Sea S un conjunto con v elementos. Los puntos del esquema J ( v , k ) son lossubconjuntos de S con k elementos. Dos subconjuntos de k -elementos A , B de S son i- ésimo asociados cuando su intersección tiene tamaño k - i .
- El esquema de Hamming , denotado H ( n , q ), se define como sigue. Los puntos de H ( n , q ) son los n ordenados q n - tuplas sobre un conjunto de tamaño q . Se dice que dos n- tuplas x , y son i ésimas asociadas si no están de acuerdo en exactamente i coordenadas. Por ejemplo, si x = (1,0,1,1), Y = (1,1,1,1), z = (0,0,1,1), entonces x y y son 1st asociados, x y z son 1st asociados y y y z son 2ª asociados en H (4,2) .
- Un gráfico de distancia regular , G , forma un esquema de asociación al definir dos vértices como i ésimo asociados si su distancia es i .
- Un grupo finito G produce un esquema de asociación en, con una clase R g para cada elemento del grupo, como sigue: para cada dejar dónde es la operación de grupo . La clase de identidad de grupo es R 0 . Este esquema de asociación es conmutativo si y solo si G es abeliano .
- Un esquema de asociación de tres clases específico: [11]
- Sea A (3) el siguiente esquema de asociación con tres clases asociadas en el conjunto X = {1,2,3,4,5,6}. La entrada ( i , j ) es s si los elementos i y j están en relación R s .
1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
1 | 0 | 1 | 1 | 2 | 3 | 3 |
2 | 1 | 0 | 1 | 3 | 2 | 3 |
3 | 1 | 1 | 0 | 3 | 3 | 2 |
4 | 2 | 3 | 3 | 0 | 1 | 1 |
5 | 3 | 2 | 3 | 1 | 0 | 1 |
6 | 3 | 3 | 2 | 1 | 1 | 0 |
Teoría de la codificación
El esquema de Hamming y el esquema de Johnson son de gran importancia en la teoría de codificación clásica .
En la teoría de la codificación , la teoría del esquema de asociación se ocupa principalmente de la distancia de un código . El método de programación lineal produce límites superiores para el tamaño de un código con una distancia mínima dada , y límites inferiores para el tamaño de un diseño con una resistencia dada. Los resultados más específicos se obtienen en el caso de que el esquema de asociación subyacente satisfaga determinadas propiedades polinómicas ; esto nos lleva a uno al reino de los polinomios ortogonales . En particular, se derivan algunos límites universales para códigos y diseños en esquemas de asociación de tipo polinomial.
En la teoría de codificación clásica , que trata con códigos en un esquema de Hamming , la transformada de MacWilliams involucra una familia de polinomios ortogonales conocidos como polinomios de Krawtchouk . Estos polinomios dan los valores propios de las matrices de relación de distancia del esquema de Hamming .
Ver también
- Diseño de bloque
- Álgebra de Bose-Mesner
- Diseño combinatorio
Notas
- ^ Bailey 2004 , pág. 387
- ^ Bose y Mesner 1959
- ^ Bose y Nair, 1939
- ^ Bannai e Ito 1984
- ^ Godsil 1993
- ^ Bailey 2004 , pág. 387
- ^ Zieschang 2005b
- ^ Zieschang 2005a
- ^ Dembowski 1968 , pág. 281, nota al pie 1
- ^ Bannai y Ito 1984 , pág. vii
- ^ Calle y calle 1987 , pág. 238
Referencias
- Bailey, Rosemary A. (2004), Esquemas de asociación: experimentos diseñados, álgebra y combinatoria , Cambridge University Press, ISBN 978-0-521-82446-0, MR 2047311. (Los capítulos del borrador preliminar están disponibles en línea ).
- Bannai, Eiichi; Ito, Tatsuro (1984), combinatoria algebraica I: esquemas de asociación , Menlo Park, CA: Benjamin / Cummings, ISBN 0-8053-0490-8, MR 0882540
- Bose, RC ; Mesner, DM (1959), "Sobre álgebras asociativas lineales correspondientes a esquemas de asociación de diseños parcialmente equilibrados" , Annals of Mathematical Statistics , 30 (1): 21–38, doi : 10.1214 / aoms / 1177706356 , JSTOR 2237117 , MR 0102157
- Bose, R. C .; Nair, K. R. (1939), "Diseños de bloques incompletos parcialmente equilibrados", Sankhyā , 4 : 337–372, JSTOR 40383923
- Bose, R. C .; Shimamoto, T. (1952), "Clasificación y análisis de diseños de bloques incompletos parcialmente equilibrados con dos clases asociadas", Revista de la Asociación Estadounidense de Estadística , 47 (258): 151-184, doi : 10.1080 / 01621459.1952.10501161
- Camion, P. (1998), "18. Códigos y esquemas de asociación: propiedades básicas de los esquemas de asociación relevantes para la codificación", en Pless, VS; Huffman, WC; Brualdi, RA (eds.), Manual de teoría de la codificación , 1 , Elsevier, págs. 1441–, ISBN 9780444500885
- Delsarte, P. (1973), "Un enfoque algebraico de los esquemas de asociación de la teoría de la codificación", Informes de investigación de Philips (Suplemento No. 10), OCLC 641852316
- Delsarte, P .; Levenshtein, VI (1998). "Esquemas de asociación y teoría de la codificación". Transacciones IEEE sobre teoría de la información . 44 (6): 2477–2504. doi : 10.1109 / 18.720545 .
- Dembowski, P. (1968), Geometrías finitas , Springer, ISBN 978-3-540-61786-0
- Godsil, CD (1993), Combinatoria algebraica , Nueva York: Chapman y Hall, ISBN 0-412-04131-6, MR 1220704
- MacWilliams, FJ; Sloane, NJA (1977), La teoría de los códigos de corrección de errores , Biblioteca matemática de Holanda Septentrional, 16 , Elsevier, ISBN 978-0-444-85010-2
- Calle, Anne Penfold ; Street, Deborah J. (1987), Combinatoria del diseño experimental , Oxford UP [Clarendon], ISBN 0-19-853256-3
- van Lint, JH; Wilson, RM (1992), Un curso de combinatoria , Cambridge University Press, ISBN 0-521-00601-5
- Zieschang, Paul-Hermann (2005a), " Esquemas de asociación: experimentos diseñados, álgebra y combinatoria por Rosemary A. Bailey, revisión" (PDF) , Boletín de la Sociedad Estadounidense de Matemáticas , 43 (2): 249-253, doi : 10.1090 / S0273-0979-05-01077-3
- Zieschang, Paul-Hermann (2005b), Teoría de los esquemas de asociación , Springer, ISBN 3-540-26136-2
- Zieschang, Paul-Hermann (2006), "La condición de intercambio para los esquemas de asociación", Israel Journal of Mathematics , 151 (3): 357–380, doi : 10.1007 / BF02777367 , MR 2214129 , S2CID 120009352