矩陣與特徵值的指標

本文的閱讀等級:中級

在線性代數中,一 n\times n 階複矩陣 A 可以視為線性算子 (linear operator),A:\mathbb{C}^n\to\mathbb{C}^n。線性算子 A 的值域是矩陣 A 的行空間,記作 C(A)=\{A\mathbf{x}\vert\mathbf{x}\in\mathbb{C}^n\};線性算子 A 的核是矩陣 A 的零空間,記作 N(A)=\{\mathbf{x}\in\mathbb{C}^n\vert A\mathbf{x}=\mathbf{0}\} (見“線性變換與矩陣的用語比較”)。若 A 是一可逆矩陣,則 C(A)=\mathbb{C}^nN(A)=\mathcal{O},其中 \mathcal{O}=\{\mathbf{0}\}。若 A 是不可逆矩陣,則 C(A) 未能充滿整個 \mathbb{C}^n 而且 N(A) 包含非零向量,C(A)\subset\mathbb{C}^n[1]N(A)\neq\mathcal{O}。秩─零度定理聲明矩陣的秩 (rank) 與零度 (nullity) 之和等於線性算子的定義域的維數 (見“運用輸入輸出模型活化秩─零度定理”):

\hbox{rank}A+\hbox{nullity}A=n

其中 \text{rank}A=\dim C(A)\hbox{nullity}A=\dim N(A)。另一方面,容斥定理闡明兩個子空間與子空間和以及子空間交集的維數關係 (見“補子空間與直和”)。容斥定理套用至行空間 C(A) 與零空間 N(A),如下:

\displaystyle \dim C(A)+\dim N(A)=\dim \left(C(A)+N(A)\right)+\dim \left(C(A)\cap N(A)\right)

因此,\dim \left(C(A)+N(A)\right)+\dim \left(C(A)\cap N(A)\right)=n,可以推論 C(A)+N(A)=\mathbb{C}^n 同義於 C(A)\cap N(A)=\mathcal{O}。這個時候,在向量空間 \mathbb{C}^nC(A)N(A) 的一個補子空間,反之亦然,記作 C(A)\oplus N(A)=\mathbb{C}^n,我們稱之為直和 (direct sum) 分解,意思說是任何一個 \mathbf{z}\in\mathbb{C}^n 可唯一分解為 \mathbf{z}=\mathbf{x}+\mathbf{y},其中 \mathbf{x}\in C(A)\mathbf{y}\in N(A)。不過當 A 為不可逆矩陣時,行空間和零空間未必不交集。例如,A=\begin{bmatrix} 0&1\\ 0&0 \end{bmatrix},不難確認 C(A)=N(A)=\mathrm{span}\left\{\begin{bmatrix} 1\\ 0 \end{bmatrix}\right\}。雖然如此,直和分解總是可以通過冪矩陣 A^k 實現,意即存在一正整數 k1\le k\le n,使得

C(A^k)\oplus N(A^k)=\mathbb{C}^n

稱為值域─零空間分解 (見“值域─零空間分解”)。值域─零空間分解衍生出兩個概念:矩陣的指標 (index) 與特徵值的指標,後者是一個相當有用的特徵分析概念。

 
冪矩陣 A^j 的行空間 C(A^j) 與零空間 N(A^j) 具有底下的包容關係 (證明見[2]):

\displaystyle\begin{aligned} &\mathbb{C}^n\supseteq C(A^0)\supseteq C(A)\supseteq C(A^2)\supseteq\cdots\supseteq C(A^k)\supseteq C(A^{k+1})\supseteq\cdots\supseteq\mathcal{O}\\ &\mathcal{O}\subseteq N(A^0)\subseteq N(A)\subseteq N(A^2)\subseteq\cdots\subseteq N(A^k)\subseteq N(A^{k+1})\subseteq\cdots\subseteq\mathbb{C}^n \end{aligned}

直白地說,隨著次冪 j=0,1,2,\ldots 遞增,行空間 C(A^j)\mathbb{C}^n 逐漸縮小,而零空間 N(A^j)\mathcal{O} 開始增大。對於每一個冪矩陣 A^jj\ge 0,秩─零度定理 \dim C(A^j)+\dim N(A^j)=n 說明 \dim C(A^j)\dim N(A^j) 跟著 j 變動而等量改變。對於不可逆矩陣 A,行空間 C(A^j) 和零空間 N(A^j) 的包容關係可以衍生出下列性質 (證明見“值域─零空間分解”):存在一最小正整數 k 使得

  1. C(A^{k+1})=C(A^k)
  2. N(A^{k+1})=N(A^k)
  3. C(A^k)\cap N(A^k)=\mathcal{O}
  4. C(A^k)+N(A^k)=\mathbb{C}^n

