本文的閱讀等級:中級
在線性代數中,一 階複矩陣
可以視為線性算子 (linear operator),
。線性算子
的值域是矩陣
的行空間,記作
;線性算子
的核是矩陣
的零空間,記作
(見“線性變換與矩陣的用語比較”)。若
是一可逆矩陣,則
且
,其中
。若
是不可逆矩陣,則
未能充滿整個
而且
包含非零向量,
[1] 且
。秩─零度定理聲明矩陣的秩 (rank) 與零度 (nullity) 之和等於線性算子的定義域的維數 (見“運用輸入輸出模型活化秩─零度定理”):
,
其中 ,
。另一方面,容斥定理闡明兩個子空間與子空間和以及子空間交集的維數關係 (見“補子空間與直和”)。容斥定理套用至行空間
與零空間
,如下:
。
因此,,可以推論
同義於
。這個時候,在向量空間
,
是
的一個補子空間,反之亦然,記作
,我們稱之為直和 (direct sum) 分解,意思說是任何一個
可唯一分解為
,其中
,
。不過當
為不可逆矩陣時,行空間和零空間未必不交集。例如,
,不難確認
。雖然如此,直和分解總是可以通過冪矩陣
實現,意即存在一正整數
,
,使得
,
稱為值域─零空間分解 (見“值域─零空間分解”)。值域─零空間分解衍生出兩個概念:矩陣的指標 (index) 與特徵值的指標,後者是一個相當有用的特徵分析概念。
冪矩陣 的行空間
與零空間
具有底下的包容關係 (證明見[2]):
直白地說,隨著次冪 遞增,行空間
從
逐漸縮小,而零空間
從
開始增大。對於每一個冪矩陣
,
,秩─零度定理
說明
和
跟著
變動而等量改變。對於不可逆矩陣
,行空間
和零空間
的包容關係可以衍生出下列性質 (證明見“值域─零空間分解”):存在一最小正整數
使得
,
,
,
。
合併等式3和4即為值域─零空間分解 。滿足這四個等式的最大可能
值是多少?答案是
。使用反證法。假設
,則
,但
不可能包含維數大於
的子空間,證明存在
使得
。同樣的推論方式可證得存在
使得
。
綜合以上討論,我們定義一 階矩陣
的指標
為滿足下列任一條件的最小非負整數:
,
,
。
若 是可逆矩陣,
。若
是不可逆矩陣,則
為滿足
的最小正整數,
。舉一個例子說明:
。
觀察得知 僅有兩個線性獨立的行,即
。因為
不可逆,可知
。計算冪矩陣
,
得到 ,故
。另外,我們還可以從冪矩陣的行空間和零空間推論同樣結果:
。
因此,,推知
。再有,
。
因此,,同樣可得
。
我們討論幾個關於矩陣的指標性質:相似變換不改變矩陣的指標,正規矩陣、冪等矩陣和冪零矩陣的指標,以及附著於指標的一個分解式。
- 若
相似於
,則
。
假設
相似於
,即存在一可逆矩陣
使得
,也就有
,推得
,
(相似變換不改變矩陣秩,證明見“相似變換下的不變性質”,性質四)。根據定義,
。
- 若
為一正規矩陣 (normal matrix),則
。
我們稱一矩陣
是正規矩陣,若
(見“特殊矩陣 (2):正規矩陣”)。如果
可逆,
。若
不可逆,我們要證明
,意味
,故可推得
。利用性質
和
(見“利用 Gramian 矩陣證明行秩等於列秩”),則有
。假設
,即存在
使得
且
。以上結果表明
,故
,
證得
。
- 若
為一冪等矩陣 (idempotent matrix),則
。
冪等矩陣
滿足
且
(見“特殊矩陣 (5):冪等矩陣”)。若
可逆,則
且
。若
不可逆,由
推知
。
- 若
為一冪零矩陣 (nilpotent matrix),則
為最小正整數使得
。
我們稱一矩陣
是冪零矩陣,若存在一正整數
使得
(見“特殊矩陣 (1):冪零矩陣”)。欲證明
是最小正整數使得
,假設
是一正整數使得
,但
。根據指標的定義,下列行空間包容關係成立:
明顯地,不可能發生
或
的情況,因此證明
。下面是一個出現於 Jordan 典型形式的冪零矩陣例子 (見“Jordan 分塊”):
。
直接計算可驗證
,如下:
。
- 若
為一
階不可逆矩陣,
,且
,則必存在一可逆矩陣
使得
,
其中
為
階可逆分塊,
為
階冪零分塊,且
。上式為核心—冪零分解 (core-nilpotent decomposition),
是核心,
是冪零 (詳見“核心─冪零分解”)。
下面說明矩陣的指標如何衍生特徵值的指標。令 為
階矩陣
的矩陣譜 (spectrum),即
的所有相異特徵值形成的集合。我們定義特徵值
的指標為對應矩陣
的指標,並記為
。因為
不可逆,
。特徵值的指標在進階特徵分析具有重要的意義,在此我們僅列舉出一些事實,請讀者自行查閱相關文章 (見“最小多項式 (下)”,“拒絕行列式的特徵分析”)。設
且
。
- 矩陣
的最小多項式包含因式
。因為最小多項式整除特徵多項式,
必不大於
的代數重數。
- 若非零向量
滿足
,則
稱為廣義特徵向量 (generalized eigenvector)。若
,則廣義特徵向量退化為一般特徵向量 。
- 特徵值為
的最大 Jordan 分塊階數等於
。例如,
的最大 Jordan 分塊階數為
。
- 若每一
都有
,則
是可對角化矩陣;若存在一
使得
,則
是不可對角化矩陣。
最後舉一個矩陣與特徵值指標的應用:若 為一正規矩陣,
,則
,故知
亦為正規矩陣,因此每一特徵值
皆有
,上述性質推論正規矩陣
可對角化。實對稱矩陣歸屬於正規矩陣家族,所以實對稱矩陣必可對角化。
註解:
[1] 我們以 表示
是
的一個真子集 (proper subset),即
且
,並以
表示
是
的一個真父集 (proper supset),即
且
。
[2] 行空間包容關係 的證明:
零空間包容關係 的證明:
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!
周老师,
用Bernoulli幂和多项式和多项式相除, 过程中会引入分数.
另外, 在高次幂和下, Bernoulli幂和多项式的系数可以
递归得到,但也是很大数.
有没有快办法: (((a4 mod a3) mod a2) mod a1) mod a0
你的問題是要求出滿足a4 = x1*a3+x2*a2+x3*a1+x4*a0+x5 的
x1, x2, x3, x4, x5, 是吧?
如果是這個問題,目前我的想法是解線性方程。等問題確定了,我再詳細回覆。
問題要求xi是整數,這有點麻煩。
谢谢您.
要求xi是整數, 最关键的是如何快速得到X5, 即可.
这是不定方程式的一类. 不知道線性方程的知识
能否给个启示.
问题也可一般化,对高次幂和,情况会如何?
原先我的想法是使用牛頓恆等式(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,重複此步驟直到無法繼續為止,最後結果即為餘數。接下來的問題是:提出一個快捷的轉換算法(除了硬算,目前我沒想出其他辦法)。
谢谢您!
利用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
在此先謝謝你。因為你的提問,我花了一二天重溫數論知識,不過仍僅及皮毛。
一時間我也想不起哪位同事(都是電機系老師)從事數論研究,你最好還是請教數學系老師確認這個發現。
Bernoulli數存在代數式,見下文(式33)
http://mathworld.wolfram.com/BernoulliNumber.html
PS 可能是你的迴響包含過多的標點符號,故被系統誤判為垃圾。倘若下回再有這種情事,請另外張貼一句短語提醒我去垃圾中找回。
再次谢谢!
我原来的打算不是数论, 而是如何快速的提取信号中的目标.
变化后的目标(定义为一种变换), 与目标配适, 理论上,可以
对变换中的每组参数, 进行检验. 这跟找素数很像!
我想将变换空间投到目标所定义的一种本性空间中.
如知道孩子们在教室里即可,不需要知道哪个孩子
在哪个位置.
回头有些问题再请教!
好的,我也會將你提出的一連串問題放在心上慢慢琢磨。