Chr.Nelius , Mathematik für Informatiker I, (WS 2000/01) 26.1.2001

§10 b) Matrizen

Wir haben bisher lineare Gleichungssysteme über den reellen Zahlen betrachtet. Für viele Anwendungen (z.B. Codierungstheorie) ist es aber erforderlich, Gleichungssysteme auch über anderen Bereichen zu untersuchen. Dabei ist allerdings wichtig, daß man dort genauso rechnen kann wie in IR, es müssen also die (1.1) entsprechenden Rechenregeln gültig sein. Einen solchen Bereich haben wir einen Körper genannt. Die uns bekannten Beispiele für Körper sind IR, Q, ZZ_{p} (p Primzahl). Wenn wir im folgenden von einem Körper reden, können wir uns eines dieser Beispiele vorstellen, in erster Linie aber IR.

Die Koeffizienten eines linearen Gleichungssystems haben wir als ein rechteckiges Schema (Matrix) aufgeschrieben. Um im allgemeinen Fall die Position eines Elementes genau angeben zu können, verwenden wir “Doppelindizes“. Das Element mit der Bezeichnung a_{ik} steht in einem solchen Schema im Schnittpunkt der i–ten Zeile und der k–ten Spalte.

\underline{(10.1) DEF:} Sei K ein Körper und seien m, n ∈ IN natürliche Zahlen. Ein rechteckiges Schema der Form

( \begin{matrix}a_{11} & a_{12} & a_{13} & … & a_{1n} \\ a_{21} & a_{22} & a_{23} & … & a_{2n} \\ a_{31} & a_{32} & a_{33} & … & a_{3n} \\ ⋮ & & & ... & ⋮ \\ a_{m1} & a_{m2} & a_{m3} & … & a_{mn} \end{matrix} ) = (a_{ik}) \begin{matrix}i = 1, 2, …, m \\ k = 1, 2, …, n \end{matrix}

mit Elementen a_{ik} ∈ K heißt eine (m × n)–Matrix über K. Die Menge aller (m × n)– Matrizen über K wird mit M_{m,n}(K) bezeichnet.

Bezeichnungen: Eine (n × n)–Matrix heißt auch eine n–reihige quadratische Matrix, M_{n}(K) := M_{n,n}(K).

Eine (m × n)–Matrix ist aus m Zeilen und n Spalten aufgebaut. Die i–te Zeile von A :=

(a_{ik}) \begin{matrix}i = 1, 2, …, m \\ k = 1, 2, …, n \end{matrix} besteht aus den Elementen a_{i1}, a_{i2}, …, a_{in} (i = 1, 2, …, m) und die k–te

Spalte aus den Elementen a_{1k} ; a_{2k} ; ⋮ ; a_{mk} (k = 1, 2, …, n).

Matrizen aus M_{m,1}(K) (m Zeilen, 1 Spalte) heißen auch (Spalten–) Vektoren mit m Elementen oder Komponenten. Man setzt M_{m,1}(K) =: K^{m}. Matrizen aus M_{1,n}(K) (1 Zeile, n Spalten) heißen auch Zeilenvektoren mit n Elementen.

Ist A eine (m × n)–Matrix, so heißt (m, n) das Format der Matrix.

\underline{(10.2) BEISPIEL:} Wir können Relationen auf endlichen Mengen oder auch endliche Graphen durch Matrizen beschreiben. a) R sei eine Relation auf {1, 2, …, n}. Die Adjazenz–Matrix von R ist die Matrix A = (a_{ik}) ∈ M_{n}(IR), deren Elemente a_{ik} folgendermaßen definiert sind:

a_{ik} = \{ \begin{matrix}1 falls iRk \\ 0 sonst \end{matrix}

Nehmen wir etwa die Teilbarkeitsrelation auf {1, 2, 3, 4, 5}. Die zugehörige Adjazenz–Matrix ist dann

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix} )

b) Folgendes ist ein Beispiel für einen ungerichteten schlichten endlichen Graphen G:

[figure: •; •; •; •; •; •; 1; 4; 2; 3; 5; 6]

Dieser Graph hat die 6 Ecken 1,2,3,4,5,6 und die eingezeichneten Kanten. i − k soll bedeuten, daß es eine Kante von i nach k (ohne Richtung) gibt. Die Adjazenz–Matrix von G ist dann die Matrix A = (a_{ik}) ∈ M_{6}(IR) mit

