Teorie matic

Mějme v tělese 𝔽 matice A∈𝔽d×d. Z lineární algebry už známe: determinant detA, stopu trA a charakteristický polynom

χA(t)=det(A−tI)=(−1)d(td−ad−1td−1−⋯−a1t−a0).

Ovšem nikdy jsme si nedokázali Jordanovu větu, takže to bude jeden z cílů tohoto předmětu.

Definice Nechť f(t)=(−1)d(td−ad−1td−1−⋯−a0)∈𝔽[t]. Potom matice
Af≔(ad−1ad−2⋯a1a010⋯0001⋯00⋮⋮⋱⋮⋮00⋯10)
je matice společnice (companion matrix) polynomu f.
Věta Pro každý polynom f∈𝔽[t] platí χAf=f.
Důkaz Provedeme rozvoj podle prvního řádku.
Definice Matice A,B∈𝔽d×d jsou podobné nad tělesem 𝔽, pokud existuje regulární matice R∈𝔽d×d taková, že R−1AR=B. Značíme A∼𝔽B.
Věta Nechť A,B∈𝔽d×d,A∼𝔽B. Potom
Důkaz Dokážeme jen první tvrzení, protože všechno už známe z lineární algebry.
R−1AR=BR−1AR(𝔽d)=B(𝔽d)R−1A(𝔽d)=B(𝔽d)
Jelikož vynásobením regulární maticí se nezmění dimenze, máme dimA(𝔽d)=dimB(𝔽d).
Definice Těleso 𝔽 je algebraické alias algebraicky uzavřené, pokud každý polynom z 𝔽[t] stupně alespoň 1 má kořen z 𝔽.
Věta Relace ∼𝔽 je ekvivalence.
Důkaz Triviální.
Věta Nechť A,B∈ℝd×d. Je-li A∼ℂB, potom A∼ℝB.
Důkaz Mějme regulární matici R∈ℂd×d takovou, že R1AR=B neboli AR=RB. Vyjádřeme si R≕P+iQ,P,Q∈ℝd×d. Potom A(P+iQ)=(P+iQ)B, takže i AP=PB a AQ=QB. Ovšem ani jedna z matic P,Q nemusí být regulární, takže ještě nejsme hotovi. Zkusíme najít lineární kombinaci, která regulární je. Definujme H(t)≔P+tQ. Existuje-li t∈ℝ takové, že detH(t)≠0, jsme hotovi, protože máme (H(t))−1AH(t)=B. Zjevně det(P+tQ) je polynom v t. Ten ale nemůže být nulový, protože víme, že když dosadíme i, vyjde detR, což je podle předpokladu nenulové.
Věta Nechť A∈ℝd×d. Potom |detA| je Lebesgueova míra množiny
M≔{∑i=1dαiA∘,i|αi∈[0,1]}.
Důkaz Míru počítáme jako
m(M)=∫⋯∫M1dβ1⋯dβd.
Provedeme substituci β→=Aα→. Z věty o substituci máme
m(M)=∫01⋯∫01|detA|dα1⋯dαd=|detA|.
Věta slabší verze Jordanovy Je-li 𝔽 algebraicky uzavřené těleso, potom každá matice je podobná horní trojúhelníkové matici.
Poznámka Toto je taky slabší verze Schurovy věty, kterou jsme si dokazovali na NMA1.
Důkaz Indukcí na d. Pro d=1 triviální. Mějme matici A∈𝔽d×d, její vlastní číslo λ a vlastní vektor x. Vezměme matici R, která má v prvním sloupci x a zbytek je doplněn jakkoli, aby byla regulární. Potom snadno dokážeme, že matice R−1AR má v prvním sloupci vektor (λ0⋯0)𝖳. Ukrojíme první sloupec a řádek a pomocí indukčního předpokladu najdeme matici R~, která zbytek transformuje na trojúhelníkovou. K této matici přidáme první řádek a sloupec, kde v levém horním rohu bude jednička a všude jinde 0, a vynásobíme ji zleva R. Tím dostaneme kýženou podobnostní matici.
Definice Nechť A∈𝔽d×d. Označme V≔d^ a
E≔{(i,j)∈V2|Ai,j≠0}.
Potom orientovaný graf (V,E) je graf matice A.
Definice Matice A∈𝔽d×d je rozložitelná, pokud existuje permutační matice P taková, že P𝖳AP=(BC0D), kde B,D jsou čtvercové matice nenulového rozměru.
Poznámka Obecně platí, že pokud řešíme nějakou úlohu, kde matice je rozložitelná, potom ji můžeme snadno převést na dvě úlohy s maticí menšího rozměru.
Cvičení Nechť A,B∈ℚd×d. Dokažte, že je-li A∼ℝB, potom A∼ℚB.
Cvičení Mějme matice A,B∈ℂd×d, které mají stejné spektrum včetně algebraických a geometrických násobností. Zjistěte, jestli nutně A∼ℂB.
Cvičení Pro matici M∈ℂd×d definujme GM≔{α∈ℂ|αM∼ℂM}.
  1. Určete GM pro M=(004000000).
  2. Nechť Mk≠0 pro každé k∈ℕ0. Dokažte, že GM je konečná.
  3. Dokažte, že GM je grupa na násobení.