合併等式3和4即為值域─零空間分解 C(A^k)\oplus N(A^k)=\mathbb{C}^n。滿足這四個等式的最大可能 k 值是多少?答案是 n。使用反證法。假設 0<\dim N(A)<\mathrm{dim}N(A^2)<\cdots,則 n<\dim N(A^{n+1}),但 \mathbb{C}^n 不可能包含維數大於 n 的子空間,證明存在 k\le n 使得 N(A^k)=N(A^{k+1})。同樣的推論方式可證得存在 k\le n 使得 C(A^k)=C(A^{k+1})

 
綜合以上討論,我們定義一 n\times n 階矩陣 A 的指標 k=\text{index}(A) 為滿足下列任一條件的最小非負整數:

  1. \text{rank}(A^{k+1})=\text{rank}(A^{k})
  2. C(A^{k+1})=C(A^{k})
  3. N(A^{k+1})=N(A^{k})

A 是可逆矩陣,\text{index}(A)=0。若 A 是不可逆矩陣,則 k=\text{index}(A) 為滿足 C(A^k)\oplus N(A^k)=\mathbb{C}^n 的最小正整數,1\le k\le n。舉一個例子說明:

\displaystyle A=\left[\!\!\begin{array}{ccr} 2&0&0\\ 0&1&-1\\ 0&1&-1 \end{array}\!\!\right]

觀察得知 A 僅有兩個線性獨立的行,即 \text{rank}A=2。因為 A 不可逆,可知 \text{index}(A)>0。計算冪矩陣

\displaystyle A^2=\begin{bmatrix} 4&0&0\\ 0&0&0\\ 0&0&0 \end{bmatrix},~A^3=\begin{bmatrix} 8&0&0\\ 0&0&0\\ 0&0&0 \end{bmatrix}

得到 \text{rank}A>\text{rank}(A^2)=\text{rank}(A^3),故 \text{index}(A)=2。另外,我們還可以從冪矩陣的行空間和零空間推論同樣結果:

\displaystyle C(A)=\text{span}\left\{\begin{bmatrix} 2\\ 0\\ 0 \end{bmatrix},\begin{bmatrix} 0\\ 1\\ 1 \end{bmatrix}\right\},~C(A^2)=\text{span}\left\{\begin{bmatrix} 4\\ 0\\ 0 \end{bmatrix}\right\},~C(A^3)=\text{span}\left\{\begin{bmatrix} 8\\ 0\\ 0 \end{bmatrix}\right\}

因此,C(A)\supset C(A^2)=C(A^3),推知 \text{index}(A)=2。再有,

\displaystyle N(A)=\text{span}\left\{\begin{bmatrix} 0\\ 1\\ 1 \end{bmatrix}\right\},~N(A^2)= \text{span}\left\{\begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix},\begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix}\right\},~ N(A^3)= \text{span}\left\{\begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix},\begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix}\right\}

