Prof. Dr. C. W. Cryer WS 99/2000

Numerische Mathematik

Übungsaufgabe 1, Abgabe 28.10.1999, 13.00

Aufgabe 1: (4 Punkte)

A := ( \begin{matrix}1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 8 \end{matrix} ) b := ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} )

Bestimmen Sie die Lösung x der Gleichung Ax = b mit Hilfe des Gaußschen Eliminationsverfahrens. Die Berechnungen sollen exakt von Hand durchgeführt werden.

Aufgabe 2: (4 Punkte) Sei

A = ( \begin{matrix}A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} )

eine invertierbare Matrix.

Die quadratischen Blockmatrizen A_{11}, A_{22} seien regulär. Bestimmen Sie A^{−1}.

Aufgabe 3: (2 Punkte) In der Vorlesung ist perm(A), die Permanente einer n × n Matrix A, definiert worden. Im Jahr 1926 äußerte van der Waerden die Vermutung, daß für stochastische n × n Matrizen gilt

perm(A) ≥ \frac{n!}{n^{n}} .

Eine Matrix heißt stochastisch, wenn für ihre Einträge a_{ij} gilt:

(i) a_{ij} ≥ 0 (ii) ∑_{k=1}^{n} a_{kj} = ∑_{k=1}^{n} a_{ik} = 1, 1 ≤ i, j ≤ n.

Zeigen Sie, daß die Vermutung für n = 2 korrekt ist. Bemerkung: Der Beweis für die Korrektheit der Vermutung im allgemeinen Fall wurde erst vor wenigen Jahren erbracht.

Aufgabe 4: (4 Punkte) Seien

A = ( \begin{matrix}1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \end{matrix} ) = (a_{ij})

B = ( \begin{matrix}1 & 3 & 5 & 7 \\ 9 & 11 & 13 & 15 \\ 17 & 19 & 21 & 23 \\ 25 & 27 & 29 & 31 \end{matrix} ) = (b_{jk})

b.w.

Wählen Sie (nicht-triviale) Partitionierungen A = (A_{ij}), 1 ≤ i ≤ u, 1 ≤ j ≤ v

B = (B_{jk}), 1 ≤ j ≤ v, 1 ≤ k ≤ w

und berechnen Sie \underline{ein} (Matrizen) Element von C := AB = (C_{ik}), 1 ≤ i ≤ u, 1 ≤ k ≤ w.

(i) Mit der Formel (n = 4),

c_{ij} = ∑_{j=1}^{n} a_{ij}b_{jk}

(ii) Mit der Formel

C_{ik} = ∑_{j=1}^{v} A_{ij}B_{jk}

Aufgabe 5: (3 Punkte) Bier wird in n Brauereien gebraut und in n Gebiete vermarktet. Die n × n Matrix A stellt die Lieferungswege dar:

\{ \begin{matrix}a_{ij} & = & 1 & falls Gebiet j von Brauerei i beliefert wird \\ & = & 0 & sonst. \end{matrix}

Ein aufmerksamer Volkswirt merkt, daß jedes Gebiet von genau einer Brauerei Lieferungen erhält.

Zeigen Sie, daß A regulär ist.

Aufgabe 6: (3 Punkte) Eine ASM Matrix (Alternating Sign Matrix) ist eine n × n Matrix A wofür:

a) Jedes Element a_{ij} von A ist entweder 0, +1 oder −1

b) In jeder Zeile und jeder Spalte von A gilt:

a) Die Summe der Elemente ist gleich 1

b) Das erste nichtnull Element ist +1

c) Die nichtnull Elemente haben wechselnde Vorzeichen

( \begin{matrix}0 & 1 & 0 \\ 1 & −1 & 1 \\ 0 & 1 & 0 \end{matrix} ) ist z.B. eine ASM Matrix.

Die Vermutung, daß die Anzahl n × n ASM Matrizen durch

A_{n} = ∏_{j=0}^{n−1} \frac{(3j + 1)!}{(n + j)!}

gegeben ist, wurde erst vor kurzem mit großem Aufwand bewiesen. (Notices of the American Mathematical Society, Vol. 46, No. 6, S. 637-646, 1999).

Überprüfen Sie diese Vermutung für n = 1, 2, 3.