Sgt/lecture2

บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Rayleigh quotient และคุณสมบัติของ eigenvector, eigenvalue ลำดับที่ 2

Rayleigh quotient

นิยาม Rayleigh quotient สำหรับ vector x และ symmetric matrix M คือ $R(M,x)={\frac {x^{T}Mx}{x^{T}x}}$ โดยสังเกตว่าถ้า x เป็น eigenvector ของ M ที่สอดคล้องกับ eigenvalue $\lambda$ จะได้ว่า $R(M,x)=\lambda$ เนื่องจาก

${\begin{aligned}R(M,x)&={\frac {x^{T}(Mx)}{x^{T}x}}\\&={\frac {x^{T}(\lambda x)}{x^{T}x}}\\&={\frac {\lambda (x^{T}x)}{x^{T}x}}=\lambda \end{aligned}}$

และเราจะพิสูจน์ทฤษฎีบทว่า

"ให้ $M$ เป็น symmetric matrix ถ้า $x$ เป็น non-zero vector ที่ทำให้ $R(M,x)$ มีค่ามากที่สุด แล้ว $x$ จะเป็น eigenvector ของ $M$ ที่สอดคล้องกับ eigenvalue ที่มากที่สุด"

---

เราจะพิสูจน์โดยการใช้ Spectral theory (เนื้อหาครั้งที่ 1) ให้ M มี dimension ขนาด n (symmetric) ได้ว่า M มี eigenvalue $\lambda _{1}\leq \lambda _{2}\leq \ldots \leq \lambda _{n}$ และ eigenvector $\phi _{i}$ ที่สอดคล้องกับ $\lambda _{i}$ เพื่อความสะดวก เราให้ว่า ||x|| = 1 และ ||$\phi _{i}$|| = 1 สำหรับทุก i และเราสามารถเขียน x ในรูป $x=\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)\phi _{i}$ จากนั้นจึงคำนวณหาค่า Rayleigh quotient

${\begin{aligned}R(M,x)&={\frac {x^{T}Mx}{x^{T}x}}\\&=(\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)\phi _{i})^{T}M(\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)\phi _{i})\\&=(\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)\phi _{i})^{T}(\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)\lambda _{i}\phi _{i})\\&=\sum \limits _{i=1}^{n}\sum \limits _{j=1}^{n}(\phi _{i}^{T}\cdot x)(\phi _{j}^{T}\cdot x)(\phi _{i}^{T}\phi _{j})\lambda _{j}\qquad &&;\ i\neq j\Rightarrow (\phi _{i}^{T}\phi _{j})=0\\&=\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)^{2}(\phi _{i}^{T}\phi _{i})\lambda _{i}\qquad &&;\ (\phi _{i}^{T}\phi _{i})=1\\&=\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)^{2}\lambda _{i}&&(*)\\&\leq \lambda _{n}\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)^{2}\\&\leq \lambda _{n}\end{aligned}}$

จะเห็นได้ว่า Rayleigh quotient มีค่ามากที่สุดเป็น eigenvalue ที่ใหญ่ที่สุด และ vector x ที่ทำให้มีค่าดังกล่าวได้แก่ eigenvalue ของ M (พิจารณาที่ $(*)$ )

---

คุณสมบัติของ Eigenvalue กับกราฟ

ให้กราฟ $G$ ขนาด $n$ โหนดและ $A_{G}$ เป็น adjacency matrix ของ $G$ ถ้าสำหรับโหนดที่ $i$ ใดๆ เขียนแทนดีกรีด้วย $\deg(v_{i})$ นิยาม diagonal matrix ($D_{G}$) ดังนี้

$D_{G}={\begin{bmatrix}\deg(v_{1})&0&\cdots &0\\0&\deg(v_{2})&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &\deg(v_{n})\end{bmatrix}}$

และนิยาม Laplacian matrix ($L_{G}$) ว่า

${\begin{aligned}L_{G}=D_{G}-A_{G}\end{aligned}}$

ต่อไปนี้จะสนใจ eigenvalue จาก Laplacian matrix ของกราฟ

Eigenvalue ตัวแรกของกราฟใดๆ

"สำหรับกราฟ $G$ ใดๆ Laplacian matrix ($L_{G}$) จะมี eigenvalue (น้อยไปมาก) ลำดับที่หนึ่งเป็นศูนย์เสมอ"

---

สมมติให้ $G^{\star }$ เป็นกราฟที่มีมีเส้นเชื่อมเพียงหนึ่งเส้น $(v_{i},v_{j})$ เราจะได้