Cvičení Nechť A∈ℂd×d. Dokažte, že pokud trA=0, potom A je podobná nějaké matici s nulovou diagonálou.
Cvičení Nechť A∈𝔽d×d. Dokažte, že [A]∼𝔽={A} (tedy A není podobná žádné jiné matici), právě když A=αI,α∈𝔽.
Cvičení Nechť G⊂ℤ2×2 je konečná grupa na násobení. Co můžeme říct o prvcích G ohledně determinantu, vlastních čísel, Jordanova tvaru a řádu v G?

Tenzorový součin

Definice Tenzorový součin matic A∈𝔽m×n,B∈𝔽o×p je matice A⊗B∈𝔽mo×np,
A⊗B≔(A⋅B1,1⋯A⋅B1,p⋮⋱⋮A⋅Bp,1⋯A⋅Bp,p).
Věta Mějme matice A∈𝔽m×n,B∈𝔽b×c,C∈𝔽n×o,D∈𝔽c×l. Potom
(A⊗B)⋅(C⊗D)=(A⋅C)⊗(B⋅D).
Důkaz Stačí si to rozepsat.
Důsledek Nechť A∈𝔽m×m,B∈𝔽n×n jsou regulární matice. Potom (A⊗B)−1=A−1⊗B−1.
Důkaz
(A⊗B)⋅(A−1⊗B−1)=AA−1⊗BB−1=Im⊗In=Imn.
Věta Tenzorový součin dvou horních/dolních trojúhelníkových matic je horní/dolní trojúhelníková matice.
Věta Nechť A∈ℂm×m,B∈ℂn×n. Potom σ(A⊗B)=σ(A)⋅σ(B).
Důkaz Převedeme obě matice do horního trojúhelníhového tvaru: A≕PA1P−1,B=QB1Q−1, kde P,Q jsou regulární a A1,B1 jsou horní trojúhelníkové. Potom A⊗B=(P⊗Q)⋅(A1⊗B1)⋅(P⊗Q)−1. Vidíme, že A1,B1 mají na diagonále vlastní čísla A,B a A1⊗B1 má na diagonále vlastní čísla A⊗B. Když si rozepíšeme, jak vypadá A1⊗B1, dostaneme první tvrzení věty.
Věta Nechť A∈ℂm×m,B∈ℂn×n,λ,μ∈ℝ∖{0}. Potom σ(λ⋅(A⊗In)+μ⋅(Im⊗B))=λ⋅σ(A)+μ⋅σ(B).
Důkaz Analogický jako u předchozí věty.
Věta Nechť A∈ℂm×m,B∈ℂn×n, e je vlastní vektor k α∈σ(A) a f je vlastní vektor k β∈σ(B). Potom e⊗f je vlastní vektor k α⋅β∈σ(A⊗B).
Důkaz
(A⊗B)⋅(e⊗f)=A⋅e⊗B⋅f=(α⋅e)⊗(β⋅f)=(α⋅β)⋅(e⊗f).
Věta Nechť A∈ℂm×m,B∈ℂn×n,λ,μ∈ℝ∖{0}, e je vlastní vektor k α∈σ(A) a f je vlastní vektor k β∈σ(B). Potom TBD: ??? je vlastní vektor k λ⋅α+μ⋅β∈σ(λ⋅(A⊗In)+μ⋅(Im⊗B)).
Důkaz Analogický jako u předchozí věty.
Věta Nechť A∈ℂm×m,B∈ℂn×n. Potom det(A⊗B)=(detA)n⋅(detB)m.
Důkaz Nechť α1,…,αm;β1,…,βn jsou vlastní čísla A;B včetně algebraických násobností. Potom
det(A⊗B)=∏i=1m∏j=1nαiβj=(∏i=1mαi)n⋅(∏j=1nβj)m=(detA)n⋅(detB)m.
Důsledek Je-li σ(A)∩σ(B)=∅, potom det(A⊗In−Im⊗B)≠0.
Věta Nechť pro i∈r^ je Ai∈ℂm×n,Bi∈ℂo×p a dále C∈ℂm×p. Potom rovnice
∑i=1rAi⋅X⋅Bi=C
má stejná řešení X∈ℂn×o jako rovnice
(∑i=1rAi⊗Bi𝖳)⋅[X]s=[C]s,
kde [⋅]s značí vektor vzniklý spojením sloupců matice pod sebe.
Důkaz Stačí uvažovat r=1, pro vyšší čísla to plyne z linearity. Máme
[A⋅X⋅B]s=[(A⋅X⋅,1⋯A⋅X⋅,o)⋅B]s=(∑i=1oA⋅Xi⋅Bi,1⋮∑i=1oA⋅Xi⋅Bi,p)=(A⊗B)[X]s.
Cvičení Nechť A⊗B=C⊗D≠0, kde A,C mají stejný rozměr. Dokažte, že existují čísla α,β taková, že α⋅β=1,A=α⋅C,B=β⋅D.
Cvičení Nechť A,B∈ℂn×n. Dokažte, že
  1. (ABBA)∼ℂ(A+B00A−B),
  2. h(A+B)≤h(A)+h(B).
