距離正則グラフ

頂点 $x$ を固定し、$\Gamma_i(x)$ と $\Gamma_{i+1}(x)$ を結ぶ辺の本数を 2 通りに数える。$\Gamma_i(x)$ の各頂点は $\Gamma_{i+1}(x)$ にちょうど $b_i$ 個の隣接頂点をもち、$\Gamma_{i+1}(x)$ の各頂点は $\Gamma_i(x)$ にちょうど $c_{i+1}$ 個の隣接頂点をもつ（隣接する 2 頂点の距離の差は $1$ 以下なので、これで辺はすべて数えている）。よって $|\Gamma_i(x)|\,b_i=|\Gamma_{i+1}(x)|\,c_{i+1}$ である。$|\Gamma_0(x)|=1$ から帰納法により $|\Gamma_i(x)|$ は上の式で与えられ、$x$ によらない。頂点全体は $\Gamma_0(x),\dots,\Gamma_d(x)$ に分かれるので $v=\sum_ik_i$ である。$\square$

$\Gamma$ が直径 $2$ の距離正則グラフなら、$k$ 正則で、隣接する 2 頂点の共通の隣接頂点は $a_1$ 個、距離 $2$ の 2 頂点（隣接しない相異なる 2 頂点）の共通の隣接頂点は $c_2$ 個である。直径 $2$ なので隣接する対も隣接しない対もあり、$\Gamma$ は $\mathrm{srg}(v,k,a_1,c_2)$ である。
逆に $\Gamma$ を連結な $\mathrm{srg}(v,k,\lambda,\mu)$ とする。強正則グラフ の記事の命題「連結でない強正則グラフ」により $\mu\ge1$ なので、隣接しない 2 頂点は共通の隣接頂点をもち、距離は $2$ である。完全グラフでないので直径はちょうど $2$ である。距離 $1$ の $x,y$ について、$y$ の隣接頂点のうち $x$ 自身が $1$ 個、$x$ にも隣接するものが $\lambda$ 個、残り $k-1-\lambda$ 個は距離 $2$ にある。距離 $2$ の $x,y$ について、$y$ の隣接頂点のうち $x$ に隣接するものが $\mu$ 個、残り $k-\mu$ 個は距離 $2$ にある（直径 $2$ なので距離 $3$ はない）。よって $c_1=1$、$a_1=\lambda$、$b_1=k-1-\lambda$、$c_2=\mu$、$a_2=k-\mu$ で、距離正則である。$\square$

$(AA_i)_{xy}=\sum_zA_{xz}(A_i)_{zy}$ は、$x$ の隣接頂点 $z$ で $d(z,y)=i$ となるものの個数である。$j:=d(x,y)$ とおく。$z$ が $x$ に隣接するなら $|d(z,y)-j|\le1$ なので、$j\notin\{i-1,i,i+1\}$ ならこの個数は $0$ である。$j=i+1$ なら、これは $|\Gamma_{j-1}(y)\cap\Gamma(x)|=c_j=c_{i+1}$ である（定義を $x,y$ の役を入れ替えて使う）。$j=i$ なら $a_i$、$j=i-1$ なら $|\Gamma_{j+1}(y)\cap\Gamma(x)|=b_j=b_{i-1}$ である。右辺の $(x,y)$ 成分も、$j=i-1,i,i+1$ に応じて $b_{i-1},a_i,c_{i+1}$、ほかは $0$ なので、両辺は等しい。$\square$