a_{ik} = \{ \begin{matrix}1 falls i − k \\ 0 sonst \end{matrix}

Im obigen Fall ergibt sich dann

A = ( \begin{matrix}0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \end{matrix} )

\underline{(10.3) DEF:} a) Zwei (m × n)–Matrizen A = (a_{ik}) und B = (b_{ik}) heißen gleich (in Zeichen: M = N), wenn gilt: a_{ik} = b_{ik} ∀ i = 1, 2, …, m∀ k = 1, 2, …, n.

b) Matrizen unterschiedlichen Formats sind nicht gleich.

Rechenoperationen für Matrizen: \underline{(10.4) DEF:} a) Die Summe zweier (m × n)–Matrizen A = (a_{ik}) und B = (b_{ik}) über K ist definiert durch A + B := (a_{ik} + b_{ik}) ∈ M_{m,n}(K). (Matrizenaddition)

b) Das Produkt aus einem Element c ∈ K und einer (m × n)–Matrix A = (a_{ik}) ist definiert durch cA := (ca_{ik}) ∈ M_{m,n}(K). (Skalare Multiplikation). Achtung: Die Summe ist nur für Matrizen vom gleichen Format definiert! \underline{(10.5) SATZ:} Sei K ein Körper und M_{m,n}(K) die Menge aller (m × n)–Matrizen mit Elementen aus K.

a) Für die Matrizenaddition auf M_{m,n}(K) gelten die folgenden Rechenregeln: A_{0}) ∀A, B ∈ M_{m,n}(K) : A + B ∈ M_{m,n}(K) A_{1}) ∀A, B, C ∈ M_{m,n}(K) : A = (B + C) = (A + B) + C A_{2}) ∀A, B ∈ M_{m,n}(K) : A + B = B + A A_{3}) ∃ O ∈ M_{m,n}(K) ∀A ∈ M_{m,n} : A + O = A A_{4}) ∀A ∈ M_{m,n}(K) ∃B ∈ M_{m,n}(K) : A + B = O

b) Für die skalare Multiplikation auf M_{m,n}(K) gelten die folgenden Rechenregeln: SM_{0}) ∀c ∈ K ∀A ∈ M_{m,n}(K) : cA ∈ M_{m,n}(K) SM_{1}) ∀c ∈ K ∀A, B ∈ M_{m,n}(K) : c(A + B) = cA + cB SM_{2}) ∀c, d ∈ K ∀A ∈ M_{m,n}(K) : (c + d)A = cA + dA SM_{3}) ∀c, d ∈ K ∀A ∈ M_{m,n}(K) : c(dA) = (cd)A SM_{4}) ∀A ∈ M_{m,n}(K) : 1_{K} · A = A.

Die Rechenregeln für die Matrizenaddition entsprechen den Regeln, die wir für die Addition reeller Zahlen in (1.1) aufgestellt hatten. Eine Menge zusammen mit einer Addition und einer skalaren Multiplikation mit Elementen aus einem Körper K, die den entsprechenden Regeln wie in (10.5) genügen, heißt ein Vektorraum über K. Insbesondere ist (M_{m,n}(K), +, ·_{K}) ein Vektorraum über K.

Wir wollen nun die Multiplikation zweier Matrizen definieren. Dazu gehen wir in zwei Scritten vor:

\underline{(10.6) DEF:} Das Produkt aus einer (m × n)–Matrix A = (a_{ik}) ∈ M_{m,n}(K) und einem

Spaltenvektor b = ( b_{1} ; b_{2} ; ⋮ ; b_{n} ) ∈ K^{n} ist definiert durch:

