close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

DIE REDUZIERTE ZEILENSTUFENFORM EINER MATRIX 1

EinbettenHerunterladen
DIE REDUZIERTE ZEILENSTUFENFORM EINER MATRIX
1. Matrixprodukt
Wie immer, sei K ein K¨orper. Eine (m × n)-Matrix


a11 a12 · · · a1n
 a21 a22 · · · a2n 
A=
∈ K m,n
..
.. 
 ...

. ···
.
am1 am2 · · ·
amn
schreiben wir auch einfach als A = (aij ).
Seien nun A = (aij ) ∈ K l,m und B = (bpq ) ∈ K m,n . Dann ist das Matrixprodukt
AB := C = (ciq ) definiert durch
m
aik bkq
ciq :=
k=1
wobei 1 ≤ i ≤ l und 1 ≤ q ≤ n. Es gilt also C = (ciq ) ∈ K l,n .
2. Reduzierte Zeilenstufenform
Ein Matrix B = (bij ) ∈ K m,n ist in reduzierter Zeilenstufenform falls gilt:
B = 0, oder es existieren ein 1 ≤ r ≤ min(m, n) und 1 ≤ j1 < j2 < · · · < jr ≤ n, so
daß gilt
(i) F¨
ur 1 ≤ k ≤ r gilt bkj = 0 falls j < jk .
(In Worten: Die ersten jk − 1 Eintr¨age der kten Zeile sind gleich 0.)
1 falls i = k,
(ii) F¨
ur 1 ≤ k ≤ r gilt bijk =
0 sonst.
(In Worten: Der kte Eintrag der jk ten Spalte ist 1, alle anderen Eintr¨age der
jk ten Spalte sind gleich 0.)
(iii) F¨
ur r + 1 ≤ k ≤ m gilt bkj = 0 f¨
ur alle 1 ≤ j ≤ n.
(In Worten: F¨
ur r + 1 ≤ k ≤ m sind alle Eintr¨age in der kten Zeile gleich 0.)
Sei
IZ (B) :=
{j1 , . . . , jr } falls B = 0,
∅
sonst.
Die Elemente in IZ (B) nennt man Zeilenstufenindizes. Sei JZ (B) := {1, . . . , n} \
IZ (B).
1
2
DIE REDUZIERTE ZEILENSTUFENFORM EINER MATRIX
Es gilt IZ (B) = ∅ genau dann wenn B = 0. Es gilt JZ (B) = ∅ genau dann wenn
B = En oder B ist von der Form


1
 1



..


.




1

.


0 0 · · · 0 
. .
.. 
 .. ..
. 
0 0 ··· 0
F¨
ur j ∈ JZ (B) definiere

1j

 ...  ∈ K n
LB
j :=
nj
durch
kj


1
:= −bsj

0
k=j,
falls k = js f¨
ur ein 1 ≤ s ≤ r,
sonst.
Wie wir wissen, kann man jede Matrix A ∈ K m,n als lineare Abbildung A : K n →
K m auffassen, welche definiert ist durch A(v) := Av. (Av ist das Matrixprodukt der
(m × n)-Matrix A mit der (n × 1)-Matrix v.) Solche Abbildungen K n → K m nennt
man auch Matrixabbildungen. (In der Vorlesungen haben wir gezeigt: Jedes
f ∈ HomK (K n , K m ) ist eine Matrixabbildung.)
Theorem 2.1. Sei B ∈ K m,n in reduzierter Zeilenstufenform.
(i) Es gilt
Kern(B) =



j∈JZ (B)


B
aj Lj | aj ∈ K, j ∈ JZ (B) .

(Falls JZ (B) = ∅, so gilt Kern(B) = 0.)
(ii) Angenommen
aj LB
j =
j∈JZ (B)
bj LB
j
j∈JZ (B)
f¨
ur gewisse Elemente aj , bj ∈ K. Dann gilt aj = bj f¨
ur alle j ∈ JZ (B).
(In fortgeschrittener Sprache ausgedr¨
uckt: Die Menge
Basis von Kern(B).)
LB
j | j ∈ JZ (B)
ist eine
DIE REDUZIERTE ZEILENSTUFENFORM EINER MATRIX
3
3. Beispiel
Die Matrix
0
0

0
B=
0
0
0

1 b13 b14
0 0
0
0 0
0
0 0
0
0 0
0
0 0
0
0 b16
1 b26
0 0
0 0
0 0
0 0
0
0
1
0
0
0
0
0
0
1
0
0
b19
b29
b39
b49
0
0

b1,10
b2,10 

b3,10 
 ∈ K 6,10
b4,10 
0 
0
ist in reduzierter Zeilenstufenform, wobei r = 4, IZ (B) = {j1 , j2 , j3 , j4 } = {2, 5, 7, 8}
und JZ (B) = {1, 3, 4, 6, 9, 10}.
Hier sind die Vektoren Lj , wobei j ∈ JZ (B):
 
1
0
 
0
 
0
 
0
LB
=
 
1
0
0
 
0
 
0
0


0
−b16 


 0 


 0 