$L_{G^{\star }}={\begin{bmatrix}&\vdots &&\vdots &\\\cdots &1&\cdots &-1&\cdots \\&\vdots &&\vdots &\\\cdots &-1&\cdots &1&\cdots \\&\vdots &&\vdots &\end{bmatrix}}$

สำหรับ vector $x=[x_{1},x_{2},\cdots ,x_{n}]^{T}$ ใดๆ คำนวณค่า $R(L_{G^{\star }},x)$ ได้ดังนี้

$R(L_{G^{\star }},x)={\frac {(x_{i}-x_{j})^{2}}{x^{T}x}}$

ต่อมา พิจรณากราฟ $G$ ใดๆ ที่มีจำนวนเส้นเชื่อม $m$ เส้น โดยเราสามารถเขียน $L_{G}$ ได้ในรูป

$L_{G}=L_{G_{1}}+L_{G_{2}}+\cdots +L_{G_{m}}$

โดยที่ $L_{G_{k}}$ สำหรับ $1\leq k\leq m$ แทน Laplacian matrix ของกราฟ $G_{k}$ ซึ่งเป็นกราฟย่อยจาก $G$ ที่มีเส้นเชื่อมเส้นที่ $k$ เพียงเส้นเดียว ดังนั้น

${\begin{aligned}R(L_{G},x)&=R(L_{G_{1}},x)+R(L_{G_{2}},x)+\cdots +R(L_{G_{m}},x)\\&={\frac {\sum \nolimits _{(i,j)\in E(G)}\left(x_{i}-x_{j}\right)^{2}}{x^{T}x}}\end{aligned}}$

ให้ $x_{i}=1$ สำหรับทุกค่า $i$ จะได้ว่า

$R(L_{G},x)={\frac {\sum \nolimits _{E(G)}\left(1-1\right)^{2}}{x^{T}x}}=0$

จากสมการ $(*)$ ในหัวข้อ Rayleigh quotient จะได้ว่า Rayleigh quotient มีค่าน้อยที่สุดเมื่อ $\lambda _{1}=0$ โดยมี $x$ เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว

ดังนั้น สำหรับ Laplacian matrix $L_{G}$ ของกราฟ G ใดๆ $\lambda _{1}=0$

---

Eigenvalue ของกราฟต่อเนื่อง

"สำหรับกราฟ $G$ ใดๆ Laplacian matrix $L_{G}$ จะมี eigenvalue ลำดับที่สองไม่เท่ากับศูนย์ ก็ต่อเมื่อ G เป็นกราฟต่อเนื่อง"

---

$(\leftarrow )$ สมมติให้ $G$ เป็นกราฟต่อเนื่อง และมี eigenvalue ลำดับที่สองเท่ากับศูนย์ ($\lambda _{2}=0$)

ให้ $\phi _{2}=[a_{1},a_{2},\cdots ,a_{n}]^{T}$ เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว

และทฤษฎีบทก่อนหน้า จะได้ว่ามี $\lambda _{1}=0$ และ $\phi _{1}=[x_{1},x_{2},\cdots ,x_{n}]^{T}$

จาก Spectral Theory เนื่องจาก $\phi _{2}\perp \phi _{1}$ ดังนั้น

${\begin{aligned}0&=\phi _{2}\phi _{1}^{T}\\&=\sum \limits _{i=1}^{n}x_{i}a_{i}\end{aligned}}$

เนื่องจากกราฟต่อเนื่อง ให้ $\phi _{1}=[1,1,\cdots ,1]^{T}$ ทำให้

$0=\sum \limits _{i=1}^{n}a_{i}$

จะเห็นว่า $a_{i}\neq 0$ สำหรับทุก $i$ และมี $a_{i}\neq a_{j}$ สำหรับบาง $i\neq j$ ส่งผลให้ $\sum \nolimits _{(i,j)\in E(G)}(a_{i}-a_{j})^{2}\neq 0$

ซึ่งหมายความว่า $\lambda _{2}\neq 0$ และขัดแย้งกับสมมติฐานตั้งต้นว่า $\lambda _{2}=0$ ดังนั้นถ้ากราฟ G เป็นกราฟต่อเนื่อง แล้ว $\lambda _{2}\neq 0$

$(\rightarrow )$ สมมติให้ $G$ เป็นกราฟไม่ต่อเนื่อง และมี eigenvalue ลำดับที่สองไม่เท่ากับศูนย์ ($\lambda _{2}\neq 0$)

ให้ $\phi _{2}=[a_{1},a_{2},\cdots ,a_{n}]^{T}$ เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว

และทฤษฎีบทก่อนหน้า จะได้ว่ามี $\lambda _{1}=0$ และ $\phi _{1}=[x_{1},x_{2},\cdots ,x_{n}]^{T}$

จาก Spectral Theory เนื่องจาก $\phi _{2}\perp \phi _{1}$ ดังนั้น

${\begin{aligned}0&=\phi _{2}\phi _{1}^{T}\\&=\sum \limits _{i=1}^{n}x_{i}a_{i}\end{aligned}}$

เนื่องจากกราฟไม่ต่อเนื่อง ให้ $\phi _{1}=[1,\cdots ,1,0,\cdots ,0]^{T}$ ทำให้

$0=\sum \limits _{i=1}^{k}a_{i}$

เมื่อให้โหนดที่ $1$ ถึง $k$ เป็นส่วนเดียวกัน และตัดขาดจากโหนดที่ $k+1$ ถึง $n$

ให้ $\phi _{2}=[0,\cdots ,0,1,\cdots ,1]$ และได้ว่า

$L_{G}\phi _{2}={\begin{bmatrix}0\\\vdots \\0\\\deg(k+1)+(-1)\cdot \deg(k+1)\\\vdots \\\deg(n)+(-1)\cdot \deg(n)\end{bmatrix}}=0\cdot \phi _{2}$

ซึ่งหมายความว่า $\lambda _{2}=0$ และขัดแย้งกับสมมติฐานตั้งต้นว่า $\lambda _{2}\neq 0$ ดังนั้นถ้ากราฟ G เป็นกราฟไม่ต่อเนื่อง แล้ว $\lambda _{2}=0$

---

Eigenvalue ของกราฟที่มี $n$ ส่วน

ให้กราฟที่มีจำนวน $n$ component ค่า eigenvalue ของ Laplacian matrix ลำดับที่หนึ่งจนถึงลำดับที่ $n$ จะมีค่าเป็น 0

---

ให้กราฟมี $n$ ส่วน ให้ eigenvalue จำนวน $n$ ตัวแรกมีค่าเป็น $0$ และมี eigenvector ที่สอดคล้องกันคือ

$\phi _{i}={\begin{cases}1&{\text{if node is in component }}i{\text{th}}\\0&{\text{otherwise}}\end{cases}}$

จะเห็นว่า $0\phi _{i}=L\phi _{i}$

---

Eigenvalue ของกราฟบริบูรณ์

ให้กราฟริบูรณ์ (complete graph) จำนวน $n$ โหนด ($K_{n}$) ค่า eigenvalue ของ Laplacian matrix ลำดับที่สองจนถึงลำดับสุดท้าย จะมีค่าเป็น $n$

---

พิสูจน์โดยให้

$L_{K_{n}}={\begin{bmatrix}n-1&-1&\cdots &-1\\-1&n-1&\cdots &-1\\\vdots &\vdots &\ddots &\vdots \\-1&-1&\cdots &n-1\end{bmatrix}}$

เลือก $\lambda _{i}=n$ ที่ $i\geq 2$ และเลือก $\phi _{i}$ ที่สอดคล้องกันดังนี้

$\phi _{i}={\begin{bmatrix}-1\\0\\\vdots \\0\\1\\0\\\vdots \\0\end{bmatrix}}={\begin{cases}-1&{\text{if }}1{\text{st row}}\\1&{\text{if }}n{\text{th row}}\\0&{\text{otherwise}}\end{cases}}$

จะเห็นว่า

$L_{K_{n}}\phi _{i}={\begin{bmatrix}(n-1)(-1)+(-1)(1)\\(-1)(-1)+(-1)(1)\\\vdots \\(-1)(-1)+(-1)(1)\\(-1)(-1)+(n-1)(1)\\(-1)(-1)+(-1)(1)\\\vdots \\(-1)(-1)+(-1)(1)\end{bmatrix}}={\begin{bmatrix}-n\\0\\\vdots \\0\\n\\0\\\vdots \\0\end{bmatrix}}=n\phi _{i}=\lambda _{i}\phi _{i}$

ดังนั้น eigenvalue ลำดับที่สองเป็นต้นไปของกราฟบริบูรณ์จำนวน $n$ โหนดมีค่าเป็น $n$

หมายเหตุ eigenvector ที่นำมาประกอบการพิสูจน์ ไม่จำเป็นต้องตั้งฉากกัน เพียงแค่แสดงให้เห็นว่ามี eigenvector ที่สอดคล้องกับ eigenvalue ได้ก็พอ

---