強正則グラフ

$(A^2)_{xy}=\sum_zA_{xz}A_{zy}$ は、$x=y$ なら $x$ の次数、$x\neq y$ なら $x,y$ の共通の隣接頂点の個数である（隣接行列 の記事の定理「隣接行列の冪と歩道の数」）。
1 ⇒ 2．1 のもとで、$A^2$ の対角成分は $k$、隣接する対の成分は $\lambda$、隣接しない対の成分は $\mu$ なので、$A^2=kI+\lambda A+\mu(J-I-A)$ であり、右辺を整理すると 2 の形になる。
2 ⇒ 1．2 の両辺の成分を比べる。対角成分から各頂点の次数は $k$ である。隣接する $x\neq y$ では $A_{xy}=1$ なので共通の隣接頂点は $(\lambda-\mu)+\mu=\lambda$ 個、隣接しない $x\neq y$ では $\mu$ 個である。これらは個数なので整数であり、1 が成り立つ。
2 ⇒ 3．2 ⇒ 1 により $\Gamma$ は $k$ 正則なので $A\mathbf 1=k\mathbf 1$ であり、$A$ は対称なので $\mathbf 1^\perp$ を $A$ 自身に写す（$x\perp\mathbf 1$ なら $\mathbf 1^{\mathsf T}Ax=(A\mathbf 1)^{\mathsf T}x=0$）。$A$ の $\mathbf 1^\perp$ への制限も対称なので、$\mathbf 1^\perp$ は $A$ の固有ベクトルからなる基底をもつ（スペクトル定理）。$\theta$ を制限された固有値、$u\perp\mathbf 1$ を固有ベクトルとすると $Ju=0$ なので、2 の両辺を $u$ に作用させて
$$ \theta^2=(\lambda-\mu)\theta+(k-\mu) $$
を得る。判別式は $\Delta:=(\lambda-\mu)^2+4(k-\mu)$ である。$\mu\le k$ なので $\Delta\ge0$ であり、$\Delta=0$ なら $\lambda=\mu=k$ となって $\lambda\le k-1$ に反するから、$\Delta>0$ である。よって制限された固有値は 2 つの相異なる実数 $r>s$ のどちらかである。もし一方、例えば $r$ だけが現れるなら、$A$ は $\mathbf 1^\perp$ の上で $r$ 倍、$\mathbf 1$ の上で $k$ 倍なので $A=rI+\frac{k-r}vJ$ となり、非対角成分がすべて等しいから $\Gamma$ は完全グラフか辺のないグラフになって仮定に反する。$s$ だけの場合も同じである。よって制限された固有値はちょうど 2 つである。
3 ⇒ 2．$\Gamma$ を $c$ 正則とし、制限された固有値を $r,s$ とする。$A\mathbf 1=c\mathbf 1$ なので、上と同じく $\mathbf 1^\perp$ は $A$ で保たれ、固有ベクトルからなる基底をもつ。その固有値は制限された固有値なので $r$ か $s$ であり、$(A-rI)(A-sI)$ は $\mathbf 1^\perp$ の上で $0$ である。また $(A-rI)(A-sI)\mathbf 1=(c-r)(c-s)\mathbf 1$ である。$J$ も $\mathbf 1^\perp$ の上で $0$、$J\mathbf 1=v\mathbf 1$ なので、$\mathbb R^v=\langle\mathbf 1\rangle\oplus\mathbf 1^\perp$ の両方の上で比べて $(A-rI)(A-sI)=\frac{(c-r)(c-s)}vJ$ である。展開すると $A^2=(r+s)A-rsI+\frac{(c-r)(c-s)}vJ$ であり、2 の形に書ける。$\square$

$\Gamma$ は $k$ 正則かつ連結なので、固有値 $k$ の固有空間は $\langle\mathbf 1\rangle$ であり、$k$ の重複度は $1$ である。$\mathbf 1^\perp$ は固有ベクトルからなる基底をもち、その固有値は $k$ と異なる（$k$ の固有ベクトルは $\mathbf 1$ の定数倍に限るから）。よって制限された固有値は $k$ 以外の固有値全体と一致し、相異なる固有値の個数は制限された固有値の個数に $1$ を足したものである。連結で完全グラフでないので辺もある。thm-srg-matrix の 1 ⇔ 3 から主張がしたがう。$\square$

