Permutacje, transpozycje i przestrzenie
wektorowe
Adam Olek, Jakub Kasznia
18 grudnia 2012
Macierze permutacji
W niektórych problemach algebry zachodzi konieczność zamiany kolejności wier-
szy lub kolumn macierzy. Służą do tego macierze permutacji.
Aby zmienić kolejność wierszy w macierzy należy wymnożyć macierz permu-
tacji przez macierz, w której chcemy zmienić kolejność wierszy. Innymi słowy
macierz permutacji musi znajdować się po lewej stronie:

0 1 a b c d
· =
1 0 c d a b
Przykład dla macierzy 3x2:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
0 0 1 3 -1 -2 9
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
1 0 0 · 7 8 = 3 -1
0 1 0 -2 9 7 8
Gdy chcemy zmienić kolejność kolumn w macierzy, wówczas mnożymy ją
przez macierz permutacji(macierz permutacji musi znajdować się po prawej stro-
nie):

a b 0 1 b a
· =
c d 1 0 d c
Przykład dla macierzy 2x3:
îÅ‚ Å‚Å‚

0 0 1
4 0 -5 0 -5 4
ðÅ‚ ûÅ‚
· 1 0 0 =
9 1 7 1 7 9
0 1 0
Można zauważyć, że macierz permutacji to macierz identycznościowa ze
zmienioną kolejnością wierszy. Oczywiście sama macierz identycznościowa
też jest macierzą permutacji - jest szczególnym przypadkiem, który nie zmienia
porzÄ…dku wierszy, ani kolumn w macierzy.

a b 1 0 a b
· =
c d 0 1 c d

