Gershgorin Circle Theorem

--- title: Gershgorin Circle Theorem --- (*L. Lévy*, 1881) 設矩陣 $A \in \mathbb R^{n \times n}$ 的各列滿足以下性質 $$|a_{ii}| \ge \sum_{k \ne i} |a_{ik}| \;\;\; (i = [1 \ .. n]),$$ 而且 $>$ 對至少一個 $i$ 成立，則 $\det A \ne 0$。 --- 證明： [反證法](http://thiseven.blogspot.com/2015/04/blog-post.html)，假設 $\det A = 0$，則方程式 $A \mathbf x = \mathbf{0}$ 有解 $\mathbf x \ne \mathbf 0$。假設 $\mathbf x$ 的各分量依序為 ${x_1}^0, {x_2}^0, \cdots, {x_n}^0$。所以存在 $\mu$ 使得 $$\left| {x_i}^0 \right| \le \left| {x_\mu}^0 \right| \;\;\; (i = [1 \ .. n]),$$ 而且因為**這些分量的絕對值不可能全相同**，$<$ 對至少一個 $i$ 成立。 > 不失一般性假設對於所有 $i = [1..n]$ 都有 $|{x_i}^0| = 1$，令集合 $X = \{ t \mid {x_t}^0 = 1 \}$, $X' = \{ t \mid {x_t}^0 = -1 \}$。 > > 對於每個 $i \in [0 \ .. n]$，方程式展開的第 $i$ 條式子是 $\sum_{k \in X} a_{ik} = \sum_{k \in X'} a_{ik}$， > > 假設 $i \in X$，由三角不等式: $$\begin{align} | a_{ii} | & = \left| \sum_{k \in X'} a_{ik} - \sum_{k \in X \setminus \{i\}} a_{ik} \right| \\ & \le \left| \sum_{k \in X'} a_{ik} \right| + \left| \sum_{k \in X \setminus \{i\}} a_{ik} \right| \\ & \le \sum_{k \in X'} \left| a_{ik} \right| + \sum_{k \in X \setminus \{i\}} \left| a_{ik} \right| \\ & = \sum_{k \ne i} \left| a_{ik} \right|. \end{align} $$ > 假設 $i \in X'$ 也可以得到一樣的結果。所以對於所有 $i$，都得到 $|a_{ii}| \le \sum_{k \ne i} |a_{ik}|$，違反原命題前提「$>$ 對至少一個 $i$ 成立」。考慮方程式展開的第 $\mu$ 條式子，將第 $\mu$ 項留著，其餘搬到右邊，即 $$a_{\mu\mu} {x_\mu}^0 = - \sum_{k \ne \mu} a_{\mu k} {x_k}^0,$$ 但是因為前提， $$\begin{align} \left| a_{\mu\mu} {x_\mu}^0 \right| &\ge \left( \sum_{k \ne \mu} | a_{\mu k} | \right) \left| {x_\mu}^0 \right| \\ & = \sum_{k \ne \mu} | a_{\mu k} | \left| {x_\mu}^0 \right| \\ & > \sum_{k \ne \mu} | a_{\mu k} | \left| {x_k}^0 \right| \\ & \ge \left| \sum_{k \ne \mu} a_{\mu k} {x_k}^0 \right|, \end{align}$$ 得到矛盾，所以 $\det A \ne 0$。