Cvičení Nechť A∈ℂm×m,B∈ℂn×n. Dokažte, že
(AB0B0)∼ℂ(00BBA).
Z toho odvoďte, že AB a BA mají stejná nenulová vlastní čísla včetně algebraických násobností. Speciálně pro m=n mají stejná vlastní čísla včetně algebraických násobností.
Cvičení Nechť λ,μ∈ℂ. Určete Jordanův tvar matice J2(λ)⊗J3(μ), kde Jk(α) značí Jordanův blok řádu k s číslem α na diagonále.

Něco o grafech a rozložitelnosti

Věta Matice A∈ℂd×d není rozložitelná, právě když pro každé i,j∈d^ existuje v grafu A orientovaný sled z i do j.
Důkaz Dokážeme obměněnou ekvivalenci: A je rozložitelná ⟺ pro nějaké i,j neexistuje sled.
(⇒)
Díky struktuře matice máme disjunktní rozklad V=V1⊎V2 takový, že (v1,v2)∉E pro každé v1,2∈V1,2.
(⇐)
Pro dané i∈d^ definujme Vi≔{v∈V|i⇝v}. Zřejmě V1≠∅ a V2≔V∖V1≠∅. TBD
Věta Matice A∈ℂd×d je nerozložitelná, právě když (A+I)d−1>0.
Důkaz Plyne z předchozí věty a z poznatku, že umocnění matice sousednosti určuje počet sledů dané délky.
Věta Vlastní číslo λ matice A má algebraickou násobnost 1, právě k němu když existuje právě jeden lineárně nezávislý vektor u pro matici A, právě jeden lineárně nezávislý vektor v pro matici A𝖳 a platí v𝖳u≠0.
Důkaz Úvahou o podobnosti zjistíme, že to stačí dokázat pro matici v Jordanově tvaru. Pro tu to dokážeme snadno.

