Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy
Lineární algebra II látka z II. semestru informatiky MFF UK dle přednášek Jiřího Fialy
Zpracovali: Jan „Zaantar“ Štětina, Ondřej „Keddie“ Profant
Obsah Determinanty...............................................................................................................................................................................................2 Geometrický význam determinantu.......................................................................................................................................................4 Polynomy.....................................................................................................................................................................................................4 Vlastní čísla a vlastní vektory......................................................................................................................................................................6 Charakteristický mnohočlen........................................................................................................................................................................6 Prostory se skalárním součinem................................................................................................................................................................10 Ortogonalita..........................................................................................................................................................................................11 Ortogonální doplněk............................................................................................................................................................................12 Pozitivně definitní matice....................................................................................................................................................................13 Bilineární a kvadratické formy..................................................................................................................................................................14
1
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy
Determinanty Opakování: Permutace na n prvcích je zobrazení p : {1,... , n} {1,... , n} , které je prosté a na. S n značí množinu všech permitací na n prvcích. S n ,° tvoří grupu (existují neutrální prvek, identita a všechny inverzní permutace). Inverze v permutaci je dvojice i,j taková, že i j a p i p j . Znaménko permutace p je sgn p=−1 # inverzí v p . Sudé permutace tvoří normální podgrupu S n ; Faktorgrupa je izomorfní grupě {1,−1 },⋅ . Def:
Nechť A je čtvercová matice řádu n nad tělesem K, potom determinant matice A je dán výrazem n
det A:= ∑ sgn p⋅∏ ai , p i . p∈S n
i=1
Formálně jde o zobrazení K m×n K . Determinanty matic se značí ☼:
∣ ∣ místo det . 0 1 1 0
0 1 1 0
T
det A =det A n
Důkaz:
n
n
−1 det AT = ∑ sgn p⋅∏ AT i , p i= ∑ sgn p⋅∏ AT p i ,i = ∑ sgn p ⋅∏ a j , p
−1
p ∈S n
i=1
p ∈S n
j=1
p ∈S n
*
j=1
j
=det A
(*) víme, že j= p i; i= p−1 j a sgn p= sgn p−1 . Q.E.D.
Důsl.: ☼:
Pokud řádková úprava nemění determinant, pak ani stejná sloupcová úprava jej nezmění.
Přerovnání sloupců matice A podle permutace q (a) nezmění determinant, pokud sgnq=1 (b) změní znaménko determinantu, pokud sgnq=−1 Důkaz:
Budiž
A původní matice, B přerovnaná matice. n
n
det B = ∑ sgn p⋅∏ bi , p i= ∑ sgn p⋅∏ a i ,q p ∈S n
i =1
p ∈S n
i=1
−1
p i
, protože b i ,q j =a i , j ; bi , j=a i ,q
−1
j
, a dále se rovná
n
∑ sgn q⋅sgn q−1 ⋅sgn p⋅∏ a i ,q
p ∈Sn
i=1
−1
p i
, kde vždy sgn q⋅sgn q−1 =1 a sgn q−1⋅sgn p= sgn q−1 ° p , takže
n
sgn q⋅ ∑ sgn q−1 ° p ⋅∏ a i ,q
−1
p ∈S n
Důsl.:
i=1
p i
= sgn q⋅det A . Q.E.D.
(a) záměna dvou řádků změní znaménko, (b) jsou-li dva řádky matice A shodné, potom det A=0 .
Tvrz.: Determinant matice je lineárně závislý na každém řádku matice. Důkaz:
Na i-tém řádku provedeme
(a) skalární násobek řádku (b) součet dvou řádků
(a) Linearita vůči násobku. Budiž A původní matice, A' pozměněná matice (i-tý řádek vynásobený t∈ K ). Pak
det A' = ∑ sgn p ⋅a ' 1, p 1 ⋅...⋅a' t⋅ai , p i ⋅...⋅a n , p n =t⋅det A . i , p i ⋅... ⋅a ' n , p n = ∑ sgn p⋅a 1, p 1 ⋅...⋅ p ∈S n
(b) Linearita vůči sčítání. Budiž A původní matice. Zkonstruujeme B,C předpisem
p∈S n
∀ j ∀ k ≠i:a k , j =bk , j =ck , j , ∀ j : a i , j =bi , jc i , j .
Pak
det A= ∑ sgn p⋅a 1, p 1 ⋅...⋅a i , p i⋅...⋅a n , p n = ∑ sgn p ⋅a 1, p 1⋅...⋅bi , p ic i , p i ⋅...⋅a n , p n = p∈S n
p ∈S n
= ∑ sgn p⋅a1, p 1⋅...⋅b i , p i ⋅... ⋅a n , p n ∑ sgn p⋅a1, p 1⋅...⋅c i , p i⋅...⋅a n , p n =det B det C . Q.E.D. p ∈S n
Důsl.:
p ∈S n
Přičtení t-násobku j-tého řádku k i-tému (pro i≠ j ) nemění determinant matice. Důkaz:
obrázkem
Postup: Výpočet determinantu Převedením na odstupňovaný tvar přičtením násobků ostatních řádků, ale nesmíme prohazovat řádky ani násobit t∈ K , zato můžeme provádět úpravy i na sloupcích. (přednáška 2.3.09)
2
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy Věta:
Nechť A a B jsou čtvercové matice stejného řádu nad K, potom platí det A⋅B=det A⋅det B . Důkaz: (a) E 1 odpovídá vynásobení i-tého řádku t≠0 Je-li A nebo B singulární, pak A⋅B je singulární. 1 ´ Některý řádek singulární matice lze složit lineární kombinací ostatních, ⇒ determinant součinu t-krát vzroste: det E 1= ´ odečtením této kombinace získáme matici s nulovým řádkem a stejným ´ 0 determinantem =0 . Je-li A regulární, lze ji rozložit na součin elementárních matic (b) E 1 odpovídá přičtení j-tého řádku k i-tému. A=E 1⋅...⋅E k . 1 ´
∣ ∣ ∣ ∣
*
⇒ determinant součinu se nezmění: det E 1=
Potom platí det A⋅B =det E ⋅...⋅E ⋅B=det E ⋅ E ⋅...⋅E ⋅B = 1 k 1 2 k *
= det E 1 ⋅det E 2⋅...⋅E k⋅B . Ad. *, máme dvě možnosti.
Důsl.:
´ ⋱ ´ ´ ´
´ ´ 0 ´ ´ ´ t ´ ´ =t ´ ⋱ ´ ´ ´ 1
´ ´ 0 ´ ⋱ ´ 1 ´ ´ ´ ⋱ ´ ´ =1 ´ ´ ´ ⋱ ´ 0 ´ ´ ´ 1
Tedy det E 1⋅...⋅det E k ⋅det B =det E 1⋅...⋅E k ⋅det B=det A⋅det B . Q.E.D.
(a) Čtvercová matice A je regulární, právě když det A≠0 . (b) det A− 1=det a −1 , respektive det A⋅det A−1 =1 .
Značení: Ai , j značí matici, která vznikne z matice A vypuštěním i-tého řádku a j-tého sloupce. Tvrz.: Rozvoj determinantu podle i-tého řádku. Pro libovolnou matici A řádu n≥2 a libovolné i ∈{1 , ... , n} n
platí det A=
∑ a i , j⋅−1i j⋅det Ai , j . j =1
Pozn.,
toto je efektivní pro řádky s n−1 nulami. Důkaz: (a) Vytýkání prvků a i , j z předpisu pro determinant – nebudeme dokazovat (b) Využití linearity: zapíšeme i-tý řádek jako vhodnou lineární kombinaci: T
e1
a i,1 , ..., a i , n=a i,1⋅1,0 ,... , 0a i ,2⋅0,1 , ..., 0...a i , n⋅0,0 ,... , 1
∣ ∣
∣ ∣ ∣∣
det ai ,1
...
ai , n
=a i ,1⋅det 1
... 0
∣ ∣ ∣∣ ∣∣
...a i , n⋅det
Zbývá určit: det 0
... 1 ... 0
i1 = −1 ⋅det permutace řádků
0 ... 1 ... 0
1 0 ... ... x x
=−1i1⋅−1 j1⋅det permutace sloupců
1 je na [i,j]
Def.:
0 ... 1
1 je na[1,j]
0
=−1i j⋅det A i j
, Q.E.D.
x - nikdy nevyužijeme
Pro čtvercovo matici A definujeme adjungovanou matici adj A změna pořadí indexů!
předpisem Věta:
A
i j
j,i
adj Ai , j=−1 ⋅det
Pro každou regulární matici A platí
−1
A =
.
1 ⋅adj A . det A
Důkaz: z rozvoje podle i-tého řádku: A i⋅adj A i=det A
a pro j≠i :
i-tý řádek
A j⋅adj Ai= rozvoj podle i-tého řádku v matici, která vznikne z A nahrazením i-tého řádku j-tým řádkem =0
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
⋅
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
Věta:
0 ⋱
=
A
det A ⋱ ⋱ 0
⇒ A⋅
det A
1
A⋅adj A =I n
det
, Q.E.D.
A−1
adj A
Cramerovo pravidlo Nechť A je regulární matice, potom řešení každé soustavy A⋅x=b lze spočítat po složkách výrazem
x i=
det Ai b , det A
kde Ai b znamená matici, která vznikne z A nahrazením i-tého sloupce vektorem pravých stran b Důkaz (1):
1 ⋅adj A⋅b det A n 1 1 X i= ⋅adj A⋅bi= ⋅∑ adj Ai , j⋅b j = det A det A j=1
Důkaz (2): Označme I i x matici, která vznikne z I n nahrazením i-tého sloupce vektorem x.
−1
X = A ⋅b=
A⋅I i x= A⋅e 1, A⋅e 2, ... , A⋅x ,... = Ai b
Provedeme rozvoj podle i-tého sloupce v Ai b 1 = ⋅det Ai b , Q.E.D. det A
=b
Víme det I i x=x i a tedy det A⋅x i =det A ib , Q.E.D
3
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy Postup: Výpočet determinantu (ze cvičení)
∣
∣
a1
I)
V odstupňovaném tvaru stačí součin diagonály:
∣ ∣∣ 1 3 5
IV) n= 3 ⇒
an
i= 1
∣
3 5 1 3 5 −6 −6 ≃ −6 ⋅0 1 1 = −6⋅−16=96 0 −11 −27 0 −11 −27
6 7 3
⇒
0
n
=∏ ai
∣ ∣
1
II) Vytýkání z řádku: 2 0 4 ≃ 0 III) n=2
⋱ ⋱
∣ac db∣=a⋅d −b⋅c Sarrusovo pravidlo:
∣ ∣∣ ∣ 1 2 1 2 3 4 5 4 5 6⇒ 7 8 7 8 9 1 2 4 5
3 6 9 =1⋅5⋅94⋅8⋅37⋅2⋅6−7⋅5⋅3−1⋅8⋅6− 4⋅2⋅6=225−225=0 3 6 1 2 5 1 3 3 i j i,j 1 2 3 3 = −6⋅1 1 =−6⋅2 = 12 ≃ 2 0 4 2 0 0 = −1 ⋅2⋅ ⋅−1 ⋅det A ; př: j 7 9 7 9 6 7 3 6 7 9
{
n
V) Rozvoj dle i-tého řádku det A=∑ a i , j =1
}
∣ ∣∣ ∣
∣ ∣
Geometrický význam determinantu Pozn., Známe různé druhy obalů (1)
L X Lineární obal
X ∈ℝn , X ={x 1 , ... , x k } nejmenší vektorový prostor obsahující X. k
L X ={∑ a i⋅xi ; x i ∈ X , a i ∈ℝ} (2)
i= 1
A X Afinní obal
nejmenší afinní prostor obsahující X. k
k
i =1
i=1
A X ={∑ ai⋅x i ; x i ∈ X , a i ℝ , ∑ a i =1}
(3)
K X Konvexní obal nejmenší konvexní množina obsahující X. k
k
i =1
i =1
K X ={∑ a i⋅xi ; xi ∈ X , a i ∈ℝ , ∑ ai =1,∀ i : a i ∈[ 0,1]}
(4)
R X Rovnoběžnostěn vymezený X. k
R X ={∑ a i⋅xi ; xi ∈ X , a i ∈ℝ , ∀ i : a i ∈[ 0,1]} i =1
Věta:
Pro vektory x1 , ... , x n udává ∣det A∣ , kde A sestává z x1 , ... , x n (po řádcích anebo po sloupcích), objem rovnoběžnostěnu určeného x1 , ... , x n . Důkaz (idea): Protože přičítání jiných řádků nemění ani determinant, ale ani objem.
Důsl.:
f lineární zobrazení ℝn ℝ n a A=[ f ] KK je matice tohoto zobrazení, f v=∣det A∣⋅vol v . tak platí, že objem vol Je-li
objem obrazu
těleso
Polynomy Def.:
Polynom (též mnohočlen) stupně n v proměnné x nad tělesem K je výraz n n−1 p x=a n⋅x a n −1⋅x ...a1⋅xa 0 , kde a n ... a 0∈ K , a n≠0 . Značení p∈ K x . Operace s polynomy n
m
i
i
p , q∈ K x : p x= ∑ ai⋅x a q x =∑ b i⋅x , BÚNO n≥m . i =0
i =0
Sčítání a odčítání n
a ±b pro i ∈{0 ,... , m} i p±q x=∑ ci⋅x , kde ci = i i ai jinak i =0 Násobení skalárem n
t ∈ K , pak t⋅p x= ∑ t⋅a i ⋅x
i
i= 0
Násobení mezi sebou mn
i
p⋅q x= ∑ ci⋅x , kde ci = i =0
mini ,n
∑
a j⋅b i − j
j = max 0,i −m
4
∣ ∣
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy Dělení se zbytkem
∃r ,t ∈K X : deg tdeg q ∧ p=r⋅qt stupeň t
a p x − 1⋅x n−m⋅q x Konstrukce řešení: má stupeň nižší než p x . b1 první člen r
Pozn., Typicky za x volíme prvky z tělesa K, ale lze i jiné struktury, např. čtvercové matice nad K. n 0 p x=a n⋅x ...a 1⋅xa 0⋅x n p A=a n⋅A ...a 1⋅Aa0⋅I n ☼:
Pro p∈ℝ x platí, že p x=0 (tj. p x=0 x =0 ), právě když a 0=...=a n=0 .
Věta:
Malá Fermatova Pro každé a ∈ℤ p , a≠0 platí a p− 1=1 . Důkaz:
Zafixuji a, uvážím zobrazení f : i a⋅i . Tedy f : {1,..., p−1}{1, ... , p−1} je prosté a f je permutací na {1,... , p−1} . p −1
p −1
p −1
i =1
i =1
i= 1
∏ i= ∏ a⋅i=a p −1⋅∏ i ⇒1=a p−1 , Q.E.D. p
Důsl.:
V ℤ p : x − x=0 . ∀ q ∈ℤ p x ∃ r ∈Z p x , deg r ≤ p−1 : ∀ x ∈ℤ p : q x = r x
Def.:
Kořen polynomu p∈ K x je takové a ∈K , že p a=0 . Např. polynom p x= x 21 (1) má kořen i v K =ℂ (2) nemá kořen v K =ℝ (3) nemá kořen v K =ℤ 3 (4) má kořen 2 v K =ℤ 5 .
Def.:
Tělesa, kde všechny polynomy mají kořen, se nazývají algebraicky uzavřená.
Věta:
Základní věta algebry Každý mnohočlen stupně alespoň 1 nad ℂ má kořen.
Důsl.:
Každý mnohočlen stupně alespoň 1 nad ℂ lze rozložit jakou součin n monomů p x = a n⋅ x − x1⋅...⋅ x− x n , kde x1 , ... , x n jsou kořeny. Důkaz (idea): Základní věta algebry: p x=a n⋅x n...a 1⋅x a 0 …... (přednáška 16.3.09)
Otázka: Reprezentace polynomů p x stupně n. – pomocí koeficientů a 0 a n ∈K (+ def.); – na algebraicky uzavřeném tělese pomocí n kořenů a a 0 ; – hodnotami p x v n+1 různých bodech. snadné n
x ,... , x p x =∑ a i⋅x i n1 i=0 1 ???
–
jakým způsobem lze užít koeficienty a 0 a n polynomu p x , x ; y známe-li dvojice i i pro n+1 různých bodů x 1 x n 1 ?
= p xi
–
řešíme soustavu o neznámých a 0 a n
a n x n1 a1 x 1 a 0 = y 1 ⋮
⋮
⋮
a n x nn1a1 x n1a 0= y n1 Maticově:
1 x 1 ⋯ xn1 a0 y1 ⋮ ⋮ ⋱ ⋮ ⋅⋮ = ⋮ 1 x n1 ⋯ x nn1 an y n1
Vandermondova matice
5
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy Věta:
Vandermondova matice je regulární, právě když hodnoty x1 xn1 jsou navzájem různé. Důkaz:
∣
n 1
1 ⋮ 1
První řádek odečteme od ostatních
∣
x1 ⋯ x ⋮ ⋱ ⋮ xn 1 ⋯ xnn1
=
∣
1 0 ⋮ 0
x1 x2 −x1 ⋮ xn 1− x 1
∣
⋯ xn1 n n ⋯ x 2− x 1 ⋱ ⋮ ⋯ x nn1 −x n1
i−2 i −1 Provedeme rozvoj dle prvního sloupce a vytkneme x ik − xi1=x k −x i x i−1 k x k ⋅x 1 x 1
∣
∣
1 x 1 x 1 x 22 x 2⋅x 1 x 21 n Vandermantova matice na = x − x ⋅ ⋮ ⋮ ⋮ ⋱ =∏ x j− x1 ⋅ ∏ ∏ x j− xi j 1 proměnných x 2 x n1 j= 2 j =2 1≤ i j≤ n1 2 2 1 x n 1 x1 x n1 x n 1⋅x 1 x 1 n
∣
∣
produkt nenulový ( ⇒ matice regulární) ⇔∀ x i různé. Q.E.D.
Postup: Lagrangerova interpolace - alternativní postup, jak proložit polynom stupně n body x i , yi , i∈{1 n} . Pro i ∈{1 n1} označme
P i x =
x−x 1 x−x 2 ⋅⋅x−x i−1 x−x i1 ⋅⋅x−x n1 x i−x 1x i −x 2⋅⋅ x i−x i−1 xi− x i1⋅⋅ xi−x n1
Platí Pi xi = 1 a pro j ≠ i : Pi x j = 0 (někde máme x− x j =0 ... nenulový čitatel). Položíme Px = y1⋅P1 x y n1 Pn 1 x . Úloha: Jakým způsobem sestavit m klíčů, aby libovolný nm klíčů dokázalo odemknout kód, ale libovolných méně než n nikoliv? polynom stupně n−1 a určíme jeho hodnoty v m různých bodech. Sestavme kód
klíč
Vlastní čísla a vlastní vektory Úvod: Jednoduchý abstraktní model dynamického systému. Systém … reprezentován vektorovým prostorem V nad K Dynamika … reprezentována lineárním zobrazením f : V V Stabilní stavy (a) pevné body zobrazení f čili f u = u (b) body jejichž obraz je skalárním násobkem vzoru: f u = a⋅u , a ∈K Př:
Osová souměrnost v ℝ2
Def:
Nechť V je vektorový prostor nad K a f : V V je lin. zobrazení. Vlastním číslem zobrazení f je takové λ ∈K pro které existuje netriviální u ∈V takový, že f u = ⋅u . Vlastním vektorem příslušný vlastnímu číslu λ je libovolné u ∈V , tž. f u = ⋅u . (Pozn: Zdvojená definice, abychom obešli u=0 .) Je-li V konečně generovaný, tj. dim V = n ∈ℕ , potom lze f reprezentovat maticí zobrazení A = [ f ]VV a rozšířit definici na matice: n Vlastní číslo matice A je libovolné ∈ K takové, že A⋅x = ⋅x pro x ∈K , x ≠ 0 . Vlastní vektor příslušný vlastnímu číslu λ je takové x ∈K n , že Ax = λ⋅x Množina všech vlastních čísel matice se nazývá spektrum matice.
Charakteristický mnohočlen Úvod:
f u = λ⋅u , u ≠ 0 A⋅x = ⋅x ⇒ A⋅x− λ⋅x = 0 ⇒ A⋅x− λ⋅I⋅x = 0 ⇒ A−λ⋅I ⋅x = 0
Def:
Charakteristickým mnohočlenem matice A nazveme polynom p a t , který je určen výrazem: p a t = det A−t⋅I
Věta:
Pro každou čtvercovou matici A platí, že λ je jejím vlastním číslem, právě když je λ kořenem charakteristického mnohočlenu p A t , čili p A = 0 Důkaz: viz. úvod... A− I x=0
Př:
A− I je singulární ⇔
⇔
det A−t⋅I =0 , x netriviální! Q.E.D.
Viz slidy.
Tvrz.: Jsou-li A, B čtvercové matice stejného řádu nad stejným tělesem, potom A⋅B a B⋅A mají stejná vlastní čísla. Důkaz: ☼ Pro násobení blokových matic platí: C
R
R
AB 0 ⋅ I A =
B
Def: ☼:
0
0
I
AB B
I K
J ⋅ P L R
Q = IPJR IQJS S KP LR KQ LS
D
ABA = I A ⋅ 0 0 BA 0 I B BA
Platí: C⋅R= R⋅D , říkáme, že C a D jsou podobné. Podobné matice mají shodné charakteristické mnohočleny.
6
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy C= R⋅D⋅R−1 pC t=det C−t⋅I =det R⋅D⋅R−1 −t⋅I =det R⋅D⋅R−1 −t⋅ R⋅I⋅R−1 =det R D −t − I ⋅R−1 =det R⋅det D−t⋅I ⋅det R−1 =P d t (*)
Podobné matice mají tedy shodná i vlastní čísla. A⋅B−t⋅I 0 −t⋅I =∣A⋅B−t⋅I ∣⋅∣−t⋅I∣= p AB t= p BA t=∣−t⋅I ∣⋅∣B⋅A−t⋅I∣= Čili B −t⋅I B Stejné charakteristické mnohočleny ⇒ stejná charakteristická čísla, Q.E.D.
∣
Věta:
∣
∣
*⋅toto=1
∣
0 B⋅A−t⋅I
Cayley-Hamilton Nechť p A t je charakteristický mnohočlen matice A. Potom platí p A A = 0 .
Důkaz: Využijeme faktu, že M ⋅adj M =det M ⋅I n , a dosadíme M := A−t⋅I ⇒
p A t 0 ⋮ 0
0 p At ⋱ 0
0 0 0 0 . ⋱ ⋱ 0 p A t
adj A−t⋅I Má na každém místě polynom proměnné t.
Můžeme zapsat adj A−t⋅I =t n− 1⋅B n −1...t⋅B 1B 0 , tedy A−t⋅I ⋅t n− 1⋅B n− 1...t⋅B1 B 0 = p A t⋅I =a n⋅t n⋅I ...a1⋅t⋅I a 0⋅I . Koeficient u t n :
−I⋅B n −1=a n⋅I
∣⋅A n
ut :
A⋅Bi −I⋅B i− 1=a i⋅I
∣⋅A i
u t0 :
A⋅B 0=a 0⋅I
∣nic
i
Provedeme úpravy (násobení jsou zleva) a sečteme. Pravá strana je a n⋅a n ...a 1⋅Aa0⋅I = p A A −A n⋅B n −1 A n− 1⋅ A⋅B n−1 −B n −2 An −2⋅ A⋅B n −2 −B n− 3... A 2⋅ A⋅B 2 −B 1 A⋅ A⋅B 1− B 0 A⋅B 0 =0 , Q.E.D.
☼:
(1) Každá matice řádu n má nejvýše n vlastních čísel. (2) Každá komplexní matice řádu n má „právě“ n vlastních čísel (některá mohou být vícenásobná): k
p A t=1−t⋅...⋅n −t p A t =1−tr ⋅...⋅k −tr ; ∑ r i=n 1
k
i=1
(3) a 0 = det A dosazením t = 0
∣
p A t=an⋅t n...a1⋅ta 0=det A−t⋅I =
a 1,1−t a 2,2−t ⋱ a n ,n −t
∣
n
(4) a n = −1 (5) a 0 = 1⋅...⋅ n dosazením t = 0 do p A t = 1−t ⋅...⋅ n−t (6)
n
n
i=1
i =1
a n−1=−1n−1⋅∑ ai ,i =−1n −1⋅∑ i
Úloha: (ze cvičení) Ve městě Pupákově jsou tři strany: Asketičtí, Bohatí a Chudí. Podrobným výzkumem se zjistilo, že 75% z těch, co volilo Askety, je bude volit opět, 5% bude volit Bohaté a 20% chudé. Podobně z těch co volili Bohaté zvolí 60% Bohaté, 20% Askety a 20% Chudé. 80% voličů chudých je bude volit i v následujícím období, o zbylé hlasy se podělí 10% Asketi a 20% Bohatí. Jak bude vypadat limitní rozložení sil v místním (stočlenném) zastupitelstvu? A B C 15 4 2 Ax = x A= A 0,75 0,20 0,10 ⇒ ⇒ 20 A = A' := 1 12 2 20 Ax =20 x B 0,05 0,60 0,10 4 4 16 C 0,20 0,30 0,80 ☼ Rozdělení dle popisků okolo matice, např. na diagonále jsou ti co volí stejně. ☼ Součet sloupců matice dá vždy 1 (100%)
∣
15−t : 1 4 x p : ⇒
∣
4 2 = 15−t 12−t 16−t832−8 12−t – 8 15−t−416−t = 12−t 2 = 20−t 12−t 11−t ⇒ 4 16−t
−5 4 2 0 9 −3 1 1 −1 1 −8 2 ≃ 0 −9 3 ≃ 0 −3 1 4 4 −4 1 1 −1 0 0 0
2p p p = 1 ⇒ 3 3
p=
1 2
⇒
1 =11 1 3 = 10 5 11 3 = 20
2 =
x3 = p 2 1 ⇒ −3 p=0⇒ x 2 = p /3 ⇒ x = p ; ;1 3 3 x 1 =−2p
1 1 1 x11 = ; ; , kde každá složka je zastoupení přislušné strany. 3 6 2
☼ Pokud bychom dosadili jiné vlastní číslo příklad by nevyšel smysluplně. Věta:
Nechť x1 , ... , x k jsou vlastní vektory příslušné navzájem různým vlastním číslům 1 , ... , k lineárního zobrazení f. 7
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy Potom x1 , ... , x k jsou lineárně nezávislé. Důkaz: indukcí a sporem. k
Nechť x1 x n tvoří nejmenší protipříklad, tj. ∃a 1 ,... , a k ≠0 : ∑ a i⋅x i=0 i=1
∑ k
0 = f 0 = f
i =1
k
k
k
k
i =1
i =1
i= 1
a i⋅x i = ∑ a ⋅f xi = ∑ a ⋅ i i = ∑ a ⋅ i k⋅x i i i i⋅x i a 0 = k⋅0 = k⋅∑ a ⋅x i= 1
k
k
k−1
i=1
i=1
i= 1
0 = 0−0 = ∑ a i⋅i⋅x i − ∑ ai⋅k⋅x i = ∑ i −k ⋅a i⋅xi ⇒ x 1 x k−1 jsou lineárně závislé, SPOR s minimalitou protipříkladu. Q.E.D. ≠0
≠0
Def:
Čtvercové matice A, B nazveme podobné, pokud existuje regulární matice R taková, že platí: A = R− 1⋅B⋅R
Věta:
Nechť matice A, B jsou si podobné a ,x jsou vlastní číslo a příslušný vlastní vektor matice A, potom y = R⋅x je vlastní vektor matice B příslušný vlastnímu číslu . Důkaz: B⋅y = R⋅A⋅R−1 ⋅ R⋅ x =R⋅A⋅x x=⋅R⋅ x=⋅y =R⋅⋅ A=R−1⋅B⋅R ⇒ B=R−1⋅A⋅R , Q.E.D.
☼:
Vlastní čísla diagonální matice jsou prvky na diagonále a kanonická báze dává vlastní vektory.
Def:
Matice A je diagonalizovatelná, pokud je podobná nějaké diagonální matici. −1
(a) A = R ⋅D⋅R ; = Dii je i-té vlastní číslo a j-tý sloupec R− 1 je vlastní vektor A. k −1 k k k (b) mocnění matic A = R ⋅D ⋅R ⇒ D i ,i = D i , i
Aplikace:
Tvrz.: Matice A řádu n je diagonalizovatelná, právě když má n lineárně nezávislých vlastních vektorů. Důkaz:
Má-li platit R−1⋅A⋅R= D , pak sloupce R jednoznačně odpovídají vlastním vektorům.
Důsl:
(1) Má-li matice A řádu n, n různých čísel potom je diagonalizovatelná. (2) Platí, že A ∈ℂn×n má vlastní čísla 1 , ... , k násobnosti r 1 , ... , r k a navíc ∀ i ∈{1 , ..., k} : rank A−⋅I = n−r i , právě když A je diagonalizovatelná.
Fakt:
Každá čtvercová komplexní matice A je podobná matici v tzv. Jordanově normálním tvaru, což je ... Tento tvar je dán jednoznačně až na pořadí bloků.
Př:
☼:
není diagonalizovatelná. 1 1 0 1
Nechť A =
1 0 ⋱ ⋱ ⋱ 1 0
má vlastní číslo s příslušným vlastním vektorem x.
0
Pak
A⋅x=⋅x ⇔ A−⋅I ⋅x=0 , tedy
1 0 ⋱ ⋱ x n= ⋱ 1 0 0
* 0 ⋮ 0
(* značí „cokoliv“)
A−⋅I
a lze nalézt posloupnost vektor, tzv. zobecněné vektory, takovou, že A−⋅I ⋅x i = xi 1 . Def.:
Komplexní čtvercová matice A je hermitovská, pokud platí a i , j = a j ,i (komplexně sdružené číslo).
Def.:
j ,i Hermitovská transpozice A je A H , kde A i , j = A H Jinými slovy: hermitovská ⇔A = A T analogie: symetrická ⇔A = A
Def.:
Komplexní čtvercová matice A se nazývá unitární, pokud platí A H⋅A = I .
☼:
Součin unitárních matic je unitární: A H⋅A = I , B H⋅B = I ⇒ ABH⋅ AB = B H⋅A H⋅A⋅B = I .
Př.: ☼: ☼ Věta:
H
A=
1 1i ; P t =t 2 – 3t ⇒ =3 , =0 a 1 2 1−i t
1i
3 R= −1 3
1
3
1−i 3
1−i
−1 H R = R = 13
3
−1 3 1i 3
R−1⋅A⋅R= 0 0 0 3
A je diagonizovatelná: A⋅R = R⋅D A je podobná J : A⋅R = R⋅J Každá hermitovská matice má všechna vlastní čísla reálná a existuje unitární matice R, že R⋅A⋅R−1 je diagonální. 8
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy Důkaz: Indukcí podle řádu matice A n := A∈C n×n .
z indukce existuje R n−1 unitární tž. R−1 . n−1⋅A n−1⋅Rn −1= D n −1
Základní věta algebry ⇒ existuje vlastní číslo
1 0 0 0 R := P =S n n ⋅ ⋮ R n −1 Definujme: n unitární unitární 0
a k němu vlastní vektor x
1
⋮ Fakt: x 1 lze doplnit dalšími vektory na unitární matici P n = x 1 ⋯ ⋮ (Důkaz: Gran-Schmidtova ortogonizace) Nyní máme matici z které jsme vyšli, její vlastní vektor a unitární matici. H
unitární H H H R−1 n ⋅A⋅R n =R n ⋅A n⋅Rn =S n ⋅P n ⋅A n⋅P n⋅S n =
H
H H P Hn = P nH⋅A⋅P n P nH⋅A⋅P n = P n ⋅A⋅ ☼
z def.
2x na H
Def.:
n−2
1 0 0 0 0 0 ⋅ ⋮ ⋮ R nH−1 0 0
=
0 0 0 IP 0 0 = ⋮ ⋮ R Hn−1 ⋅A n−1⋅ R n−1 0 0
hermitovská
T P Hn ⋅A⋅P n má v prvním sloupci ,0 ,... ,0 ⇒ ∈ℝ (z ☼, je hermitovská) A n−1 je hermitovská matice řádu n−1 ,
=
A⋅P n má v prvním sloupci vektor ⋅x1 .
Opak.: K n = n
A n− 1
0
⋅
1 0 0 ⋮ 0
R n −1
0
=
0
D n−1
, Q.E.D.
je počet koster úplného grafu.
Laplaceova matice grafu G na n vrcholech v 1 ,, v n je matice Q taková,
q i , j=−1⇔ v i , v j ∈E G ; i≠ j 0 jinak q i , i=deg v i
že
Qi , j je matice vyniklá y Q vyškrtnutím i-tého řádku a j-tého sloupce. Věta:
Pro každý graf G platí K G = detQ 11 Poznámka – důkaz:
∣
∣
n−1 −1 ⋯ n−1 −1 ⋯ −1 −n n 0 −1 n−1 ⋱ ⋮ Q= det Q11 = ⋮ 0 n ⋮ ⋱ ⋱ −1 ⋮ ⋮ ⋱ −1 ⋯ −1 n−1 −n 0 ⋯
∣
∣
n
Věta:
⋯ −1 ⋯ 0 n− 2 ⋱ ⋮ =n ⋱ 0 0 n
Bimet-Cauchyho
T T {1 n} Pro A , B∈K m ×n platí ∣A ⋅B∣= ∑ ∣A I ⋅B I∣; * : I ∈ . m *
Důkaz věty o G :
že w i je list ve zbylém stromu w i1 , ..., wn .
, Zvolíme orientaci G zavedeme orientovanou matici incidence
{
1 n×m D∈ℝ ; n=∣V G ∣, m=∣E G∣; d i , j= −1 0
Přeuspořádáme sloupce D 1I podle pořadí w 1 ,... , w n . v i začátek e j vi konec e j jinak
}
D 1I =
☼: D⋅DT =Q . Zavedeme D 1= D bey prvního řádku. Platí D ⋅D =Q 1
1T
1,1
a dle Bimet-Cauchyho:
∑ ∣D1I⋅D1TI ∣= ∑ ∣D1I 2∣ = I = {1 ,... ,m} I = {1 ,... ,m} n−1 n −1
⋱ ⋱
0 0 0 ⋮ 0 ±1
...determinant ±1 .
lemma
det Q 1,1=det D 1⋅D 1T =
0 ±1 0 ⋱ 0 ⋱
±1
G
(2) {e i ; i∈ I } neindukují strom, pak existuje cyklus. v1 ∉cyklus ⇒ sloupce hran, které jsou LZ ⇒ det=0 .
Lemma 1: ∣D1I∣=±1 , právě když {ei ; i∈ I } indukují strom.
má komponentu, která obsahuje v 1 : e1 e 2
Lemma 2: ∣D1I∣=0 , právě když {ei ; i∈ I } neindukují strom. Stačí již jen dokázat lemmátka. (1) {e i ; i∈ I } indukují strom, spořádáme vrcholy w 1 ,... , w n tak,
v2 0
9
0 1 1 −1 −1
, Q.E.D. LZ
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy
Prostory se skalárním součinem Úvod: Vektory můžeme násobit jako matici: ∀ a ∈ℂ : i aa ∈ℝ ii a⋅a ∈ℝ Def.:
x⋅y = xy∈ℝ iii ∣a∣∈ℝ
Nechť je V vektorový prostor nad ℂ . Zobrazení, které dvěma vektorům u, v ∈V přiřadí číslo 〈u∣ v 〉 ∈ℂ , se nazývá skalární součin (ss), pokud splňuje axiomy:
N L1 L2 KS P
〈 u∣ u 〉=0 ⇔ u =0 〈 a⋅u∣v 〉 = a⋅〈u∣v 〉 〈 u v∣w 〉 = 〈 u∣w 〉〈 v∣w 〉 〈 v∣u 〉 = 〈 u∣v 〉 〈 u∣ u〉 ≥ 0
∀ u ∈V : ∀ a ∈ℂ , ∀ u , v ∈V : ∀ u , v , w ∈V : ∀ u , v ∈V : ∀ u ∈V :
Pozn., (1) Formálně: 〈∣〉: V ×V ℂ (2) Pro prostory nad ℝ se skalární součin definuje stejně, (KS) se interpretuje jako ∀ u , v ∈V : 〈 v∣ u 〉 = 〈 u∣v 〉 . ☼
SS pro ℝ stejné až na axiom (KS):
Př.:
(1) Standardní SS pro aritmetické vektorové prostory:
KS ∀ u ,v ∈V : 〈 v∣ u 〉 = 〈 v∣u 〉
n
V = ℂ n : 〈 u∣v 〉 = ∑ u i v i = v H⋅u ≠ u H⋅v i=1 n
n
T
T
V = ℝ : 〈 u∣v 〉 = ∑ u i vi = v ⋅u = u ⋅v i =1
☼ 〈u∣a⋅ v 〉 = 〈a⋅v∣u 〉 = a⋅〈 v∣ u 〉 = a⋅〈v∣ u 〉 = a⋅〈 u∣v 〉 (2) SS na ℝ n definovaný pomocí regulární matice A :〈 u∣v 〉 := uT⋅AT⋅A⋅v ,
T A := 10 12 〈 u∣ v 〉=u 10 21 v = u1⋅v 12⋅u1⋅v 12⋅u2⋅v 15⋅u2⋅v 2 (3) SS na prostoru spojitých funkcí integrovatelných na intervalu [ a , b ] :
například V := ℝ
2
b
〈 f ∣ g 〉 = ∫ f x⋅g x⋅dx a
Def.:
Nechť V je vektorový prostor se SS. Potom norma určená tímto SS je zobrazení ∥∥: V ℝ dané předpisem ∥u∥ = 〈u∣ u〉 .
Pozn:
Význam:
☼
Na ℝn : 〈u∣ v 〉 = ∥u∥⋅∥v∥⋅cos , kde je úhel sevřený vektory u a v.
☼
Plyne z cosinové věty: c 2 = a 2b 2−2ab⋅cos 〈u −v∣ u − v 〉 = 〈u∣ u 〉〈 v∣v 〉−2⋅∥ u∥⋅∥ v∥⋅cos 〈u∣u〉 −〈u∣v〉−〈 v∣u 〉〈u∣u〉=〈u∣u〉〈v∣v 〉−2⋅∥u∥⋅∥v∥⋅cos
a=∥ u∥ b=∥v∥ c =∥u −v∥
∥u∥ délka vektoru u ∥u⋅ v ∥ vzdálenost vektorů u a v 〈u∣ v 〉 určuje úhel mezi u a v
=−2⋅〈 u∣v〉
Věta:
Cauchy-Schwarzova nerovnost 〈u∣ v 〉∣≤ ∥ u∥⋅∥ v∥ Nechť V je vektorový prostor se SS a normou z něj odvozenou, potom platí ∀ u , v ∈V : ∣ . kvůli ℂ
Důkaz: Je-li u=0 nebo v =0 ⇒ 0≤0 platí. a ∈ℂ :∥ua⋅v∥ ≥ 0 a tedy 0 ≤∥ua⋅v∥2 = 〈ua⋅v∣ua⋅v 〉 = 〈 u∣u 〉a⋅〈v ∣u〉 a⋅〈 u∣v 〉a⋅ a⋅〈 v∣v 〉 . 〈 u∣v 〉 Zvolíme a := − ∣ ⇒ eliminuje poslední dva členy. 〈v v〉 〈 v∣u 〉⋅〈u∣v 〉 2 0 ≤ 〈u∣u〉− ⇒ 〈 v∣u〉⋅〈 u∣v 〉 ≤ 〈u∣u〉 〈 v∣v 〉 ⇒ ∣〈 u∣v 〉∣ ≤∥u∥2⋅∥v∥2 = ∣〈 u∣v 〉∣ ≤ ∥u∥⋅∥v∥ , Q.E.D. 〈v∣v 〉 BÚNO ∣〈 u∣ v〉 2∣
≠0
Důsl.:
n
(1) Nerovnost mezi aritmetickým a kvadratickým průměrem: Důkaz: Zvolíme v =1 , ,1 ∈ℝ T
n
u ∈ℝn :
1 ∑u ≤ n i =1 i
n
n
∑ u i = 〈 u∣v 〉 ≤ ∥u∥⋅∥v∥ = ∑ u2i⋅ n , Q.E.D. i=1
i=1
(2) Norma odvozená ze SS splňuje trojúhelníkovou nerovnost: ∥uv∥ ≤ ∥u∥ ∥v∥ 10
n
1 2 ui n∑ i=1
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy ∥uv∥= 〈uv ∣uv 〉 = 〈u∣u〉〈 u∣v 〉〈 v∣u〉〈 v∣v 〉 ≤ ∥u∥22∣〈 u∣v 〉∣∥v∥2 ≤
Důkaz:
≤ ∥u∥22⋅∥u∥⋅∥v∥∥v∥2 = ∥u∥∥v∥2 = ∥u∥∥v∥ Q.E.D.
Odbočka do analýzy Obecně je norma nad prostorem zobrazení V ℝ 1) ∀ u ∈V : ∥u∥ ≥ 0 2) ∀ u ∈V : ∥u∥ = 0 ⇔ u = 0 3) ∀ u ∈V , a ∈ℂ : ∥a⋅u∥ = ∣a∣⋅∥u∥ 4) ∀ u , v ∈V : ∥uv∥≤∥u∥∥v∥ Př.:
p
L p normy na ℝn : ∥u∥ p =
jiných norem:
stat. norma odpovídá p =2.
pozitivnost jednoznačnost nuly linearita (?) trojúhelníková nerovnost
n
∑∣u i p∣ i=1
n
p=1∥u∥1 = ∑ u i i =1
p=∞∥u∥∞ = max u i i= 1 ,, n
Ortogonalita Def.:
Dva vektory ua v v prostoru se SS jsou navzájem kolmé (značíme u ⊥v ), pokud platí, že 〈u∣ v〉=0 .
☼:
Každý systém vzájemně kolmých vektorů je lineárně nezávislý. n
Máme: u 1 , ,u n : ∀u i ⊥ u j ∧ ∀ i ≠ j, ale LZ ⇒ u i= ∑ a i u i
Důkaz sporem:
i=2
〈∣ 〉 n
0 〈u i∣u j 〉 = u 1 ∑ a i u i = ∑ a i 〈 u 1∣u i〉 = 0
⇒ SPOR
Q.E.D.
i= 2
Def.:
Nechť Z je báze prostoru V se SS taková, že ∀ v ∈Z : ∥v∥ = 1 a navíc ∀ v , v ' ∈Z : v ≠ v' ⇒ v ⊥v ' . Potom takovou bázi nazveme ortonormální bází prostoru V.
☼:
Mějme Z ortonormální bázi prostoru ℝ n . Pak
⋱ ⋱ T A= v 1 v n ⇒ A ⋅A=I ⇒ A je ortogonální. ⋱ ⋱ n
H
(analogicky ℂ : A ⋅A = I n ⇒ A je unitární) (27. 4. 2009)
Tvrz:
Nechť Z =v 1 ,… , v n je ortonormální báze prostoru V, n
potom
∀ u ∈V : u =∑ 〈 u∣v1 〉⋅v 1〈 u∣v2 〉⋅v 2...〈 u∣vn 〉⋅v n . i=1
n
Důkaz: v1 , … , vn je báze, vyjádříme: v=
〈u∣vi 〉 =
〈
∣〉
n
∑ a j vj vi j =1
∑ a i vi , chceme ukázat: i =1
a i = 〈 u∣ vi 〉
n
= ∑ a j 〈 v j∣v i 〉 = a i ; možnosti: a) „<> = 0“ pro i ≠ j j=1
, b) „<>= 1“ pro i = j
Q. E. D.
2 možnosti
∈V se koeficientům 〈 u∣vi 〉 říká Fourierovy koeficienty.
Def:
Pro ortonormální bázi v1 ,… , v n a vektor u
Tvrz:
Parsevalova rovnost: Je-li Z =v 1 ,… , v n ortogonální báze prostoru V, potom ∀ u , w ∈V : 〈 u∣ w 〉 = [ w ] Z [ u] Z
H
n
n
u = ∑ 〈 u∣v i 〉 v i ; w = ∑ 〈 w∣vi 〉 vi
Důkaz:
i =1
〈u∣w 〉 =
〈
n
i =1
∣
n
∑ 〈u∣vi 〉 vi ∑ 〈 w∣v j 〉 v j i =1
j=1
〉
n
n
n
H = ∑ ∑ 〈u∣vi 〉〈 w∣v j 〉〈 vi∣v j 〉 = ∑ 〈u∣vi 〉 〈w ∣v i 〉 = [ w ] Z [ u] Z Q. E. D. i =1 j =1
i=1
Def:
Lineární zobrazení f : V W mezi prostory s SS se nazývá unitární, pokud f zachovává SS. ∀ u , v ∈V : 〈 u∣v 〉 = 〈 f u ∣f v 〉
Tvrz:
Zobrazení f : V W je unitární právě když pro normy odvozené se SS platí: ∀ u ∈V : ∥u∥ = ∥ f u ∥ Důkaz: „=>“ ∥u∥= 〈u∣u〉 = 〈 f u∣f u〉=∥ f u ∥ „<=“
Jako u CS nerovnosti.
∥va⋅w∥ = ∥w∥ =
11
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy Def:
Unitární isomorfismus prostorů s SS se nazývá ISOMETRIE.
Věta:
Nechť V a W jsou prostory s ortogonálními bázemi X=Y, stejné konečné dimenze, potom platí, že f : V W je isometrie právě když [ f ]XY je unitární.
Def:
Nechť W je prostor se SS, V ⊆W , a Z =v1 , … , v n je ortonormální báze V. n
Zobrazení
p :W V je definováno předpisem: p u := ∑ 〈 u∣vi 〉 vi se nazývá ortogonální projekcí prostoru W na V. i=1
Lemma:Nechť p je ortogonální projekcí W na V, potom u – pu ⊥ vi pro ∀ vi ∈Z Důkaz:
〈
∣〉
n
n
〈u − p u ∣v i 〉 = u − ∑ 〈 u∣v i 〉 v i = 〈u∣v i 〉− ∑ 〈 u∣v j 〉 〈v j∣vi 〉 = 〈u∣v i 〉−〈u∣v i 〉 = 0 Q. E. D. i=1
j=1
Gram-Schmidtova ortogonalizace Vstup: Libovolná váze u1 , ... , u n prostoru V se SS. Výstup: Ortonormální báze v1 ,… , v n Algoritmus: pro i:=1 do n opakuj { i−1
1)
w i := u i−∑ 〈 u i∣v j 〉v j
2)
1 vi = w ∥wi∥ i
j=1
} Korektnost:
1) 2)
=> w i ⊥ v j pro j=i z … 1 1 ∥w i∥= w = ∥w ∥= 1 ∥wi∥ i ∥wi∥ i
3)
Pozn, ☼:
u
a
∥
w i ⊥ v j pro i≠ j
∥
span v 1 … v i−1 , ui , v i1 … v n z lemmatu o výměně
toto je využito ve větě o diagonalizovatelnosti hermitovských matic – potřebujeme G-S algoritmus. p(u) je nejbližší bod z u v prostoru V. a = u − p u a ⊥ b b = u − p u a b ∥a −b∥ = 〈 a−b∣a−b〉 = 〈 a∣a 〉−〈 a∣b 〉−〈 b∣a 〉〈 b∣b 〉 ∥a∥ w
p u
V
=0
0
(4. 5. 2009)
Ortogonální doplněk
Def:
Nechť V je množina vektorů ve vektorovém prostoru W se SS. Ortogonální doplněk množiny V je množina: ⊥ V := { u ∈W : u ⊥ v ∀ v ∈V }
Př:
Když hledáme řešení homogení soustavy, tak hledáme Ax =0 <=> hledáme r a ⊥ vůči std. SS.
☼:
U ⊆V ⇒ U ⊥ ⊇V ⊥ Důkaz:
Věta:
u ∈V ⊥ ⇔ u ⊥v ∀ v ∈V ⇒ u ⊥v ∀ v ∈U ⇔ u ∈U ⊥ Q. E. D.
Nechť V je podprostorem W se SS, potom platí: (a) V ⊥ je podprostorem W (b) V ∩V ⊥ ={ 0} Je-li navíc W konečné dimenze: (c) dimV dimV ⊥ =dimW ⊥ (d) V ⊥ = V Důkaz:
(a)
(b)
u , v ∈V ⊥ , ∀ w∈W : 〈uv∣w 〉 = 〈u∣w〉〈 v∣w〉 = 00 = 0 ⇒ uv ∈V ⊥ II. u ∈V ⊥ 〈 a⋅u∣w〉 = a⋅〈u∣w 〉 = a⋅0 = 0 ⇒ a⋅u ∈V ⊥ ⇒ I.∧II. ⇒ je podprostorem 0 u u =0 spor. sporem: kdyby u ∈V ∩V ⊥ , v ≠ 0 I.
〈∣ 〉 ∈V ∈V ⊥
Příprava na (c) a (d): Vezmeme ortonormální bázi X prostoru V a rozšíříme ji na ON bázi Z prostoru W.
X ={x 1 x n }
Y =Z ∖ X Cíl: Chceme ukázat, že
Y ={ y 1 y n }
⊥
V = span Y
12
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy k
∀ x i ∈ X a ∀ y j ∈Y : xi ⊥ y j ⇒ y j ⊥
1)
l
〈w∣z 〉 =
j=1 l
〈∑ ∣∑ 〉 l
k
j yj
j=1
i =1
2) Libovolné w ∈V
vyjádříme jako
i =1
k
j =1 i =1 k
∑ j y j∑ i x i j=1
0 = 〈w∣xi 〉 = i
k
∀ z∈V : Z = ∑ i x i
i x i = ∑ ∑ j i 〈 y j∣xi 〉 = 0 ⇒ span Y ⊆V ⊥ l
⊥
⇒ Y⊆V ⊥
i=1
∑ j yj
navíc: w ∈ span W ⇒ w =
∑ i x i
i=1
⇒ w∈span Y ⇒ V ⊥ ⊆ span Y
Z je ON báze V
– konec přípravy – (c) dimV = ∣X ∣ ; dim V ⊥ = ∣Y ∣ ; dimW = ∣X ∣∣Y∣
V ⊥
(d)
⊥
Q. E. D.
= span Z ∖Y = span X = V
Pozitivně definitní matice Tvrz.: Nechť V prostor se SS a X = y1 , , y n je jeho báze, potom pro matici A definovanou: ai , j := 〈 xi∣x j 〉 platí, že ∀ u , v ∈V : 〈 u∣w〉 = [w]HX⋅A⋅[ u ]X Pozn.: Je-li X ON báze, je A jednotková. n
Důkaz:
[u] X = 1 ,... ,n u = ∑ i xi i =1 n
[w ]X = 1 ,... , n w = ∑ i x i i =1
〈∑ ∣∑ 〉 n
〈u∣w〉 =
n
i x i
i =1
j =1
n
n
j x j = ∑ ∑ i j 〈 x i∣x j 〉 = [w] HX ⋅A⋅[u] X
Q. E. D.
i=1 j =1
Jaké vlastnosti musí mít A? 1) a ij = 〈 x j∣xi 〉 = 〈 xi∣x j 〉 = a ij ⇒ A je hermitovská H 2) musí zaručit, že 〈u∣u〉 = [ u ] X⋅A⋅[ u]X 0 pro u ≠ 0 Def:
Hermitovská matice A řádu n se nazývá pozitivně definitní, pokud ∀ x ∈ℂn ∖{∅} platí: H x ⋅A⋅x 0 .
Užití:
V MA vyšetřování lokálních a globálních extrémů funkcí více proměnných.
Věta:
Pro hermitovskou matici A řádu n jsou následující podmínky ekvivalentní: a) A je pozitivně definetní b) A má všechna vlastní čísla kladná c) existuje regulární matice U taková, že A = U H⋅U Důkaz:
(a=>b)
A hermitovská, vlastní číslo A ⇒ ∈ℝ , vezmeme vlastní vektor x, aby A x = x
0 x H⋅A⋅x = ⋅x H⋅x H
(b=>c) (c=>a)
Tvrz:
⇒ 0
x ⋅x 0 ze součinu na ℂ: a⋅a ≥ 0 A hermitovská => ∃ regulární R, tž. A = R H⋅D⋅R , D diagonální : dij = d ij H⋅D⋅R = U H⋅U D A = R H⋅D x H⋅A⋅x = x H⋅U H⋅U⋅x = UxH⋅Ux 0 ⇔ U je regulární ax≠0
Pro pozitivně definitní matice existuje jednoznačná trojúhelníková matice U s kladnými prvky na diagonále taková, že A = U H⋅U , matici U se říká Choleskeho rozklad. Důkaz: algoritmem: Vstup: hermitovská matice A Výstup: choleského rozklad, nebo odpověď, že A není poz. definetní. Pro i:=1 do V proveď: {
1)
k−1
U ii := aii – ∑ U ki U ki k=1
2) není-li u ii ∈ℝ , u ii 0 3) pro j = (i + 1) do u proveď: { }
u ij :=
⇒ STOP, A není pozitivně definetní i−1
1 a −∑ U ⋅U } uii ij k=1 ki kj
Q. E. D. (přednáška 11.5.09)
H
Tvrz.: Bloková matice
A=
a je positivně definitní, právě když 0 a zároveň A− 1 ⋅a⋅a H je positivně definitní. a A 13
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy
aH = Pozn., Gaussovou eliminací sloupce pod dostaneme 0 a A ∈ℂ
x1 ∈ℂ n . Důkaz: ⇐ Nechť x ∈ℂ n , x ≠0 , značme x= x
a H x1 x1 = x H⋅A⋅x = x1, xH ⋅ ⋅ =x 1⋅ xH⋅a , x1⋅a H xH⋅A⋅ a A x x 1 H 1 H H H H H H =x1⋅⋅x 1 x 1⋅x ⋅ax 1⋅a ⋅x x ⋅A⋅x − ⋅x ⋅a⋅a ⋅x ⋅x ⋅a⋅a ⋅x =
=0
1 1 H 1 H H H = x ⋅ A− ⋅a⋅a ⋅x ⋅x 1 ⋅x ⋅a ⋅ ⋅x 1 ⋅a ⋅x 0
≥0
y∈ℂ
y ∈ℂ
aH . − 1 ⋅a⋅a H A protože alespoň na jedné straně bude ostrá nerovnost, jinak by muselo platit zároveň x 1=0∧ x =0 . ⇒ Položíme =eH1 ⋅A⋅e 1, e 1=1,0 , ... , 0T 1 H Pro libovolné x ∈ℂ n−1 zvolíme x 1 :=− ⋅a ⋅x , potom platí: H H − 1 ⋅a⋅a H ... 0x ⋅A⋅x= x ⋅ A ⋅... =0
0
1⋅a⋅a H je positivně definitní, Q.E.D. ⇒ A−
,
≥0
Důsl.:
(1) Positivně definitní matice lze rozeznat Gaussovou eliminací. (2) Jacobiho podmínka: Hermitovská matice A řádu n je positivně definitní, právě když mají matice An , ... , A1 kladný determinant, kde Ai vznikne z A umazáním posledních n−i řádků a sloupců. Důkaz: Aplikujeme předchozí tvrzení rekurentně a převedeme do odstupňovaných tvarů …
Bilineární a kvadratické formy
Def: 1. 2. 3. 4.
Nechť V je vektorový prostor nad K a f je zobrazení V ×V K splňující axiomy:
f f f f
∀ u , v , w ∈V : ∀ u , v∈V ∀ ∈ K : ∀ u , v , w∈V : ∀ u , v∈V ∀ ∈ K :
uv , w= f u , w f v , w ⋅u , v=⋅ f u , v u , v w= f u , v f u , w u , ⋅v=⋅ f u , v
Potom se f nazývá bilineární formou V. Bilineární forma je symetrická, platí-li ∀ u , v ∈V : f u , v = f v ,u . Zobrazení g :V K se nazývá kvadratická forma, pokud existuje bilineární forma taková, že ∀ u ∈V : g u = f u , u . Def.:
☼:
☼:
Nechť V je vektorový prostor a X = v 1 ,... , v n je jeho báze, pak matice bilineární formy f vůči bázi X je B, kde platí b i , j = f v i , v j a matice kvadratické formy g je matice symetrické bilineární formy, která g vytvořuje, pokud taková existuje. 1 b i , j = f v i , v j = ⋅ g v iv j −g vi − g v j ⇒ matice kvadratické formy existuje vždy, 2 je-li K charakteristiky ≠ 2 .
Počítání s maticemi formy: T
f u , w =[u ] X⋅B⋅[w ]X , protože
f ∑ a i⋅v i , ∑ b j⋅v j =∑ ∑ ai⋅bj ⋅ f vi , v j i
j
i
j
[ u] X [ w]X
,
B
g u=[u]TX⋅B⋅[u ] X Def.:
Pro bilineární formu f na
n
n
K je její analytické vyjádření polynom f x 1 , ... , x n , y 1 , ... , y n =∑ ∑ x i⋅y j⋅b i , j . T
n
T
i=1 j =1
Podobně analytické vyjádření kvadratické formy vůči dané bázi. Věta:
Sylvesterův zákon o setrvačnosti kvadratických forem Nechť V je prostor konečné dimenze nad ℝ a g :V ℝ je kvadratická forma. Potom existuje báze X taková, že matice g vůči X je diagonální a prvky na diagonále jsou 1, -1 nebo 0, navíc počet 1, -1, 0 nezávisí na X a je pro všechny vhodné báze stejný.
(přednáška 18.5.09) Důkaz: (a) existence Zvolíme libovolnou bázi Y, sestavíme matici B ' formy g vůči Y.
Tedy existuje R, že R−1⋅B '⋅R=R T⋅B '⋅R= D ' . Víme, že pro B matici g vůči X a B ' vůči Y platí B=[id ]TXY⋅B '⋅[id ]XY . Zvolíme B, S diagonální matice, že:
Víme, že B ' je reálná symetrická. Platí, že každá symetrická matice A má vlastní čísla reálná a existuje ortogonální matice R, že A=R⋅D⋅R −1 (známe v „hermitovské“ verzi).
d i ,i0 ⇒b i ,i =1, si , i= d i ,i
14
Lin. algebra – determinanty, polynomy, vlast. čísla a vektory, charakteristický mnohočlen, skalární součin, pos.def. matice, bilineární a kvadratické formy Zbývá již jen hranice 1/-1. Označme n '=rank B =# 1#−1 . Analytické vyjádření formy g je
d i ,i0 ⇒b i ,i =−1, si ,i = −d i ,i
d i ,i=0 ⇒b i ,i =0, si ,i=1 d i,i
0
1
⋱ ⋱
0
−1
⋅
0
d i,i
0 ⋱
⋅
⋱
d i ,i
=
0 ⋱ ⋱
g u=
[u] X = x1 , ... , x nT , r=#1 v B
0 ⋱ 0 0 0 d d d i ,i
S
i,i
B
T
S
i ,i
y 21 y 22... y 2s − y2s1 −...− y 2n ' , kde
D= DT
Čili platí RT ⋅B '⋅R= S T⋅B⋅S , S, R regulární. ⇒ B=S ⋅R ⋅B '⋅R⋅S , čili pro bázi X: [id ]XY =R⋅S platí, že matice B formy g vůči X je diagonální a dle znění věty „(1, -1, 0)“. Pozn., sloupce [id ]XY jsou tvořeny souřadnicemi vektorů hledané báze X vůči bázi Y. (b) jednoznačnost: Značení: g :V ℝ , X =v 1 , ... , v n ,Y =w 1 , ... , w n dvě báze takové, že matice formy g vůči X, Y jsou B, B' diagonální ve tvaru T −1
T
1 ⋱ 1
0 −1 ⋱ −1
0
−1
−1
0 ⋱
x 21 x 22... x2r − x 2r1 −...−x 2n ' , kde
[u]Y = y 1 ,... , y n T , s=# 1 v B' Pro spor ať r s . L{v1 , ..., v r }∪ L{w s1 , ... , w n } , Zvolíme netriviální z∈ L1
dim U dim V =dim LU ∪V dim LU ∩V . z∈L{v 1 ,... , vr }∖ {0 }⇒ pro [z ]X = x1 , ..., xr T je alespoň jedno z x 1 , ..., xr ≠0 a zároveň xr1 , ... , x n=0⇒ g z 0 .
(odlišné jen délkou úseků).
z∈L{w s1 , ... , w n}∖ { 0 }⇒ pro [z ]Y = y s 1 , ... , yn T je alespoň jedno z y s1 ,... , y n≠0 ; y1, ... , ys =0 , čili
0
Pozorování: #0 v B=n−rank B
=
g z = y 21... y 2s − y 2s1−...− y 2n' ≤0 , SPOR. Q.E.D.
n−rank B '= #0 v B'.
=0
B =RT⋅B '⋅R
Def:
L2
dim L1 =r , dim L2 =n− s . Víme, že pro U, V platí
Vektoru # 1,# −1, # 0 se říká signatura formy, respektive signatura symetrické matice, a příslušná báze se nazývá polární báze.
Úloha: Na závěr, kolik lze v ℝd nalézt nejvíce přímek, aby každé dvě svíraly stejný úhel? (pokud někdo chce, abych přepsal i tuto úlohu, nechť se mi ozve)
15
