wyklad05.pdf
(
110 KB
)
Pobierz
55622554 UNPDF
WykÃlad5
Permutacje
Niech
n¸
2b
,
edzieustalon
,
aliczb
,
anaturaln
,
a.Niech
X
n
=
{
1
,
2
,...,n}
.Ka˙zd
,
abijekcj
,
e
f
:
X
n
−!X
n
nazywamy
permutacj
,
a
zbioru
X
n
.Poniewa˙zzbi´or
X
n
jestsko´nczony,wi
,
ec
funkcja
f
:
X
n
−!X
n
jestpermutacj
,
awtedyitylkowtedy,gdy
f
jestr´o˙znowarto´sciowa(lub
r´ownowa˙znie,wtedyitylkowtedy,gdy
f
jest”na”).
Zbi´orwszystkichpermutacjizbioru
X
n
oznaczamyprzez
S
n
.JakwiadomozeszkoÃly´sredniej
S
n
posiadadokÃladnie
n
!=1
·
2
·...·n
element´ow.Zewst
,
epudomatematykiwynika,˙zezÃlo˙zenie
permutacjizbioru
X
n
jestpermutacj
,
ategozbioru,skÃladaniepermutacjijestÃl
,
aczne,posiada
elementneutralny
e
,kt´orymjestprzeksztaÃlcenieto˙zsamo´sciowezbioru
X
n
wsiebieiponadto
ka˙zdapermutacja
f2S
n
posiadaprzeksztaÃlcenieodwrotne
f
−
1
,kt´orete˙zjestpermutacj
,
a
zbioru
X
n
(oczywi´scie
f±f
−
1
=
f
−
1
±f
=
e
).
Permutacj
,
e
f2S
n
wygodniejestzapisywa´cwpostacidwuwierszowejtablicy
Ã
!
1 2
... i ... n
f
(1)
f
(2)
...f
(
i
)
...f
(
n
)
f
=
,
(1)
wkt´orejwpierwszymwierszuumieszczones
,
awszystkieelementyzbioru
X
n
(najcz
,
e´sciejw
porz
,
adkurosn
,
acym),za´swdrugimwierszuumieszczones
,
akolejneobrazytychelement´owprzy
odwzorowaniu
f
.ZatemnaprzykÃlad
Ã
!
12
... i ...n
12
... i ...n
e
=
.
(2)
Inwersj
,
apermutacjif2S
n
nazywamytakipodzbi´ordwuelementowy
{i,j}
zbioru
X
n
,˙ze
i<j
oraz
f
(
i
)
>f
(
j
).Zbi´orwszystkichinwersjipermutacji
f2S
n
oznaczamyprzez
I
f
.Np.
I
e
=
;
,wi
,
ec
|I
e
|
=0,czylipermutacjato˙zsamo´sciowanieposiadainwersji.
PrzykÃlad1.Niech
i,j2X
n
,
i<j
.Oznaczmyprzez(
i,j
)permutacj
,
ezbioru
X
n
,kt´ora
zamieniamiejscamielementy
i
,
j
orazniezmieniapozostaÃlychelement´owzbioru
X
n
(takie
permutacjenazywamy
transpozycjami
).Zatem
Ã
!
12
... i−
1
ii
+1
...j−
1
jj
+1
...n
12
... i−
1
ji
+1
...j−
1
ij
+1
...n
(
i,j
)=
.
(3)
| {z }
j−i
,
{
i
+1
,j},{i
+2
,j},{
i
+3
,j},...,{j−
1
,j
}
| {z }
(
j−
1)
−i
}
.Zatem
|I
(
i,j
)
|
=(
j−i
)+(
j−
1)
−i
=2(
j−i
)
−
1.Uzyskali´smyzatem,˙zeka˙zdatranspozycjaposiadanieparzyst
,
aliczb
,
ewszystkich
inwersji.
Znakiempermutacjif2S
n
nazywamyliczb
,
e
sgn
(
f
)okre´slon
,
awzorem:
sgn
(
f
)=(
−
1)
|I
f
|
.
(4)
1
St
,
ad
I
(
i,j
)
=
{{
i,i
+1
},{i,i
+2
},{i,i
+
3
},...,{i,j−
1
},{i,j
}
Powiemy,˙zepermutacja
f2S
n
jest
parzysta
,je´sli
sgn
(
f
)=1oraz,˙ze
f
jestnieparzyta,
je´sli
sgn
(
f
)=
−
1.ZatemzprzykÃladu1mamy,˙zedowolnatranspozycjajestpermutacj
,
a
nieparzyst
,
a.Poniewa˙z
sgn
(
e
)=(
−
1)
0
=1,wi
,
ecpermutacjato˙zsamo´sciowajestparzysta.
Zbi´orwszystkichpermutacjiparzystych
f2S
n
b
,
edziemyoznaczaliprzez
A
n
.
Twierdzenie1.Dladowolnychpermutacji
f,g2S
n
zachodziwz´or:
sgn
(
f±g
)=
sgn
(
f
)
·sgn
(
g
)
.
(5)
Wszczeg´olno´sci
sgn
(
f
−
1
)=
sgn
(
f
).
Dow´od.Oznaczmyprzez
P
n
rodzin
,
ewszystkichpodzbior´owdwuelementowychzbioru
X
n
.
Niech
h2S
n
.We´zmydowolne
A2P
n
.Wtedy
A
=
{i,j}
dlapewnych
i,j2X
n
,
i6
=
j
.
Oznaczmy
sgn
h
(
A
)=
sgn
³
h
(
i
)
−h
(
j
)
i−j
´
.Okre´slenietojestpoprawne,bo
h
(
j
)
−h
(
i
)
j−i
=
−
(
h
(
i
)
−h
(
j
))
−
(
i−j
)
=
h
(
i
)
−h
(
j
)
i−j
.Ponadto
A2I
h
,sgn
h
(
A
)=
−
1.Wynikast
,
adwz´or:
Y
sgn
(
h
)=
sgn
h
(
A
)
.
(6)
A2P
n
ÃLatwozauwa˙zy´c,˙zedowolnapermutacja
g2S
n
wyznaczabijekcj
,
e
G
:
P
n
−!P
n
przypomocy
wzoru
G
(
A
)=
{g
(
i
)
,g
(
j
)
}
dla
A
=
{i,j}
.Wynikast
,
ad,˙zedladowolnych
f,g2S
n
zachodzi
wz´or:
Y
sgn
(
f
)=
sgn
f
(
G
(
A
))
.
(7)
A2P
n
Ponadtodla
A2P
n
mamy,˙ze
sgn
f
(
G
(
A
))
·sgn
g
(
A
)=
sgn
f±g
(
A
)
.
(8)
.Ale
sgn
(
x
)
·sgn
(
y
)=
sgn
(
x·y
)dladowolnychliczbrzeczywistych
x
,
y
,wi
,
ec
sgn
f
(
G
(
A
))
·sgn
g
(
A
)=
sgn
³
f
(
g
(
i
))
−f
(
g
(
j
))
g
(
i
)
−g
(
j
)
´
oraz
sgn
g
(
A
)=
sgn
³
g
(
i
)
−g
(
j
)
i−j
´
³
f
(
g
(
i
))
−f
(
g
(
j
))
g
(
i
)
−g
(
j
)
·
g
(
i
)
−g
(
j
)
´
³
(
f±g
)(
i
)
−
(
f±g
)(
j
)
i−j
´
=
sgn
=
sgn
f±g
(
A
).
i−j
Zatemnamocy(6),(8)i(7)mamy,˙ze
sgn
(
f±g
)=
Y
Y
Y
Y
sgn
f±g
(
A
)=
[
sgn
f
(
G
(
A
))
·sgn
g
(
A
)]=
sgn
f
(
G
(
A
))
·
sgn
g
(
A
)=
Y
A2P
n
Y
A2P
n
A2P
n
A2P
n
sgn
f
(
A
)
·
sgn
g
(
A
)=
sgn
(
f
)
·sgn
(
g
).
Wszczeg´olno´scimamyst
,
ad,˙ze1=
sgn
(
e
)=
sgn
(
f±f
−
1
)=
sgn
(
f
)
·sgn
(
f
−
1
),czyli
sgn
(
f
−
1
)=
sgn
(
f
).Ko´nczytodow´odnaszegotwierdzenia.
A2P
n
Okre´sleniemacierzy
Niech
K
b
,
edziedowolnymciaÃlemorazniech
n
i
m
b
,
ed
,
adowolnymiliczbaminaturalnymi.
Prostok
,
atn
,
atablic
,
e
2
6
6
6
6
4
a
11
a
12
...a
1
n
a
21
a
22
...a
2
n
.
.
.
.
.
.
.
.
.
.
.
.
a
m
1
a
m
2
...a
mn
3
7
7
7
7
5
(9)
2
Rzeczywi´scie,
A
=
{i,j}
dlapewnych
i,j2X
n
,
i6
=
j
oraz
sgn
f
(
G
(
A
))=
sgn
f
(
{g
(
i
)
,g
(
j
)
}
)=
sgn
A2P
n
utworzon
,
azelement´ow
a
ij
(
i
=1
,
2
,...,m
;
j
=1
,
2
,...,n
)ciaÃla
K
nazywamy
m×n
-
macierz
,
a
nadciaÃlem
K
.Elementy
a
ij
nazywamy
wyrazami
macierzy.Rz
,
edypionowenazywamy
kolum-
nami
,apoziome-
wierszami
tejmacierzy.Zatemelement
a
ij
stoiw
i
-tymwierszui
j
-tej
kolumnierozpatrywanejmacierzy.
n×n
-macierze,nazywamy
macierzamikwadratowymistopnian
.
Dwiemacierzenazywamyr´ownymi,je˙zelijakotablices
,
aidentyczne.
Oznaczeniamacierzy:
A
,
B
,
C
,itd.
Dlamacierzy(1)piszemyte˙z:
A
=[
a
ij
]
i
=1
,...,m
j
=1
,...,n
.
(10)
Macierz
,
atransponowan
,
aA
T
m×n
-macierzy
A
postaci(1)nazywamytak
,
a
n×m
-macierz,kt´ora
jakosw
,
a
i
-t
,
akolumn
,
e,dla
i
=1
,
2
,...,m
,ma
i
-tywierszmacierzy
A
.Zatem
2
6
6
6
6
4
3
7
7
7
7
5
A
T
=
a
11
a
21
...a
m
1
a
12
a
22
...a
m
2
.
.
.
.
.
.
.
.
.
.
.
.
a
1
n
a
2
n
...a
mn
.
(11)
Okre´sleniewyznacznika
Wyznacznikiem
macierzykwadratowej
A
=[
a
ij
]
i
=1
,...,n
j
=1
,...,n
stopnia
n
nadciaÃlem
K
nazywamy
nast
,
epuj
,
acyelementciaÃla
K
:
X
det(
A
)=
sgn
(
f
)
·a
1
f
(1)
·a
2
f
(2)
·...·a
nf
(
n
)
.
(12)
f2S
n
Wyznacznikmacierzy
A
=[
a
ij
]
i
=1
,...,n
j
=1
,...,n
b
,
edziemyte˙zoznaczalisymbolem:
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
a
11
a
12
...a
1
n
a
21
a
22
...a
2
n
.
.
.
.
.
.
.
.
.
.
.
.
a
n
1
a
n
2
...a
nn
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
.
(13)
Stopie´nmacierzykwadratowej
A
nazywasi
,
er´ownie˙z
stopniemwyznacznika
tejmacierzy,za´s
wiersze(kolumny)macierzy
A
nazywamy
wierszami(kolumnami)wyznacznika
tejmacierzy.
PrzykÃlad2.Udowodnimy,˙zedladowolnychelement´ow
a,b,c,d
ciaÃla
K
zachodziwz´or:
¯
¯
¯
¯
¯
ab
cd
¯
¯
¯
¯
¯
=
a·d−b·c.
(14)
Zauwa˙zmy,˙ze
S
2
=
{e,g}
,gdzie
g
=(1
,
2)jesttranspozycj
,
a.Zatem
sgn
(
e
)=1i
sgn
(
g
)=
−
1.
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
=
Ponadto
a
11
=
a
,
a
12
=
b
,
a
21
=
c
,
a
22
=
d
,wi
,
ecnamocydefinicjiwyznacznika
ab
cd
X
sgn
(
f
)
·a
1
f
(1)
·a
2
f
(2)
=
sgn
(
e
)
·a
11
·a
22
+
sgn
(
g
)
·a
12
·a
21
=
a·d−b·c
.
f2S
2
3
PrzykÃlad3.Udowodnimy,˙zenaddowolnymciaÃlem
K
zachodziwz´or:
¯
¯
¯
¯
¯
¯
¯
a
11
a
12
a
13
a
21
a
22
a
23
a
31
a
32
a
33
¯
¯
¯
¯
¯
¯
¯
=
a
11
a
22
a
33
+
a
12
a
23
a
31
+
a
13
a
21
a
32
−a
13
a
22
a
31
−a
12
a
21
a
33
−a
11
a
23
a
32
.
Ã
!
123
132
Mamytutaj
n
=3oraz
S
3
skÃladasi
,
eznast
,
epuj
,
acychelement´ow:
e
,
f
1
=
,
Ã
!
,
f
3
=
Ã
!
Ã
!
Ã
!
123
213
123
231
123
321
123
312
f
2
=
,
f
4
=
,
f
5
=
.Ponadto
sgn
(
e
)=1,
f
1
,f
2
,f
4
s
,
atranspozycjami,wi
,
ec
sgn
(
f
1
)=
sgn
(
f
2
)=
sgn
(
f
4
)=
−
1oraz
|I
f
3
|
=2i
|I
f
5
|
=2,czyli
sgn
(
f
3
)=
sgn
(
f
5
)=1.Zatemzdefinicjiwyznacznikamamy,
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
˙ze
a
11
a
12
a
13
a
21
a
22
a
23
a
31
a
32
a
33
=
X
sgn
(
f
)
a
1
f
(1)
a
2
f
(2)
a
3
f
(3)
=
sgn
(
e
)
a
11
a
22
a
33
+
sgn
(
f
1
)
a
11
a
23
a
32
+
f2S
3
sgn
(
f
2
)
a
12
a
21
a
33
+
sgn
(
f
3
)
a
12
a
23
a
31
+
sgn
(
f
4
)
a
13
a
22
a
31
+
sgn
(
f
5
)
a
13
a
21
a
32
=
a
11
a
22
a
33
−a
11
a
23
a
32
−a
12
a
21
a
33
+
a
12
a
23
a
31
−a
13
a
22
a
31
+
a
13
a
21
a
32
,
sk
,
adzwÃlasno´scidodawaniawcielewynikanaszwz´or.Jednakpodanywy˙zejwz´ornawyz-
nacznikstopnia3jestzbytskomplikowanydozapami
,
etania.Wzwi
,
azkuztymdooblicza-
niawyznacznik´owstopnia3stosujesi
,
etzw.
reguÃl
,
eSarrusa
.Polegaonanadopisaniuz
prawejstronywyznacznikadw´ochjegopierwszychkolumninast
,
epniewymno˙zeniuprawosko´snie
wyraz´owzeznakiem+orazlewosko´sniezeznakiem-idodaniuotrzymanychwynik´ow.Istot-
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
nie:
a
11
a
12
a
13
a
21
a
22
a
23
a
31
a
32
a
33
a
11
a
12
a
21
a
22
a
31
a
32
=
a
11
a
22
a
33
+
a
12
a
23
a
31
+
a
13
a
21
a
32
−a
13
a
22
a
31
−a
11
a
23
a
32
−
a
12
a
21
a
33
.
Mo˙znasprawdzi´c,˙zedotegosamegorezultatuprowadzite˙zdopisywanieudoÃluwyznacznika
dw´ochjegopierwszychwierszy.
PrzykÃlad4.Udowodnimy,˙zezachodziwz´or:
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
a
11
a
12
a
13
...a
1
n
0
a
22
a
23
...a
2
n
0 0
a
33
...a
3
n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 0
...a
nn
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
=
a
11
a
22
a
33
...a
nn
.
Niech
f2S
n
oraz
f6
=
e
.Wtedyistniejenajwi
,
ekszaliczbanaturalna
k
taka,˙ze
f
(
k
)
6
=
k
.
Zatem
f
(
k
+1)=
k
+1
,f
(
k
+2)=
k
+2
,...,f
(
n
)=
n
,sk
,
adwynika,˙ze
f
(
k
)
<k
,czyli
a
kf
(
k
)
=0.Zatemzdefinicjiwyznacznikamamy,˙ze
det(
A
)=
X
sgn
(
f
)
a
1
f
(1)
a
2
f
(2)
...a
nf
(
n
)
=
sgn
(
e
)
a
11
a
22
...a
nn
=
a
11
a
22
...a
nn
.
f2S
n
4
WÃlasno´sciobliczaniawyznacznika
Wszystkiemacierzewyst
,
epuj
,
acewpodanychni˙zejwÃlasno´sciachs
,
amacierzamikwadratowymi
nadustalonymciaÃlem
K
,kt´oregoelementyb
,
edziemynazywali
skalarami
.
Uwaga1.Niech
I
oraz
J
b
,
ed
,
aniepustymisko´nczonymizbiorami,niech
Á
:
I−!J
b
,
edzie
bijekcj
,
ainiech
a
j
2K
dla
j2J
.Wtedy
X
a
Á
(
i
)
=
X
a
j
,gdy˙zsumujemytesameelementy,
leczby´cmo˙zewinnymporz
,
adku.
1.Wyznacznikmacierzykwadratowej
A
jestr´ownywyznacznikowijejmacierzytranspono-
wanej
A
T
:
i2I
j2J
det(
A
)=det(
A
T
).
Dow´od.Niech
A
=[
a
ij
]
i,j
=1
,...,n
i
A
T
=[
b
ij
]
i,j
=1
,...,n
.Wtedy
b
ij
=
a
ji
dla
i,j
=1
,...,n
.
Zatemzdefinicjiwyznacznika:
X
X
det(
A
T
)=
sgn
(
f
)
b
1
f
(1)
b
2
f
(2)
...b
nf
(
n
)
=
sgn
(
f
)
a
f
(1)1
a
f
(2)2
...a
f
(
n
)
n
.
f2S
n
f2S
n
Zauwa˙zmy,˙zedla
f2S
n
zachodzir´owno´s´c
{
(
f
(
i
)
,i
):
i
=1
,
2
,...,n}
=
{
(
j,f
−
1
(
j
)):
j
=1
,
2
,...,n}
.
Ale
sgn
(
f
)=
sgn
(
f
−
1
)namocytwierdzenia1orazzprzemienno´sciiÃl
,
aczno´scimno˙zeniaw
cielemamy,˙ze
X
det(
A
T
)=
sgn
(
f
−
1
)
a
1
f
−
1
(1)
a
2
f
−
1
(2)
...a
nf
−
1
(
n
)
.
f2S
n
PonadtoprzeksztaÃlcenie
f7!f
−
1
dla
f2S
n
jestbijekcj
,
azbioru
S
n
nazbi´or
S
n
,wi
,
eczuwagi
1:
X
det(
A
T
)=
sgn
(
f
)
a
1
f
(1)
a
2
f
(2)
...a
nf
(
n
)
=det(
A
).
f2S
n
Uwaga2.Z1.wynika,˙zeka˙zdawÃlasno´s´cwyznacznikasformuÃlowanawj
,
ezyku
wierszy(kolumn)jestprawdziwawprzetÃlumaczeniunaj
,
ezykkolumn(wierszy).Z
tegopowoduwsz
,
edziedalejb
,
edziemydowodzilitylkojednejwersjitakichwÃlasno´sci.
2.Je˙zelimacierzkwadratowa
B
powstajezmacierzykwadratowej
A
przezpomno˙zenie
wszystkichelement´owpewnegojejwiersza(kolumny)przezustalonyskalar
a
,to
det(
B
)=
a·
det(
A
).
Dow´od.Niech
A
=[
a
ij
]
i,j
=1
,...,n
,
a2K
izÃl´o˙zmy,˙zemacierz
B
=[
b
ij
]
i,j
=1
,...,n
powstajez
A
przezpomno˙zenie
k
-tegowierszaprzez
a
.Wtedy
b
kj
=
aa
kj
dla
j
=1
,
2
,...,n
oraz
b
ij
=
a
ij
dla
i6
=
k
oraz
j
=1
,
2
,...,n
.Zatemzdefinicjiwyznacznika
det(
B
)=
X
sgn
(
f
)
b
1
f
(1)
...b
kf
(
k
)
...b
nf
(
n
)
=
X
sgn
(
f
)
a
1
f
(1)
...
(
aa
kf
(
k
)
)
...a
nf
(
n
)
X
f2S
n
f2S
n
=
a·
sgn
(
f
)
a
1
f
(1)
...a
kf
(
k
)
...a
nf
(
n
)
=
a·
det(
A
).
f2S
n
5
Plik z chomika:
nemezisss
Inne pliki z tego folderu:
wyklad07.pdf
(116 KB)
wyklad06.pdf
(108 KB)
wyklad05.pdf
(110 KB)
wyklad04.pdf
(85 KB)
wyklad03.pdf
(93 KB)
Inne foldery tego chomika:
Zgłoś jeśli
naruszono regulamin