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 společnice (companion matrix) polynomu f je
Af≔(ad−1ad−2⋯a1a010⋯0001⋯00⋮⋮⋱⋮⋮00⋯10).
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.

Jordanova věta

Definice Matice J∈ℂn×n je v Jordanově tvaru, pokud
J=(Jd1(λ1)⋯0⋮⋱⋮0⋯Jdk(λk)),kdeJd(λ)≔(λ10⋯00λ1⋯0⋮⋮⋱⋱⋮000λ10000λ)}dřádků.
Lemma Je-li matice A v Jordanově tvaru a μ∈ℂ, potom A+μI je v Jordanově tvaru.
Důkaz Triviální.
Lemma Je-li A∈ℂn×n a μ∈ℂ, potom σ(A+μI)=σ(A)+μ.
Důkaz Triviální.
Věta Nechť A∈ℂn×n,0∈σ(A). Označme V≔ℂn. Potom existují podprostory V0,V1⋐V takové, že
  1. V0⊕︎V1=V,
  2. AV0⊂V0,
  3. AV1=V1,
  4. σ(A|V0)={0}.
Důkaz Jistě existuje takové k∈ℕ, že Ak+1V=AkV. (Kdyby pro spor neexistovalo, potom dimV>dimAV>dimA2V>⋯, což v prostoru konečné dimenze nejde.) Vezměme nejmenší takové k a položme V0≔kerAk,V1≔AkV. Zbývá ověřit kýžené vlastnosti.
  1. Z druhé věty o dimenzi pro každé i≥k platí d(Ai)=n−h(Ai)=n−h(Ak)=d(Ak). TBD
  2. Nechť y∈AV0, tedy y=Ax,x∈kerAk. Potom Aky=Ak+1x=0, tudíž y∈kerAk=V0.
  3. Plyne přímo z definice.
  4. Nechť Ax=μx pro nějaké nenulové x∈V0.
Lemma Nechť A∈ℒ(P). Označme m≔d(A),n≔h(A). Nechť x1,…,xm je báze kerA, y1,…,yn je báze A(P) a z1,…,zn jsou vektory takové, že yj=Azj. Potom x1,…,xm,z1,…,zn je báze P.
Důkaz Počet vektorů sedí, stačí tedy ověřit, že jsou lineárně nezávislé. Předpokládejme, že platí
0=∑i=1mαixi+∑j=1nβjzj.
Vynásobením A dostaneme
0=∑i=1mαiAxi+∑j=1nβjAzj=∑j=1nβjAzj.
Z toho plyne βj=0. Tedy i αi=0.
Věta Pro každou matici A∈ℂn×n,σ(A)={0} existuje matice J∈ℂn×n v Jordanově tvaru taková, že A∼J.
Důkaz Zkonstruujeme množinu S⊂V takovou, že
  • pro všechny w∈S existuje životnost iw∈ℕ taková, že Aiww=0, ale Aiw−1w≠0,
  • množina {Ajw|w∈S,0≤j<iw−1} je báze V.
