ดูต้นฉบับสำหรับ Sgt/lecture3

เนื้อหาในสัปดาห์นี้ จะเป็นความเกี่ยงเนื่องของ eigen value ลำดับที่ 2 กับกราฟ และบทพิสูจน์
== Intuitive of Rayleight Quotient term numerator ==
จาก 

<math>R(M, x) = \frac{x^TMx}{x^Tx}</math> 

สังเกตว่า 

<math>x^TLx = \sum\limits_{(u,v)} (x(u) - x(v))^2</math> 

ถ้าเรามองว่า <math>x(u)</math> คือการเปลี่ยนมิติ ของจุดจากกราฟมายังเส้นตรงแล้ว ราคาที่เพิ่มขึ้นจาก เส้นเชื่อมแต่ละเส้น จะเท่ากับระยะห่างของจุดปลายของเส้นเชื่อมนั้นบนเส้นตรงดังกล่าว

== Terminology ==
สำหรับกราฟ <math>G=(V,E)</math> และเซ็ตของปม <math>S \subseteq V</math> 
เราจะนิยาม <math>\partial(S) = \{ (u,v) \in E, u \in S, v \in V-S \}</math>
เป็นขนาดของคัท และ อัตราการขยายตัวของปริมาตรผ่านทางเส้นเชื่อม

== Isoperimetric Inequality ==
Isoperimetric ratio of vertices set  <math> \theta (S) = \frac{|\partial (S)|}{|S|} </math>

Isoperimetric ratio of graph <math> \theta (G) = min_{S,|S|\leq n/2} \theta(S) </math>

ณ จุดนี้ เราจะพิจารณาขอบล่างของ <math> \theta (G) </math> เทียบกับ <math> \lambda_{2} </math> โดยจะพิจารณาขอบบน ซึ่งก็คือ Cheeger Inequality ใน lecture ครั้งถัดไป

{{กล่องทฤษฎีบท|"For every <math>S \subset V, \theta (S) \geq {\lambda}_{2}(1-s), where s = \frac{|S|}{|V|}  </math>"}}
{{เริ่มบทพิสูจน์}}
จาก Rayleight Quotient เรารู้ว่า
<math>
{\lambda}_{2} = min_{x \neq 0, x\perp {\bold{1}}} \frac{x^TLx}{x^Tx}
</math>

แสดงว่า ถ้าเราหยิบ vector ใด ๆ ซึ่งไม่ใช่ 0 ที่ตั้งฉากกับ vector 1 มา เราสามารถนำมาบอกขอบเขตของ <math>\lambda_{2}</math> ได้เสมอ

พิจารณา characteristic vector <math>x</math> โดย
<math>
\begin{align}
x(u) = 1&,  u \in S \\
x(u) = 0&,  otherwise 
\end{align}
</math>

สังเกตว่า <math> \frac{x^TLx}{x^Tx} = \theta (S) </math> แต่ <math>x</math> ไม่ตั้งฉากกับ vector <math>{\bold{1}}</math> 

พิจารณา <math> x' = x - \frac{|S|}{|V|} {\bold{1}} = x - s{\bold{1}} </math>
สังเกตว่า <math> x' \perp {\bold{1}}, x' \neq 0</math>

จากนั้นเราจะพิจารณาผลของ <math> \frac{{x'}^TLx'}{{x'}^Tx'} </math>

โดย <math> {x'}^TLx' = |\partial{S}|</math>

และ 

<math> 
\begin{align}
{x'}^Tx' & = \sum\limits_{u} (x'(u))^2 \\
& = \sum\limits_{u} (x(u)-s)^2 \\
& = \sum\limits_{u} x(u)^2 - 2x(u)s + s^2 \\
& = |S| - 2s|S| + |V|s^2 \\
& = |S| - 2\frac{ |S|^2}{|V|} + \frac{|S|^2}{|V|} \\
& = |S| - \frac{|S|^2}{|V|} \\ 
& = |S|(1-s) 
\end{align}
</math>

ดังนั้น 

<math>
\begin{align}
\lambda_{2} & \leq \frac{{x'}^TLx'}{{x'}^Tx'} \\
\lambda_{2} (1-s) & \leq \frac{{x'}^TLx'}{|S|} \\
\lambda_{2} (1-s) & \leq \theta{S}
\end{align}
</math>
{{จบบทพิสูจน์}}

== The Adjacency Matrix ==

กำหนดให้ A เป็น adjacency matrix ของกราฟ <math>G = (V,E)</math> โดยถ้าเรานำ vector x ไปคูณ ผลลัพธ์ที่ได้คือ

<math> (Ax)(u) = \sum\limits_{(u,v) \in E} w(u,v)x(v) </math>

พิจารณา regular graph G ที่มี degree d เราสามารถหาความสัมพันธ์ระหว่าง laplacian matrix กับ adjacency matrix ได้โดย

<math> L = D - A = Id - A </math> 

ถ้า <math>\lambda</math> และ <math>\varphi</math> เป็น eigen value และ eigen vector ที่สอดคล้องกันใน L แล้ว

<math> 
\begin{align}
L\varphi &= (Id - A)\varphi = \lambda\varphi \\
A\varphi &= (Id- L)\varphi = (d-\lambda)\varphi \\
\end{align}
</math>

ได้ว่า <math>\mu = (d-\lambda)</math> และ <math>\varphi</math> เป็น eigen value และ eigen vector ที่สอดคล้องกันใน A

สังเกตว่าถ้ากราฟเป็น regular แล้ว eigen vector ของ L กับ A จะเป็นชุดเดียวกัน แต่มี eigen value ต่างกัน

กำหนดให้ <math> \mu_1 \geq \mu_2 \geq ... \geq \mu_n </math> เป็น eigen value ของ A

เมื่อกราฟ G เป็น regular ได้ว่า <math> \mu_1 = d </math>