uestc08暑假集訓(xùn)3.數(shù)學(xué)矩陣操作

矩陣操作唐文斌基本概念矩陣的定義Mm*n(R)方陣

矩陣的轉(zhuǎn)置行/列向量向量的定義

基本概念特殊矩陣(方陣)對(duì)角矩陣非主對(duì)角元全為0記為diag(a11,a22…,ann)三對(duì)角矩陣若|i-j|>1,則aij=0上/下三角矩陣若i>j,則aij=0(上三角)對(duì)稱(反對(duì)稱)矩陣A=AT

A=-AT排列矩陣零矩陣,單位矩陣,數(shù)乘矩陣,初等變換矩陣矩陣運(yùn)算加法(減法)A+B,A-B=A+(-B)結(jié)合律,交換律數(shù)乘kA結(jié)合律,對(duì)于加法的分配律(線性映射)矩陣乘法交換律?結(jié)合律?Example矩陣的作用線性映射(線性函數(shù)f)Fibnacci遞推坐標(biāo)旋轉(zhuǎn)變換二次曲線二次一般方程:二元關(guān)系圖論應(yīng)用Floyd關(guān)聯(lián)矩陣求解方程組[矩陣應(yīng)用][例](UVa???) [問題描述]已知P=a+b,Q=a*b求an+bnP,Q,n均為整數(shù)[Sample]P=3,Q=2,n=3an+bn=9[矩陣應(yīng)用][例](UVa???) P=a+bQ=a*b=(P–b)*b=-b2+P*bb2–P*b+Q=0Sob=(P+Sqrt(P*P–4*Q))/2a=(P–Sqrt(P*P–4*Q))/2Done?[矩陣應(yīng)用][例](UVa???) Butif…P=1,Q=10?an+bn=(a+b)*(an-1+bn-1)–(a*bn-1+b*an-1)=P*(an-1+bn-1)-Q*(an-2+bn-2)設(shè)Fn=an+bn,則Fn=P*Fn-1–Q*Fn-2[矩陣應(yīng)用][例]Sgu196考慮包含N個(gè)點(diǎn)M條邊的無向圖G=(V,E)關(guān)聯(lián)矩陣An*m=(aij)n*m如果頂點(diǎn)i是第j條邊的一個(gè)端點(diǎn),則aij=1否則aij=0求矩陣A*AT的元素和拓展:求矩陣AT*A的元素和[矩陣應(yīng)用][例]Sgu196求ATA將A行分塊為(x1,x2…xn)T則(cij)n*n=ATA

滿足cij

為xi與xj的標(biāo)準(zhǔn)內(nèi)積i==jcij為2i!=jcij為邊i與邊j的公共點(diǎn)個(gè)數(shù)=1(邊i與邊j交于某一點(diǎn))=0(否則)[矩陣應(yīng)用][例]Sgu196求AAT將A行分塊為(x1,x2…xn)T則(cij)n*n=AAT

滿足cij

為xi與xj的標(biāo)準(zhǔn)內(nèi)積i==jcij為點(diǎn)i的度數(shù)i!=jcij為點(diǎn)i與點(diǎn)j之間的邊數(shù)More?[矩陣應(yīng)用]高斯消元法求解線性方程組Example:矩陣表示:Ax=bA :系數(shù)矩陣x :未知數(shù)向量 (A,b):增廣矩陣[矩陣應(yīng)用]高斯消元法消元過程通過三種操作,將方程組化為形式更簡(jiǎn)單的同解方程組;即將增廣矩陣(A,b)化為階梯形矩陣(上三角矩陣).將某一行乘以一個(gè)非零常數(shù)將某一行乘以一個(gè)非零常數(shù)后加到另一行交換兩行多解?無解?缺乏理性認(rèn)識(shí)矩陣的逆(乘法逆運(yùn)算)方陣:Mn(R)單位矩陣:En=diag(1,1,1…1)A∈Mm*n(R),則EmA=AEn