A·b := ( \begin{matrix}a_{11} & a_{12} & a_{13} & … & a_{1n} \\ a_{21} & a_{22} & a_{23} & … & a_{2n} \\ a_{31} & a_{32} & a_{33} & … & a_{3n} \\ ⋮ & & & ... & ⋮ \\ a_{m1} & a_{m2} & a_{m3} & … & a_{mn} \end{matrix} )·( b_{1} ; b_{2} ; b_{3} ; ⋮ ; b_{n} ) = ( a_{11}b_{1} + a_{12}b_{2} + a_{13}b_{3} + … + a_{1n}b_{n} ; a_{21}b_{1} + a_{22}b_{2} + a_{23}b_{3} + … + a_{2n}b_{n} ; a_{31}b_{1} + a_{32}b_{2} + a_{33}b_{3} + … + a_{3n}b_{n} ; ⋮ ; a_{m1}b_{1} + a_{m2}b_{2} + a_{m3}b_{3} + … + a_{mn}b_{n} ) ∈ K^{m}

Dieses Produkt läßt sich nur in ganz bestimmten Situationen bilden: Es muß die Spaltenzahl der Matrix A mit der Anzahl der Komponenten des Spaltenvektors b übereinstimmen. Das Ergebnis ist ein Spaltenvektor, der genausoviel Komponenten hat wie A Zeilen hat.

A ∈ M_{m,n}(K) , b ∈ K^{n} ⟹ A · b ∈ K^{m}

Die i–te Komponente von A · b ist ∑_{k=1}^{n} a_{ik}b_{k}, d.h.

A · b = (∑_{k=1}^{n} a_{ik}b_{k}) _{i = 1, 2, …, m}

Um jetzt das Produkt zweier Matrizen A und B passenden Formats zu bilden, denken wir uns B aus den Spalten aufgebaut und multiplizieren nacheinander die Zeilen von A mit den Spalten von B. Dazu muß die Spaltenzahl von A mit der Zeilenzahl von B übereinstimmen. Beispiel:

( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix} ) · ( \begin{matrix}1 & 0 & 1 & 1 \\ 1 & 1 & 2 & 1 \\ 0 & 1 & −1 & 1 \end{matrix} ) = ( \begin{matrix}3 & 5 & 2 & 6 \\ 9 & 11 & 8 & 15 \end{matrix} )

Das Produkt aus A = (a_{ik}) mit der l–ten Spalte von B = (b_{kl}) ist

(a_{ik}) · ( b_{1l} ; b_{2l} ; ⋮ ; b_{nl} ) = (∑_{k=1}^{n} a_{ik}b_{kl}) _{i = 1, 2, …, m}

\underline{(10.7) DEF:} Das Produkt A · B aus einer (m × n)–Matrix A = (a_{ik}) und einer (n × p)– Matrix B = (b_{kl}) ist die (m × p)–Matrix C = (c_{il}) mit den Elementen

c_{il} := ∑_{k=1}^{n} a_{ik}b_{kl} (i = 1, 2, …, m , l = 1, 2 …, p)

\underline{(10.8) BEM:} a) Das Matrizenprodukt A·B ist nur für den Fall definiert, daß die Spaltenzahl des ersten Faktors gleich der Zeilenzahl des zweiten Faktors ist.

b) M_{m,n}(K) × M_{n,p}(K) ⟶ M_{m,p}(K) , (A, B) ⟼ A · B

Zur Berechnung des Elementes c_{il} an der Stelle (i, l) der Produktmatrix “multipliziert“ man die i–te Zeile von A mit der (gleichlangen) l–ten Spalte von B.

( i–te Zeile von A ) · (  ) = ( ⋮ ; … c_{il} …; ⋮ )

↑

l–te Spalte von B

c) Für zwei n–reihige quadratische Matrizen A und B ist das Matrizenprodukt A · B immer definiert und wieder eine n–reihige quadratische Matrix, d.h. die Matrizenmultiplikation ist eine Rechenoperation auf M_{n}(K) .

d) Es bezeichne δ_{ik} das Kronecker–Symbol, d.h. δ_{ik} := \{ \begin{matrix}1 für i = k \\ 0 für i ≠ k \end{matrix} . Dann heißt die

Matrix

E_{n} := (δ_{ik}) = ( \begin{matrix}1 & 0 & 0 & … & 0 \\ 0 & 1 & 0 & … & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & … & 0 & 1 & 0 \\ 0 & … & 0 & 0 & 1 \end{matrix} )

n–reihige Einheitsmatrix. Es gilt: ∀ A ∈ M_{n}(K) : A · E_{n} = A = E_{n} · A , d.h. E_{n} ist das neutrale Element bzgl. der Matrizenmultiplikation in M_{n}(K).