−b26 
LB
=


6
 1 
 0 


 0 


 0 
0

0
−b13 


 1 


 0 


 0 
LB
=


3
 0 
 0 


 0 


 0 
0


0
−b19 


 0 


 0 


−b29 
LB
=


9
 0 
−b 
 39 
−b 
 49 
 1 
0


0
−b14 


 0 


 1 


 0 
LB
=


4
 0 
 0 


 0 


 0 
0


0
−b1,10 


 0 


 0 


−b2,10 
LB
=
.

10
 0 
−b 
 3,10 
−b 
 4,10 
 0 
1

4. Elementarmatrizen
(m)
F¨
ur 1 ≤ p, q ≤ m mit p = q und a ∈ K definieren wir eine Matrix Tpq (a) :=
Tpq (a) = (tij ) ∈ K m,m durch


1 falls i = j,
tij := a falls (i, j) = (p, q),

0 sonst.
4
DIE REDUZIERTE ZEILENSTUFENFORM EINER MATRIX
F¨
ur 1 ≤ p ≤ m und a ∈ K × definieren
K m,m durch


1
dij := a

0
F¨
ur 1 ≤ p, q ≤ m definieren wir eine

1



1
eij :=

1



0
(m)
(m)
(m)
wir eine Matrix Dp (a) := Dp (a) = (dij ) ∈
falls i = j = p,
falls i = j = p,
sonst.
(m)
Matrix Epq := Epq = (eij ) ∈ K m,m durch
falls q = i = j = p,
falls (i, j) = (p, q),
falls (i, j) = (q, p),
sonst.
(m)
Bemerkung: Ep,q = Eq,p und Epp = Em .
(m)
(m)
(m)
Matrizen der Form Tpq (a), Dp (a) oder Epq nennt man Elementarmatrizen.
5. Beispiele
¨
An den freien Stellen der Matrizen stehen jeweils Nullen, welche wir der Ubersichtlichkeit
halber weggelassen haben:
1

1

1
(7)
T25 (a)
=
1
0
(7)
E25 = 
1
1
1
a
1
1
1
1
=
1

(7)
0
E23 = 

1
1
a
1
1
1
1
1
(7)
T52 (a)

0 1
1 0
1

1
1

1
1