固有値の全体．$\Gamma$ は $k$ 正則なので $A\mathbf 1=k\mathbf 1$ である。$\mathbf 1^\perp$ は $A$ の固有ベクトルからなる基底をもち（prf-srg-matrix の 2 ⇒ 3 と同じ理由）、その固有値は thm-srg-matrix により $r$ か $s$ で、どちらも現れる。$\mathbb R^v=\langle\mathbf 1\rangle\oplus\mathbf 1^\perp$ なので、$A$ の固有値は重複度をこめて $k,\ r^{(f)},\ s^{(g)}$ であり（右肩は個数）、$f,g\ge1$ は正の整数である。
1．$r,s$ は prf-srg-matrix の 2 次方程式 $\theta^2-(\lambda-\mu)\theta-(k-\mu)=0$ の 2 根なので、根と係数の関係から $r+s=\lambda-\mu$、$rs=-(k-\mu)=\mu-k$ である。
2．固有値の個数から $f+g=v-1$ である。$A$ の対角成分は $0$ なので、固有値の和（トレースと固有値）について
$$ 0=\operatorname{tr}A=k+fr+gs=k+\frac{(r+s)(f+g)}2+\frac{(r-s)(f-g)}2 $$
である。$f+g=v-1$ を代入して $f-g=-\dfrac{(r+s)(v-1)+2k}{r-s}$ を得る。$f=\frac12\bigl((f+g)+(f-g)\bigr)$、$g=\frac12\bigl((f+g)-(f-g)\bigr)$ から 2 の式を得る。
3．$r-s=\sqrt\Delta$、$\Delta=(\lambda-\mu)^2+4(k-\mu)$ は正の整数である。$\Delta$ が平方数なら、$r,s=\frac{(\lambda-\mu)\pm\sqrt\Delta}2$ は有理数で、整数係数の最高次係数 $1$ の多項式 $\theta^2-(\lambda-\mu)\theta-(k-\mu)$ の根なので整数である。よって $r$ か $s$ が整数でないなら $\Delta$ は平方数でなく、$\sqrt\Delta$ は無理数である。2 の計算から
$$ (f-g)\sqrt\Delta=-\bigl((\lambda-\mu)(v-1)+2k\bigr) $$
で、右辺は整数、左辺は $f-g\neq0$ なら無理数なので、$f=g$ かつ $(\mu-\lambda)(v-1)=2k$ である。$\Gamma$ は辺をもち完全グラフでないので $0< k< v-1$、すなわち $0< 2k< 2(v-1)$ であり、整数 $\mu-\lambda$ は $0<\mu-\lambda<2$ をみたすから $\mu-\lambda=1$、$v-1=2k$ である。これをパラメータの基本関係 $k(k-\lambda-1)=\mu(v-k-1)=\mu k$ に代入すると $k-\lambda-1=\mu=\lambda+1$、すなわち $k=2\lambda+2=2\mu$ である。$t:=\mu$ とおくと $k=2t$、$\lambda=t-1$、$v=2k+1=4t+1$ で、$k\ge1$ から $t\ge1$ である。$\square$

存在したとして隣接行列を $A$ とする。thm-srg-matrix の 2 により $A^2=-4A+5I+4J$ である。$E:=\frac1{84}(A-I)(A-9I)$ は、$\mathbf 1$ と固有値 $1$ の固有ベクトルを $0$ に、固有値 $-5$ の固有ベクトルを $\frac{(-6)(-14)}{84}=1$ 倍に写すので、固有値 $-5$ の固有空間 $V$ への直交射影である。$A^2$ の式を代入すると $E=\frac1{84}(14I-14A+4J)$ で、$E$ の成分は対角が $\frac3{14}$、隣接する対が $-\frac5{42}$、隣接しない対が $\frac1{21}$ である。
成分ごとに 2 乗した行列を $F$（$F_{xy}=E_{xy}^2$）とすると、成分は $\frac{81}{1764}$、$\frac{25}{1764}$、$\frac4{1764}$ なので $F=\frac1{1764}(77I+21A+4J)$ である。$Au=-5u$、$u\perp\mathbf 1$、$u\neq0$ なら $Fu=\frac{77-105}{1764}u=-\frac1{63}u$ で、$F$ は負の固有値をもつ。
一方 $F$ は半正定値である。

