Identitäten bei Matrizen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo Allerseits,
Ich zitiere zunächst die relevante Stelle aus dem Skript:
Sei [mm] $\IK$ [/mm] ein Körper und $A,B,C [mm] \in \IK^{n \times n}$ [/mm] Matrizen.
Frage: Ist $AB = C$? FREIVALDS schlug 1979 folgende probabilistische Lösung vor:
(1) Wähle $X [mm] \in \left\{0,1\right\}^n$ [/mm] zufällig.
(2) Gib aus, ob [mm] $A\left(BX\right) [/mm] = CX$ mit Aufwand [mm] $\Theta\left(n^2\right)$.
[/mm]
Die Antwort kann mit Wahrscheinlichkeit [mm] $\le \bruch{1}{2}$ [/mm] falsch sein, wenn $AB [mm] \ne [/mm] C$ aber [mm] $A\left(BX\right) [/mm] = CX$.
So, und das verstehe ich nicht. Das Einzige, was hier gemacht wird ist doch die Multiplikation mit $X$ auf beiden Seiten der Gleichung. Wenn $X [mm] \ne [/mm] 0$ oder nicht? Vielleicht habe ich gerade ein Brett vorm Kopf, aber ist das nicht eine Äquivalenzumformung? Was genau macht diesen Test nun zu einem Monte-Carlo-Algorithmus?
Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:18 Fr 16.09.2005 | | Autor: | Stefan |
Lieber Karl!
Einfaches Beispiel:
Es gilt:
[mm] $\pmat{1 & 0 \\ 0 & 1} \cdot \left( \pmat{1 & 1 \\ 1 & 1} \pmat{0 \\ 0} \right) [/mm] = [mm] \pmat{0 & 1\\ 0 & 1} \pmat{0 \\ 0}$
[/mm]
[mm] $\pmat{1 & 0 \\ 0 & 1} \cdot \left( \pmat{1 & 1 \\ 1 & 1} \pmat{1 \\ 0} \right) \ne \pmat{0 & 1 \\ 0 & 1} \pmat{1 \\ 0}$
[/mm]
[mm] $\pmat{1 & 0 \\ 0 & 1} \cdot \left( \pmat{1 & 1 \\ 1 & 1} \pmat{0 \\ 1} \right) [/mm] = [mm] \pmat{0 & 1 \\ 0 & 1} \pmat{0 \\ 1}$
[/mm]
[mm] $\pmat{1 & 0 \\ 0 & 1} \cdot \left( \pmat{1 & 1 \\ 1 & 1} \pmat{1 \\ 1} \right) \ne \pmat{0 & 1 \\ 0 & 1} \pmat{1 \\ 1}$.
[/mm]
Wie du siehst, gilt genau in der Häfte der Fälle
$A(BX) = CX$,
obwohl ja offenbar
$AB = [mm] \pmat{1 & 0 \\0 & 1} \pmat{1& 1 \\ 1 & 1} [/mm] = [mm] \pmat{1 & 1 \\ 1 & 1} \ne \pmat{0 & 1 \\ 0 & 1} [/mm] = C$
gilt.
Liebe Grüße
Stefan
|
|
|
| |
|
Hallo Stefan,
Danke für das einfache Beispiel, das Du mir gegeben hast! Damit ist es jetzt klar.
Im Anhang findest Du, ![[a]](/images/paperclip.gif "Dateianhänge") die Beispiele, die ich für diesen Test gemacht habe. Wie du siehst, hat sich der Test dort kein einziges Mal geirrt mit Ausnahme des Nullvektors aber den habe ich in der vorherigen Frage ausgeschlossen. Die Matrizen habe ich mir zufällig generieren lassen.
Was ich immer noch nicht so ganz verstehe, ist, warum diese Art der Multiplikation im Allgemeinen keine Äquivalenzumformung ist?
Vielen Dank!
Grüße
Karl
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:15 Fr 16.09.2005 | | Autor: | Stefan |
Lieber Karl!
Leider kann ich mir die Beispiele zur Zeit nicht anschauen, weil seltsamerweise mein Acrobat Reader im Moment völlig durchdreht. ![[haee]](/images/smileys/haee.gif "[haee]") Vermutlich hilft ein Neustart, aber dazu habe ich jetzt keine Lust, ich schaue es mir demnächst mal an... 
Zu deiner Frage: Es gilt:
$AB=C$ [mm] $\Leftrightarrow$ [/mm] $(AB)x=A(Bx) = Cx$ für alle $x [mm] \in \{0,1\}^n$.
[/mm]
Wenn du aber ein $x [mm] \in \{0,1\}^n$ [/mm] stochastisch erzeugst, kann es doch sehr wohl passieren, dass $(AB)x=Cx$, aber $AB [mm] \ne [/mm] C$ gilt.
Stell dir zwei lineare Abbildungen vor, die eine heißt $AB$, die andere $C$. Nun betrachten wir deren Differenz, $AB-C$. Für alle $x [mm] \in \{0,1\}^n$, [/mm] für die $ABx=Cx$ gilt, liegt $x [mm] \in [/mm] Kern(AB-C)$. Nun kann aber die lineare Abbildung zwar einen nichttrivialen Kern haben, muss aber deswegen doch noch lange nicht die Nullabbildung sein! D.h. es kann doch durchaus ein [mm] $\{0,1\}^n \ni x_0 \notin [/mm] Kern(AB-C)$ geben! Und für dieses [mm] $x_0$ [/mm] gilt dann eben [mm] $ABx_0 \ne Cx_0$, [/mm] d.h. insbesondere $AB [mm] \ne [/mm] C$.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:51 Fr 16.09.2005 | | Autor: | Stefan |
Lieber Karl!
Jetzt konnte ich es mir anschauen, Danke. Kein Wunder, dass du kein Gegenbeispiel gefunden hast, wenn du die Matrizen ebenfalls stochastisch erzeugt hast. Denn um ein Gegenbeispiel zu finden, mus ja zwangsläufig $Rang(AB-C)<n$ sein (siehe meine Bemerkung zuvor). Und gerade solche Matrizen zufällig zu generieren ist dann doch ziemlich unwahrscheinlich... In den meisten Fällen wird halt $AB-C$ vollen Rang haben und dann kannst du einfach kein Gegenbeispiel finden.
Was lernen wir daraus? Nicht der Informatik vertrauen, sondern der Mathematik!
Liebe Grüße
Stefan
|
|
|
|
![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]"){kind=small}
