13 Association Schemes

Consider an $SRG(v,k,\lambda ,\mu )$ $\Gamma$. Let $p_{ij}(x,y)$ denote the number of vertices in $\Gamma$ at distance $i$ from $x$ and at distance $j$ from $y$.

If $d(x,y)=0$, then $p_{00}(x,y)=1$, $p_{11}(x,y)=k$, $p_{22}(x,y)=v-k-1$, and otherwise $p_{ij}(x,y)=0$.

If $d(x,y)=1$, then $p_{01}(x,y)=p_{10}(x,y)=1$, $p_{11}(x,y)=\lambda$, $p_{12}(x,y)=p_{21}(x,y)=k-\lambda -1$, $p_{22}(x,y)=v-2k+\lambda$, and otherwise $p_{ij}(x,y)=0$.

Definition

Define $p_{ij}^k$ as number of vertices $z$ such that $d(x,z)=i$, $d(z,y)=j$ for any fixed $x,y$ such that $d(x,y)=k$, where $i,j,k\in \{0,1,2\}$.

Define SRGs-Algebra $\mathcal{A}$ as $⟨I,A,J-A-I⟩={⟨J,E_1,E_2⟩}_0$.

Define $L_i=(p_{ij}^k{)}_{kj}\in {\mathbb{R}}^{3\times 3}$. Then

$$L_0=\left(\begin{array}{ccc}1& & \\ & 1& \\ & & 1\end{array}\right),L_1=\left(\begin{array}{ccc}& k& \\ 1& \lambda & k-\lambda -1\\ & \mu & k-\mu \end{array}\right),L_2=\left(\begin{array}{ccc}& & v-k-1\\ & k-\lambda -1& v-2k-2+\mu \end{array}\right).$$

Eigenvalues of $L_1$ are $k$, $\frac{\mu -\lambda \pm \sqrt{(\mu -\lambda {)}^2-4\mu +4k}}{2}$. (distinct eigenvalues of $A$) Eigenvalues of $L2$ are $v-k-1$, $-r-1$, $-s-1$. (distinct eigenvalues of $J-I-A$)

Write $P$-matrix/eigenvalue matrix

$$P=\left(\begin{array}{ccc}1& k& v-k-1\\ 1& r& -r-1\\ 1& s& -s-1\end{array}\right)$$

Write $Q$-matrix/dual eigenvalue matrix

$$Q=\left(\begin{array}{ccc}1& f/1& g/1\\ 1& fr/k& gs/k\\ 1& -f(r+1)/(v-k-1)& -g(s+1)/(v-k-1)\end{array}\right).$$

$E(k)=J/v$, and

