ผลต่างระหว่างรุ่นของ "Sgt/lecture2"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 19 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน)
แถว 1: แถว 1:
 +
<noinclude>{{Sgt/เนื้อหา}}</noinclude>
 
{{หัวคำบรรยาย|Spectral graph theory}}
 
{{หัวคำบรรยาย|Spectral graph theory}}
  
สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Rayleigh quotient และคุณสมบัติของ eigen vector, eigen value ลำดับที่ 2
+
สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Rayleigh quotient และคุณสมบัติของ eigenvector, eigenvalue ลำดับที่ 2
  
 
==Rayleigh quotient==
 
==Rayleigh quotient==
 
นิยาม [http://en.wikipedia.org/wiki/Rayleigh_quotient Rayleigh quotient] สำหรับ vector ''x'' และ symmetric matrix ''M'' คือ <math>R(M, x) = \frac{x^TMx}{x^Tx}</math>
 
นิยาม [http://en.wikipedia.org/wiki/Rayleigh_quotient Rayleigh quotient] สำหรับ vector ''x'' และ symmetric matrix ''M'' คือ <math>R(M, x) = \frac{x^TMx}{x^Tx}</math>
โดยสังเกตว่าถ้า ''x'' เป็น eigen vector ของ ''M'' ที่สอดคล้องกับ eigen value <math>\lambda</math> จะได้ว่า
+
โดยสังเกตว่าถ้า ''x'' เป็น eigenvector ของ ''M'' ที่สอดคล้องกับ eigenvalue <math>\lambda</math> จะได้ว่า
 
<math>R(M, x) = \lambda</math> เนื่องจาก  
 
<math>R(M, x) = \lambda</math> เนื่องจาก  
  
แถว 17: แถว 18:
  
 
และเราจะพิสูจน์ทฤษฎีบทว่า
 
และเราจะพิสูจน์ทฤษฎีบทว่า
{{กล่องทฤษฎีบท|"ให้ <math>M</math> เป็น symmetric matrix ถ้า <math>x</math> เป็น non-zero vector ที่ทำให้ <math>R(M,x)</math> มีค่ามากที่สุด แล้ว <math>x</math> จะเป็น eigen vector ของ <math>M</math> ที่สอดคล้องกับ eigen value ที่มากที่สุด"}}
+
{{กล่องทฤษฎีบท|"ให้ <math>M</math> เป็น symmetric matrix ถ้า <math>x</math> เป็น non-zero vector ที่ทำให้ <math>R(M,x)</math> มีค่ามากที่สุด แล้ว <math>x</math> จะเป็น eigenvector ของ <math>M</math> ที่สอดคล้องกับ eigenvalue ที่มากที่สุด"}}
 
{{เริ่มบทพิสูจน์}}
 
{{เริ่มบทพิสูจน์}}
 
เราจะพิสูจน์โดยการใช้ [http://en.wikipedia.org/wiki/Spectral_theory Spectral theory] ([[sgt/lecture1|เนื้อหาครั้งที่ 1]])
 
เราจะพิสูจน์โดยการใช้ [http://en.wikipedia.org/wiki/Spectral_theory Spectral theory] ([[sgt/lecture1|เนื้อหาครั้งที่ 1]])
ให้ ''M'' มี dimension ขนาด ''n'' (symmetric) ได้ว่า ''M'' มี eigen value
+
ให้ ''M'' มี dimension ขนาด ''n'' (symmetric) ได้ว่า ''M'' มี eigenvalue
<math>0 \leq \lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n</math>
+
<math>\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n</math>
และ eigen vector <math>\phi_i</math> ที่สอดคล้องกับ <math>\lambda_i</math>
+
และ eigenvector <math>\phi_i</math> ที่สอดคล้องกับ <math>\lambda_i</math>
 
เพื่อความสะดวก เราให้ว่า ||''x''|| = 1 และ ||<math>\phi_i</math>|| = 1 สำหรับทุก ''i''
 
เพื่อความสะดวก เราให้ว่า ||''x''|| = 1 และ ||<math>\phi_i</math>|| = 1 สำหรับทุก ''i''
 
และเราสามารถเขียน ''x'' ในรูป <math>x = \sum\limits_{i=1}^n (\phi_i^T \cdot x)\phi_i</math>
 
และเราสามารถเขียน ''x'' ในรูป <math>x = \sum\limits_{i=1}^n (\phi_i^T \cdot x)\phi_i</math>
แถว 35: แถว 36:
 
&= \sum\limits_{i=1}^n (\phi_i^T \cdot x)^2\lambda_i &&(*)\\
 
&= \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\sum\limits_{i=1}^n (\phi_i^T \cdot x)^2 \\
&= \lambda_n
+
&\leq \lambda_n
 
\end{align}
 
\end{align}
 
</math>
 
</math>
จะเห็นได้ว่า Rayleigh quotient มีค่ามากที่สุดเป็น eigen value ที่ใหญ่ที่สุด และ vector ''x'' ที่ทำให้มีค่าดังกล่าวได้แก่ eigen value ของ ''M'' (พิจารณาที่ <math>(*)</math> ){{จบบทพิสูจน์}}
+
จะเห็นได้ว่า Rayleigh quotient มีค่ามากที่สุดเป็น eigenvalue ที่ใหญ่ที่สุด และ vector ''x'' ที่ทำให้มีค่าดังกล่าวได้แก่ eigenvalue ของ ''M'' (พิจารณาที่ <math>(*)</math> ){{จบบทพิสูจน์}}
  
==คุณสมบัติของ eigen value กับกราฟ==
+
== คุณสมบัติของ Eigenvalue กับกราฟ ==
ให้กราฟ ''G'' ขนาด ''n'' nodes และ <math>A_G</math> เป็น adjacency matrix ของ G ถ้าสำหรับ node ที่ i ใดๆ เราแทนดีกรีด้วย <math>deg(v_i)</math> เราจะนิยาม diagonal matrix <math>D_G</math> ดังนี้
+
 
:<math>D_G =
+
ให้กราฟ <math>G</math> ขนาด <math>n</math> โหนดและ <math>A_G</math> เป็น adjacency matrix ของ <math>G</math> ถ้าสำหรับโหนดที่ <math>i</math> ใดๆ เขียนแทนดีกรีด้วย <math>\deg(v_i)</math> นิยาม diagonal matrix (<math>D_G</math>) ดังนี้
\begin{pmatrix}
+
 
   deg(v_1) & 0 & \cdots & 0 \\
+
:<math>
  0 & deg(v_2) & \cdots & 0 \\
+
D_G = \begin{bmatrix}
  \vdots  & \vdots  & \ddots & \vdots  \\
+
   \deg(v_1) &     0     & \cdots &     0     \\
  0 & 0 & \cdots & deg(v_n)
+
      0     & \deg(v_2) & \cdots &     0     \\
\end{pmatrix}</math>
+
    \vdots  &   \vdots  & \ddots &   \vdots  \\
และนิยาม laplacian matrix ของ ''G'' ว่า <math>L_G = D_G - A_G</math> ซึ่งหาก ''G'' มีเส้นเชื่อมเพียงหนึ่งเส้น <math>(v_i,v_j)</math> เราจะได้
+
      0     &     0     & \cdots & \deg(v_n)
:<math>L_G =
+
\end{bmatrix}
\begin{pmatrix}
+
</math>
  & \vdots & & \vdots &   \\
+
 
   \cdots & 1 & \cdots & -1 & \cdots   \\
+
และนิยาม Laplacian matrix (<math>L_G</math>) ว่า
  & \vdots & & \vdots &   \\
+
 
   \cdots & -1 & \cdots & 1 & \cdots \\
+
:<math>
  & \vdots & & \vdots &   \\
+
\begin{align}
\end{pmatrix}</math>
+
L_G = D_G - A_G
สำหรับ vector <math>x = [x_1,x_2,\cdots,x_n]</math> ใดๆที่มีขนาด 1 เราจะคำนวณค่า <math>R(L_G,x)</math> ได้ว่า
+
\end{align}
<math>R(L_G,x) = \frac{(x_i-x_j)^2}{x^Tx}</math>
+
</math>
ดังนั้น ถ้าเราเขียน <math>L_G</math> ให้อยู่ในรูป <math>L_G = L_1 + L_2 + \cdots + L_m</math> เมื่อ ''m'' เป็นจำนวนเส้นเชื่อมของ ''G'' และแต่ละ
+
 
<math>L_k</math> แทน laplacian matrix ของกราฟ <math>G_k</math> ที่มีเส้นเชื่อมเพียงเส้นเดียว คือเส้นที่ ''k'' ของ ''G''
+
ต่อไปนี้จะสนใจ eigenvalue จาก Laplacian matrix ของกราฟ
จะเห็นได้ว่า
+
 
<math>
+
=== Eigenvalue ตัวแรกของกราฟใดๆ ===
 +
 
 +
{{กล่องทฤษฎีบท|"สำหรับกราฟ <math>G</math> ใดๆ Laplacian matrix (<math>L_G</math>) จะมี eigenvalue (น้อยไปมาก) ลำดับที่หนึ่งเป็นศูนย์เสมอ"}}
 +
 
 +
{{เริ่มบทพิสูจน์}}
 +
สมมติให้ <math>G^{\star}</math> เป็นกราฟที่มีมีเส้นเชื่อมเพียงหนึ่งเส้น <math>(v_i,v_j)</math> เราจะได้
 +
 
 +
:<math>
 +
L_{G^{\star}} = \begin{bmatrix}
 +
        & \vdots &       & \vdots &       \\
 +
   \cdots &   1   & \cdots &   -1   & \cdots \\
 +
        & \vdots &       & \vdots &       \\
 +
   \cdots &   -1   & \cdots &   1   & \cdots \\
 +
        & \vdots &       & \vdots &
 +
\end{bmatrix}
 +
</math>
 +
 
 +
สำหรับ vector <math>x = [x_1,x_2,\cdots,x_n]^T</math> ใดๆ คำนวณค่า <math>R(L_{G^{\star}},x)</math> ได้ดังนี้
 +
 
 +
:<math>
 +
R(L_{G^{\star}},x) = \frac{(x_i-x_j)^2}{x^Tx}
 +
</math>
 +
 
 +
ต่อมา พิจรณากราฟ <math>G</math> ใดๆ ที่มีจำนวนเส้นเชื่อม <math>m</math> เส้น โดยเราสามารถเขียน <math>L_G</math> ได้ในรูป
 +
 
 +
:<math>
 +
L_G = L_{G_1} + L_{G_2} + \cdots + L_{G_m}
 +
</math>
 +
 
 +
โดยที่ <math>L_{G_k}</math> สำหรับ <math>1 \le k \le m</math> แทน Laplacian matrix ของกราฟ <math>G_k</math> ซึ่งเป็นกราฟย่อยจาก <math>G</math> ที่มีเส้นเชื่อมเส้นที่ <math>k</math> เพียงเส้นเดียว ดังนั้น
 +
 
 +
:<math>
 +
\begin{align}
 +
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^Tx}
 +
\end{align}
 +
</math>
 +
 
 +
ให้ <math>x_i = 1</math> สำหรับทุกค่า <math>i</math> จะได้ว่า
 +
 
 +
:<math>
 +
R(L_G,x) = \frac{\sum\nolimits_{E(G)}\left(1-1\right)^2}{x^Tx} = 0
 +
</math>
 +
 
 +
จากสมการ <math>(*)</math> ในหัวข้อ Rayleigh quotient จะได้ว่า Rayleigh quotient มีค่าน้อยที่สุดเมื่อ <math>\lambda_1 = 0</math> โดยมี <math>x</math> เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว
 +
 
 +
ดังนั้น สำหรับ Laplacian matrix <math>L_G</math> ของกราฟ G ใดๆ <math>\lambda_1 = 0</math>
 +
{{จบบทพิสูจน์}}
 +
 
 +
=== Eigenvalue ของกราฟต่อเนื่อง ===
 +
 
 +
{{กล่องทฤษฎีบท|"สำหรับกราฟ <math>G</math> ใดๆ Laplacian matrix <math>L_G</math> จะมี eigenvalue ลำดับที่สองไม่เท่ากับศูนย์ ก็ต่อเมื่อ G เป็นกราฟต่อเนื่อง"}}
 +
 
 +
{{เริ่มบทพิสูจน์}}
 +
{{col-begin}}
 +
{{col-break|width=50%}}
 +
<math>(\leftarrow)</math> สมมติให้ <math>G</math> เป็นกราฟต่อเนื่อง และมี eigenvalue ลำดับที่สองเท่ากับศูนย์ (<math>\lambda_2 = 0</math>)
 +
 
 +
ให้ <math>\phi_2 = [a_1,a_2,\cdots,a_n]^T</math> เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว
 +
 
 +
และทฤษฎีบทก่อนหน้า จะได้ว่ามี <math>\lambda_1 = 0</math> และ <math>\phi_1 = [x_1,x_2,\cdots,x_n]^T</math>
 +
 
 +
จาก Spectral Theory เนื่องจาก <math>\phi_2 \perp \phi_1</math> ดังนั้น
 +
 
 +
:<math>
 +
\begin{align}
 +
0 &= \phi_2 \phi_1^T \\
 +
  &= \sum\limits_{i=1}^n x_i a_i
 +
\end{align}
 +
</math>
 +
 
 +
เนื่องจากกราฟต่อเนื่อง ให้ <math>\phi_1 = [1,1,\cdots,1]^T</math> ทำให้
 +
 
 +
:<math>
 +
0 = \sum\limits_{i=1}^n a_i
 +
</math>
 +
 
 +
จะเห็นว่า <math>a_i \ne 0</math> สำหรับทุก <math>i</math> และมี <math>a_i \ne a_j</math> สำหรับบาง <math>i \ne j</math> ส่งผลให้ <math>\sum\nolimits_{(i,j) \in E(G)}(a_i-a_j)^2 \ne 0</math>
 +
 
 +
ซึ่งหมายความว่า <math>\lambda_2 \ne 0</math> และขัดแย้งกับสมมติฐานตั้งต้นว่า <math>\lambda_2 = 0</math> ดังนั้นถ้ากราฟ G เป็นกราฟต่อเนื่อง แล้ว <math>\lambda_2 \ne 0</math>
 +
 
 +
{{col-break|width=50%}}
 +
<math>(\rightarrow)</math> สมมติให้ <math>G</math> เป็นกราฟไม่ต่อเนื่อง และมี eigenvalue ลำดับที่สองไม่เท่ากับศูนย์ (<math>\lambda_2 \ne 0</math>)
 +
 
 +
ให้ <math>\phi_2 = [a_1,a_2,\cdots,a_n]^T</math> เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว
 +
 
 +
และทฤษฎีบทก่อนหน้า จะได้ว่ามี <math>\lambda_1 = 0</math> และ <math>\phi_1 = [x_1,x_2,\cdots,x_n]^T</math>
 +
 
 +
จาก Spectral Theory เนื่องจาก <math>\phi_2 \perp \phi_1</math> ดังนั้น
 +
 
 +
:<math>
 
\begin{align}
 
\begin{align}
R(L_G,x) &= R(L_1,x) + R(L_2,x) + \cdots + R(L_m,x) \\
+
0 &= \phi_2 \phi_1^T \\
&= \frac{\sum\nolimits_{(i,j) \in E(G)}(x_i-x_j)^2}{x^Tx} \\
+
  &= \sum\limits_{i=1}^n x_i a_i
&= \sum\nolimits_{(i,j) \in E(G)}(x_i-x_j)^2
 
 
\end{align}
 
\end{align}
 
</math>
 
</math>
  
จากสมการ <math>(*)</math> ในหัวข้อ Rayleigh quotient จะได้ว่า Rayleigh quotient จะมีค่าน้อยที่สุด (เป็นศูนย์) เมื่อ ''x'' เป็น eigen vector ที่สอดคล้องกับ eigen value <math>\lambda_1 = 0</math>
+
เนื่องจากกราฟไม่ต่อเนื่อง ให้ <math>\phi_1 = [1,\cdots,1,0,\cdots,0]^T</math> ทำให้
 +
 
 +
:<math>
 +
0 = \sum\limits_{i=1}^k a_i
 +
</math>
 +
 
 +
เมื่อให้โหนดที่ <math>1</math> ถึง <math>k</math> เป็นส่วนเดียวกัน และตัดขาดจากโหนดที่ <math>k+1</math> ถึง <math>n</math>
 +
 
 +
ให้ <math>\phi_2 = [0,\cdots,0,1,\cdots,1]</math> และได้ว่า
 +
 
 +
:<math>
 +
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
 +
</math>
 +
 
 +
ซึ่งหมายความว่า <math>\lambda_2 = 0</math> และขัดแย้งกับสมมติฐานตั้งต้นว่า <math>\lambda_2 \ne 0</math> ดังนั้นถ้ากราฟ G เป็นกราฟไม่ต่อเนื่อง แล้ว <math>\lambda_2 = 0</math>
 +
{{col-end}}
 +
{{จบบทพิสูจน์}}
 +
 
 +
=== Eigenvalue ของกราฟที่มี <math>n</math> ส่วน ===
 +
 
 +
ให้กราฟที่มีจำนวน <math>n</math> component ค่า eigenvalue ของ Laplacian matrix ลำดับที่หนึ่งจนถึงลำดับที่ <math>n</math> จะมีค่าเป็น 0
 +
 
 +
{{เริ่มบทพิสูจน์}}
 +
 
 +
ให้กราฟมี <math>n</math> ส่วน ให้ eigenvalue จำนวน <math>n</math> ตัวแรกมีค่าเป็น <math>0</math> และมี eigenvector ที่สอดคล้องกันคือ
 +
 
 +
:<math>
 +
\phi_i = \begin{cases}
 +
1 & \text{if node is in component } i \text{th} \\
 +
0 & \text{otherwise}
 +
\end{cases}
 +
</math>
 +
 
 +
จะเห็นว่า <math>0 \phi_i = L \phi_i</math>
 +
{{จบบทพิสูจน์}}
 +
 
 +
=== Eigenvalue ของกราฟบริบูรณ์ ===
 +
 
 +
ให้กราฟริบูรณ์ (complete graph) จำนวน <math>n</math> โหนด (<math>K_n</math>) ค่า eigenvalue ของ Laplacian matrix ลำดับที่สองจนถึงลำดับสุดท้าย จะมีค่าเป็น <math>n</math>
 +
 
 +
{{เริ่มบทพิสูจน์}}
 +
พิสูจน์โดยให้
 +
 
 +
:<math>
 +
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}
 +
</math>
 +
 
 +
เลือก <math>\lambda_i = n</math> ที่ <math>i \ge 2</math> และเลือก <math>\phi_i</math> ที่สอดคล้องกันดังนี้
 +
 
 +
:<math>
 +
\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}
 +
</math>
 +
 
 +
จะเห็นว่า
 +
 
 +
:<math>
 +
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
 +
</math>
 +
 
 +
ดังนั้น eigenvalue ลำดับที่สองเป็นต้นไปของกราฟบริบูรณ์จำนวน <math>n</math> โหนดมีค่าเป็น <math>n</math>
  
ดังนั้น สำหรับ laplacian matrix <math>L_G</math> ของกราฟ G ใดๆ, vector <math>x = [\frac{1}{\sqrt{m}},\frac{1}{\sqrt{m}},\cdots,...,\frac{1}{\sqrt{m}}]</math>
+
''หมายเหตุ eigenvector ที่นำมาประกอบการพิสูจน์ ไม่จำเป็นต้องตั้งฉากกัน เพียงแค่แสดงให้เห็นว่ามี eigenvector ที่สอดคล้องกับ eigenvalue ได้ก็พอ''
จะเป็น eigen vector ที่สอดคล้องกับ eigen value <math>\lambda_1 = 0</math>
+
{{จบบทพิสูจน์}}
ดังนั้น พิจารณา <math>\lambda_2 \perp \lambda_1</math> จะเห็นได้ว่า ถ้า G เป็น connected graph เราไม่สามารถหา <math>\lambda_2 \perp \lambda_1</math> ที่สอดคล้องกับ eigen value เป็นศูนย์ได้ เพราะฉะนั้น
 
{{กล่องทฤษฎีบท|"สำหรับกราฟ ''G'' ใดๆ laplacian matrix <math>L_G</math> จะมี eigen value (เรียงจากน้อยไปมาก)ลำดับที่หนึ่งเป็นศูนย์
 
และ eigen value ลำดับที่สองจะมีค่าเป็นศูนย์ เมื่อและต่อเมื่อ G ไม่เป็น connected graph"}}
 

รุ่นแก้ไขปัจจุบันเมื่อ 11:09, 10 กุมภาพันธ์ 2558

Spectral Graph Theory

  1. บทนำและทบทวนพีชคณิตเชิงเส้น (ณัฐวุฒิ)
  2. คุณสมบัติของ Eigenvalue ต่อกราฟ (ธานี,ณัฐวุฒิ)
  3. คุณสมบัติของ Eigenvalue ต่อกราฟ[2] (ภัทร)
  4. คุณสมบัติของ Eigenvalue ลำดับที่สองบนกราฟต่างๆ (ธานี)
  5. Cheeger Inequality (ศุภชวาล)
  6. การทดลอง Cheeger Inequality และ Effective Resistance (ธานี)
  7. Random Walks และ Psuedo Random Generator (ศุภชวาล)
  8. Psuedo Random Generator[2] (ภัทร)
  9. Coding Theory และ Expander code (ธานี)
  10. Expander graph from Linear coding (ภัทร)
  11. Chebyshev polynomial (ศุภชวาล)
  12. Preconditioning (ธานี)

แก้ไขกล่องนี้แก้ไขสารบัญ

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

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

Rayleigh quotient

นิยาม Rayleigh quotient สำหรับ vector x และ symmetric matrix M คือ โดยสังเกตว่าถ้า x เป็น eigenvector ของ M ที่สอดคล้องกับ eigenvalue จะได้ว่า เนื่องจาก

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

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


เราจะพิสูจน์โดยการใช้ Spectral theory (เนื้อหาครั้งที่ 1) ให้ M มี dimension ขนาด n (symmetric) ได้ว่า M มี eigenvalue และ eigenvector ที่สอดคล้องกับ เพื่อความสะดวก เราให้ว่า ||x|| = 1 และ |||| = 1 สำหรับทุก i และเราสามารถเขียน x ในรูป จากนั้นจึงคำนวณหาค่า Rayleigh quotient

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

Littlebox.png

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

ให้กราฟ ขนาด โหนดและ เป็น adjacency matrix ของ ถ้าสำหรับโหนดที่ ใดๆ เขียนแทนดีกรีด้วย นิยาม diagonal matrix () ดังนี้

และนิยาม Laplacian matrix () ว่า

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

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

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


สมมติให้ เป็นกราฟที่มีมีเส้นเชื่อมเพียงหนึ่งเส้น เราจะได้

สำหรับ vector ใดๆ คำนวณค่า ได้ดังนี้

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

โดยที่ สำหรับ แทน Laplacian matrix ของกราฟ ซึ่งเป็นกราฟย่อยจาก ที่มีเส้นเชื่อมเส้นที่ เพียงเส้นเดียว ดังนั้น

ให้ สำหรับทุกค่า จะได้ว่า

จากสมการ ในหัวข้อ Rayleigh quotient จะได้ว่า Rayleigh quotient มีค่าน้อยที่สุดเมื่อ โดยมี เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว

ดังนั้น สำหรับ Laplacian matrix ของกราฟ G ใดๆ

Littlebox.png

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

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


Littlebox.png

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

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



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

จะเห็นว่า

Littlebox.png

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

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


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

เลือก ที่ และเลือก ที่สอดคล้องกันดังนี้

จะเห็นว่า

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

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

Littlebox.png