循環向量定理

本文的閱讀等級：高級

令 $A$ 為一個 $n\times n$ 階矩陣。對於 $n$ 維向量 $\mathbf{x}$ ，如果向量集 $\{\mathbf{x}, A\mathbf{x}, \ldots, A^{n-1}\mathbf{x}\}$ 構成 $\mathbb{C}^n$ 的一組基底，則 $\mathbf{x}$ 稱為 $A$ 的一個循環向量 (cyclic vector)。任一方陣 $A$ 未必總是存在循環向量，譬如，單位矩陣 $I_n$ ，因為對於所有 $\mathbf{x}$ ， $I_n\mathbf{x}=\mathbf{x}$ 。本文證明循環向量定理，包含下列等價陳述：

$A$ 有一個循環向量。
$A$ 相似於一個相伴矩陣 (companion matrix)。
$A$ 的最小多項式即為其特徵多項式。
若 $A$ 和 $B$ 是可交換矩陣， $AB=BA$ ，則 $B$ 是由 $A$ 形成的矩陣多項式，即 $B=p(A)$ ， $p(t)$ 是一個多項式。

(1) $\Rightarrow$ (2)

若 $A$ 有一個循環向量 $\mathbf{x}$ ，則 $S=\begin{bmatrix} \mathbf{x}&A\mathbf{x}&\cdots&A^{n-1}\mathbf{x} \end{bmatrix}$ 是 $n\times n$ 階可逆矩陣。設唯一數組 $c_0, c_1,\ldots, c_{n-1}$ 使得

$c_0\mathbf{x}+c_1A\mathbf{x}+\cdots+c_{n-1}A^{n-1}\mathbf{x}+A^n\mathbf{x}=\mathbf{0}$ ，

就有

$\begin{aligned} AS&=A\begin{bmatrix} \mathbf{x}&A\mathbf{x}&\cdots&A^{n-1}\mathbf{x} \end{bmatrix}=\begin{bmatrix} A\mathbf{x}&A^2\mathbf{x}&\cdots &A^n\mathbf{x} \end{bmatrix}\\ &=\begin{bmatrix} \mathbf{x}&A\mathbf{x}&\cdots&A^{n-1}\mathbf{x} \end{bmatrix}\begin{bmatrix} 0&0&\cdots&0&-c_0\\ 1&0&\cdots&0&-c_1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&1&-c_{n-1} \end{bmatrix}\\ &=SC,\end{aligned}$

上式中， $C$ 是特徵多項式 $p_C(t)=t^n+c_{n-1}t^{n-1}+\cdots+c_1t+c_0$ 的相伴矩陣 (見“利用循環子空間計算特徵多項式”)，因此證明 $A$ 相似於一個相伴矩陣。

(2) $\Rightarrow$ (1)

若 $A$ 相似於相伴矩陣 $C$ ，即存在一個可逆矩陣 $S=\begin{bmatrix} \mathbf{x}_1&\mathbf{x}_2&\cdots&\mathbf{x}_n \end{bmatrix}$ 使得 $AS=SC$ ，如下：

$A\begin{bmatrix} \mathbf{x}_1&\mathbf{x}_2&\cdots&\mathbf{x}_n \end{bmatrix}=\begin{bmatrix} \mathbf{x}_1&\mathbf{x}_2&\cdots &\mathbf{x}_n \end{bmatrix}\begin{bmatrix} 0&0&\cdots&0&-c_0\\ 1&0&\cdots&0&-c_1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&1&-c_{n-1} \end{bmatrix}$ 。

乘開上式，置換等號兩邊，可得

$\begin{aligned} \mathbf{x}_2&=A\mathbf{x}_1\\ \mathbf{x}_3&=A\mathbf{x}_2=A^2\mathbf{x}_1\\ &\vdots\\ \mathbf{x}_n&=A\mathbf{x}_{n-1}=A^{n-1}\mathbf{x}_1. \end{aligned}$

因此證明 $\{\mathbf{x}_1,A\mathbf{x}_1,\ldots,A^{n-1}\mathbf{x}_1\}$ 是線性獨立集，故 $A$ 有一循環向量 $\mathbf{x}_1$ 。

(2) $\Leftrightarrow$ (3)

相伴矩陣