因此,N(A)\subset N(A^2)=N(A^3),同樣可得 \text{index}(A)=2

 
我們討論幾個關於矩陣的指標性質:相似變換不改變矩陣的指標,正規矩陣、冪等矩陣和冪零矩陣的指標,以及附著於指標的一個分解式。

  • A 相似於 B,則 \text{index}(A)=\text{index}(B)

    假設 A 相似於 B,即存在一可逆矩陣 M 使得 A=MBM^{-1},也就有 A^j=MB^jM^{-1},推得 \text{rank}(A^j)=\text{rank}(B^j)j\ge 0 (相似變換不改變矩陣秩,證明見“相似變換下的不變性質”,性質四)。根據定義,\text{index}(A)=\text{index}(B)

  • A 為一正規矩陣 (normal matrix),則 \text{index}(A)\le 1

    我們稱一矩陣 A 是正規矩陣,若 AA^\ast=A^\ast A (見“特殊矩陣 (2):正規矩陣”)。如果 A 可逆,\text{index}(A)=0。若 A 不可逆,我們要證明 C(A)\cap N(A)=\mathcal{O},意味 C(A)\oplus N(A)=\mathbb{C}^n,故可推得 \text{index}(A)=1。利用性質 N(A)=N(A^\ast A)N(A^\ast)=N(AA^\ast) (見“利用 Gramian 矩陣證明行秩等於列秩”),則有 N(A)=N(A^\ast)。假設 \mathbf{x}\in C(A)\cap N(A),即存在 \mathbf{y}\in\mathbb{C}^n 使得 \mathbf{x}=A\mathbf{y}A\mathbf{x}=\mathbf{0}。以上結果表明 A^\ast\mathbf{x}=\mathbf{0},故

    \displaystyle \Vert\mathbf{x}\Vert^2=\mathbf{x}^\ast\mathbf{x}=(A\mathbf{y})^\ast\mathbf{x}=\mathbf{y}^\ast A^\ast\mathbf{x}=\mathbf{y}^\ast\mathbf{0}=0

    證得 \mathbf{x}=\mathbf{0}

  • P 為一冪等矩陣 (idempotent matrix),則 \text{index}(P)\le 1

    冪等矩陣 P 滿足 P^2=PC(P)\cap N(P)=\mathcal{O} (見“特殊矩陣 (5):冪等矩陣”)。若 P 可逆,則 P=I\text{index}(P)=0。若 P 不可逆,由 C(P)\cap N(P)=\mathcal{O} 推知 \text{index}(P)=1

  • N 為一冪零矩陣 (nilpotent matrix),則 k=\text{index}(N) 為最小正整數使得 N^k=0

    我們稱一矩陣 N 是冪零矩陣,若存在一正整數 k 使得 N^k=0 (見“特殊矩陣 (1):冪零矩陣”)。欲證明 k=\text{index}(N) 是最小正整數使得 N^k=0,假設 m 是一正整數使得 N^m=0,但 N^{m-1}\neq 0。根據指標的定義,下列行空間包容關係成立:

    \displaystyle C(N^0)\supset C(N)\supset\cdots\supset C(N^{k-1})\supset C(N^k)=C(N^{k+1})=C(N^{k+2})=\cdots

    明顯地,不可能發生 m<km>k 的情況,因此證明 m=k。下面是一個出現於 Jordan 典型形式的冪零矩陣例子 (見“Jordan 分塊”):

    \displaystyle N=\begin{bmatrix} 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}

    直接計算可驗證 \text{index}(N)=4,如下:

    \displaystyle N^2=\begin{bmatrix} 0&0&1&0\\ 0&0&0&1\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix},~N^3=\begin{bmatrix} 0&0&0&1\\ 0&0&0&0\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix},~N^4=\begin{bmatrix} 0&0&0&0\\ 0&0&0&0\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix}

  • A 為一 n\times n 階不可逆矩陣,k=\text{index}(A),且 r=\text{rank}A^k,則必存在一可逆矩陣 Q 使得

    \displaystyle Q^{-1}AQ=\begin{bmatrix}     F&0\\     0&N     \end{bmatrix}

    其中 Fr\times r 階可逆分塊,N(n-r)\times(n-r) 階冪零分塊,且 \text{index}(N)=k。上式為核心—冪零分解 (core-nilpotent decomposition),F 是核心,G 是冪零 (詳見“核心─冪零分解”)。

 
下面說明矩陣的指標如何衍生特徵值的指標。令 \sigma(A)n\times n 階矩陣 A 的矩陣譜 (spectrum),即 A 的所有相異特徵值形成的集合。我們定義特徵值 \lambda\in\sigma(A) 的指標為對應矩陣 A-\lambda I 的指標,並記為 \text{index}(\lambda)=\text{index}(A-\lambda I)。因為 A-\lambda I 不可逆,1\le\text{index}(\lambda)\le n。特徵值的指標在進階特徵分析具有重要的意義,在此我們僅列舉出一些事實,請讀者自行查閱相關文章 (見“最小多項式 (下)”,“拒絕行列式的特徵分析”)。設 \lambda\in\sigma(A)k=\text{index}(\lambda)

  • 矩陣 A 的最小多項式包含因式 (t-\lambda)^k。因為最小多項式整除特徵多項式,k 必不大於 \lambda 的代數重數。
  • 若非零向量 \mathbf{x} 滿足 (A-\lambda I)^k\mathbf{x}=\mathbf{0},則 \mathbf{x} 稱為廣義特徵向量 (generalized eigenvector)。若 k=1,則廣義特徵向量退化為一般特徵向量 。
  • 特徵值為 \lambda 的最大 Jordan 分塊階數等於 k。例如,

    \displaystyle J=\begin{bmatrix} \lambda&1&0&0\\ 0&\lambda&1&0\\ 0&0&\lambda&0\\ 0&0&0&\lambda \end{bmatrix}=\begin{bmatrix} \lambda&1&0\\ 0&\lambda&1\\ 0&0&\lambda \end{bmatrix}\oplus\begin{bmatrix} \lambda \end{bmatrix}

    的最大 Jordan 分塊階數為 \text{index}(\lambda)=3

  • 若每一 \lambda\in\sigma(A) 都有 \text{index}(\lambda)=1,則 A 是可對角化矩陣;若存在一 \lambda\in\sigma(A) 使得 \text{index}(\lambda)>1,則 A 是不可對角化矩陣。

 