1：有限体 の記事の定理「有限体の乗法群の構造」により $\mathbb F_q^\times$ は位数 $q-1$ の巡回群なので、生成元 $\gamma$ をとる。$\gamma^j$ が平方元であることと $j$ が偶数であることは同値である（$\gamma^j=(\gamma^i)^2$ なら $j\equiv2i\pmod{q-1}$ で、$q-1$ は偶数なので $j$ は偶数）。よって $\chi(\gamma^j)=(-1)^j$ であり、$\chi(\gamma^i\gamma^j)=(-1)^{i+j}=\chi(\gamma^i)\chi(\gamma^j)$ である。$0$ を含む場合は両辺が $0$ である。$j=0,\dots,q-2$ のうち偶数と奇数は $\frac{q-1}2$ 個ずつなので、平方元と非平方元も $\frac{q-1}2$ 個ずつである。
2：$-1$ は位数 $2$ の元なので $-1=\gamma^{(q-1)/2}$ であり、$\chi(-1)=(-1)^{(q-1)/2}$ である。これが $1$ であることは $\frac{q-1}2$ が偶数、すなわち $q\equiv1\pmod4$ であることと同値である。
3：$z=0$ と $z=a$ の項は $0$ である。$z\neq0$ では、1 により $\chi(z)\chi(z-a)=\chi\bigl(z^2(1-az^{-1})\bigr)=\chi(z)^2\,\chi(1-az^{-1})=\chi(1-az^{-1})$ である。$z$ が $\mathbb F_q^\times$ を動くと、$w=1-az^{-1}$ は $\mathbb F_q\setminus\{1\}$ をちょうど 1 回ずつ動く（$z=a(1-w)^{-1}$ と戻せる）。よって和は $\sum_{w\neq1}\chi(w)=0-\chi(1)=-1$ である。$\square$

lem-srg-quadratic-character の 2 により $\chi(-1)=1$ なので $\chi(y-x)=\chi(x-y)$ であり、隣接関係は対称である。頂点 $x$ に隣接する頂点 $z$ は $z-x$ が平方元となるもので、1 によりちょうど $\frac{q-1}2=2t$ 個ある。平方元も非平方元もあるので、完全グラフでも辺のないグラフでもない。
相異なる $x,y$ の共通の隣接頂点の個数を数える。$z\notin\{x,y\}$ について、$\frac14\bigl(1+\chi(z-x)\bigr)\bigl(1+\chi(z-y)\bigr)$ は、$z-x$ と $z-y$ がともに平方元なら $1$、そうでなければ $0$ である。よって
$$ |\Gamma(x)\cap\Gamma(y)|=\frac14\sum_{z\neq x,y}\Bigl(1+\chi(z-x)+\chi(z-y)+\chi(z-x)\chi(z-y)\Bigr) $$
である。各項を計算する。$\sum_{z\neq x,y}1=q-2$ である。1 により $\sum_{z}\chi(z-x)=0$ なので、$\sum_{z\neq x,y}\chi(z-x)=-\chi(0)-\chi(y-x)=-\chi(x-y)$、同様に $\sum_{z\neq x,y}\chi(z-y)=-\chi(x-y)$ である。最後の和は $z=x,y$ の項が $0$ なので、$w=z-x$ とおいて 3 を $a=y-x$ で使うと $-1$ である。合わせて
$$ |\Gamma(x)\cap\Gamma(y)|=\frac{q-3-2\chi(x-y)}4 $$
である。$x,y$ が隣接するなら $\chi(x-y)=1$ で $\frac{q-5}4=t-1$、隣接しないなら $\chi(x-y)=-1$ で $\frac{q-1}4=t$ である。
固有値は、thm-srg-spectrum の 1 により $r+s=-1$、$rs=t-2t=-t$ から $r,s=\frac{-1\pm\sqrt{1+4t}}2=\frac{-1\pm\sqrt q}2$ であり、2 により $f-g=-\frac{(-1)\cdot4t+4t}{\sqrt q}=0$、$f+g=4t$ から $f=g=2t$ である。$\square$