Potom definujeme-li
R≔(Aiw1−1w1⋯Aw1w1Aiw2−1w2⋯Aw2w2⋯wk),
bude platit AR=RJ, kde J je Jordanova matice s bloky Jiw1(0),…,Jiwk(0). Pojďme nyní takovou množinu S najít. Jelikož σ(A)={0}, jistě existuje k∈ℕ takové, že
A0(V)⋑≠A1(V)⋑≠⋯⋑≠Ak(V)={0}.
Podle druhé věty o dimenzi pro každé i∈ℕ platí
dimAi(V)=dimAi+1(V)+d(A|Ai(V)),
přičemž
d(A|Ai(V))=dim(kerA∩Ai(V))≕di.
Vidíme, že 0=dk≤dk−1≤⋯≤d0=h(A). Označme ni≔di−1−di. Je-li 𝒳︀ báze AiV, potom Ai−1V má bázi 𝒳︀∪{z1,…,zni}. Jistě najdeme x1,…,xni takové, že zl=Ai−1xl. Z takovýchto vektorů xl sestavíme množinu S.
Věta Jordanova Pro každou matici A∈ℂn×n existuje matice J∈ℂn×n v Jordanově tvaru taková, že A∼J.
Důkaz Indukcí na počtu různých vlastních čísel. Je-li σ(A)={λ}, definujme B≔A−λI. Potom σ(B)={0}, takže podle předchozí věty je R−1BR=J, kde J je v Jordanově tvaru. Potom R−1AR=J+λI, takže A je také v Jordanově tvaru. Tím jsme dokázali základní případ. Nechť dále λ,μ∈σ(A),λ≠μ. Definujme opět B≔A−λI. Potom 0∈σ(B), takže podle věty najdeme podprostory V0,V1 takové, že V0⊕︎V1=V, BV0⊂V0, BV1=V1 a σ(B|V0)={0}. Nechť a1,…,an0 je báze V0 a b1,…,bn1 je báze V1. Označme R≔(a1⋯an0b1⋯bn1). Potom BR=(Ba1⋯Bbn1)=R(B000B1) pro nějaké B0∈ℂn0×n0,B1∈ℂn1×n1. Podle indukčního předpokladu je R0−1B0R0=J1,R1−1B1R1=J2 pro R0,R1 regulární a J0,J1 v Jordanově tvaru. Definujme-li L≔R(R000R1), potom L−1BL=J, kde J je v Jordanově tvaru. Z toho plyne L−1A=J+λI, čímž je tvrzení dokázáno.

Algoritmy pro násobení matic

Násobení matic podle definice má složitost 𝒪︀(n3) (kde n je řád matice). Nešlo by to nějak rychleji? Ukážeme si Stressenův algoritmus, který má složitost 𝒪︀(nlog27)≈𝒪︀(n2.83). Jsou známé i algoritmy s lepší asymptotickou složitostí, ale v praxi se nepoužívají.

Pojďme si vynásobit dvě 2×2 matice:

(A1,1A1,2A2,1A2,2)⋅(B1,1B1,2B2,1B2,2)=(C1,1C1,2C2,1C2,2).
Definujeme
N1≔A1,1⋅B1,1,N2≔A1,2⋅B2,1,S1≔A2,1+A2,2,S2≔S1−A1,1,S3≔A1,1−A2,1,S3≔A1,2−S2,S5≔B1,2−B1,1,S6≔B2,2−S5,S7≔B2,2−B1,2,S8≔B2,1−S6,N3≔S1⋅S5,N4≔S2⋅S6,N5≔S3⋅S7,N6≔S4⋅B2,2,N7≔A2,2⋅S8,S4≔N1+N4,S10≔S9+N3,S11≔S9+N5.
Potom platí
C1,1=N1+N2,C1,2=S10+N6,C2,1=S11+N7,C2,2=S10+N5.
Zdánlivě to vypadá, že jsme si zbytečně ztížili práci. Ale všimněme si, že jsme provedli jen 7 násobení, zatímco při postupu z definice by se jich provedlo 8. Pokud matice obsahuje čísla, tak je nám to k ničemu, ale pointa je v tom, že můžeme vzít matici 2n×2n, rozdělit ji na čtyři bloky a postup použít na ně. Ukážeme si, že když to takto budeme provádět rekurzivně, dosáhneme požadované složitosti.

Co když máme matici, jejíž řád není mocnina dvojky? Jedna možnost je doplnit ji nulami (static padding). Ale tím ji můžeme zvětšit skoro čtyřikrát. Lepší možnost je dynamic padding – matici sudého řádu vždy necháme být a matici lichého řádu doplníme o jeden řádek a sloupec.

Označme T(n) počet operací při použití algoritmu na matice řádu n=2k. Máme celkem 7 násobení a 15 sčítání, takže platí

T(n)=7⋅T(n2)+15⋅(n2)2.
Rekurzivním rozepsáním se základním případem T(1)=1 dostaneme
T(n)=7k+15⋅∑i=1k7i−1⋅22(k−i)=7k+154⋅n2⋅(74)k−174−1=nlog27+5n2(nlog27−2+1)=6nlog27−5n2.
Zároveň vidíme, že ani není potřeba moc velké n na to, aby byl algoritmus rychlejší.