最後舉一個矩陣與特徵值指標的應用:若 A 為一正規矩陣,AA^\ast=A^\ast A,則 (A-\lambda I)^\ast(A-\lambda I)=(A-\lambda I)(A-\lambda I)^\ast,故知 A-\lambda I 亦為正規矩陣,因此每一特徵值 \lambda 皆有 \text{index}(\lambda)=\text{index}(A-\lambda I)=1,上述性質推論正規矩陣 A 可對角化。實對稱矩陣歸屬於正規矩陣家族,所以實對稱矩陣必可對角化。

 
註解:
[1] 我們以 S\subset T 表示 ST 的一個真子集 (proper subset),即 S\subseteq TS\neq T,並以 S\supset T 表示 ST 的一個真父集 (proper supset),即 S\supseteq TS\neq T
[2] 行空間包容關係 C(A^{j+1})\subseteq C(A^j) 的證明:

\displaystyle\begin{aligned} \mathbf{x}\in{C}(A^{j+1})&\Rightarrow \mathbf{x}=A^{j+1}\mathbf{y}=A^j(A\mathbf{y}), \exists \mathbf{y}\in \mathbb{C}^n\\ &\Rightarrow \mathbf{x}=A^j\mathbf{z}, \mathbf{z}=A\mathbf{y}\\ &\Rightarrow \mathbf{x}\in C(A^j) \end{aligned}

零空間包容關係 N(A^{j})\subseteq N(A^{j+1}) 的證明:

\displaystyle\begin{aligned} \mathbf{x}\in{N}(A^j)&\Rightarrow A^j\mathbf{x}=\mathbf{0}\\ &\Rightarrow A^{j+1}\mathbf{x}=A(A^j\mathbf{x})=A\mathbf{0}=\mathbf{0}\\ &\Rightarrow \mathbf{x}\in N(A^{j+1}) \end{aligned}

Advertisements
本篇發表於 線性代數專欄, 向量空間 並標籤為 , , , , , , , , 。將永久鏈結加入書籤。

