隣接行列

1：$v_iv_j=v_jv_i$ なので $a_{ij}=a_{ji}$ であり、単純グラフにはループがないので $a_{ii}=0$ である。2：第 $i$ 行で $a_{ij}=1$ となる $j$ は、$v_j$ が $v_i$ に隣接する $j$ そのものなので、行の和は隣接頂点の個数 $\deg v_i$ である。$i$ について足すと、次数の総和は $2\lvert E\rvert$ である（次数(グラフ) の記事の定理「次数の総和と辺数」）。3：$E:=\{v_iv_j\mid i\neq j,\ b_{ij}=1\}$ とおくと、$B$ の対称性から条件は $i,j$ の順序によらず、これは $\{v_1,\dots,v_n\}$ 上のグラフで隣接行列は $B$ である。辺の集合は $B$ から決まるので、このようなグラフは 1 つだけである。$\square$

$k$ についての帰納法による。$k=0$ では長さ $0$ の歩道は 1 頂点の列だけなので成り立つ。長さ $k+1$ の歩道を最後から 2 番目の頂点 $v_l$ で分けると、その個数は $\sum_l(A^k)_{il}a_{lj}=(A^{k+1})_{ij}$ である。詳しい証明は、ループと平行辺を許す場合も含めて 隣接行列と道の数 の記事の定理「隣接行列の累乗の成分は道筋の数」に、有向グラフについて 有向グラフ の記事の命題「隣接行列の冪と有向歩道の個数」にある。$\square$

$P=P_\sigma$ とおくと $(P)_{ki}=1\iff k=\sigma(i)$ なので、
$$ (PAP^{\mathsf T})_{kl}=\sum_{i,j}P_{ki}\,a_{ij}\,P_{lj}=a_{\sigma^{-1}(k)\,\sigma^{-1}(l)},\quad\text{すなわち}\quad (PAP^{\mathsf T})_{\sigma(i)\sigma(j)}=a_{ij} $$
である。$v_i\mapsto w_{\sigma(i)}$ が同型であるとは、すべての $i,j$ で「$v_iv_j\in E(G)\iff w_{\sigma(i)}w_{\sigma(j)}\in E(H)$」、すなわち $a_{ij}=a'_{\sigma(i)\sigma(j)}$ となることであり（グラフ の記事の定義「グラフの同型」）、これは上の式により $A'=PAP^{\mathsf T}$ と同値である。$V(G)$ から $V(H)$ への全単射はどれも $v_i\mapsto w_{\sigma(i)}$ の形に書けるので、$G\cong H$ なら $A'=PAP^{-1}$ となる置換行列 $P$ があり、相似な行列の固有多項式は等しい（固有値 の記事の命題「固有多項式の相似不変性」）。最後の主張は、番号のつけ替えが恒等写像による同型であることによる。$\square$

rem-adjacency-matrix-spectral-theorem の正規直交基底で $x=\sum_ic_iu_i$ と書くと、$x^{\mathsf T}x=\sum_ic_i^2$、$x^{\mathsf T}Mx=\sum_i\mu_ic_i^2$ である。よって $\mu_1x^{\mathsf T}x-x^{\mathsf T}Mx=\sum_i(\mu_1-\mu_i)c_i^2\ge0$ で、等号は $\mu_i<\mu_1$ となる $i$ について $c_i=0$ となること、すなわち $x$ が固有値 $\mu_1$ の固有空間に属することと同値である。左の不等式も同様である。$\square$

1：lem-adjacency-matrix-rayleigh を $x=\mathbf{1}$ に使うと $\lambda_1\ge\mathbf{1}^{\mathsf T}A\mathbf{1}/n=2\lvert E\rvert/n=\overline d$ である。次に、固有値 $\lambda$ の実固有ベクトル $x$ をとり、$\lvert x_i\rvert$ が最大となる $i$ を選ぶ（$x_i\neq0$）。
$$ \lvert\lambda\rvert\lvert x_i\rvert=\Bigl\lvert\sum_ja_{ij}x_j\Bigr\rvert\le\sum_ja_{ij}\lvert x_j\rvert\le\deg v_i\cdot\lvert x_i\rvert\le\Delta\lvert x_i\rvert $$
なので $\lvert\lambda\rvert\le\Delta$、特に $\lambda_1\le\Delta$ である。
2：$\lambda$ の実固有ベクトル $x$ と、各成分の絶対値を並べたベクトル $\lvert x\rvert$ について、$a_{ij}\ge0$ と補題から
$$ \lvert\lambda\rvert\,x^{\mathsf T}x=\lvert x^{\mathsf T}Ax\rvert=\Bigl\lvert\sum_{i,j}a_{ij}x_ix_j\Bigr\rvert\le\sum_{i,j}a_{ij}\lvert x_i\rvert\lvert x_j\rvert=\lvert x\rvert^{\mathsf T}A\lvert x\rvert\le\lambda_1\lvert x\rvert^{\mathsf T}\lvert x\rvert=\lambda_1x^{\mathsf T}x $$
である。
3：$A\mathbf{1}=d\mathbf{1}$ なので $d$ は固有値で、1 から $\lambda_1\le\Delta=d$ なので $\lambda_1=d$ である。固有値 $d$ の固有空間は、連結成分ごとに一定の値をとるベクトル全体であり、その次元は連結成分の個数である。rem-adjacency-matrix-spectral-theorem により重複度も同じである。$\square$