=AAn*n的逆A-1滿足AB=BA=E,則A可逆,B稱為A的逆,記為A-1矩陣的逆唯一,Why?性質(zhì):可逆矩陣的乘積仍可逆數(shù)乘性質(zhì),(AB)-1=B-1A-1矩陣乘法樸素乘法復(fù)雜度:O(n*m*t)Strassen算法(求兩個(gè)n*n的矩陣的乘積)O(nLog7)分治思想矩陣乘法的Strassen算法令n為2的冪(補(bǔ)0即可).將A,B,C都分塊為4個(gè)n/2*n/2的矩陣矩陣乘法的Strassen算法復(fù)雜度:上述計(jì)算方法,共有8次遞歸調(diào)用與4次加法So,Then,矩陣乘法的Strassen算法令矩陣乘法的Strassen算法復(fù)雜度:上述計(jì)算方法,共有7次遞歸調(diào)用與18次加法So,Then,矩陣乘法的Strassen算法復(fù)雜度優(yōu),但是常數(shù)巨大Coppersmith-Winograds算法:O(nLog5)常數(shù)更大……矩陣的初等變換使用高斯消元求解線性方程組時(shí),我們對(duì)增廣矩陣所作的是3種行初等運(yùn)算:1)將矩陣的某一行乘以一個(gè)非零常數(shù)c2)將矩陣的某一行乘以一個(gè)非零常數(shù)c加到另一行3)交換矩陣中的某兩行這三種初等運(yùn)算統(tǒng)稱為矩陣的行初等變換(1)稱為倍乘行變換

(2)稱為倍加行變換

(3)成為對(duì)換行變換相應(yīng)的,我們還可以定義初等列變換矩陣的初等變換[定義]初等矩陣:將單位矩陣E作一次初等變換(行/列)所得到的矩陣與三種初等行/列變換所對(duì)應(yīng)的初等矩陣為:將E第i行(或列)乘c,得到初等倍乘矩陣Ei(c)將E第i行乘以c加到第j行,或?qū)⒌趈列乘以c加到第i列,得到初等倍加矩陣Eij(c)將E的第i,j行(或列)交換,得到初等對(duì)換矩陣Eij矩陣的初等變換Example矩陣的初等變換初等矩陣的性質(zhì):將矩陣A左乘初等矩陣,等同作相應(yīng)的行初等變換將矩陣A右乘初等矩陣,等同作相應(yīng)的列初等變換初等矩陣都是可逆矩陣矩陣的初等變換[定理]對(duì)于一個(gè)可逆矩陣A,可以作若干次初等行變換將其化為單位矩陣E,即存在初等矩陣P1,P2…Pk,使得

Pk….P2P1A=E

[證明]???[推論A]可逆矩陣A可以表示為若干個(gè)初等矩陣的乘積[推論B](A,E)(E,A-1)一個(gè)求逆的算法矩陣求逆的初等變換法算法步驟(由推論B)將矩陣(A,E)進(jìn)行行初等變換當(dāng)A變成E時(shí),E就變成了A-1O(n3)Example:矩陣求逆的樸素算法:高斯消元,O(n4)基本概念[線性空間]V(R)是一個(gè)向量集合,稱為實(shí)數(shù)域上的一個(gè)線性空間,如果滿足:對(duì)于任意向量a,b∈V(R),任意k1,k2∈R有

k1a+k2b

∈V(R)性質(zhì):運(yùn)算封閉線性性質(zhì)[線性相關(guān)性]V(R)中的一組向量{x1,x2…xn},若存在不全為零的數(shù)k1,k2...kn,使

k1x1+k2x2+…knxn

