# Eigenvector from eigenvalue

## Summary

這篇論文首先提出了一種從 eigenvalue 推導出 eigenvector 的方法，並用簡單的證明驗證其正確性。
這種方法有幾個限制，首先，矩陣必須是 Hermitian matrix，也就是 $A^{'}$ = $A$；其次，你必須要計算出所有的 eigenvalue，才能藉由這些 eigenvalue 推出每一個 eigenvector。方程式如下：

$\sum_{j=1}^n{|v_{n, j}|}^2 \prod_{k=1}^{n-1} \lambda_k(A) = \sum_{j=1}^n det(M_j)$

證明的部分，藉由證明兩個 lemma 來推得以上的等式。

### Lemma 1:

$\prod_{i=1}^{n-1} \lambda_i(A) {|det(B\ |\ v_n)|}^2 = det(B^*AB)$

其中，$B$ 為一個 $n * (n\ -\ 1)$ 的矩陣，$B\ |\ v_n$ 為一個 $n * n$ 的矩陣

Lemma 1 的證明很單純：

1. 首先將矩陣 $A$ 拆解為 $VDV^*$，因此

$det(B^*AB) = det(B^*VDV^*B) = det((V^*B)^*DV^*B)$

令 $V^*B = B^{'}$ 為一個 $n * (n\ -\ 1)$ 的矩陣

$\Rightarrow det(B^*AB) = det({B^{'}}^*DB^{'})$

又我們可以把 $B^{'}$ 寫成 $\left(\begin{array} {c} B^{"} \\ X\end{array}\right)$，其中 $B^{"}$ 為一個 $(n\ -\ 1) * (n\ -\ 1)$ 的矩陣，而 $X$ 則是 $1 * (n\ -\ 1)$ 的矩陣，則

$\begin{split} \Rightarrow det(B^*AB) &= det\left(({B^{"}}^*\ X^*) \left(\begin{array} {cc} \Lambda_{(n\ -\ 1) * (n\ -\ 1)} & \\ & 0\end{array}\right) \left(\begin{array} {c} B^{"} \\ X\end{array}\right)\right) \\
&= det((B^{"})^*\Lambda B^{"}) = det((B^{"})^*)det(\Lambda)det(B^{"})\end{split}$

2. 另一方面
$\begin{split} det(B\ |\ v_n) &= det(VB^{'}\ |\ V \left(\begin{array} {c} 0_{1 * (n\ -\ 1)} \\ 1\end{array}\right)) = det(V\left(\begin{array} {c} B^{"} \\ X\end{array}\right)\ |\ V \left(\begin{array} {c} 0_{1 * (n\ -\ 1)} \\ 1\end{array}\right)) \\
&= det(V\left(\begin{array} {c} B^{"} \\ X\end{array}\ \begin{array} {c} 0_{1 * (n\ -\ 1)} \\ 1\end{array}\right)) = det(V)det(B^{"}) = \pm det(B^{"})\end{split}$

$\Rightarrow \prod_{i=1}^{n-1} \lambda_i(A) {|det(B\ |\ v_n)|}^2 = \prod_{i=1}^{n-1} \lambda_i(A) {|det(B^{"})|}^2$

由 1. 與 2. 可以得到等式成立。

### Lemma 2:

${|v_{i, j}|}^2\prod_{k=1, k\neq i}^{n}[\lambda_i(A) - \lambda_k(A)] = \prod_{k=1}^{n-1}[\lambda_i(A) - \lambda_k(M_j)]$

lemma 2 則是希望得到 eigenvector 中每一個元素 $v_{i, j}$ 與 $A$ 及其子矩陣的 eigenvalue 有何關係。

這裡只證明第 $i$ 個 eigenvector 的第一個元素，我們一樣假設第 n 個 eigenvalue 為零，也就是 $\lambda_n(A_1) = 0$。

令 $A_1 = \left(\begin{array} {cc} a_{11} & .. \\ : & M_1^{'} \end{array}\right) = A - \lambda_nI$

因此等式可以化減為 ${|v_{i, j}|}^2\prod_{k=1}^{n-1}\lambda_k(A_1) = \prod_{k=1}^{n-1}\lambda_k(M_1^{'})$

接著要使用到前面所證明的 lamma 1，令 $B = \left(\begin{array} {c} 0_{1 * (n\ -\ 1)} \\ I_{n-1}\end{array}\right)$

1. 由於
${|v_{i, j}|}^2\prod_{k=1}^{n-1}\lambda_k(A_1) = \prod_{i=1}^{n-1}\lambda_i(A_1){|v_{n, 1}|}^2 = \prod_{i=1}^{n-1} \lambda_i(A) {|det(B\ |\ v_n)|}^2 = det(B^*A_1B)$
$\Rightarrow {|v_{i, j}|}^2\prod_{k=1}^{n-1}\lambda_k(A_1) = det(B^*A_1B)$

2. 又
$det(B^*A_1B) = det\left((0_{(n\ -\ 1) * 1}\ I_{n-1}) \left(\begin{array} {cc} a_{11} & .. \\ : & M_1^{'}\end{array}\right) \left(\begin{array} {c} 0_{1 * (n\ -\ 1)} \\ I_{n-1}\end{array}\right)\right) = det(M_1^{'}) = \prod_{k=1}^{n-1}\lambda_k(M_1^{'})$

由 1. 與 2. 可以得到等式成立。

## Discussion

這篇論文讓我們知道，原來這個理論是可以用簡單的矩陣運算證明得出，不過還是有幾點可以注意的。

首先，這裡只證明了當第 n 個 eigenvalue 為零的情況，但要將 lemma 1 推廣到任意形式的 eigenvalue 並不難，可以猜想即使擁有 full rank 的 eigenvalue，仍然可以透過創造一個 $(n\ +\ 1) * (n\ +\ 1)$ 的矩陣的驗證其正確性。

然而在 lemma 2 中，當矩陣不包含零的特徵值時，該如何驗證其正確性？論文中有提到可以透過位移的方式產生包含特徵值為零的矩陣，而在後續更完整的論文中也有提到，稱為的 translation symmetry，也就是當今天對矩陣 $A$ 加上一個 $\lambda I$ 時，其 eigenvalue 與所有子空間的 eigenvalue 皆會位移，因此在這種情況下，不失一般性。

在後續的論文中也有提到，其實這種透過 eigenvalue 推得 eigenvector 的方法，在過去許多研究中都有使用過，並有多種不同形式的表達方式，只是不那麼耳熟能詳，透過這次的討論，讓大多數人認識了這套理論。

而這種方法其實也有缺陷，包含無法確認其 eigenvector 每個元素的正負號，如果是在複數平面，甚至更難找到 eigenvector。

另一件有趣的事情，對於一個 $n * n$ 的矩陣，其 eigenvector 需要 $n^2$ 的空間，而根據論文中的方法，記錄一個矩陣必須儲存矩陣的 eigenvalue 以及其所有子矩陣的 eigenvalue，也就是 $n + n(n - 1) = n^2$，其空間複雜度都是 $O(n^2)$，反倒是新的方法必須計算各個矩陣、子矩陣的 eigenvalue，因此需要大量的計算時間。