Re: [線代] eigenvalue

[TassTW (塔矢)]

如推文所說, 關鍵是 n-cycle Cn 的 Laplacian eigenvalue
即是 Cn + 2In 的 eigenvalues,
即是 Cn 的 eigenvalues + 2

以下提供一個不是那麼暴力的算法

Fix n,

       ┌ 0 1      1 ┐
       │ 1 0        │
看 C = │     ＼     │  = A + A^T
       │        0 1 │
       └ 1      1 0 ┘

         ┌ 0 1       ┐
         │   0       │
其中 A = │     ＼    │ of char. polyn. x^n - 1 = 0
         │       0 1 │
         └ 1       0 ┘

故 A 的 eigenvalues 為 n 次方根 ξ^k
簡單算一下知 A^T A = I

故 A^T 和 A 有相同的 eigenvector u
        since A^T u = ξ^{-k} A^T A u = ξ^{-k} u

因 C 也有相同的 eigenvector u
        since C u = (A + A^T) u = (ξ+ξ^{-k}) u

故 C 有 eigenvalues ξ^k+ξ^{-k} = 2 cos(2πk/n)
故 Cn = -C 有 eigenvalues -2 cos(2πk/n)
故 Cn 的 Laplacian eigenvalues 為 2 - 2 cos(2πk/n)

--
╭═──═───══╮╭═──═╯    ． . ‧           ╰══─═──╮
║細雪紛然，悄落無聲├╯    .  .                    .                 ╰═╮╭
│衣阡陌田野以素衣裳║˙ .‧     .‥    ．            ．殘雪濁淖，不復瑩潔╰╯
│我心啊！請白潔勝雪║  ．   ,       ˙   ‧.     ． .  曾經底光華已為陳蹟
║請無垢無瑕        │                                  然我心啊，如磐石無轉
╰═══──═──═╯╴╴╴╴╴╴╴╴╴╴╴╴╴╴╴╴╴仍燁然如昔  ψTassTW

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.50.14
→ ntust661    :推 囧>