=0則稱x1,x2…xn線性相關(guān).否則稱其線性無關(guān).基本概念[線性表示]若向量x=k1x1+k2x2+…knxn,則稱向量x可由x1,x2…xn線性表示.[定理]V(R)中的一組向量{x1,x2…xn}線性相關(guān)的充要條件是x1,x2…xn中有一個(gè)向量可用其他向量線性表示.[證明][定理*]若向量組{x1,x2…xn}線性無關(guān),而{x1,x2…xn,y}線性相關(guān),則y可由x1,x2…xn線性表示且表示法唯一.[證明]基本概念[線性空間的基與維數(shù)]V(R)中的一組向量{x1,x2…xn}線性無關(guān),且V(R)中的任意向量都可由{x1,x2…xn}線性表示.則稱{x1,x2…xn}是V(R)的一組基,n稱為V(R)的維數(shù),記為dimV(R).[向量組的秩]S是V(R)的一個(gè)子集,若S的一個(gè)子集B={x1,x2…xk}線性無關(guān),且S中任意向量都可由B線性表示,則稱B為其極大線性無關(guān)組,k稱為S的秩,記為r(S)[向量組張成的空間]向量組S={x1,x2…xk}張成的空間L(S)為S中向量所有線性組合的集合.基本概念[等價(jià)向量組]向量組A={x1,x2…xs},B={y1,y2…yt}稱為等價(jià),若A中任意向量可由B線性表示且B中任意向量可由A線性表示.[引理]向量組A={x1,x2…xs}線性無關(guān),B={y1,y2…yt}且t>s.如果B中每一個(gè)向量都可由A線性表示,則B線性相關(guān).[定理]等價(jià)向量組必有相同的秩.[推論]初等變換不改變矩陣的秩(后面的定理)基本概念[標(biāo)準(zhǔn)內(nèi)積]n維空間V(R)中的兩個(gè)向量x,y:x=(a1,a2…an),y=(b1,b2…bn),定義其標(biāo)準(zhǔn)內(nèi)積

(x,y)=a1b1+a2b2+…+anbn[正交(垂直)向量]稱V(R)中的兩個(gè)向量x,y正交,如果(x,y)=0.記為x┴y[單位正交基]設(shè)B={e1,e2…en}是n維空間V(R)的一個(gè)子集,稱為V(R)的一組單位正交基,如果:

為什么e1,e2…en線性無關(guān)?

自然基e1….en基本概念[子空間]W稱為V的一個(gè)子空間,如果W是一個(gè)線性空間,且是V的一個(gè)子集.[子空間的正交]設(shè)W1和W2都是V的子空間,如果對(duì)于任意向量x∈W1,y∈W2均有x

┴

y,則稱W1與W2正交,記為W1

┴

W2.Schmidt正交化[定理]V(R)必有單位正交基.[證明]構(gòu)造矩陣的秩[矩陣的秩,列秩,行秩]對(duì)于矩陣Am*n列秩:n個(gè)列向量的秩行秩:m個(gè)行向量的秩矩陣的秩:定義為矩陣的列秩,記為r(A)[定理]初等變換不改變矩陣的秩[定理(弱)]初等行(列)變換不改變矩陣的行(列)秩[定理]Am*n的列秩=A的行秩[證明]行列式[行列式的起源]二元一次方程組行列式行列式[行列式的公理化定義]實(shí)數(shù)域R上的一個(gè)n階行列式是取值于n個(gè)n維列向量x1,x2…xn的一個(gè)函數(shù),而且對(duì)于任意xi,yi,k滿足:D(x1,…,kxi,…,xn)=kD(x1,…,xi,…,xn)D(x1,…,xi+yi,…,xn)=

