Esquema de asociación

La teoría de 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, los diseños combinatorios y la teoría de códigos de corrección de errores . ^{[4] [5]} En álgebra, los esquemas de asociación generalizan los grupos , y la teoría de esquemas de asociación generaliza la teoría de caracteres de las representaciones lineales de grupos . ^{[6] [7] [8]}

Definición

Un esquema de asociación de n clases consiste en un conjunto X junto con una partición S de X × X en n  + 1 relaciones binarias , R ₀ , R ₁ , ..., R _n que satisfacen:

• ${\displaystyle R_{0}=\{(x,x):x\in X\}}$;se llama relación de identidad .
• Definiendo , si R en S , entonces R* en S . ${\displaystyle R^{*}:=\{(x,y):(y,x)\in R\}}$
• Si , el número de tales que y es una constante que depende de , , pero no de la elección particular de y . ${\displaystyle (x,y)\in R_{k}}$ ${\displaystyle z\in X}$ ${\displaystyle (x,z)\in R_{i}}$ ${\displaystyle (z,y)\in R_{j}}$ ${\displaystyle p_{ij}^{k}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle x}$ ${\displaystyle y}$

Un esquema de asociación es conmutativo si para todos , y . La mayoría de los autores suponen esta propiedad. Nótese, sin embargo, que mientras que la noción de un esquema de asociación generaliza la noción de un grupo, la noción de un esquema de asociación conmutativo solo generaliza la noción de un grupo conmutativo . ${\displaystyle p_{ij}^{k}=p_{ji}^{k}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle k}$

Un esquema de asociación simétrica es aquel en el que cada uno es una relación simétrica . Es decir: ${\displaystyle R_{i}}$

• si ( x , y ) ∈ R _i , entonces ( y , x ) ∈ R _i . (O equivalentemente, R * = R .)

Todo esquema de asociación simétrica es conmutativo.

Dos puntos x e y se llaman i  ésimos asociados si . La definición establece que si x e y son i  ésimos asociados, entonces también lo son y y x . Cada par de puntos son i  ésimos asociados para exactamente un . Cada punto es su propio asociado cero, mientras que los puntos distintos nunca son asociados cero. Si x e y son k  ésimos asociados, entonces el número de puntos que son a la vez i  ésimos asociados de y j  ésimos asociados de es una constante . ${\displaystyle (x,y)\in R_{i}}$ ${\displaystyle i}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle p_{ij}^{k}}$

Interpretación de gráficos y matrices de adyacencia

Un esquema de asociación simétrica puede visualizarse como un gráfico completo con aristas etiquetadas. El gráfico tiene vértices, uno para cada punto de , y la arista que une los vértices y está etiquetada si y son  los asociados. Cada arista tiene una etiqueta única, y el número de triángulos con una base fija etiquetada que tiene las otras aristas etiquetadas y es una constante , que depende de, pero no de, la elección de la base. En particular, cada vértice incide exactamente con aristas etiquetadas ; es la valencia de la relación . También hay bucles etiquetados en cada vértice , correspondientes a . ${\displaystyle v}$ ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle i}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle i}$ ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle p_{ij}^{k}}$ ${\displaystyle i,j,k}$ ${\displaystyle p_{ii}^{0}=v_{i}}$ ${\displaystyle i}$ ${\displaystyle v_{i}}$ ${\displaystyle R_{i}}$ ${\displaystyle 0}$ ${\displaystyle x}$ ${\displaystyle R_{0}}$

Las relaciones se describen mediante sus matrices de adyacencia . es la matriz de adyacencia de para y es una matriz v × v con filas y columnas etiquetadas por los puntos de . ${\displaystyle A_{i}}$ ${\displaystyle R_{i}}$ ${\displaystyle i=0,\ldots ,n}$ ${\displaystyle X}$

${\displaystyle \left(A_{i}\right)_{x,y}={\begin{cases}1,&{\mbox{if }}(x,y)\in R_{i},\\0,&{\mbox{otherwise.}}\end{cases}}\qquad (1)}$

La definición de un esquema de asociación simétrica es equivalente a decir que existen v × v (0,1)-matrices que satisfacen ${\displaystyle A_{i}}$

I. es simétrico, ${\displaystyle A_{i}}$

II. (la matriz de todos unos), ${\displaystyle \sum _{i=0}^{n}A_{i}=J}$

III. , ${\displaystyle A_{0}=I}$

IV. . ${\displaystyle A_{i}A_{j}=\sum _{k=0}^{n}p_{ij}^{k}A_{k}=A_{j}A_{i},i,j=0,\ldots ,n}$

La entrada ( x , y )-ésima del lado izquierdo de (IV) es el número de caminos de longitud dos entre x e y con etiquetas i y j en el gráfico. Nótese que las filas y columnas de contienen 's: ${\displaystyle A_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle 1}$

${\displaystyle A_{i}J=JA_{i}=v_{i}J.\qquad (2)}$

Terminología

• Los números se denominan parámetros del esquema y también constantes estructurales . ${\displaystyle p_{ij}^{k}}$

Historia

