KAIST POW 2019-03 Simple Spectrum

문제 링크

2019-03 Simple spectrum - KAIST Math Problem of the Week

\(N \times N\) 실수 행렬 \(T\)가 다음과 같고, 모든 \(b_i > 0\)일 때 \(T\)는 서로 다른 \(N\)개의 eigenvalue를 가짐을 보여라.

 

$$ T = \begin{pmatrix} a_{1} & b_{1} & 0 & \cdots & 0 \\ b_{1} & a_{2} & b_{2} & \ddots & \vdots \\ 0 & b_{2} & a_{3} & \ddots & 0 \\ \vdots & \ddots & \ddots & \ddots & b_{N-1} \\ 0 & \cdots & 0 & b_{N-1} & a_{N} \end{pmatrix} $$

 

---

스포일러 방지선

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

Sol 1. (구데기)

 

Note 1. \(T\)는 real symmetric이므로, \(T\)의 eigenvalue는 모두 실수이다.

 

\(f_{k} (\lambda)\)를 \(T\)의 1행 1열부터 \(k\)행 \(k\)열까지를 딴 submatrix에서 구한 특성방정식이라고 하자. 다음이 성립한다.

$$ f_{1}(\lambda) = a_{1} - \lambda, f_{2}(\lambda) = (a_{1} - \lambda)(a_{2} - \lambda) - b_{1}^{2}. \\ f_{k}(\lambda) = (a_{k} - \lambda)f_{k-1}(\lambda) - b_{k-1}^{2} f_{k-2}(\lambda) (k \ge 2)$$

 

귀납법으로, 모든 \(i < k\)에 대해 \(f_{i}(\lambda) = 0\)은 \(i\)개의 근을 가진다고 가정하자. \(k = 1,2\)인 경우는 자명하다.

 

Note 2. \(f_{k}(-\infty) > 0\)이다.

 

Claim. \(f_{k-1}(\lambda) = 0\)의 근을 \(r_{1} < r_{2} < \cdots <r_{k-1}\)이라고 하자. \(\text{sgn}(f_{k-2}(r_{i})) = (-1)^{i-1}\)가 성립한다.

 

pf. \(k = 2\)인 경우는 쉽게 보일 수 있다.

\(k > 2\)인 경우 귀납을 걸자. \(f_{k-2}(\lambda) = 0\)의 근을 \(t_{1} < t_{2} < \cdots < t_{k-2}\)라고 하면 귀납 가정에 따라 \(f_{k-1}(t_{1}) < 0\), \(f_{k-1}(t_{2}) > 0\) ... 이 성립한다. 중간값의 정리에 의해 다음이 성립한다.

$$ r_{1} \in (-\infty, t_{1}), r_{2} \in (t_{1}, t_{2}), r_{3} \in (t_{2}, t_{3}), \cdots r_{k-1} \in (t_{k-2}, \infty) $$

따라서 \(r_{1} < t_{1}\)이므로 \(f_{k-2}(r_{1}) > 0\), 마찬가지로 \(r_{1} < t_{2} < r_{2}\)이므로 \(f_{k-2}(r_{2}) < 0, \cdots \)가 성립한다.

 

그런데 위의 점화식 \(f_{k}(\lambda) = (a_{k} - \lambda)f_{k-1}(\lambda) - b_{k-1}^{2}f_{k-2}(\lambda)\)인데 \(-b_{k-1}^{2} < 0\)이므로 \(f_{k}(r_{1}) < 0\), \(f_{k}(r_{2}) > 0\), \(\cdots\)가 성립한다. 따라서 \(f_{k}(\lambda)\)는 \((-\infty, r_{1}), (r_{1}, r_{2}), \cdots (r_{k-1}, \infty)\)에서 영점을 하나씩 갖는다.\( _{\blacksquare}\)

 

Sol 2. (공식 풀이)

 

\(T - \lambda I\)의 submatrix를 생각하는데, 대신 첫 번째 row랑 마지막 column을 제거한 matrix를 생각하자.

그런데 이 matrix는 \(b_{i}\)가 대각선에 놓인 Upper triangular matrix이므로 nonsingular이고, rank는 당연히 \(N-1\)이다.

\(T - \lambda I\)는 rank \(N-1\)의 submatrix를 가지므로 \(\text{rank}(T - \lambda I) \ge n-1\)이다. rank - nullity theorem에 의해서 \(\text{nullity}(T - \lambda I) \le 1\)이다. 즉, 모든 eigenspace의 dimension은 1이 된다.

 

그런데 \(T\)는 real symmetric이므로 \(N\)개의 orthonormal한 eigenvector를 가진다. 그렇다면 이에 대응되는 eigenvalue가 총 \(N\)개 있어야 하고, 그 eigenvalue들은 겹칠 수 없으므로 증명이 끝난다.