D(x1,…,xi,…,xn)+D(x1,…,yi,…,xn)D(x1,…,xi,…,xj…,xn)=-D(x1,…,xj,…,xi…,xn)D(e1,…,en)=1(e1,…,en為Rn的自然基)記為Det(A)或|A|行列式的計(jì)算[性質(zhì)一]如果有一列為0,則行列式為0[性質(zhì)二]如果有兩列相同,則行列式為0[性質(zhì)三]如果有兩列對(duì)應(yīng)成比例,則行列式為0[性質(zhì)四]倍加列變換不改變行列式的值[性質(zhì)五]若x1,x2…xn線性相關(guān),則行列式為0[性質(zhì)六]|AT|=|A|上述性質(zhì)對(duì)于行也成立[性質(zhì)七]上三角(下三角)矩陣的行列式等于其主對(duì)角元元素乘積[證明]性質(zhì)一性質(zhì)七行列式計(jì)算(Ex.)Laplace展開定理[代數(shù)余子式]在n階行列式D=|aij|n*n中,去掉元素aij所在的第i行與第j列得到的n-1階行列式,稱為元素aij的余子式,記為Mij.并把數(shù)Aij=(-1)i+jMij稱為其代數(shù)余子式.[展開定理]n階行列式D=|aij|n*n等于它的任意一行(或列)的所有元素與它們的代數(shù)余子式的乘積之和:方陣乘積的行列式[定理]A,B均為n階方陣.則

|AB|=|A|*|B|[證明][定理]n階方陣A可逆的充要條件是|A|≠0[證明]1=|E|=|A|*|A-1|構(gòu)造伴隨矩陣A*行列式秩[子式]n階矩陣An*n,我們順序選擇任意的k行與k列,并選擇這k行與k列交點(diǎn)的k2個(gè)元素得到一個(gè)k階矩陣B.則稱det(B)為det(A)的一個(gè)k階子式.[矩陣的行列式秩]若A存在一個(gè)k階子式非零,且所有的k+1階子式均為0.則稱A的行列式秩為k.記為rdet(A).[定理]對(duì)于n階矩陣A,r(A)=rdet(A)[證明]Cramer法則[Cramer法則]線性方程組AX=b,若系數(shù)行列式D=|A|≠0,則方程組解唯一且其中Dj是將系數(shù)矩陣第j列用b替換得到的行列式再談線性方程組[定理]若齊次線性方程組AX=0,系數(shù)矩陣r(A)=r,則其解空間N(A)是一個(gè)n-r維的子空間.[證明](略)[基礎(chǔ)解系]齊次線性方程組AX=0解空間N(A)的基[求解方法]再談線性方程組[非齊次線性方程組]對(duì)于非齊次線性方程組AX=b,下列命題等價(jià):1)AX=b有解2)b可被A的列向量線性表示3)r(A)=r(A,b)[推論]AX=b有唯一解的充要條件為:

r(A)=r(A,b)=A的列數(shù)再談線性方程組[非齊次線性方程組的求法]特解+通解無解與多解特征值與特征向量[定義]設(shè)矩陣A是n階矩陣,如果存在數(shù)及非零向量X,使得

AX=X則稱是A的一個(gè)特征值,X是A屬于特征值的特征向量.AX=X

?(E-A)X=0,又X是非零向量

?

(E-A)X=0有非零解?

r(E-A)<n

?det(E-A)=0[矩陣A的特征多項(xiàng)式]f()=det(E–A)特征值與特征向量[特征子空間]矩陣A的特征值所對(duì)應(yīng)的特征子空間為所有屬于的特征向量集合與{0}的并.[特征值與特征子空間的求法]求特征值:特征多項(xiàng)式det(E–A)=0求特征子空間(求一組基):

對(duì)于特定的,求(E–A)X=0的基礎(chǔ)解系對(duì)角化及其條件[矩陣的對(duì)角化]對(duì)于n階矩陣A,如果存在n階可逆矩陣P使得P-1AP=diag(1,…n),則稱A可對(duì)角化,稱P為A的對(duì)角變換矩陣.[矩陣可對(duì)角化的條件]不妨假設(shè)A可以對(duì)角化,則即設(shè)P=(X1,X2,…,Xn)(列分塊),則對(duì)角化及其條件則有AXi=iXi

(i=1,2,…n)故:X1,X2