Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
26
Rozdział1.Wybranefaktyzanalizyialgebryliniowej
wtedy,gdy
aij>
0,1
˛ijj˛n
.Mówimy,że
A
jestnieredukowalna(nieprzy-
wiedlna),jeśligrafskierowanyodpowiadający
D
jest(silnie)spójny.Jeślinie,
tomówimy,żeAjestredukowalna(przywiedlna).
Równoważna,algebraiczna,definicjanieredukowalnościmacierzywymaga
wprowadzenienowychoznaczeń.Zapiszmyk-tąpotęgęmacierzywpostaci
Ak=1a
(k)
ij)
1˛i,j˛n
.
Widzimy,że
a
(k)
ij
=
1˛ir˛n,rl1,...,k11
ÿ
aii
1·ai
1i2·...·ai
k≠1j.
Jeśli
aii
1·ai
1i2·...·ai
k≠1j”
=0
j
towodpowiadającymjejdigrafieistniejedroga
zaczynającasięwwierzchołku
vj
ikończącaw
vi
.Ponieważwspółczynniki
macierzysąnieujemne,więcaby
a
(k)
i,j”
=0wystarcza,byistniałatylkojedna
takadroga.Zatem
A
jestnieredukowalnawtedyitylkowtedy,gdydlakażdej
pary(ijj)istniejektakie,żea
(k)
i,j>0.
Uwaga1.4.Widzimy,żewdefinicjinieredukowalnościgrafupętle(
vijvi
)
niemająznaczenia.Zatemrównieżwprzypadkumacierzywspółczynnikina
przekątnejnieodgrywajążadnejroli.
Jeślimacierzjestredukowalna,towodpowiadającymjejdigrafieistnieją
wierzchołki
vi
i
vjj
któreniesąpołączoneżadnądrogą.Równoważnie,macierz
A
jestredukowalna,jeślizapomocąjednoczesnychpermutacjitychsamych
wierszyikolumnmożnająsprowadzićdopostaci
AA110
A21A22Bj
Przykład1.4.
Macierzenieujemnemajązastosowaniewmodelachzdyskretną
strukturąwieku,jakrównieżwopisywaniuprocesówmigracji,wczasiedys-
kretnym.Współczynnik
aij
takiejmacierzyopisujewkładgrupy
j
dogrupy
i
,Chap-
ter2]).Naprzykładtzw.macierzUshera
Q
c
c
c
a
a21
0
0
0
a32
0
0
0
a13
a43a44
0
0
0
0
0
R
d
d
d
b
