https://gall.dcinside.com/mgallery/board/view/?id=math&no=23997


1. K_n의 eigenvalue

글에 있는 K_4 경우를 그대로 하자

K_n의 adjacency matrix에 I를 더하면 모든 entry가 1인 행렬이 나오고 이거는 eigenvalue n(multiplicity 1)이랑 0(multiplicity n-1)이다.

그러므로 K_n은 eigenvalue n-1 (multiplicity 1)이랑 -1 (multiplicity n-1)을 가진다


2. K_m, n의 eigenvalue

일단은 adjacent matrix의 rank가 2니까 2개 빼고 나머지는 전부 0이다.

크기가 m쪽인 component에 sqrt(n), n쪽인 component에 sqrt(m)의 값을 가지는 vector u는 eigenvalue sqrt(mn)에 대응되는 eigenvector임을 알 수 있고

trace는 0이여야하니 남은 하나는 -sqrt(mn)이다.


3. C_n의 eigenvalue

w를 n-th root of unity라고 하자. 그리고 각 0 〈= i 〈= n-1에 대해 vector (1, w^i, w^2i, ..., w^(n-1)i)를 생각해 보면 각각이 eigenvalue w^i+w^(-i)에 대응되는 eigenvector임을 알 수 있다.

Vandermonde matrix의 determinant를 생각해보면 저 벡터들이 linearly independent하다는 것도 알 수 있다. 


4. P_n의 eigenvalue

w를 (2n+2)-th root of unity라고 하자. vector (w^i, w^2i, ..., w^ni)를 u_i라고 두자.

그러면 u_i-u_{-i}는 w^i+w^{-i}에 대응되는 eigenvector이다.

각 0 〈= i 〈= n-1는 다른 eigenvalue를 주므로 u_i-u_{-i}들은 linearly independent하다.


참고: 4번은 Lovasz의 combinatorial problems and exercises를 보면 다른 풀이가 있다.

그리고 양심고백하자면 4번은 옛날에 수업시간에 들었다.