1 0 a b a b
· =
0 1 c d c d
Istotną cechą macierzy permutacji jest to, że są one odwracalne, ponieważ
możemy przywrócić pierwotny porządek wierszy(lub kolumn) w macierzy, w
której wcześniej ten porządek zmieniliśmy. Co więcej, macierz odwrotna do
macierzy permutacji jest transponowanÄ… macierzÄ… permutacji.
-1 T
P = P
T
P P = I
Przykładowo, załóżmy, że mamy macierz A, w której chcemy zmienić kolejność
wierszy:
îÅ‚ Å‚Å‚
-2 4 7
ðÅ‚ ûÅ‚
A = 1 3 -5
8 2 9
1
Wykorzystujemy do tego następującą macierz permutacji:
îÅ‚ Å‚Å‚
0 0 1
ðÅ‚ ûÅ‚
P = 1 0 0
0 1 0
Po wykonaniu mnożenia otrzymujemy:
îÅ‚ Å‚Å‚
8 2 9
ðÅ‚ ûÅ‚
P A = -2 4 7
1 3 -5
Chcemy teraz otrzymać z powrotem naszą macierz A. Aby tego dokonać, znaj-
-1 -1 T
dujemy macierz P . Wiemy jednak, że P = P , więc wyznaczamy macierz
T
P :
îÅ‚ Å‚Å‚
0 1 0
T
ðÅ‚ ûÅ‚
P = 0 0 1
1 0 0
T
Mnożymy zatem P P A i otrzymujemy:
îÅ‚ Å‚Å‚
-2 4 7
T
ðÅ‚ ûÅ‚
P P A = 1 3 -5 = A
8 2 9
Warto wspomnieć o tym, ile mamy możliwości utworzenia macierzy permu-
tacji o danym wymiarze. Ilość macierzy permutacji o danym wymiarze
(oznaczonym jako n) obliczamy ze wzoru:
n! = 1 · 2 · . . . · (n - 1) · n
Na przykład, mamy 4! = 24 macierzy permutacji o wymiarach 4x4.
Jednym z przypadków, w którym korzystamy z narzędzia, jakim są macierze
permutacji, jest rozwiązanie równania Ax=b z wykorzystaniem metody elimi-
nacji Gaussa. Jeżeli w jakimś wierszu, na miejscu elementu osiowego pojawia
się zero należy zamienić ten wiersz, z wierszem poniżej. Przy zapisie kolejnych
działań na macierzy rozszerzonej [A | b], oprócz macierzy eliminacji pojawią się
również macierze permutacji.
Kolejnym przypadkiem, w którym mogą przydać się macierze permutacji
jest faktoryzacja LU. Może zdarzyć się tak, że w którymś z etapów eliminacji
na pozycji elementu osiowego pojawi się zero. Powinniśmy więc użyć macierzy
permutacji do przestawienia danego wiersza z wierszem poniżej. W praktyce
robi się to tak, że najpierw wykonujemy zamiany wierszy w macierzy, której
faktoryzację chcemy przeprowadzić, a dopiero póz
niej rozpoczynamy faktoryza-
cję. W wyniku takiej kolejności działań otrzymujemy zapis PA=LU. Załóżmy,
że mamy przeprowadzić faktoryzację LU macierzy A:
îÅ‚ Å‚Å‚
0 -1 3
ðÅ‚ ûÅ‚
A = 1 -1 1
-2 2 -4
Jak widać, przeszkodą w przeprowadzeniu faktoryzacji i otrzymania kolejno
macierzy U i L jest fakt, że już w miejscu pierwszego elementu osiowego pojawia
2
się 0. Zamieńmy zatem wiersz pierwszy z drugim:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
0 1 0 0 -1 3 1 -1 1
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
1 0 0 · 1 -1 1 = 0 -1 3
0 0 1 -2 2 -4 -2 2 -4
Otrzymujemy:
îÅ‚ Å‚Å‚
1 -1 1
ðÅ‚ ûÅ‚
P A = 0 -1 3
-2 2 -4
Teraz bez trudu możemy przeprowadzić faktoryzację. W efekcie otrzymuje-
my:
îÅ‚ Å‚Å‚
1 -1 1
ðÅ‚ ûÅ‚
U = 0 -1 3
0 0 -2
îÅ‚ Å‚Å‚
1 0 0
ðÅ‚ ûÅ‚
L = 0 1 0
-2 0 1
Nasze PA=LU przedstawia siÄ™ tak:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 -1 1 1 0 0 1 -1 1
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
P A = 0 -1 3 = 0 1 0 · 0 -1 3 = LU
-2 2 -4 -2 0 1 0 0 -2
Jeżeli A jest macierzą odwracalną, to macierz permutacji P usta-
wia wiersze w takiej kolejności, że możliwa jest faktoryzacja PA=LU.
Macierze transponowane
Macierz transponowana macierzy A, to taka macierz, której wierszami
sÄ… kolumny macierzy A, a kolumnami sÄ… wiersze macierzy A. OperacjÄ™,
która pozwala nam otrzymać macierz transponowaną nazywamy transpozycją.
Ogólnie mówimy, że po dokonaniu transpozycji element Aji macierzy A staje
siÄ™ elementem AT macierzy AT .
ij
AT = Aji
ij
Najprościej zauważyć to na przykładzie. Mamy macierz A:
îÅ‚ Å‚Å‚
1 -3 7 4
ðÅ‚ ûÅ‚
A = 2 0 5 -8
9 3 -2 9
Dokonujemy transpozycji:
îÅ‚ Å‚Å‚
1 2 9
ïÅ‚ śł
-3 0 3
ïÅ‚ śł
AT =
ðÅ‚ ûÅ‚
7 5 -2
4 -8 9
Warto zwrócić uwagę na fakt, że wymiary macierzy AT są  przestawionymi
wymiarami macierzy A. W powyższym przykładzie macierz A miała wymiary
3x4, więc macierz AT ma wymiary 4x3.
3
Macierze symetryczne
Macierz symetryczną definiujemy jako macierz kwadratową, w któ-
rej elementy położone symetrycznie względem głównej przekątnej są
równe. Spełniony jest zatem warunek:
Aij = Aji
Zapisany ogólniej wygląda następująco:
AT = A
Przykład takiej macierzy:
îÅ‚ Å‚Å‚
1 3 7
ðÅ‚ ûÅ‚
AT = 3 4 -5
7 -5 -9
W jaki sposób otrzymujemy macierze symetryczne z dowolnych macierzy?
Posłużmy się przykładem. Mamy macierz A:

2 8 7
A =
5 -3 -1
Dokonujemy jej transpozycji:
îÅ‚ Å‚Å‚
2 5
ðÅ‚ ûÅ‚
AT = 8 -3
7 -1
Po wymnożeniu AT A mamy:
îÅ‚ Å‚Å‚
29 1 9
ðÅ‚ ûÅ‚
AT A = 1 73 59
9 59 50
Zauważmy, że otrzymana macierz jest symetryczna. Okazuje się, że każda
macierz wymnożona przez swoją transpozycję daje w wyniku macierz syme-
trycznÄ….
AT A zawsze daje macierz symetrycznÄ….
Można tego dowieść stosunkowo łatwo. Dokonajmy transpozycji wyrażenia
AT A. Otrzymamy wyrażenie (AT A)T . Zgodnie z zasadą transponowania iloczy-
nu dwóch macierzy mamy (AT AT T ). Wiemy, że AT T = A. Ostatecznie więc
(AT A)T = AT A, więc macierz AT A jest macierzą symetryczną, co kończy do-
wód.
4
Przestrzenie wektorowe
Przestrzeń wektorowa (nazywana czasem przestrzenią liniową) Rn za-
wiera wszystkie n-wymiarowe wektory v. Innymi słowy, przestrzeń wek-
torowa Rn to pewien pęk wektorów, o współrzędnych rzeczywistych spełniający
określone warunki. Warunki te regulują jaki pęk wektorów może stanowić prze-
strzeń wektorową. Przede wszystkim powinniśmy móc wykonywać operacje
dodawania wektorów i mnożenia ich przez skalary, bez ryzyka, że otrzy-
many wówczas wynik do tej przestrzeni nie będzie należał. Przykładowo wez
my
trzy wektory dwuwymiarowe(jest ich zdecydowanie więcej, ale nie jesteśmy w
stanie wypisać wszystkich):

1 3 0
v = , w = , z =
2 4 0
w
v
2
z
-2 2
-2
Skoro mają dwa wymiary, należą do przestrzeni R2. W wyniku dodawania
którychkolwiek dwóch z nich otrzymujemy wektor dwuwymiarowy, czyli taki,
który też należy do przestrzeni R2, np.:

4
v + w =
6
Wektor dwuwymiarowy otrzymujemy także w wyniku mnożenia któregokolwiek
z tych wektorów przez dowolny skalar, np.:

-6
-2w =
-8
5
v+w
w
v
2
z
-2 2
-2
-2w
Gdybyśmy w pomnożyli przez zero otrzymalibyśmy 0w=z. Widzimy, że wek-
tor zerowy należy do każdej przestrzeni wektorowej, ponieważ musimy móc mno-
żyć przez każdy skalar, włącznie z zerem oraz dla każdego wektora musi istnieć
wektor przeciwny - ich suma musi dać zero. Skoro v oraz -2w należy do prze-
strzeni wektorowej, to v-2w także należy do tej przestrzeni. Wnioskujemy, że
jeżeli do przestrzeni wektorowej należą dowolne wektory v i w, to
dowolna ich kombinacja liniowa też należy do tej przestrzeni.
Zastanówmy się teraz czy wektor
îÅ‚ Å‚Å‚
1
ðÅ‚ ûÅ‚
v = 2
0
należy do przestrzeni R2 czy R3. Oczywiście należy do przestrzeni R3. Mimo
tego, że jego trzeci element jest równy zero, to wektor nadal ma trzy wymiary.
Po przeczytaniu powyższych przykładów, można zauważyć, że przestrzeń R2
to cała płaszczyzna XY. Widzimy także, że przestrzeń R3, to po prostu cała
przestrzeń XYZ.
Wszystko to, co zostało do tej pory zapisane dla R2 i R3 stosuje się do
wszystkich przestrzeni Rn. Zmienia się oczywiście liczba współrzędnych wekto-
rów i fakt, że przestrzeni większych niż trójwymiarowe nie da się zilustrować
geometrycznie.
Warto zwrócić uwagę na fakt, że dodawanie wektorów i mnożenie przez skalar
w obrębie przestrzeni wektorowej muszą spełniać osiem zasad:
1. Dodawanie wektorów jest łączne: (v+w)+z=v+(w+z)
2. Dodawanie wektorów jest przemienne: v+w=w+v
3. Dodawanie wektorów ma element neutralny: v+0=v, gdzie 0 to wektor
zerowy
4. Dodawanie wektorów ma element przeciwny: v+w=0, gdzie w to wektor
przeciwny do wektora v
5. Mnożenie przez skalar jest rozdzielne względem dodawania wektorów:
a(v+w)=av+aw
6. Mnożenie przez wektor jest rozdzielne względem dodawania skalarów:
(a+b)v=av+bv
6
7. Mnożenie przez skalar jest zgodne z mnożeniem skalarów: a(bv)=(ab)v
8. Mnożenie przez skalar ma element neutralny 1v=v, gdzie 1 to element
neutralny mnożenia.
Na koniec tego rozdziału wróćmy jeszcze na chwilę do przestrzeni R2. Za-
łóżmy, że bierzemy tylko pierwszą ćwiartkę układu współrzędnych XY:
2
-2 2
-2
Czy jest to przestrzeń wektorowa? Sprawdz
my to. Widać, że możemy dodać
do siebie dowolne wektory z tej ćwiartki i nadal w niej pozostaniemy. Co jednak
z mnożeniem? Dowolnie wybrany wektor, pomnożony przez dowolny ujemny
skalar nie znajduje się już w pierwszej ćwiartce układu współrzędnych. Wnio-
sek: ćwiartka układu współrzędnych XY jest przykładem tworu, który nie jest
przestrzeniÄ… wektorowÄ….
Podprzestrzenie przestrzeni wektorowych
Pod koniec poprzedniego rozdziału zobaczyliśmy co stanie się, gdy wez
miemy
tylko część przestrzeni wektorowej. W tamtym przypadku wzięta część nie była
przestrzenią wektorową. Może być jednak tak, że jeżeli znajdziemy odpowied-
nią część, to będzie ona przestrzenią wektorową(będzie spełniać odpowiednie
warunki). Taką część nazywamy poprzestrzenią przestrzeni wektorowej.
Podprzestrzeń przestrzeni wektorowej jest zbiorem wektorów, za-
wierającym wektor zerowy, który spełnia następujące wymagania: Je-
żeli v i w są wektorami, a c jest skalarem, to v+w należy do podprze-
strzeni i cv należy do podprzestrzeni.
Tak wygląda formalna definicja. Spróbujmy znalez
ć teraz podprzestrzenie
przestrzeni R2. Załóżmy, że w układzie współrzędnych mamy wektor