El término esquema de asociación se debe a (Bose & Shimamoto 1952) pero el concepto ya es inherente en (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 un 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 DG Higman (configuraciones coherentes) y B. Weisfeiler ( grafos regulares de distancia ).

Datos básicos

• ${\displaystyle p_{00}^{0}=1}$, es decir, si entonces y el único tal que es . ${\displaystyle (x,y)\in R_{0}}$ ${\displaystyle x=y}$ ${\displaystyle z}$ ${\displaystyle (x,z)\in R_{0}}$ ${\displaystyle z=x}$
• ${\displaystyle \sum _{i=0}^{k}p_{ii}^{0}=|X|}$; esto se debe a que la partición . ${\displaystyle R_{i}}$ ${\displaystyle X}$

El álgebra de Bose-Mesner

Las matrices de adyacencia de los grafos generan un álgebra conmutativa y asociativa (sobre los números reales o complejos ) tanto para el producto matricial como para el producto puntual . Esta álgebra asociativa y conmutativa se denomina álgebra de Bose-Mesner del esquema de asociación. ${\displaystyle A_{i}}$ ${\displaystyle \left(X,R_{i}\right)}$ ${\displaystyle {\mathcal {A}}}$

Como las matrices en son simétricas y conmutan entre sí, pueden diagonalizarse simultáneamente. Por lo tanto, es semisimple y tiene una base única de idempotentes primitivos . ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle J_{0},\ldots ,J_{n}}$

Existe otra álgebra de matrices que es isomorfa a , y a menudo es más fácil trabajar con ella. ${\displaystyle (n+1)\times (n+1)}$ ${\displaystyle {\mathcal {A}}}$

Ejemplos

• El esquema de Johnson , denotado por J ( v , k ), se define de la siguiente manera. Sea S un conjunto con v elementos. Los puntos del esquema J ( v , k ) son los subconjuntos de S con k elementos. Dos subconjuntos de k elementos A , B de S son i  ésimos asociados cuando su intersección tiene tamaño k  −  i . ${\displaystyle {v \choose k}}$
• El esquema de Hamming , denotado por H ( n , q ), se define de la siguiente manera. Los puntos de H ( n , q ) son las q n ⁿ - tuplas ordenadas sobre un conjunto de tamaño q . Se dice que dos n -tuplas x , y son i-  ésimos asociados si no están de acuerdo exactamente en las coordenadas i . Por ejemplo, si x = (1,0,1,1), y = (1,1,1,1), z = (0,0,1,1), entonces x e y son primeros asociados, x y z son primeros asociados e y y z son segundos asociados en H (4,2).
• Un grafo regular de distancia , G , forma un esquema de asociación al definir dos vértices como i  -ésimos 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 sea donde es la operación de grupo . La clase de la identidad de grupo es R ₀ . Este esquema de asociación es conmutativo si y solo si G es abeliano . ${\displaystyle X=G}$ ${\displaystyle g\in G}$ ${\displaystyle R_{g}=\{(x,y)\mid x=g*y\}}$ ${\displaystyle *}$
• Un esquema específico de asociación de 3 clases: ^[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 .

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 de esquemas 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 en que el esquema de asociación subyacente satisface ciertas propiedades polinómicas ; esto nos lleva 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 polinómico.

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 .

Véase también

• Diseño de bloques
• Álgebra de Bose-Mesner
• Diseño combinatorio

Notas

1. Bailey 2004, pág. 387
2. Bose y Mesner 1959
3. Bose y Nair 1939
4. Bannai y Ito 1984
5. Diossil 1993
6. Bailey 2004, pág. 387
7. Zieschang 2005b
8. Zieschang 2005a
9. Dembowski 1968, pág. 281, nota al pie 1
10. Bannai e Ito 1984, pág. vii
11. 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, Sr.  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, Sr.  0882540
• Bose, RC ; Mesner, DM (1959), "Sobre álgebras asociativas lineales correspondientes a esquemas de asociación de diseños parcialmente balanceados", 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 (3): 337–372, JSTOR  40383923
• Bose, R. C. ; Shimamoto, T. (1952), "Clasificación y análisis de diseños de bloques incompletos parcialmente balanceados con dos clases asociadas", Journal of the American Statistical Association , 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.), Handbook of Coding Theory , vol. 1, Elsevier, págs. 1441–, ISBN 978-0-444-50088-5
• Delsarte, P. (1973), "Un enfoque algebraico de los esquemas de asociación de la teoría de codificación", Philips Research Reports (Suplemento n.° 10), OCLC  641852316
• Delsarte, P.; Levenshtein, VI (1998). "Esquemas de asociación y teoría de codificación". IEEE Transactions on Information Theory . 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, Sr.  1220704
• MacWilliams, FJ; Sloane, NJA (1977), La teoría de los códigos de corrección de errores, North-Holland Mathematical Library, vol. 16, Elsevier, ISBN 978-0-444-85010-2
• Street, 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 Matemática Americana , 43 (2): 249–253, doi : 10.1090/S0273-0979-05-01077-3
• Zieschang, Paul-Hermann (2005b), Teoría de esquemas de asociación , Springer, ISBN 3-540-26136-2
• Zieschang, Paul-Hermann (2006), "La condición de intercambio para esquemas de asociación", Israel Journal of Mathematics , 151 (3): 357–380, doi : 10.1007/BF02777367 , MR  2214129, S2CID  120009352