Nezáporné matice

Definice Nechť A∈ℂn×n. Potom definujeme její modul
m(A)≔(|A1,1|⋯|A1,n|⋮⋱⋮|An,1|⋯|An,n|).
Lemma Nechť A,B∈ℝn×n,m(A)≤B. Potom ρ(A)≤ρ(B).
Důkaz Předpokládejme pro spor, že pro nějaké s∈ℝ je ρ(A)>s>ρ(B). Označme P≔As,Q≔Bs. Potom pro každé k∈ℕ je podle trojúhelníkové nerovnosti m(Pk)≤(m(P))k≤Qk. Jelikož ρ(Q)<1, máme limk→∞Qk=0, tedy i limk→∞(m(P))k=0, což je spor s tím, že ρ(P)>0.
Důsledek Pro každou matici A∈ℝn×n platí ρ(A)≤ρ(m(A)).
Důkaz Stačí vzít B≔m(A).
Lemma Nechť A∈ℝn×n,z∈ℝn,ξ∈ℝ,A,z≥0,Az>ξz. Potom ρ(A)>ξ.
Důkaz Vezměme s∈ℝ takové, že Az>sz>ξz. Označme P≔As. Potom Pz>z. Opakovaným použitím této nerovnosti dostaneme Pkz>z pro každé k∈ℕ. Z toho plyne ρ(P)≥1 neboli ρ(A)≥s>ξ.
Lemma Perronovo Nechť A∈ℝn×n,A>0. Potom ρ(A)∈σ(A) a existuje k němu kladný vlastní vektor, který je jediný lineárně nezávislý.
Důkaz Vezměme vlastní číslo λ takové, že |λ|=ρ(A), tedy pro nějaké u∈ℝn,u≠0 je λu=Au. Aplikací m na obě strany rovnosti a použitím trojúhelníkové nerovnosti dostáváme ρ(A)m(u)=m(Au)≤Am(u). Kdyby nerovnost byla ostrá, potom by podle předchozího lemmatu bylo ρ(A)<ρ(A), což je blbost. Musí tedy platit rovnost, což znamená, že všechna čísla sečtená v trojúhleníkové nerovnosti mají stejný směr. Tudíž existuje η∈ℂ,|η|=1 takové, že v≔ηu≥0. Jelikož v≠0,A>0, máme λv=Av>0. Z toho plyne v>0 a také λ>0 neboli λ=|λ|=ρ(A). Zbývá dokázat, že v je jediný lineárně nezávislý vlastní vektor k vlastnímu číslu λ. Vezměme jiný vlastní vektor w. Pro nějaké k takové, že vk≠0, definujme z≔w−wkvk⋅v. Kdyby byly v,w lineárně nezávislé, potom z≠0, takže je to také vlastní vektor k λ a stejnou logikou můžeme dokázat, že m(z)>0. To je ale spor s tím, že zk=0.
Věta Perronova-Frobeniova Nechť A∈ℝn×n,n≥2,A≥0 je nerozložitelná. Potom ρ(A)∈σ(A) s algebraickou násobností 1 a existuje k němu kladný vlastní vektor. Zároveň k žádnému jinému vlastnímu číslu neexistuje nezáporný vlastní vektor.
Důkaz Podle nějaké věty je B≔(I+A)n−1>0, tedy i B𝖳>0. Z Perronova lemmatu existuje y∈ℝn,y>0 takové, že B𝖳y=ρ(B)y neboli y𝖳B=ρ(B)y𝖳. Vezměme vlastní číslo λ splňující |λ|=ρ(A) a k němu příslušný vlastní vektor x. Označme u≔m(x). Potom opět podle trojúhelníkové nerovnosti ρ(A)u=m(Ax)≤Au. Opakovaným použitím nerovnosti dostaneme (ρ(A))ku≤Aku pro každé k∈ℕ0. Z toho plyne
(1+ρ(A))n−1u=∑k=0n−1(n−1k)(ρ(A))ku≤∑k=0n−1(n−1k)Aku=Bu.
Vynásobením zleva y𝖳 dostáváme (1+ρ(A))n−1y𝖳u≤y𝖳Bu=ρ(B)y𝖳u. Jelikož x≠0,y>0, máme y𝖳u>0, takže můžeme vydělit a dostáváme (1+ρ(A))n−1≤ρ(B). Podle nějaké věty existuje μ∈σ(A) takové, že ρ(B)=|(1+μ)n−1|. Odmocněním a trojúhelníkovou nerovností dostáváme
1+ρ(A)≤|1+μ|≤1+|μ|≤1+ρ(A).
Musí tedy ve všech nerovnostech platit rovnost. Z toho plyne |μ|=ρ(A) a zároveň μ≥0, tedy μ=ρ(A). Také v nerovnostech, které jsme sumili, platí rovnost, takže speciálně μu=ρ(A)u=Au. Zároveň Bu=(1+μ)n−1u=ρ(B)u. Z Perronova lemmatu plyne u>0. Našli jsme tedy kladný vlastní vektor k u, pro který analogicky jako u Perronova lemmatu můžeme dokázat, že je jediný lineárně nezávislý. Nechť ξ≠μ je jiné vlastní číslo matice A a z je příslušný vlastní vektor. Podle již dokázaného existuje v>0 takové, že A𝖳v=μv neboli v𝖳A=μv𝖳. Máme tedy v𝖳Az=μv𝖳z a zároveň v𝖳Az=ξv𝖳z. Odečtením rovností dostaneme 0=(μ−ξ)v𝖳z. Jelikož μ≠ξ, musí být v𝖳z=0, a protože u>0, nemůže být zároveň z≥0. Zbývá dokázat, že μ má jako vlastní číslo A algebraickou násobnost 1. To nějak plyne ze Schurovy věty a z toho, že v𝖳u>0.
Věta Nechť A∈ℝn×n,A≥0 je nerozložitelná a h∈ℕ. Potom následující tvrzení jsou ekvivalentní:
  1. Existuje právě h vlastních čísel λ∈σ(A) takových, že |λ|=ρ(A).
  2. Existuje permutační matice P taková, že jde psát blokově PAP𝖳=(0B10⋯000B2⋯0⋮⋮⋮⋱⋮000⋯Bh−1Bh00⋯0).
  3. Největší společný dělitel délek všech cyklů v G(A) je h.
  4. Je-li χA(t)=(−1)ntn+∑i=1sknitni, kde kni≠0, potom
    nsd(n−n1,n1−n2,…,ns−1−ns)=h.
  5. h=max{k∈ℕ|σ(exp2πikA)=σ(A)}.
