Sgt/lecture4

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

ในสัปดาห์นี้ เราได้พูดถึง Courant–Fischer Theorem

Courant–Fischer Theorem

ให้ A เป็น symmetric matrix ขนาด n ที่มี eigen value $\mu _{1}\geq \mu _{2}\geq \ldots \geq \mu _{n}$ (สังเกตว่าเรียงสลับด้านกับ $\lambda$ ในเลคเชอร์อื่นๆ)

เราจะได้ว่า

${\begin{aligned}\mu _{k}&=\max \limits _{S\subseteq \mathbb {R} ^{n}\ ;\ dim(S)=k}&&\min _{x\in S\ ;\ x\neq {\bar {0}}}{\frac {x^{T}Ax}{x^{T}x}}\\&=\min \limits _{T\subseteq \mathbb {R} ^{n}\ ;\ dim(T)=n-k+1}&&\max _{x\in S\ ;\ x\neq {\bar {0}}}{\frac {x^{T}Ax}{x^{T}x}}\end{aligned}}$

---

To be proved...

---

Graphic Inequality

เป็นการเปรียบเทียบกราฟโดยให้ sense ของการ "มากกว่า" "น้อยกว่า" เหมือนการเปรียบเทียบจำนวนจริง
ให้ A เป็น matrix ใดๆ เราเขียนแทนว่า A เป็น positive semi-definite ด้วย $A\succeq 0$ โดยนิยามดังนี้

$A\succeq 0$ เมื่อและต่อเมื่อ $\forall \psi \in \mathbb {R} ^{n}\ ;\ \psi ^{T}A\psi \geq 0$

และสำหรับ matrix A,B ใดๆ เราเขียนแทนว่า $A\succeq B$ เมื่อและต่อเมื่อ $A-B\succeq 0$

ความสัมพันธ์นี้มีคุณสมบัติถ่ายทอด คือถ้า $A\succeq B;B\succeq C$ จะได้ว่า $A\succeq C$

ทำนองเดียวกัน สำหรับกราฟ G,H ใดๆ เราแทนว่า $G\succeq H$ เมื่อและต่อเมื่อ $L_{G}\succeq L_{H}$ และสังเกตว่า ถ้า H เป็น subgraph ของ G จะได้ว่า $G\succeq H$

TO BE CONTINUED