$C=\begin{bmatrix} 0&0&\cdots&0&-c_0\\ 1&0&\cdots&0&-c_1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&1&-c_{n-1} \end{bmatrix}$

的最小多項式和特徵多項式同為

$p(t)=t^n+c_{n-1}t^{n-1}+\cdots+c_1t+c_0$ 。

證明見“多項式的相伴矩陣”。

(1) $\Rightarrow$ (4)

若 $\mathbf{x}$ 是 $A$ 的一個循環向量，對於任一 $n\times n$ 階矩陣 $B$ ，存在唯一數組 $b_0, b_1,\ldots, b_{n-1}$ 使得

$B\mathbf{x}=b_0\mathbf{x}+b_1A\mathbf{x}+\cdots+b_{n-1}A^{n-1}\mathbf{x}=\left(b_0I+b_1A+\cdots+b_{n-1}A^{n-1}\right)\mathbf{x}$ 。

令 $p(t)=b_0+b_1t+\cdots+b_{n-1}t^{n-1}$ ，則 $B\mathbf{x}=p(A)\mathbf{x}$ 。若 $A$ 和 $B$ 是可交換矩陣，則 $A^k$ 和 $B$ 也是可交換矩陣。利用此性質並代入上面結果，對於非負整數 $k$ ，可得

$BA^k\mathbf{x}=A^kB\mathbf{x}=A^kp(A)\mathbf{x}=p(A)A^k\mathbf{x}$ ，

或改寫為 $(B-p(A))A^k\mathbf{x}=\mathbf{0}$ 。我們定義 $A^0\equiv I$ 。因為 $\mathbf{x}, A\mathbf{x},\ldots, A^{n-1}\mathbf{x}$ 構成一線性獨立集，即知 $\dim N(B-p(A))=n$ ，利用秩─零度定理可知 $\mathrm{rank}(B-p(A))=0$ ，故 $B=p(A)$ ，即證得所求。

(4) $\Rightarrow$ (1)

若 $A$ 沒有循環向量，我們只要證明存在一 $B$ 使得 $AB=BA$ ，但 $B$ 不可表示為矩陣多項式 $p(A)$ 。根據循環分解定理 (見“不變子空間──解構線性算子的利器”)，向量空間 $\mathbb{C}^n$ 有一組基底 $\mathfrak{B}=\mathfrak{B}_1\cup\cdots\cup\mathfrak{B}_m$ ，其中 $\mathfrak{B}_j=\{\mathbf{v}_j,A\mathbf{v}_j,\ldots,A^{k_j-1}\mathbf{v}_j\}$ 代表第 $j$ 個循環子空間基底， $\sum_{j=1}^mk_j=n$ ，使得 $AS=SC$ ，或

$C=S^{-1}AS=\begin{bmatrix} C_1&&&\\ &\ddots&&\\ &&C_{m-1}&\\ &&&C_m \end{bmatrix}$ ，

其中 $S$ 的行向量由 $\mathfrak{B}$ 的 $n$ 個基底向量組成，主對角分塊 $C_i$ 是 $k_i\times k_i$ 階相伴矩陣，且 $C_i$ 的特徵多項式 (也稱為 $A$ 的不變因子) $p_i(t)$ 整除 $C_{i+1}$ 的特徵多項式 $p_{i+1}(t)$ ， $i=1,\ldots,m-1$ 。這個由相伴矩陣構成的分塊對角矩陣 $C$ 稱為有理標準形式 (rational canonical form)。因為 $A$ 不存在循環向量，可知 $m>1$ 。設 $n\times n$ 階矩陣 $B$ 滿足

$\begin{aligned} B(A^j\mathbf{v}_1)&=A^j\mathbf{v}_1,~~j=0,1,\ldots,k_1-1,\\ &\vdots\\ B(A^j\mathbf{v}_{m-1})&=A^j\mathbf{v}_{m-1},~~j=0,1,\ldots,k_{m-1}-1,\\ B(A^j\mathbf{v}_m)&=\mathbf{0},~~j=0,1,\ldots,k_m-1,\end{aligned}$

將方程組整理成 $BS=SD$ ，或

$D=S^{-1}BS=\begin{bmatrix} I_{k_1}&&&\\ &\ddots&&\\ &&I_{k_{m-1}}&\\ &&&0 \end{bmatrix}$ 。

