グラフラプラシアンの固有値

はじめに

備忘録です．
ググっても出てこなかったので．

円グラフ

グラフの頂点数を$N$とします．

グラフラプラシアンは

    \boldsymbol{L} = 
        \begin{bmatrix}
            2 & -1 &  &  & -1 \\
            -1 & 2 & -1 &  &  \\
             &  & \ddots &  &  \\
             &  & -1 & 2 & -1 \\
            -1 &  &  & -1 & 2 
        \end{bmatrix}

固有値は

\lambda_n = 2 - 2\cos \frac{2 n\pi}{N} = 4 \sin^2 \frac{n \pi}{N}

対称性があるので，$n$ の取り方は複数ありえます．
単純には，$n=0, 1, \cdots, N-1$ となります．

一方，周期境界の調和振動子の分散関係という物理的な対応関係を考えると，$N$を偶数として

n = -\frac{N}{2}, -\frac{N-1}{2}, \cdots, -1, 1, 1, \cdots, \frac{N-1}{2}, \frac{N}{2}

というとり方をすれば，$n$の符号によって波の伝搬の向きを意味づけることができます．

パスグラフ

グラフラプラシアンは

    \boldsymbol{L} = 
        \begin{bmatrix}
            1 & -1 &  &  & -1 \\
            -1 & 2 & -1 &  &  \\
             &  & \ddots &  &  \\
             &  & -1 & 2 & -1 \\
            -1 &  &  & -1 & 1 
        \end{bmatrix}

固有値は

\lambda_n = 2 - 2\cos \frac{n\pi}{N} = 4 \sin^2 \frac{n \pi}{2N}