Wie viele Möglichkeiten gibt es um das Matrizenprdukt zu ermitteln und wie viele Zahlenmultiplikationen sind dazu nötig?

Question

Ich habe da mal eine Frage und zwar folgende Aufgabe, zu welcher ich auch eine Lösung habe aber eben keinen Lösungsweg und ich auch nichts passendes gefunden habe. Ich hoffe hier kennt sich jemand aus und kann mir das folgende Beispiel verständlich erklären:

Also zum Beispiel:

Gegeben seien folgende vier Matrizen:
M1   10 x 20
M2   20 x 50
M3   50 x 1
M4   1 x 100
Die Werte der Matrizen sind ganzzahlig.

a) Wie viele Möglichkeiten gibt es um das Matrizenprdukt M = M1 x M2 x M3 x M4 zu ermitteln (Angeben)? (5 laut Lsg)

b) Wie viele Zahlenmultiplikationen werden (minimal und maximial) zur Berechung von M benötigt. (65000, 2200, 23000, 11500, 125000)

Ich hoffe es kennt sich jemand aus, damit ich weiß wie man dieses Beispiel lösen kann.

Lg Fritz

Answer 1

Aloha :)

Willkommen in der Mathelounge... \o/

Wir überlegen uns zuerst, wie viele Multiplikationen nötig sind, um zwei Matrizen miteinander zu multiplizieren. Dazu betrachten wir das Produkt aus zwei Matrizen \(A\) und \(B\):$$A\in\mathbb Z^{n\times p}\quad;\quad B\in\mathbb Z^{\,p\times m}\quad\implies\quad(A\cdot B)\in\mathbb Z^{n\times m}$$Die einzelnen Komponenten der Produktmatrix sind:$$(A\cdot B)_{ik}=\sum\limits_{\ell=1}^p a_{i\ell}\times b_{\ell k}\quad;\quad i=1,\ldots,n\quad;\quad k=1,\ldots,m$$Die Produktmatrix hat also \(n\times m\) Elemente und zur Berechnung jedes dieser Elemente brauchen wir \(p\) Multiplikationen. Das macht insgesamt \(n\cdot m\cdot p\) Multiplikationen.

Nun gehen wir an die Aufgabe ran. Wir haben gegeben:$$M_1\in\mathbb Z^{10\times20}\quad;\quad M_2\in\mathbb Z^{20\times50}\quad;\quad M_3\in\mathbb Z^{50\times1}\quad;\quad M_4\in\mathbb Z^{1\times100}$$Das Produkt dieser 4 Matrizen$$M=M_1\cdot M_2\cdot M_3\cdot M_4$$können wir auf verschiedene Arten berechnen. Unten steht die Dimension des Produktes, oben die Anzahl der nötigen Multiplikationen:

$$1)\quad M=\overbrace{\underbrace{(\overbrace{\underbrace{\overbrace{\underbrace{(\underbrace{M_1}_{\in\mathbb Z^{10\times20}}\cdot \underbrace{M_2}_{\in\mathbb Z^{20\times50}})}_{\in\mathbb Z^{10\times50}}}^{=10\cdot50\cdot20=10000}\cdot \underbrace{M_3}_{\in\mathbb Z^{50\times1}}}_{\in\mathbb Z^{10\times1}}}^{=10\times1\times50=500})\cdot\underbrace{M_4}_{\mathbb Z^{1\times100}}}_{\in\mathbb Z^{10\times100}}}^{=10\cdot100\cdot1=1000}\quad;\quad11500\text{ Multiplikationen}$$

$$2)\quad M=\overbrace{\underbrace{\overbrace{\underbrace{(\underbrace{M_1}_{\in\mathbb Z^{10\times20}}\cdot\overbrace{\underbrace{(\underbrace{M_2}_{\in\mathbb Z^{20\times50}}\cdot\underbrace{M_3}_{\in\mathbb Z^{50\times1}})}_{\in\mathbb Z^{20\times1}}}^{=20\cdot1\cdot50=1000})}_{\in\mathbb Z^{10\times1}}}^{=10\cdot1\cdot20=200}\cdot\underbrace{M_4}_{\in\mathbb Z^{1\times100}}}_{\in\mathbb Z^{10\times100}}}^{=10\cdot100\cdot1=1000}\quad;\quad2200\text{ Multiplikationen}$$

$$3)\quad M=\overbrace{\underbrace{\underbrace{M_1}_{\in\mathbb Z^{10\times20}}\cdot\overbrace{\underbrace{(\overbrace{\underbrace{(\underbrace{M_2}_{\in\mathbb Z^{20\times50}}\cdot\underbrace{M_3}_{\in\mathbb Z^{50\times1}})}_{\in\mathbb Z^{20\times1}}}^{=20\cdot1\cdot50=1000}\cdot\underbrace{M_4}_{\in\mathbb Z^{1\times100}})}_{\in\mathbb Z^{20\times100}}}^{=20\cdot100\cdot1=2000}}_{\in\mathbb Z^{10\times100}}}^{=10\cdot100\cdot20=20000}\quad;\quad23000\text{ Multiplikationen}$$

$$4)\quad M=\overbrace{\underbrace{\underbrace{M_1}_{\in\mathbb Z^{10\times20}}\cdot\overbrace{\underbrace{(\underbrace{M_2}_{\in\mathbb Z^{20\times50}}\cdot\overbrace{\underbrace{(\underbrace{M_3}_{\in\mathbb Z^{50\times1}}\cdot\underbrace{M_4}_{\in\mathbb Z^{1\times100}})}_{\in\mathbb Z^{50\times100}}}^{=50\cdot100\cdot1=5000})}_{\in\mathbb Z^{20\times100}}}^{=20\cdot100\cdot50=100000}}_{\in\mathbb Z^{10\times100}}}^{=10\cdot100\cdot20=20000}\quad;\quad125000\text{ Multiplikationen}$$

$$5)\quad M=\overbrace{\underbrace{\overbrace{\underbrace{(\underbrace{M_1}_{\in\mathbb Z^{10\times20}}\cdot\underbrace{M_2}_{\in\mathbb Z^{20\times50}})}_{\in\mathbb Z^{10\times50}}}^{=10\times50\times20=10000}\cdot\overbrace{\underbrace{(\underbrace{M_3}_{\in\mathbb Z^{50\times1}}\cdot\underbrace{M_4}_{\in\mathbb Z^{1\times100}})}_{\in\mathbb Z^{50\times100}}}^{=50\cdot100\cdot1=5000}}_{\in\mathbb Z^{10\times100}}}^{=10\times100\times50=50000}\quad;\quad65000\text{ Multiplikationen}$$

Answer 2

M1 x M2 x M3 x M4

Die 5 Möglichkeiten sind denke ich folgende:

(M1 x M2) x (M3 x M4)

((M1 x M2) x M3) x M4

(M1 x (M2 x M3)) x M4

M1 x ((M2 x M3) x M4)

M1 x (M2 x (M3 x M4))

Wie viele Zahlenmultiplikationen brauchst du um M1 * M2 zu rechnen?

Comments

Na ja, wenn ich es richtig verstehe, dann müsste M12 (ich schreib das mal so an) = M1 x M2 ja 10x50x20 also 10000 sein und M34 = M3 x M4 50x100x1 also 5000 sein. Dann komme ich auf 15000.

Da du jetzt ja schreibst (M1 x M2) x (M3 x M4). Heißt das ich müsste jetzt M12 x M34 rechnen. Aber wie rechne ich (10x50x20) x (50x100x1)?

---

Oder wie fahre ich hier fort?