$I$ と $A$ は交換するので、二項定理により $(I+A)^{n-1}=\sum_{k=0}^{n-1}\binom{n-1}{k}A^k$ である。成分はすべて $0$ 以上なので、$(i,j)$ 成分が正であることは、ある $0\le k\le n-1$ で $(A^k)_{ij}>0$、すなわち thm-adjacency-matrix-walks により長さ $n-1$ 以下の歩道が $v_i$ から $v_j$ へあることと同値である。1 ⇒ 2：$v_i$ と $v_j$ を結ぶ道は頂点が相異なるので長さ $n-1$ 以下の歩道である。2 ⇒ 3 は明らかである。3 ⇒ 1：$v_i$ から $v_j$ への歩道があれば道がある（距離(グラフ) の記事の補題「歩道からの道の取り出し」）ので、$G$ は連結である。$\square$

要点：相異なる固有値が $t$ 個なら $A^t$（したがって $A^D$）は $I,A,\dots,A^{t-1}$ の 1 次結合である。距離 $D$ の 2 頂点について $A^D$ の成分は正だが、$A^k$（$k< D$）の成分は $0$ なので、$t\ge D+1$ である。

部集合 $X,Y$ の頂点を順に並べると（番号のつけ替えはスペクトルを変えない）、$X$ の中・$Y$ の中に辺はないので $A=\begin{pmatrix}0&B\\B^{\mathsf T}&0\end{pmatrix}$ の形になる。対角行列 $S:=\begin{pmatrix}I&0\\0&-I\end{pmatrix}$ について $SAS^{-1}=-A$ なので、$A$ と $-A$ は相似で、$\varphi_G(x)=\det(xI-A)=\det(xI+A)=(-1)^n\varphi_G(-x)$ である。よって $\lambda$ と $-\lambda$ は固有多項式の根として同じ重複度をもつ。$\square$

$x$ を $\lambda_1$ の実固有ベクトルとし、$y:=\lvert x\rvert$ とおく。lem-adjacency-matrix-rayleigh と $a_{ij}\ge0$ により
$$ \lambda_1\,y^{\mathsf T}y=\lambda_1\,x^{\mathsf T}x=x^{\mathsf T}Ax\le y^{\mathsf T}Ay\le\lambda_1\,y^{\mathsf T}y $$
なので等号が成り立ち、補題の等号条件から $Ay=\lambda_1y$ である。ある $i$ で $y_i=0$ とすると、$0=\lambda_1y_i=\sum_{j:\,v_j\sim v_i}y_j$ で $y_j\ge0$ なので、$v_i$ の隣接頂点 $v_j$ でも $y_j=0$ である。これを繰り返すと、$G$ は連結なので $y=0$ となり、$x\neq0$ に反する。よって $\lambda_1$ の固有ベクトル $x$ はどれも $0$ の成分をもたず、$\lvert x\rvert$ はすべての成分が正の固有ベクトルである。
固有空間の次元が $2$ 以上なら、第 1 成分が $0$ の $0$ でない固有ベクトルが作れて前段に反する。よって固有空間は 1 次元であり、rem-adjacency-matrix-spectral-theorem により重複度も $1$ である。$\square$

1：二部グラフなら prop-adjacency-matrix-bipartite-symmetric により $-\lambda_1$ は固有値である。逆に $Ax=-\lambda_1x$（$x$ は実ベクトル、$x\neq0$）とし、$y:=\lvert x\rvert$ とおく。$x^{\mathsf T}Ax=-\lambda_1x^{\mathsf T}x$ と $a_{ij}\ge0$、lem-adjacency-matrix-rayleigh から
$$ \lambda_1\,y^{\mathsf T}y=\lambda_1\,x^{\mathsf T}x=-x^{\mathsf T}Ax=-\sum_{i,j}a_{ij}x_ix_j\le\sum_{i,j}a_{ij}\lvert x_i\rvert\lvert x_j\rvert=y^{\mathsf T}Ay\le\lambda_1\,y^{\mathsf T}y $$
であり、等号が成り立つ。右の等号から $Ay=\lambda_1y$ なので、thm-adjacency-matrix-perron により $y$ の成分はすべて正、すなわち $x$ の成分はどれも $0$ でない。中央の等号から $\sum_{i,j}a_{ij}(\lvert x_i\rvert\lvert x_j\rvert+x_ix_j)=0$ で、各項は $0$ 以上なので、辺 $v_iv_j$ ごとに $x_ix_j=-\lvert x_i\rvert\lvert x_j\rvert<0$ である。よって $X:=\{v_i\mid x_i>0\}$、$Y:=\{v_i\mid x_i<0\}$ は頂点集合の分割で、どの辺も $X$ と $Y$ を結ぶので、$G$ は二部グラフである。
2：二部グラフなら prop-adjacency-matrix-bipartite-symmetric により対称である。逆は連結成分の個数についての帰納法で示す。要点：最大固有値 $\theta$ と $-\theta$ をともにもつ連結成分が 1 つあり、1 によりそれは二部グラフである。その成分を除いた残りのスペクトルもまた対称になる。