Lemma Nechť A∈ℝn×n,A≥0 je nerozložitelná. Je-li sρ(A) vlastní číslo A pro |s|=1, potom existuje diagonální matice D taková, že m(D)=I a AD=sDA. Naopak, pokud nějaké s,|s|=1 existuje taková matice D, potom sρ(A)∈σ(A). Navíc je-li u Perronův vlastní vektor k ρ(A), potom Du je vlastní vektor k sρ(A), tedy ADu=sρ(A)u.
Důkaz Nechť z je vlastní vektor k vlastnímu číslu sρ(A). Potom ρ(A)m(z)=m(sρ(A)z)=m(Az)≤Am(z). Z Perronovy-Frobeniovy věty máme y>0 takový, že A𝖳y=ρ(A)y neboli y𝖳A=ρ(A)y𝖳. Potom ρ(A)y𝖳m(z)≤y𝖳Am(z)=ρ(A)y𝖳m(z), takže v první nerovnosti platí rovnost, tudíž m(z)>0 je vlastní vektor. Jistě existuje diagonální matice D taková, že m(D)=I,z=Dm(z). Potom Az=sρ(A)z=sρ(A)Dm(z)=ADm(z). TBD
Věta Nechť A∈ℝn×n,A≥0. Potom ρ(A)∈σ(A) a existuje k němu nezáporný vlastní vektor.