基本関係 $k(k-1)=v-k-1$ から $v=k^2+1$ である。辺があり $\mu=1$ なので $k\ge2$ である（$k=1$ なら $K_2$ の非交和で $\mu=0$）。thm-srg-spectrum の 1 から $r+s=-1$、$rs=1-k$ である。
$r,s$ が整数でない場合．3 により $(v,k,0,1)=(4t+1,2t,t-1,t)$ で、$t-1=0$ から $t=1$、$(v,k)=(5,2)$ である。
$r,s$ が整数の場合．$r>s$、$r+s=-1$ なので $r\ge0$ で $s=-r-1$、$k=1-rs=r^2+r+1$ である。2 の計算から $(f-g)(r-s)=-\bigl((r+s)(v-1)+2k\bigr)=k^2-2k$、すなわち
$$ (2r+1)(f-g)=k(k-2) $$
である。$m:=2r+1$ とおくと $4k=m^2+3$、$4(k-2)=m^2-5$ なので $16k(k-2)=(m^2+3)(m^2-5)$ であり、$m$ は $16k(k-2)$ を割り切るから、$(m^2+3)(m^2-5)\equiv3\cdot(-5)=-15\pmod m$ により $m$ は $15$ を割り切る。よって $m\in\{1,3,5,15\}$、$r\in\{0,1,2,7\}$ である。$r=0$ なら $k=1$ で $k\ge2$ に反する。$r=1,2,7$ は $k=3,7,57$、$v=k^2+1=10,50,3250$ を与える。$\square$

補グラフの隣接行列は $\bar A=J-I-A$ である。$AJ=JA=kJ$、$J^2=vJ$ と thm-srg-matrix の 2 の式を使って展開し、最後に $A=J-I-\bar A$ を代入すると
$$ \bar A^2=(\mu-\lambda-2)\bar A+(k-\lambda-1)I+(v-2k+\lambda)J $$
となる。

1：連結でなければ、異なる連結成分の 2 頂点は隣接せず共通の隣接頂点ももたないので $\mu=0$ である。逆に $\mu=0$ とすると、$x\sim y\sim z$、$x\neq z$ なら $y$ は $x,z$ の共通の隣接頂点なので $x\sim z$ である。よって「一致するか隣接する」は同値関係で、各連結成分は完全グラフであり、$k$ 正則なので $K_{k+1}$ である。完全グラフでないので成分は 2 つ以上あり、連結でない。
2：補グラフが連結なので、1 を補グラフ（prop-srg-complement）に使うと $\bar\mu=v-2k+\lambda\neq0$ である。一方 $\mu=k$ なら、基本関係から $k(k-\lambda-1)=k(v-k-1)$、$k>0$ なので $\lambda=2k-v$、すなわち $\bar\mu=0$ となる。よって $\mu\neq k$、すなわち $\mu< k$ で、$rs=\mu-k<0$ から $r>0>s$ である。$\Gamma$ は連結なので固有値 $k$ の重複度は $1$ で（隣接行列 の記事の定理「最大固有値と次数」）、$r\neq k$、$|r|\le k$ から $r< k$ である。最後に $(r+1)(s+1)=rs+(r+s)+1=\lambda-k+1$ である。$\lambda=k-1$ なら、1 の証明と同様に隣接する頂点の隣接頂点どうしが隣接して各連結成分が完全グラフになり、連結性と完全グラフでないことに反する。よって $\lambda< k-1$、$(r+1)(s+1)<0$ で、$r+1>0$ から $s<-1$ である。$\square$