크기가 $n \times n$인 실대칭행렬 $A = (a_{ij})$에 대해 $i \neq j \implies a_{ij} \le 0$을 만족하고, $A$의 모든 고윳값이 음이 아닌 실수이다. (positive-semidefinite) $n \ge 2$라고 할 때, 다음 물음에 답하여라.
- $\ker A = \set{v \in \mathbb{R}^{n} : v^{t}Av = 0}$
- $[n] = \set{1, \cdots, n}$의 nonempty partition $I, J$에 대해, 항상 $a_{ij} < 0$인 $i \in I$, $j \in J$가 존재한다고 하자. 이 때, $\dim \ker A \le 1$임을 보여라.
본 포스트에서는 이 문제의 풀이와, 이것이 함의하는 바에 대해 논의한다.
Problem 1
$v \in \ker A$에서 $v^{t} A v = 0$임이 자명하므로, $v^{t}A v = 0 \implies Av = 0$을 보이면 충분하다.
Real symmetric matrix에 대한 spectral theorem으로부터, $\lambda_{i} \ge 0$과 $\mathbb{R}^{n}$의 orthonormal basis $\set{q_{1}, \cdots, q_{n}}$에 대해 $A = \sum_{i = 1}^{n} \lambda_{i} q_{i}q_{i}^{t}$로 쓸 수 있다.
이 때 $Av =\sum_{i} \lambda_{i} (q_{i}^{t}v) q_{i}$, 그리고 $v^{t}A v = \sum_{i} \lambda_{i} (q_{i}^{t} v)^{2}$ 으로 쓸 수 있다.
$v^{t}Av = 0$이라면 $\lambda_{i} \ge 0$이므로 $\lambda_{i} (q_{i}^{t}v)^{2} = 0$이 성립해야 하고, 따라서 $\lambda_{i} (q_{i}^{t}v) = 0$이다. 따라서 $Av = 0 \implies v \in \ker A$. $\square$
Problem 2
Starrysky와 함께 풀었다.
Problem 1은 워낙 잘 알려진 사실이지만, 의외로 이 사실이 큰 힌트가 된다.
$\ker A = 0$인 경우에는 간단하니, $\dim \ker A \ge 1$인 경우만 보인다.
null space의 nonzero vector $v \in \ker A$를 잡자. 이 때, $[n]$을 다음과 같이 분할한다.
- $I^{+} := \set{i \in [n] : v_{i} >0 }$
- $I^{0} := \set{i \in [n] : v_{i} =0 }$
- $I^{-} := \set{i \in [n] : v_{i} < 0 }$
$v^{+} := \sum_{i \in I^{+}} v_{i}\mathbf{e}_{i}$, $v^{-} = \sum_{i \in I^{-}} (-v_{i})\mathbf{e}_{i}$로 두면, $v = v^{+} - v^{-}$로 나타낼 수 있고 $v^{+}$와 $v^{-}$ 는 각 성분이 음이 아닌 실수이다.
Claim 1. $v^{+}, v^{-} \in \ker A$.
Proof. $v^{t}Av = (v^{+} - v^{-})^{t} A (v^{+} - v^{-}) = 0$에서, $(v^{+})^{t}Av^{+} + (v^{-})^{t}Av^{-} - 2((v^{+})^{t}Av^{-}) = 0$을 얻는다. 앞 두 항은 당연히 nonnegative고, 맨 뒤 항은 풀어 쓰면 $(v^{+})^{t}Av^{-} = \sum_{i \in I^{+}} \sum_{j \in I^{-}} a_{ij}v_{i}(-v_{j}) \ge 0$이다. 따라서 nonnegative real 3개의 합이 $0$이고 셋 다 $0$이어야 한다. 앞의 $1$에 의해 $v^{+}, v^{-} \in \ker A$. $\square$
위 식의 세 번째 항에 조금 더 집중해보자.
일반성을 잃지 않고, $0 < \left\lvert I^{+} \right\rvert < n$이라고 두자. $i \in I^{+}, j \in I^{-}$에 대해 $a_{ij} = 0$이다. 문제에 주어진 조건에 $I = I^{+}$, $J = I^{0} \cup I^{-}$를 대임해서 생각하면 $a_{ij} < 0$인 $i \in I^{+}, j \in I^{0}$가 하나 이상 존재한다. 이 위치를 $(p \in I^{+}, q \in I^{0})$라고 두자.
$A$의 $i$번째 column vector를 $A^{i}$로 두면, $Av_{+} = 0$은 결국 $\sum_{i \in I^{+}} A^{i} v_{i} = 0$이라는 뜻이 된다. 이 때 $Av_{+}$의 $q$번째 항을 보면
$(Av_{+})_{q} = \sum_{i \in I^{+}} a_{qi}v_{i} = 0$이다. $a_{qi} \le 0, v_{i} \ge 0$이므로 결국 $a_{qi}v_{i} = 0$을 얻는다. 여기에 $p$를 넣으면 $a_{qp}v_{p} < 0$이므로 모순이 발생한다!
Claim 2. $v \in \ker A$이고 $v \neq 0$이면, $v$의 모든 항은 nonzero이고 부호가 동일하다. $\square$
$0 < \left\lvert I^{-} \right\rvert < n$도 동일하게 모순이 발생함을 알 수 있으므로, 결국 $I^{+}, I^{-}$ 중 하나가 전체집합이어야 한다는 사실을 알 수 있다. 이제 $ I^{+} = n$이라고 두자. 아닌 경우는 $v$대신 $-v$를 쓰면 된다.
$w \in \ker A$를 생각하자. 역시 $w$도 동일한 논증을 거쳐 모든 항이 양수인 벡터로 잡을 수 있다. 일반성을 잃지 않고 $v_{1} = w_{1} = 1$이 되게 scaling하자.
만약 $v, w$가 linearly independent하다면 $v - w \neq 0$이어야 한다. 일반성을 잃지 않고 $(v - w)_{k} > 0$이라고 두자. 그런데 $(v - w)_{1} = 0$이고, 똑같이 $v - w \in \ker A$이므로 Claim 2에 모순. 따라서 $\dim \ker A = 1$이다. $\square$
Implication
정점이 $n$개인 양수 가중치를 갖는 양방향 연결그래프 $G$를 생각하자. 이 때 $G$의 laplacian $L(G)$는 Problem 2의 조건을 만족하는 한 예시가 된다.
$L(G)$는 모든 항이 $1$인 vector에 대해 $L(G)1 = 0$을 만족하고, $\mathrm{rk} L(G) = n - 1$이 잘 알려져 있다. 즉, Problem 2는 “연결그래프의 laplacian의 rank는 $n - 1$이다”라는 사실을 일반화한 명제로 볼 수 있다.
컴포넌트가 $c$개인 laplacian의 rank는 $n - c$로 알려져 있다. Problem 2의 증명을 아래와 같이 확장할 수 있을까?
- $[n]$의 nonempty partition $I_{1}, \cdots, I_{c}$에 대해 어떤 $i \in I_{u}, j \in I_{v}$가 존재하여 $u \neq v$, $a_{ij} < 0$이다. 이 때, $\dim \ker A \le c$임을 보여라.