$$v(E(r){)}_{xy}=\{\begin{array}{ll}f& \text{if }x=y\\ fr/k& \text{if }x\sim y\\ -f(r+1)/(v-k-1)& \text{if }x\nsim y\end{array}$$

and same for $E(s)$.

Definition

Let $X$ be a finite set. An association scheme with $d$ classes is a pair $(X,\mathcal{R})$ such that

• $\mathcal{R}=\{R_0\cdots ,R_d\}$ is a partition of $X\times X$;
• $R_0=\{(x,x):x\in X\}$;
• $R_i=R_i^T$, i.e. $(x,y)\in R_i$ yields $(y,x)\in R_i$;
• there exists number $p_{ij}^k$ (intersection numbers) such that for any pair $(x,y)\in R_k$, the number of $z\in X$ with $(x,z)\in R_i$ and $(z,y)\in R_j$ equals $p_{ij}^k$.

Write $n_j=p_{jj}^0$, $n=\sum n_j=|X|$, where $n_j=|\{y\in X:(x,y)\in R_j\}|$.

Remark. Some (Bannai, Delsurte) call this symmetric association scheme, then more general replace (iii) by

• (iii’) for each $i$, there exists $j$ such that $R_i=R_j^T$
• $p_{ij}^k=p_{ji}^k$

Alternatively, define $A_i$ by

$$(A_i{)}_{xy}=\{\begin{array}{ll}1& \text{if }(x,y)\in R_i\\ 0& \text{otherwise.}\end{array}$$

Note that

• ${\sum }_{i=0}^d{A}_i=J$
• $A_0=I$
• $A_i=A_i^T$
• $A_i{A}_j={\sum }_{k=0}^d{p}_{ij}^k{A}_k=A_j{A}_i$

(i) shows that the $A_i$ are linearly independent; (iii) and (iv) shows that the $A_i$ generate a $(d+1)$-dimensional commutative matrix algebra of symmetric matrices.

Examples.

• SRGs, $d=2$, $A_1=A$, $A_2=J-I-A$
• The Johnson scheme $J(v,d)$, $X=d$-subsets of $\{1,\cdots ,v\}$, $(x,y)\in R_i$ if $|x\cap y|=d-i$.
• Hamming scheme $H(d,1)$, $X=[q{]}^n=\{1,\cdots ,q{\}}^n$, $(x,y)\in R_i$ if $x,y$ differ in precisely $i$ coordinates (Hamming distance)
• The $q$-Johnson scheme $J_q(v,d)$, $X=d$-subspaces of $V(v,q)$, $(x,y)\in R_i$ if $\dim (x\cap y)=d-i$.

Remark. (ii)-(iv) are examples for distance-regular graphs $(x,y)\in R_i$ iff $x,y$ at distance $i$.

• Cyclotomic schemes, let $q$ be a prime power, let $d\mid q-1$. Let $c_1$ be a subgroup of ${\mathbb{F}}_q^{\ast }$ of index $d$, let $c_2,\cdots ,c_d$ be the cosets of $c_1$. $X=$ elements of ${\mathbb{F}}_q$, $(x,y)\in R_i$ if $x-y\in C_i$.
  • problem: not necessarily symmetric. We need $-1\in C_1$, $2d\mid q-1$ if $q$ odd. If $d=2$, then $4\mid q-1$, Paley graphs.
• Schurian association scheme, $G$ group, $U$ subgroup, $X=G/U$. Fix some double cosets $U\backslash G/U$, $(xU,yU)\in R_i$ if $x^{-1}y\in U{g}_{i}U$. For symmetry, $UgU=U{g}^{-1}U$ for all $g\in G$.

Remark. (ii)-(vi) are examples are Schurian.

$PQ=QP=nI$, $\mathcal{A}=⟨A_0,\cdots ,A_d⟩$. Recall

(i) shows that the $A_i$ are linearly independent; (iii) and (iv) shows that the $A_i$ generate a $(d+1)$-dimensional commutative matrix algebra of symmetric matrices.

Link to original

The $A_i$ commute, then we can diagonalize simultaneously. We find a decomposition of ${\mathbb{R}}^n$ into $d+1$ common eigenspaces $V_0,\cdots ,V_d$. Write $f_j=\dim (V_j)$. We have $\mathcal{J}\in \mathcal{A}$, so one eigenspaces is $⟨j⟩$. By convention, $V_0=⟨j⟩$ (so $f_0=1$). Let $E_j$ be the orthogonal projection onto $V_j$, $f_j=\mathrm{rk}{E}_j=\mathrm{tr}{E}_j$.

${\sum }_{j=0}^d{E}_j=I$, $E_0=J/n$. The $E_j$ are a second basis of $\mathcal{A}$. Basis transformation $(A_0,A_1,\cdots ,A_d)=(E_0,E_1,\cdots ,E_d)P$ and $n(E_0,\cdots ,E_d)=(A_1,\cdots ,A_d)Q$. Equivalently, $A_j={\sum }_{i=0}^d{P}_{ij}{E}_i$, $E_j=\frac{1}{n}{\sum }_{i=0}^d{Q}_{ij}{A}_i$. $PQ=QP=nI$.

Note that $A_j{E}_i={\sum }_{\ell =0}^d{P}_{\ell j}{E}_{\ell }{E}_i=P_{ij}{E}_i^2$. So $P_{ij}$ are eigenvalues of $A_j$.

两块不知所云的黑板。。。

Pasted image 20260603152448.png

Pasted image 20260603152437.png

Example

Let $H(d,2)$ be a hypercube. For $a\in \{0,1{\}}^d$, define $V_a(b)=(-1{)}^{⟨a,b⟩}$. In the section on spectral graph theory, we saw that these are eigenvectors of $H(d,2)$. For $a\ne a^{\prime }$, it is not too hard to see that $⟨V_a,V_{a^{\prime }}⟩=0$, and so they span ${\mathbb{R}}^{2^d}:={\mathbb{R}}^n$.

The $V_a$ are the columns of a Hadamard matrix of order $2^d$.

Take $a$ with $\Vert a\Vert =i$. Then

$$\begin{array}{rl}(A_j{V}_a)(b)& =\sum _c{A}_j(b,c)V_a(c)\\ & =\sum _{c:d(b,c)=j}(-1{)}^{⟨a,c⟩}\\ & =(-1{)}^{⟨a,b⟩}\sum _{c:d(b,c)=j}(-1{)}^{⟨a,b+c⟩}\\ & =V_a(b)\sum _{u:\Vert u\Vert =j}(-1{)}^{⟨a,u⟩}\\ & =V_a(b)\sum _{\ell =0}^j(-1{)}^{\ell }(\genfrac{}{}{0ex}{}{i}{\ell }\left)\right(\genfrac{}{}{0ex}{}{d-i}{j-\ell })\end{array}$$

So $A_j={\sum }_{i=0}^d({\sum }_{k=0}(-1{)}^n\left(\genfrac{}{}{0ex}{}{i}{n}\right)\left(\genfrac{}{}{0ex}{}{d-i}{j-n}\right))E_i$. Thus, we know $P$. For $d=4$, we have

$$P=\left(\begin{array}{ccccc}1& 4& 6& 4& 1\\ 1& 2& 0& -2& -1\\ 1& 0& -2& 0& 1\\ 1& -2& 0& 2& -1\\ 1& -4& 6& -4& 1\end{array}\right)$$

Furthermore, $Q=P$, and so we say such scheme is self-dual.

Example

Let $J(v,d)$ be the Johnson Scheme. Then $P_{ij}={\sum }_{n=0}^j(-1{)}^{j-n}(\genfrac{}{}{0ex}{}{d-i}{n}\left)\right(\genfrac{}{}{0ex}{}{d-n}{j-n}\left)\right(\genfrac{}{}{0ex}{}{v-d-i+n}{n})$. For $J(8,3)$, we have

$$P=\left(\begin{array}{cccc}1& 15& 30& 10\\ 1& 7& -2& -6\\ 1& 1& -5& 3\\ 1& -3& 3& -1\end{array}\right)$$

and

$$Q=\left(\begin{array}{cccc}1& 7& 20& 28\\ 1& 49/15& 4/3& -28/5\\ 1& -2/15& -10/3& 14/5\\ 1& -21/5& 6& -14/5\end{array}\right)$$

Note that $PQ=cI$, $8=\dim (V_0)+\dim (V_1)$, and $28=\dim (V_0)+\dim (V_1)+\dim (V_2)$.

Clearly, $a_0=1$, $\sum a_i=|Y|$.

Delsarte LP bound

For $V\ne \varnothing$, $(aQ{)}_j⩾0$ for all $0⩽j⩽d$. If equality holds, then $\chi (Y)$ is orthogonal to $V_j$.

\begin{proof} 忘记拍照了 \end{proof}