9 則回應給 矩陣與特徵值的指標

  1. David 說道:

    Teacher Zhou,

    学习中,发现一个问题:
    如何对下面的幂和求余:
    a4=1^4+2^4+3^4+4^4+….+n^4
    a3=1^3+2^3+3^3+4^3+….+n^3
    a2=1^2+2^2+3^2+4^2+….+n^2
    a1=1+2+3+4+….+n
    a0=n (n 个1相加)

    问题:
    ( ( (a4 mod a3) mod a2 ) mod a1 ) a0

    How to solve a4 = x1*a3+x2*a2+x3*a1+x4*a0 + x5?
    x1,x2,x3, and x4, x5 are integers(x5<=n).

    Thank you!

    • David 說道:

      周老师,
      用Bernoulli幂和多项式和多项式相除, 过程中会引入分数.
      另外, 在高次幂和下, Bernoulli幂和多项式的系数可以
      递归得到,但也是很大数.

      有没有快办法: (((a4 mod a3) mod a2) mod a1) mod a0

    • ccjou 說道:

      你的問題是要求出滿足a4 = x1*a3+x2*a2+x3*a1+x4*a0+x5 的
      x1, x2, x3, x4, x5, 是吧?

      如果是這個問題,目前我的想法是解線性方程。等問題確定了,我再詳細回覆。

      問題要求xi是整數,這有點麻煩。

      • David 說道:

        谢谢您.
        要求xi是整數, 最关键的是如何快速得到X5, 即可.
        这是不定方程式的一类. 不知道線性方程的知识
        能否给个启示.

        问题也可一般化,对高次幂和,情况会如何?

        • ccjou 說道:

          原先我的想法是使用牛頓恆等式(https://ccjou.wordpress.com/2012/11/07/%E5%88%A9%E7%94%A8%E7%89%9B%E9%A0%93%E6%81%86%E7%AD%89%E5%BC%8F%E8%81%AF%E7%B9%AB%E7%89%B9%E5%BE%B5%E5%A4%9A%E9%A0%85%E5%BC%8F%E4%BF%82%E6%95%B8%E8%88%87%E5%86%AA%E7%9F%A9%E9%99%A3%E8%B7%A1%E6%95%B8/)
          或以Smith normal form解出linear Diophantine equation a4=x1*a3+x2*a2+x3*a1+x4*a0+x5,但這還是必須先算出冪和ak,如你所說,當次冪增大時,ak的數值過大。縱使解出一般式,仍未解決原本的問題:求出(((a4 mod a3) mod a2) mod a1) mod a0的快算法。

          如果不實際算出ak,我們就必須有a_{k+1} mod ak (以及任何數 z mod ak) 的特殊算法,譬如,以連續減法取代除法。考慮a_{k+1}-ak=(1*1^k+2*2^k+3*3^k+…+n*n^k)-(1^k+2^k+3^k+4^k+….+n^k)=0*1^k+1*2^k+2*3^k+…+(n-1)*n^k,這個結果可記為序列 (0,1,2,…,n-1)_k,再將之轉換為新序列 (b1,b2,b3,…,bn)_k 使得兩序列表示同一數且 b1,b2,…,bn >=1,再減ak可得(b1-1,b2-1,b3-1,…,bn-1)_k,重複此步驟直到無法繼續為止,最後結果即為餘數。接下來的問題是:提出一個快捷的轉換算法(除了硬算,目前我沒想出其他辦法)。

          • David 說道:

            谢谢您!

            利用Bernoulli幂和多项式, 采用一种特定的多项式消除法,最后的余项是:
            B_{2m} * n. B_{2m} 是Bernoulli数.

            =================================================
            如用余项做素数判定. 有:
            一个奇数a是素数, 则有 (((Bernoulli_{a-1}) * a) + 1) mod a = 0
            =================================================
            您有做数论的同事, 这结论是新的吗?

            如 B4= -1/30, (B4*5+1) = 5/6, (B4*5+1) mod 5 = 0.
            如 B8= -/30, (B8*9+1) = 7/10, (B8*9+1) mod 9 = 7.
            对于: 341, 561
            (bernoulli(340)*341+1) mod 341 =311
            (bernoulli(560)*561+1) mod 561 =291

            在MuPad 下, 做验证:
            对应于第二项为0, 第一项是素数.
            二项式系数能递归得到,也可以直接用函数得到C_{n}^{k}.
            Bernoulli数能递归得到, 有函数直接得到吗??
            如有, 对Bernoulli数作某种变换,就能得到自然数中素数列,
            下一个素数的是?

            >for i from 2 to 100 step 2 do print((i+1), (bernoulli(i)*(i+1)+1) mod (i+1)); end_for
            3, 0
            5, 0
            7, 0
            9, 7
            11, 0
            13, 0
            15, 11
            17, 0
            19, 0
            21, 15
            23, 0
            25, 21
            27, 19
            29, 0
            31, 0
            33, 23
            35, 1
            37, 0
            39, 27
            41, 0
            43, 0
            45, 22
            47, 0
            49, 43
            51, 35
            53, 0
            55, 1
            57, 39
            59, 0
            61, 0
            63, 43
            65, 53
            67, 0
            69, 47
            71, 0
            73, 0
            75, 51
            77, 1
            79, 0
            81, 55
            83, 0
            85, 69
            87, 59
            89, 0
            91, 79
            93, 63
            95, 1
            97, 0
            99, 67
            101, 0

            • ccjou 說道:

              在此先謝謝你。因為你的提問,我花了一二天重溫數論知識,不過仍僅及皮毛。

              一時間我也想不起哪位同事(都是電機系老師)從事數論研究,你最好還是請教數學系老師確認這個發現。

              Bernoulli數存在代數式,見下文(式33)
              http://mathworld.wolfram.com/BernoulliNumber.html

              PS 可能是你的迴響包含過多的標點符號,故被系統誤判為垃圾。倘若下回再有這種情事,請另外張貼一句短語提醒我去垃圾中找回。

  2. David 說道:

    再次谢谢!

    我原来的打算不是数论, 而是如何快速的提取信号中的目标.
    变化后的目标(定义为一种变换), 与目标配适, 理论上,可以
    对变换中的每组参数, 进行检验. 这跟找素数很像!

    我想将变换空间投到目标所定义的一种本性空间中.
    如知道孩子们在教室里即可,不需要知道哪个孩子
    在哪个位置.

    回头有些问题再请教!

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s