UNIVERZA V LJUBLJANI
FAKULTETA ZA MATEMATIKO IN FIZIKO
Finančna matematika – 1. Stopnja
Bor Rotar
INVERZNI PROBLEM LASTNIH VREDNOSTI ZA NENEGATIVNE MATRIKE MAJHNIH
REDOV
Delo diplomskega seminarja Mentor : doc. dr. Gregor Cigler
Ljubljana, 2021
KAZALO
UVOD ... 5
1. Definicije in že znane trditve oz. izreki ... 6
2. Trditev o konstrukciji ... 7
3. Primera 2x2 in 3x3 ... 10
4. Primer 4x4 ... 12
5. Primer 5x5 ... 17
6. Pridružena matrika (Companion Matrix) ... 27
7. Zgledi ... 27
8. Razširjanje že znanega spektra nenegativne matrike z realnim številom ... 30
9. Razširjanje že znanega spektra nenegativne matrike s konjugiranim parom ... 31
10. Uporaba razširjanja spektra na prehodu iz 5x5 na 6x6 matriko ... 32
Slovar strokovnih izrazov... 35
LITERATURA ... 36
Inverzni problem lastnih vrednosti za nenegativne matrike majhnih redov POVZETEK
Delo obravnava inverzni problem lastnih vrednosti nenegativnih matrik manjših dimenzij. Nanaša se predvsem na članek A. M. Nazarija in Sherafata z naslovom On the inverse eigenvalue problem for nonegative matrices of order two to five. Obravnavamo problem do dimenzije 5x5 s trditvami in njihovimi dokazi, hkrati pa tudi sestavimo pravila oz.
pogoje s katerimi pridemo do matrik večjih dimenzij in možnih začetkov trditev za te dimenzije. Z dokazi tudi pridemo do preprostih nastavkov, če želimo iz danih lastnih vrednosti, ki upoštevajo pogoje, priti takoj do nenegativne matrike. V dokazih matrike sestavimo s trditvijo o konstrukciji, ki je tudi razložena v delu.
The inverse eigenvalue problem for nonnegative matrix of smaller dimensions ABSTRACT
The work focuses on the inverse eigenvalue problem for nonnegative matrix of smaller dimensions with its main source being a research article by A. M. Nazari and F. Sherafat titled On the inverse eigenvalue problem for nonnegative matrices of order two to five. We study the problem of dimensions for up to 5x5 with corresponding thesis and proof. Simultaneously we also try to find conditions with which we can address problems of bigger dimensions and possible sources for claims for those dimensions. With proofs we also get matrix “models” if we want to quickly find the possible nonnegative solution for the given values. We create the matrix using the newer claim of construction, that is also explained.
Math. Subj. Class. (2021): 65F18, 15A15, 15A18, 47A10
Ključne besede: NIEP problem, nenegativni problem lastnih vrednosti matrik, konstrukcija nenegativnih matrik, matrike manjših dimenzij, spekter matrike, pridružena matrika.
Keywords: NIEP problem, inverse eigenvalue problem for nonnegative matrix, construction of nonnegative matrix, matrix of smaller dimensions, matrix spectrum, companion matrix.
5
UVOD
Inverzni problem lastnih vrednosti nenegativnih matrik ali NIEP, je del večjega skupka inverznih problemov lastnih vrednosti, ki so eni od težjih problemov v linearni algebri. Radi bi čim hitreje ugotovili ali obstaja matrika s poljubnimi lastnostmi, katere lastne vrednosti so izbrana števila. Rešitve teh problemov so uporabne povsod, kjer podatke, procese, produkcijo
… predstavljamo z matrikami in nam lastne vrednosti teh matrik predstavljajo neke dinamične parametre. Uporabne so tudi za konstrukcije željenih matrik. Trditve in začetni pogoji, ki so predstavljeni, pokrivajo problem do velikosti 5x5 in izhajajo iz članka A. M. Nazarija in Sherafata z naslovom On the inverse eigenvalue problem for nonegative matrices of order two to five. Predstavili bomo vse potrebne izreke za dokazovanje. Potem bomo predstavili nove trditve iz članka in njihove dokaze. Pokazali bomo še uporabo teh trditev na zgledih in
predstavili še pridruženo matriko oz. pogoj, ki sledi iz nje. Na koncu bomo dodali posledice in možne izpeljave iz teh trditev za dodajanje števil v spekter matrike.
6
1. Definicije in že znane trditve oz. izreki
Matrike, ki jih obravnavamo, imajo elemente v . Najprej bomo omenili vse (manj) znane definicije in trditve oz. izreke potrebne za nadaljnje izjave ter njihove dokaze in začetne pogoje, ki sledijo iz njih.
Definicija 1.1. Seznam kompleksnih števil ( ) je spekter matrike, če so vse njene lastne vrednosti.
Definicija 1.2. U je unitarna matrika, če velja . Stolpci/vrstice unitarne matrike so med seboj pravokotni in tvorijo ortonormirano bazo. R je ireducibilna matrika, če R ni permutacijsko podobna bločni zgornje trikotni matriki (s preureditvijo stolpcev/vrstic ne moremo dobiti zgornje trikotno matriko). O je ortogonalna matrika, če je O realna matrika, ki je unitarna.
Izrek 1.3. (Perron Frobenius)
Če je A irreducibilna nenegativna matrika, velja:
Perronova lastna vrednost r = max{ | | } je lastna vrednost A.
Obstaja tak nenegativen vektor , da velja .
Izrek 1.4. (Schurova forma) Za vsako matriko A obstajata unitarna matrika Q in zgornje trikotna matrika T, da je .
Definicija 1.4. Naj bo , Jordanova kletka ali je matrika naslednje oblike
[ ]
Jordanska kanonična forma kompleksne matrike A pa je bločno diagonalna matrika , ki ima Jordanove kletke za bloke.
Izrek 1.5. Vsaka kvadratna kompleksna matrika A je podobna matriki v Jordanski kanonični formi, .
Definicija 1.6. Sled kvadratne matrike oz tr(A) je vsota njenih diagonalnih elementov.
Trditev 1.7. Dve podobni matriki imata isto sled. Za dve kvadratni matriki istih dimenzij X in Y velja tr(XY) = tr(YX).
7
Nekateri potrebni pogoji, da je seznam kompleksnih števil spekter nenegativne matrike oz. da je to seznam lastnih vrednosti neke nenegativne matrike, so:
Perronova lastna vrednost max | | je v (posledica Perron Frobeniusovega izreka).
je zaprt za kompleksno konjugacijo, saj kompleksne lastne vrednosti nastopajo v konjugiranih parih.
∑ za k , sledi iz tega, da je vsaka matrika podobna matriki v Jordanovi kanonični formi in da imajo podobne matrike enako sled.
2. Trditev o konstrukciji
Nadaljne nove trditve nam bodo dale postopek za dokazovanje trditev za matrike velikosti 3,4 in 5.
TRDITEV (o konstrukciji)
Naj bo B nenegativna matrika, njen spekter in Perronova lastna vrednost . Naj bo A nenegativna matrika oblike
[ ], Kjer je velikosti in a, b
, potem obstaja nenegativna matrika dimenzije , ki ima za spekter.
Dokaz trditve:
Naj bo s normaliziran (vsota kvadratov elementov je 1) lastni vektor za B pri Perronovi lastni vrednosti . Poiščemo matriko , da je [ ] unitarna matrika.
Potem [ ] [ ].
Sledi: [ ]
[
̂
]
Skalarni produkt je vektor ničel zaradi unitarnosti matrike [ ].
8
̂ in njene lastne vrednosti so . Po Schurovi dekompoziciji obstaja unitarna matrika , dimenzije , da velja:
̂ ̂ , kjer je ̂ zgornje trikotna matrika, katere diagonalni elementi so lastne vrednosti ̂.
Definiramo:
[ ]
, ker je unitarna je tudi unitarna
, [ ] [ ] * +
Y je unitarna in za , ki je dimenzije , velja , ker so stolpci ortonormiran sistem.
(identiteta dimenzije ) * + [ ]
*
+ * ̂ + je zgornje trikotna matrika, na diagonali ima vrednosti .
Podobno za A obstaja unitarna matrika X, da je . je zgornje trikotna matrika z na diagonali.
* + [ ] , dimenzije in dimenzije .
*
+ * + (1)
9 Uvedemo novi matriki :
*
+ * + in [
] . Iz enakosti (1) vidimo, da je Z unitarna, C pa je nenegativna.
[
]
[
̂ ]
Matrika je zgornje trikotna, njeni diagonalni elementi pa so elementi . Ker sta matriki in C podobni, imata iste lastne vrednosti, torej C reši zadani problem.
☐ POMEMBNA POVEZAVA IZ TRDITVE ZA NAPREJ:
[ ] , nenegativna matrika,
B nenegativna matrika, , s normaliziran lastni vektor Perronove lastne vrednosti
[
]
nenegativna matrika, . Ta povezava se bo uporabljala za nadaljnje dokaze.
10
3. Primera 2x2 in 3x3
TRDITEV 3.1. (primer 2x2)
Naj bo { , da velja | |. Potem je spekter nenegativne matrike.
Dokaz trditve 3.1.:
Pokazati moramo, da obstaja matrika, ki ima za lastne vrednosti:
a) če je , potem [ ] reši problem. (2.a)
b) če je , potem [
] reši problem. (2.b)
☐
TRDITEV 3.2. (primer 3x3)
Naj bo množica kompleksnih števil.
| |
| |
| |
Če števila v zadostujejo naslednjim pogojem, obstaja nenegativna matrika C dimezije 3x3, katere spekter je :
̅
| |
če je ( ) .
11 Dokaz trditve 3.2.:
Najprej poglejmo primere, če so vsi elementi v realna števila:
a) če sta [ ] reši problem. (3.a)
b) če sta , uporabimo trditev o konstrukciji:
[
] po (2.b) [
]
[
√ √ ] je normaliziran lastni vektor Perronove lastne vrednosti .
[
√ √
√
√
]
reši problem. (3.b)
c) če je in , potem [
] reši problem. (3.c) (Zgornji 2x2 del je iz (2.b))
Naj bosta zdaj konjugiran kompleksni števili:
d) če je , potem [
] reši problem. (3.d)
e) če je , potem mora veljati in *
| |
+. (3.e)
Za oba primera, z izračunom ničel karakterističnega polinoma ( ), pokažemo, da je res spekter matrike C.
☐
12
4. Primer 4x4
TRDITEV 4. (primer 4x4)
Naj bo množica kompleksnih števil.
| |
| |
| |
Če števila v zadostujejo naslednjim pogojem, obstaja nenegativna matrika C s spektrom :
̅
| |
če sta in konjugiran par in , mora veljati še:
(4.1) če je ( ) ; (4.2) če je ( ) ; (4.3) če je ( )
in (( | | | | .
13 Dokaz trditve:
Poglejmo primere, če so vsi elementi v realna števila:
a) če so [ ] reši problem. (4.a)
b) če so , uporabimo trditev o konstrukciji:
[
√ √
√
√
]
, , to je matrika (3.b).
[
]
[
√ √ ] je normaliziran lastni vektor Perronove lastne vrednosti .
[
√ √ √ √ √
√
√
√
√ √
√
√ √ √
]
reši problem. (4.b)
c) če je in uporabimo C iz (3.c) za zgornji 3x3 blok novega C :
[
] reši problem. (4.c)
14
d) če sta in in (( :
naj velja potem [
] reši problem. (4.d)
e) če sta in in ( :
[ ] [
]ortogonalna matrika.
[
]
(4.e) Naj bosta zdaj kompleksen kojugiran par:
f) če je
[ ] reši problem, kjer je A matrika iz (3.d) (0 tu predstavlja stolpec/vrstico ničel).
(4.f) g) če je , uporabimo trditev o konstrukciji:
Za A vzamemo matriko iz (3.d) s in [
] s
je Perronova lastna vrednost z normaliziranim lastnim vektorjem
(
√ √
) , zato
15
[
√ √
√ √
√
√
]
reši problem. (4.g)
h) če je , velja (4.2) torej in
[ ] reši problem, kjer je A (3.e). (4.h)
i) če je , velja (4.3) torej in (( | |
| | .
1. Naj velja | | . Uporabimo trditev o konstrukciji:
*
| |
+ s (rešitev (3.e))
[
] s
je Perronova lastna vrednost z normaliziranim lastnim vektorjem (
√ √
) ,
zato
[
√ √
√
| |
√
√
| |
√
]
reši problem. (4.i.1)
16
2. Naj velja | |. Uporabimo trditev o konstrukciji:
*
| |
+ s
[
] s
je Perronova lastna vrednost z normaliziranim lastnim vektorjem (
√ √
) ,
torej
[
| |
√
| |
√
√ √
√
√
]
reši problem. (4.i.2)
☐
17
5. Primer 5x5
TRDITEV 5. (primer 5x5)
Naj bo množica kompleksnih števil.
| |
| |
| |
| |
| |
| |
| | | |
| |
| |
| |
| |
| |
Če števila v zadostujejo naslednjim pogojem, obstaja nenegativna matrika C s spektrom :
18 (5.1)
(5.2) ̅ ;
(5.3) | | Če so vsa števila v realna, mora veljati:
(5.4) če sta ; (5.5) če so ;
Če je , kompleksen konjugiran par in realni števili, mora veljati:
(5.6) če sta ; (5.7) če sta ;
(5.8) če je ;
(5.9) če je ;
(5.10) če je | | | | ; (5.11) če sta ;
(5.12) če sta | | če sta | | ;
Če sta , in , dva konjugirana kompleksna para, mora veljati:
(5.13) če sta ;
(5.14) če je ;
(5.15) če je ; (5.16) če je ; (5.17) če je ; (5.18) če je .
19 Dokaz trditve:
Naj bodo vsi elementi v realna števila:
a) če so
[ ]
reši problem. (5.a)
b) če so , uporabimo trditev o konstrukciji:
Za A vzamemo matriko (4.b) s . [
] s
je Perronova lastna vrednost z normaliziranim lastnim vektorjem
(
√ √
) .
Označimo: √ √ √ .
[
]
reši problem.
(5.b) c) če je , [ ] reši problem, kjer je A rešitev (4.c).
d) če sta , velja (5.4), torej .
[
]
reši problem. (5.d)
20
e) če so , velja (5.5), torej . [ ] reši problem, kjer je A rešitev (4.b).
Naj bosta , kompleksen konjugiran par in realni števili:
f) če sta , velja (5.6), torej . [ ] reši problem, kjer je A rešitev (4.f).
g) če sta , velja (5.7), torej . [ ] reši problem, kjer je A rešitev (4.h).
h) če je , velja (5.8), torej . [ ] reši problem, kjer je A rešitev iz (4.g).
i) če je , velja (5.9), torej . Uporabimo trditev o konstrukciji:
*
| |
+ s (rešitev (3.e))
[
] s
je Perronova lastna vrednost z normaliziranim lastnim vektorjem ( ) . Na koncu dodamo še na diagonalo in dobimo rešitev:
[
| |
| |
]
. (5.i)
j) če je ,
velja (5.10), torej | | | | .
[ ] reši problem, kjer je A rešitev (4.i.1) v prvem primeru in rešitev (4.i.2) v drugem.
21
k) če sta , velja (5.11), torej . Sledi, da velja . Uporabimo trditev o konstrukciji:
[
]
s (rešitev (4.g))
[
] s
je Perronova lastna vrednost z normaliziranim lastnim vektorjem ( ) ,
Zato
[
]
reši problem. (5.k)
l) če sta ,
potem po (5.12) velja | | | | V prvem primeru uporabimo trditev o konstrukciji:
[
| |
| |
]
s (rešitev (4.i.1))
[
] s
je Perronova lastna vrednost z normaliziranim lastnim vektorjem ( ) ,
22 torej
[
| |
| |
| |
]
reši problem.
(5.l.1) V drugem primeru na podoben način:
[
| | | |
]
s (rešitev (4.i.2))
[
] s
je Perronova lastna vrednost z normaliziranim lastnim vektorjem ( ) ,
zato
[
| | | | | |
]
reši problem.
(5.l.2)
23
Naj bosta , in , sta dva konjugirana kompleksna para:
m) če sta , velja (5.13) oz. . Za iskanje rešitev bomo uporabili trditev o konstrukciji na 3x3 matrikah iz dokaza pri :
[
] s (rešitev (3.d))
*
| |
+ s (prirejena rešitev (3.d))
Dokažimo, da je s Perronova lastna vrednost za B. Ker je in oz.
| | , sledi in , kjer je .
| |
| |
Torej s je res Perronova lastna vrednost matrike B. Definiramo √ | | . Perronov normaliziran lastni vektor je potem (| | ) . Po trditvi o konstrukciji:
[
| |
| | | |
| |
]
reši problem. (5.m)
n) če je , velja (5.14) oz. . Podobno kot prej uporabimo trditev o konstrukciji:
[
] s (rešitev (3.d))
*
| |
| |
+ s (prirejena rešitev (3.e))
24
Sledi, da je s Perronova lastna vrednost z normaliziranim lastni vektorjem ( | | ) , kjer je √ | | .
[
| |
| |
| | | |
| | ]
reši problem. (5.n)
o) če je , velja (6.15) oz. . Uporabimo trditev o konstrukciji:
*
| |
+ s (prirejena rešitev (3.e))
*
| |
+ s (prirejena rešitev (3.d))
Sledi, da je Perronova lastna vrednost (sklep podoben kot v m)) z normaliziranim lastnim vektorjem (| | ) , kjer je √ | | .
[
| |
| | | | | |
| |
| |
| |
]
reši problem. (5.o)
25
p) če je , velja (5.16) oz. . Uporabimo trditev o konstrukciji:
*
| |
+ s (prirejena rešitev (3.e))
*
| |
| |
+ s (prirejena rešitev (3.e))
Sledi, da je Perronova lastna vrednost (sklep podoben kot v m)) z normaliziranim lastnim vektorjem (| | ) , kjer je √ | | .
[
| |
| | | | | |
| |
| |
| |
| | ]
reši problem. (5.p)
q) če je velja (5.17) oz. . Uporabimo trditev o konstrukciji:
*
| |
+ s
*
| |
+ s (prirejena rešitev (3.e))
Sledi, da je Perronova lastna vrednost (sklep podoben kot v m)) z normaliziranim lastnim vektorjem (| | ) , kjer je √ | | .
26
[
| | | | | | | |
| |
| |
| |
]
reši problem. (5.q)
r) če sta velja (5.18) oz. . Uporabimo trditev o konstrukciji:
*
| |
+ s
*
| |
| |
+ s (prirejena rešitev (3.e))
Sledi, da je Perronova lastna vrednost z normaliziranim lastnim vektorjem ( | | ) , kjer je √ | | .
[
| | | | | | | |
| |
| |
| | ]
reši problem. (5.r)
☐
27
6. Pridružena matrika (Companion Matrix)
Pridružena matrika nam da še en kriterij za obstoj nenegativne matrike.
Definicija: Pridružena matrika polinoma je kvadratna matrika naslednje oblike:
[
]
Važna lastnost te matrike je predvsem, da je njen karakteristični polinom in celo njen minimalni polinom. Če imamo podane lastne vrednosti in za
velja , je rešitev NIEP.
7. Zgledi
Ali je spekter nenegativne matrike?
Ker so nekateri koeficienti pred pozitivni, drugi pa negativni, p nima nenegativne
pridružene matrike. Uporabimo trditev 5. Vsota elementov je nenegativna, je zaprta za konjugiranje in je absolutno največja.
| |
| | | |
28
| |
| |
| |
| |
velja (5.18)
Nahajamo se v primeru (5.r), torej je to spekter nenegativne matrike C:
√ | | √
[
| | | | | | | |
| |
| |
| | ]
[
]
29
Ali je spekter nenegativne matrike?
Ker so nevodilni koeficienti negativni, lahko najdemo nenegativno pridruženo matriko, ki reši ta problem.
[
]
Če uporabimo trditev 5., odkrijemo, da smo v primeru (5.l.1), kar nam da rešitev:
[
√
√ √
√ √ √
√
√
√
√ √
√ √
√
√ √
√ √
√ ]
30
8. Razširjanje že znanega spektra nenegativne matrike z realnim številom
Naj bo množica kompleksnih števil, ki je spekter nenegativne matrike A velikosti nxn. Množici zdaj dodamo še . Zanima nas, kaj mora veljati za , da lahko s trditvijo o konstrukciji pridemo do nenegativne matrike s spektrom . Veljati morajo začetni pogoji:
)
̅
| |
Če je , je rešitev preprosta. Vzamemo matriko A in ji dodamo vrstico in stolpec ničel in na mesto .
[
] reši problem.
Če je , bi pa uporabili trditev o konstrukciji kot pri dokazu trditve 5.
V tem primeru moramo najti nenegativno 2x2 matriko, ki bo imela Perronovo lastno vrednost
| |. Sestavimo matriko, ki smo jo uporabili za dokaz trditve 2.
[
] s
ima normaliziran lastni vektor (
√ √
)
Matriki A in B lahko zdaj združimo s trditvijo o konstrukciji in dobimo nenegativno matriko s spektrom
31
9. Razširjanje že znanega spektra nenegativne matrike s konjugiranim parom
Naj bo spekter nenegativne matrike A velikosti nxn. Množici zdaj dodamo konjugiran par . Zanima nas, kaj vse mora veljati za , da lahko s trditvijo o konstrukciji pridemo do nenegativne matrike s spektrom
. Veljati morajo začetni pogoji:
̅
| | | | ( ) Najti moramo nenegativno 3x3 matriko, ki bo imela Perronovo lastno vrednost
| |. Matriko sestavimo s pomočjo dokaza trditve za 3x3 (3.d) in (3.e).
Potrebujemo
če , izberemo *
+.
če , potem mora veljati:
| |
| |
| | Definiramo *
| |
+.
Matriki A in B lahko zdaj združimo s trditvijo o konstrukciji in dobimo nenegativno matriko s spektrom .
32
10. Uporaba razširjanja spektra na prehodu iz 5x5 na 6x6 matriko
Naj bo množica kompleksnih števil, za katere najdemo nenegativno matriko A z uporabo trditve za 5x5. Zanima nas, kaj vse mora veljati za , da najdemo nenegativno 6x6 matriko, katere spekter je .
Začetni pogoji:
| | | | Če je , [ ] reši problem.
Če je , pa uporabimo trditev o konstrukciji. Veljati mora | |. To kombiniramo s pogoji za 5x5 in dobimo pogoje za 6x6 predstavljene z naslednjima tabelama.
Ti pogoji, nam dajo nekaj kriterijev za obstoj 6x6 nenegativne matrike.
33
Začetni pogoji: ; ̅ ; | | ;
; ; | |;
Pogoji za 5x5 Nov pogoj
| |
| |
| |
| |
, | |
(,) kompleksen konjugiran par
, | |
| |
; | |
; | | ;
| | | |
| |
| |
; | | | | ; | | | |
Tabela 1: Pogoji za prehod iz 5x5 na 6x6, če je (1)
34
Pogoji za 5x5 Nov pogoj
(,) in () kompleksna konjugirana para ; | |
; 0 | |
| |
; | |
;
| |
; 0 | | Tabela 2: Pogoji za prehod iz 5x5 na 6x6, če je (2)
Pri dveh kompleksnih konjugiranih parih smo prišli do pogoja 0 | |, kar nasprotuje pogoju oz. predpostavki . V teh primerih torej na ta način ne moremo razširiti spektra.
35
Slovar strokovnih izrazov
NIEP – nonnegative inverse eigenvalue problem inverzni problem lastnih vrednosti nenegativne matrike
companion matrix of a polinom pridružena matrika polinoma spectrum spekter, množica lastnih vrednosti matrike
36
LITERATURA
[1] A. M. Nazari in F. Sherafat, On the inverse eigenvalue problem for nonnegative matrices of order two to five, verzija april 2012, [ogled 7.8.2021], dostopno na
https://www.researchgate.net/publication/256805489_On_the_inverse_eigenvalue_problem_f or_nonnegative_matrices_of_order_two_to_five
[2] Anja Jozelj, Inverzni problem lastnih vrednosti za posebne matrike, diplomsko delo, Fakulteta za matematiko in fiziko, Univerza v Ljubljani, 2012.
[3] T.J. Laffey, Helena Šmigoc, On a Classic Example in the Nonnegative Inverse Eigenvalue Problem, vol. 17, ELA, Julij 2008, strani 333–342.
[4] Cian Jameson, The non-negative inverse eigenvalue problem Undergraduate Summer Research Project Report, raziskovalno delo, avgust 2018, [ogled 7.8.2021], dostopno na
https://www.ucd.ie/mathstat/t4media/CJ%20Report.pdf