明顯地， $CD=DC$ ，因此

$\begin{aligned} AB&=(SCS^{-1})(SDS^{-1})=SCDS^{-1}=SDCS^{-1}\\ &=(SDS^{-1})(SCS^{-1})=BA.\end{aligned}$

最後我們證明 $B$ 不為 $A$ 的矩陣多項式。使用反證法。令 $q(t)=b_0+b_1t+\cdots+b_{r-1}t^{r-1}$ 。假設 $B$ 可表示成矩陣多項式 $B=q(A)=b_0I+b_1A+\cdots+b_{r-1}A^{r-1}$ ，則

$\begin{aligned} S^{-1}BS&=S^{-1}\left(b_0I+b_1A+\cdots+b_{r-1}A^{r-1}\right)S\\ &=b_0S^{-1}IS+b_1S^{-1}AS+\cdots+b_{r-1}S^{-1}A^{r-1}S\\ &=b_0I+b_1C+\cdots+b_{r-1}C^{r-1}\\ &=\begin{bmatrix} \sum_{i=0}^{r-1}b_iC_1^i&&&\\ &\ddots&&\\ &&\sum_{i=0}^{r-1}b_iC_{m-1}^i&\\ &&&\sum_{i=0}^{r-1}b_iC_m^i \end{bmatrix}=D. \end{aligned}$

比較最末等式兩邊，可知 $\sum_{i=0}^{r-1}b_iC_m^i=q(C_m)=0$ ，由此推論 $C_m$ 的特徵多項式 $p_m(t)$ 整除 $q(t)$ (因為 $C_m$ 的特徵多項式即為消滅 $C_m$ 的最小多項式。)。在有理標準形式中， $p_{m-1}(t)$ 整除 $p_m(t)$ ，也就整除 $q(t)$ 。所以， $q(C_{m-1})=\sum_{i=0}^{r-1}b_iC_{m-1}^i=0$ ，但這與 $D$ 的主對角分塊 $I_{k_{m-1}}$ 相矛盾，因此證明 $B$ 不可能是 $A$ 的矩陣多項式。

6 Responses to 循環向量定理

edge says:

03/11/2014 at 11:43 am

S空間感覺跟Krylove子空間很像
循環向量跟其是否有些關係??

- ccjou says:
  
  03/11/2014 at 12:16 pm
  
  Krylov子空間不必充滿 $\mathbb{C}^n$ ，但以循環向量作為種子所產生的Krylov子空間充滿整個 $\mathbb{C}^n$ 。見
  https://ccjou.wordpress.com/2014/01/15/krylov-%E5%AD%90%E7%A9%BA%E9%96%93%E6%B3%95/
  
ayl says:

11/22/2014 at 11:22 pm

关于(4)=>(1)的证明中，为什么在A不存在循环向量时，就可以假设文中的B？或者如果A存在循环变量，就不能像文中那样构建B？此处的B感觉有些突兀。

- ccjou says:
  
  11/23/2014 at 8:00 pm
  
  論證基礎是邏輯等價： $p\to q$ 等價於 $\neg q\to\neg p$ 。見
  http://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E7%AD%89%E4%BB%B7
  
  - ayl says:
    
    11/24/2014 at 9:36 am
    
    老师您好，可能我表述的不清楚。我困惑的是为什么会有这样的 $n\times n$ 阶矩阵 $B$ 满足:
    $\begin{aligned} B(A^j\mathbf{v}_1)&=A^j\mathbf{v}_1,~~j=0,1,\ldots,k_1-1,\\ &\vdots\\ B(A^j\mathbf{v}_{m-1})&=A^j\mathbf{v}_{m-1},~~j=0,1,\ldots,k_{m-1}-1,\\ B(A^j\mathbf{v}_m)&=\mathbf{0},~~j=0,1,\ldots,k_m-1,\end{aligned}$
    也就是为什么可以这样构建 $B$ ，这样的 $B$ 一定存在吗？
    
    - ccjou says:
      
      11/24/2014 at 10:55 am
      
      其實我這樣寫是畫蛇添足。直接令 $D=\text{diag}(1,\ldots,1,0,\ldots,0)$ 且 $B=SDS^{-1}$ 即可。換句話說，給定任一基底作為特徵向量，對應任意特徵值，這樣的方陣必定存在。

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