1
1
6. Gauß-Algorithmus
Theorem 6.1. Sei A = (aij ) ∈ K m,n . Dann gibt es Elementarmatrizen T1 , . . . , Tt
mit Tt · · · T2 T1 A ist in reduzierter Zeilenstufenform.
Beweis/Algorithmus: Falls A = 0, so ist A bereits in Zeilenstufenform und der
Algorithmus stoppt.
(0)
Sei also A = 0 und setze A(0) = (aij ) := A.
Sei
j1 := min{1 ≤ s ≤ n | es gibt ein 1 ≤ p ≤ m mit a(0)
ps = 0}.
(0)
W¨ahle ein 1 ≤ p ≤ m mit apj1 = 0.
Setze
(0)
(0)
C (0) = (cij ) := D1 ((apj1 )−1 )E1p A(0)
und
(1)
(0)
(0)
A(1) = (aij ) := Tm1 (−cm1 ) · · · T21 (−c21 )C (0) .
DIE REDUZIERTE ZEILENSTUFENFORM EINER MATRIX
5
Wir definieren induktiv Matrizen A(k) und nat¨
urliche Zahlen j1 < · · · < jk wie folgt:
(k−1)
Angenommen A(k−1) = (aij
k ≥ 2. Sei
) und j1 < · · · < jk−1 sind bereits definiert f¨
ur ein
= 0}.
jk := min{jk−1 + 1 ≤ s ≤ n | es gibt ein k ≤ p ≤ m mit a(k−1)
ps
Wenn ein solches jk nicht existiert, so ist A(k−1) bereits in reduzierter Zeilenstufenform und der Algorithmus stoppt.
(k−1)
Angenommen, jk existiert. W¨ahle ein k ≤ p ≤ m mit apjk
= 0.
Setze
(k−1)
C (k−1) = (cij
(k−1)
) := Dk ((apjk )−1 )Ekp A(k−1)
und
(k)
(k−1)
(k−1)
(k−1)
(k−1)
A(k) = (aij ) := Tmk (−cmk ) · · · Tk+1k (−ck+1k )Tk−1k (−ck−1k ) · · · T1k (−c1k
)C (k−1) .
Beachte: F¨
ur k ≥ 1 ist die (m × k)-Matrix, welche aus den ersten k Spalten von
A(k) besteht, in reduzierter Zeilenstufenform.
Nun sieht man leicht: Nach sp¨atestens k = min(m, n) Schritten ist A(k) in reduzierter
Zeilenstufenform.
Lemma 6.2. Sei A ∈ K m,n , und sei T ∈ K m,m eine Elementarmatrix. Dann gilt
Kern(A) = Kern(T A).
Beweis: Elementarmatrizen sind invertierbar, also sind die zugeh¨origen Matrixabbildungen Isomorphismen.
Der Gauß-Algorithmus liefert also eine explizites Verfahren f¨
ur die Konstruktion
einer Basis von Kern(A).
7. Eindeutigkeit der reduzierten Zeilenstufenform
Sei A ∈ K m,n . Eine Matrix B ∈ K m,n , welche in reduzierter Zeilenstufenform ist,
ist eine reduzierte Zeilenstufenform von A, falls es Elementarmatrizen T1 , . . . , Tt
gibt mit B = Tt · · · T1 A.
Theorem 7.1. Sei A ∈ K m,n . Dann gibt es genau eine reduzierte Zeilenstufenform
B von A.
Beweis: Die Existenz von B ist bereits durch den Gauß-Algorithmus bewiesen. Es
bleibt zu zeigen, daß B eindeutig ist: Seien also B und B reduzierte Zeilenstufenformen einer Matrix A ∈ K m,n . Zu zeigen: B = B .
Es gilt IZ (B) = ∅ genau dann wenn B = 0 genau dann wenn Kern(B) = K n .
Wegen Kern(A) = Kern(B) = Kern(B ) gilt also: IZ (B) = ∅ genau dann wenn
IZ (B ) = ∅. In diesem Fall folgt sofort B = B = 0.
Wir nehmen also an, daß IZ (B) und IZ (B ) beide nicht-leer sind, d.h. IZ (B) =
{j1 < · · · < jr } und IZ (B ) = {j1 < · · · < jt } mit r, t ≥ 1. Wir wissen, daß
Kern(B) = Kern(B ) und Kern(B) ∼
= K n−r und Kern(B ) ∼
= K n−t . Also K n−r ∼
=
n−t
K . Es folgt r = t. (Siehe das Kapitel u
¨ber bijektive Matrixabbildungen.)
6
DIE REDUZIERTE ZEILENSTUFENFORM EINER MATRIX
Schritt 1: Angenommen j1 < j1 . Dann gilt B (ej1 ) = 0 und B(ej1 ) = e1 = 0.
Widerspruch zu Kern(B) = Kern(B ). (Bemerkung: Es gilt ej1 = LB
j1 .) Also haben
wir gezeigt: j1 = j1 . Der Fall j1 > j1 wird analog behandelt.
Schritt 2: Sei nun p > j1 mit der Eigenschaft: F¨
ur 1 ≤ k ≤ p − 1 ist die kte
Spalte von B gleich der kten Spalte von B . Wir werden zeigen, daß dann auch die
pte Spalte von B gleich der pten Spalte von B ist. (Damit h¨atten wir dann per
Induktion bewiesen, daß B = B gilt.)
ur alle
Sei 1 ≤ s − 1 ≤ r maximal mit j1 < · · · < js−1 < p (Es folgt jk = jk f¨
1 ≤ k ≤ s − 1, und es folgt p ≤ js und p ≤ js falls s − 1 < r.)
Fall I: p ∈
/ IZ (B) und p ∈
/ IZ (B ). Seien B = (bij ) und B = (bij ). Dann gilt


−b1p + b1p
−b1p + b1p 

=0
B(LB
..
p) = 

.
−b1p + b1p
und wegen Kern(B) = Kern(B ) gilt

−b1p + b1p
 −b2p + b2p 
 = 0.

B (LB
)
=
..
p


.

−bmp + bmp
(Nebenbei bemerkt gilt bip = bip = 0 f¨
ur alle s + 1 ≤ i ≤ m.) Es folgt also bip = bip
f¨
ur alle 1 ≤ i ≤ m, d.h. die pten Spalten von B und B sind gleich.
Fall II: Sei s − 1 < r und p = js = js . Dann sind die pten Spalten von B und B
gleich es , stimmen also u
¨berein.
B
Fall III: Sei s − 1 < r und p = js < js . Es folgt B (LB
p ) = 0, aber B(Lp ) = es = 0.
Widerspruch zu Kern(B) = Kern(B ).
Der Fall s − 1 < r und p = js < js wird analog zu Fall III bewiesen.
Damit ist der Satz von der Eindeutigkeit der reduzierten Zeilenstufenform bewiesen.
8. Ein Invariante von A
Sei A ∈ K m,n , und sei B eine reduzierte Zeilenstufenform von A. Der Satz von der
Eindeutigkeit der reduzierten Zeilenstufenform erlaubt nun die Definition IZ (A) :=
IZ (B). Insbesondere wird die Anzahl r der Elemente in IZ (B) damit zu einer
interessanten Invariante von A.
Es stellt sich heraus, daß r gleich dem Rang von A ist. (Die Definition von Rang
kommt sp¨ater.)
DIE REDUZIERTE ZEILENSTUFENFORM EINER MATRIX
7
9. Reduzierte Spaltenstufenform
Man kann nun eine analoge Theorie u
¨ber reduzierte Spaltenstufenformen von Matrizen entwickeln. (Man multipliziert eine Matrix dann von Rechts mit Elementarmatrizen. Dies entspricht dann elementaren Spaltenumformungen.)
Document
Kategorie
Bildung
Seitenansichten
10
Dateigröße
187 KB
Tags
1/--Seiten
melden