1
v = .
2
7
v
2
-2 2
-2
Jeżeli ma on należeć do podprzestrzeni, to musimy mieć możliwość pomnoże-
nia go przez 2, przez 1/2, przez 100, przez -1, przez -100 i tak dalej, i oczywiście
przez zero(wektor zerowy należy do każdej podprzestrzeni, podobnie jak należał
do każdej przestrzeni). Wszystkie wyniki mnożenia przez skalar leżą na prostej.
BiorÄ…c teraz dowolne dwa wektory z tej prostej np.: v i 3v, po ich zsumowaniu
otrzymamy wektor, który też leży na tej prostej.
2v
v
2
1/2 v
z
-2 2
-2
-v
Widzimy, że jedną z podprzestrzeni przestrzeni R2 jest linia prosta. Jednak
nie wszystkie linie proste mogą być podprzestrzeniami. Załóżmy, że mamy taką
liniÄ™ prostÄ…:
8
2
-2 2
-2
Widzimy, że nie przechodzi ona przez środek układu współrzędnych. Czy
zatem jest podprzestrzeniÄ…? Nie jest, bo nie zawiera wektora zerowego.
2
-2 2
-2
Nasuwa się jeszcze jedno ważne pytanie: czy linia prosta w układzie współ-
rzędnych to przestrzeń R1? Nie, ponieważ każdy wektor leżący na takiej linii
jest dwuwymiarowy. Przestrzeń R1 jest jednowymiarowa.
Kolejną podprzestrzenią przestrzeni R2 jest cała przestrzeń R2. Jest to po
prostu podprzestrzeń samej siebie.
Ostatnią poprzestrzenią przestrzeni R2 jest sam wektor zerowy. Spełnia on
bowiem wszystkie zasady, które musi spełniać podprzestrzeń - gdy dodamy go
do samego siebie otrzymujemy wektor zerowy, gdy pomnożymy go przez dowolny
skalar, również otrzymujemy wektor zerowy. Cały czas pozostajemy w początku
układu współrzędnych XY.
PodsumowujÄ…c, istniejÄ… trzy podprzestrzenie przestrzeni R2:
" wektor zerowy,
" linia prosta przechodząca przez początek układu współrzędnych,
" cała przestrzeń R2.
Warto wypisać jeszcze podprzestrzenie przestrzeni R3:
" wektor zerowy,
" linia prosta przechodząca przez początek układu współrzędnych,
9
" płaszczyzna przechodząca przez początek układu współrzędnych,
" cała przestrzeń R3.
Przestrzeń kolumnowa
Przestrzeń kolumnowa macierzy A zawiera wszystkie kombinacje li-
niowe kolumn tej macierzy. Kombinacjami są wszystkie możliwe wek-
tory Ax, które wypełniają przestrzeń kolumnową oznaczaną C(A).
Zastanówmy się teraz, jak uzyskać obraz przestrzeni kolumnowej macierzy.
Wez
my macierz:
îÅ‚ Å‚Å‚
1 -2
ðÅ‚ ûÅ‚
A = 4 2
3 1
Widzimy, że jej kolumnami są dwa wektory trójwymiarowe. Chcemy, aby ko-
lumny naszej macierzy należały do jakiejś podprzestrzeni przestrzeni R3.
z
kol.1
kol. 2
x
y
Jednak nie wystarczy, by tylko te dwa wektory znajdowały się w naszej
podprzestrzeni - bo nie byłaby to nawet podprzestrzeń. Muszą być spełnione
warunki dotyczące poprzestrzeni. Musimy móc dodać te dwa wektory do siebie,
musimy móc pomnożyć każdy z nich przez liczbę, pomnożone przez skalar wek-
tory dodawać do innych itd. Innymi słowy w podprzestrzeni będącej przestrzenią
kolumnową muszą być zawarte wszystkie kombinacje liniowe kolumn macierzy.
Przestrzenią kolumnową C(A) będzie zatem płaszczyzna w R3, przechodząca
przez początek układu współrzędnych:
10
z
kol.1
kol. 2
x
y
Na koniec zwróćmy uwagę na jeszcze jedną rzecz. Co stałoby się, gdyby
jedna kolumna tej macierzy była wielokrotnością drugiej? Oba reprezentujące
je wektory leżałyby na jednej prostej w układzie współrzędnych. Przestrzenią
kolumnową byłaby wówczas tylko linia prosta.
11