段 1（$\mathbb R[A]$ の次元と固有値）．$A$ の相異なる固有値を $\theta_0,\dots,\theta_t$ とし、固有ベクトルからなる正規直交基底をとる（スペクトル定理）。多項式 $p$ について、$p(A)$ は固有値 $\theta_j$ の固有ベクトルを $p(\theta_j)$ 倍するので、$p(A)=0$ であることと、すべての $j$ で $p(\theta_j)=0$ であることは同値である。これは $p$ が $\prod_{j=0}^t(x-\theta_j)$ で割り切れることと同値なので、$p\mapsto p(A)$ の核は $t+1$ 次の多項式の倍数全体であり、$\dim\mathbb R[A]=t+1$ である。
段 2（1 と 2）．$M:=\langle A_0,\dots,A_d\rangle$（$A_0,\dots,A_d$ の張る空間）とおく。lem-drg-recurrence の後で見たとおり $A_i=p_i(A)\in\mathbb R[A]$ なので $M\subset\mathbb R[A]$ である。逆に、lem-drg-recurrence により $AM\subset M$ で、$I=A_0\in M$ なので、帰納法によりすべての $A^m$ は $M$ に属し、$\mathbb R[A]\subset M$ である。よって $\mathbb R[A]=M$ で、$A_0,\dots,A_d$ は線形独立だから基底であり、$\dim\mathbb R[A]=d+1$ である。段 1 と合わせて $t+1=d+1$、すなわち相異なる固有値はちょうど $d+1$ 個である。
段 3（3）．線形写像 $\Phi\colon M\to M$、$X\mapsto AX$ を考える。lem-drg-recurrence により
$$ \Phi(A_j)=b_{j-1}A_{j-1}+a_jA_j+c_{j+1}A_{j+1}=\sum_{i=0}^dL_{ij}A_i $$
なので（$i=j-1,j,j+1$ の係数がそれぞれ $L_{j-1,j}=b_{j-1}$、$L_{jj}=a_j$、$L_{j+1,j}=c_{j+1}$）、基底 $A_0,\dots,A_d$ に関する $\Phi$ の表現行列は $L$ であり、$L$ と $\Phi$ の固有値は一致する。
$\Phi$ の固有値を求める。$\theta$ が $\Phi$ の固有値で、$p(A)\neq0$、$Ap(A)=\theta p(A)$ とすると、$(x-\theta)p(x)$ はすべての $\theta_j$ で $0$ になる。$p(A)\neq0$ なので $p(\theta_j)\neq0$ となる $j$ があり、そこで $\theta_j-\theta=0$ である。よって $\theta$ は $A$ の固有値である。逆に、$A$ の固有値 $\theta_j$ について $q_j(x):=\prod_{l\neq j}(x-\theta_l)$ とおくと、$q_j(\theta_j)\neq0$ なので $q_j(A)\neq0$ であり、$(x-\theta_j)q_j(x)$ はすべての $\theta_l$ で $0$ なので $Aq_j(A)=\theta_jq_j(A)$ である。よって $\theta_j$ は $\Phi$ の固有値である。以上から $\Phi$ の固有値の集合は $\{\theta_0,\dots,\theta_d\}$ で、これは $d+1$ 個の相異なる数だから、$d+1$ 次の行列 $L$ の固有値はこれらがちょうど 1 つずつである。$\square$

$A$ の固有値を $\theta_0,\dots,\theta_d$、$\theta=\theta_0$ とし、$E$ を固有値 $\theta$ の固有空間 $V_\theta$ への直交射影とする。
段 1（$E$ は $A_i$ の 1 次結合）．$q(x):=\prod_{l\neq0}\frac{x-\theta_l}{\theta-\theta_l}$ とおくと、$q(A)$ は $V_\theta$ の上で恒等写像、ほかの固有空間の上で $0$ なので、固有ベクトルからなる正規直交基底で比べて $q(A)=E$ である。thm-drg-eigenvalues の 1 により、実数 $\alpha_0,\dots,\alpha_d$ があって $E=\sum_i\alpha_iA_i$ と書ける。
段 2（係数は標準列の定数倍）．$AE=\theta E$ である。左辺に lem-drg-recurrence を使って $A_i$ ごとに係数を集めると
$$ AE=\sum_j\alpha_j\bigl(b_{j-1}A_{j-1}+a_jA_j+c_{j+1}A_{j+1}\bigr)=\sum_i\bigl(c_i\alpha_{i-1}+a_i\alpha_i+b_i\alpha_{i+1}\bigr)A_i $$
であり（$\alpha_{-1}=\alpha_{d+1}=0$）、$A_i$ が線形独立なので $c_i\alpha_{i-1}+a_i\alpha_i+b_i\alpha_{i+1}=\theta\alpha_i$、すなわち $L\alpha=\theta\alpha$ である。標準列の説明と同じく $\alpha$ は $\alpha_0$ から決まるので、$\alpha=\alpha_0u$ である。
段 3（跡と $E^2=E$）．直交射影の跡は像の次元なので $\operatorname{tr}E=\dim V_\theta=m(\theta)$ である（スペクトル定理 により重複度は固有空間の次元に等しい）。$A_i$（$i\ge1$）の対角成分は $0$ なので $\operatorname{tr}E=\alpha_0\operatorname{tr}I=v\alpha_0$ であり、$m(\theta)\ge1$ から $\alpha_0>0$ である。次に $E$ は対称で $E^2=E$ なので、1 つの頂点 $x$ について
$$ \alpha_0=E_{xx}=(E^2)_{xx}=\sum_yE_{xy}^2=\sum_{i=0}^d\ \sum_{y\in\Gamma_i(x)}\alpha_i^2=\sum_{i=0}^dk_i\alpha_i^2=\alpha_0^2\sum_{i=0}^dk_iu_i^2 $$
である（$y\in\Gamma_i(x)$ なら $E_{xy}=\alpha_i$）。$\alpha_0>0$ で割って $\alpha_0=1/\sum_ik_iu_i^2$、したがって $m(\theta)=v\alpha_0=v/\sum_ik_iu_i^2$ を得る。$\square$