Sgt/lecture1

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

สัปดาห์แรกของ Spectral Graph Theory เป็นการเกริ่นนำความรู้พื้นฐานที่จะใช้ในวิชานี้ ซึ่งประกอบไปด้วยการทำความรู้จักกับ eigenvector, eigenvalue และ spectral theory

Eigenvector, Eigenvalue

สำหรับเมทริกซ์จตุรัส $A$ นิยาม eigenvector $\phi$ และ eigenvalue $\lambda$ ดังนี้

${\begin{aligned}A\phi =\lambda \phi \end{aligned}}$

เนื่องจาก

${\begin{aligned}0&=A\phi -\lambda \phi \\&=\left(A-\lambda I\right)\phi \end{aligned}}$

สมการข้างต้น จะมีคำตอบที่ $\phi$ ไม่เป็นศูนย์ ก็ต่อเมื่อ

${\begin{aligned}0=\det \left(A-\lambda I\right)\end{aligned}}$

การแก้สมการ determinant จะทำให้ได้เซ็ตคำตอบของ eigenvalue ทั้งหมดของ $A$ หลังจากนั้นจึงแทนค่า eigenvalue แต่ละตัวเพื่อหา eivenvector ที่สอดคล้องกันต่อไป

Spectral Theory

ให้เมทริกซ์ $M$ ที่มีมิติ $n\times n$ และ $M=M^{\top }$ (เมทริกซ์สมมาตร) แล้ว ได้ว่ามี eigenvalue จำนวน $n$ ตัวดังนี้

$\lambda _{1}\leq \lambda _{2}\leq \ldots \leq \lambda _{n}$

(เรียงค่า eigenvalue จากน้อยไปมาก) และมี eigenvector $\phi _{i}$ ที่สอดคล้องกับ eigenvalue $\lambda _{i}$ โดยที่

$\phi _{i}\perp \phi _{j}$

สำหรับทุก $i\neq j$