Sgt/lecture2

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

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

Rayleigh quotient

นิยาม Rayleigh quotient สำหรับ vector x และ symmetric matrix M คือ $R(M,x)={\frac {x^{T}Mx}{x^{T}x}}$ โดยสังเกตว่าถ้า x เป็น eigen vector ของ M ที่สอดคล้องกับ eigen value $\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$ จะเป็น eigen vector ของ $M$ ที่สอดคล้องกับ eigen value ที่มากที่สุด"

---

เราจะพิสูจน์โดยการใช้ Spectral theory (เนื้อหาครั้งที่ 1) ให้ M มี dimension ขนาด n (symmetric) ได้ว่า M มี eigen value $\lambda _{1}\leq \lambda _{2}\leq \ldots \leq \lambda _{n}$ และ eigen vector $\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}\\&=\lambda _{n}\end{aligned}}$

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

---

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

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

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

และนิยาม laplacian matrix ของ G ว่า $L_{G}=D_{G}-A_{G}$ ซึ่งหาก G มีเส้นเชื่อมเพียงหนึ่งเส้น $(v_{i},v_{j})$ เราจะได้

$L_{G}={\begin{pmatrix}&\vdots &&\vdots &\\\cdots &1&\cdots &-1&\cdots \\&\vdots &&\vdots &\\\cdots &-1&\cdots &1&\cdots \\&\vdots &&\vdots &\\\end{pmatrix}}$

สำหรับ vector $x=[x_{1},x_{2},\cdots ,x_{n}]$ ใดๆ เราจะคำนวณค่า $R(L_{G},x)$ ได้ว่า $R(L_{G},x)={\frac {(x_{i}-x_{j})^{2}}{x^{T}x}}$