Discussion:
Zeilen von Matrizen vertauschen, Diagonal-Elemente
(zu alt für eine Antwort)
Stephan Gerlach
2010-11-12 00:23:16 UTC
Permalink
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?

"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."

Mir fällt zwar was ein, aber das geht über Determinanten und ist IMHO zu
umständlich.
--
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
WM
2010-11-12 10:01:06 UTC
Permalink
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?
"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir fällt zwar was ein, aber das geht über Determinanten und ist IMHO zu
umständlich.
Es geht über das Produkt geeigneter Elementarmatrizen.
http://www.oldenbourg-verlag.de/wissenschaftsverlag/mathematik-ersten-semester/9783486591859
p. 92ff

Gruß, WM
Stephan Gerlach
2010-11-13 00:11:01 UTC
Permalink
Post by WM
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?
"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir fällt zwar was ein, aber das geht über Determinanten und ist IMHO zu
umständlich.
Es geht über das Produkt geeigneter Elementarmatrizen.
... welche hier Permutationsmatrizen sein sollten. Sogar eine einzige
solche Matrix P genügt hier, wie ich auch selber schrieb. Daß man die
gewünschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, weiß ich selber. Die Frage war aber, wie
begründet man die Existenz dieser "passenden" Permutationsmatrix P.


Ich hätte als Idee, folgende Darstellung der Determinante

det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}

sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}

zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.

Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
--
Post by WM
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Marc Olschok
2010-11-13 02:21:22 UTC
Permalink
Post by Stephan Gerlach
Post by WM
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?
"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir fällt zwar was ein, aber das geht über Determinanten und ist IMHO zu
umständlich.
Es geht über das Produkt geeigneter Elementarmatrizen.
... welche hier Permutationsmatrizen sein sollten. Sogar eine einzige
solche Matrix P genügt hier, wie ich auch selber schrieb. Daß man die
gewünschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, weiß ich selber. Die Frage war aber, wie
begründet man die Existenz dieser "passenden" Permutationsmatrix P.
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
Induktion sollte funktionieren.
Zunächst einmal gibt es in der ersten Spalte einen von 0 verschiedene
Wert, so dass man die Matrix A mittels einer Transposition in die Gestalt

( r | v^T)
(---+----)
( u | B )

bringen kann, so dass r =/= 0 ein Skalar ist, u und v (n-1) Vektoren sind
und B eine (n-1) x (n-1) Matrix ist.
Einmal angenommen man hätte schon gezeigt, dass B regulär ist, dann
kann man nach Induktion B in die gewünschte Gestalt bringen.
Die hierbei verwendeten Permutationen sind natürlich in Sym({2,..,n}),
als kann man sie auch als Permutationen in Sym({1,..,n}) lesen, die
im Stabilisator von 1 liegen. Oder auf deutsch: man kann B so abändern,
dass man die 1. Zeile obiger Matrix unverändert lässt.
Das liefert auch dann das gewünschten Produkt aller Permutationen.

Es bleibt also nur noch zu begründen, dass obiges B regulär ist.
Sei Bx = 0 für einen (n-1) Vektor x.

Ist u = 0, dann ist

(-rv^Tx)
(------)
( x )

im Kern von A, also folgt x = 0.

Ist u =/= 0, dann kann man A in die Gestalt

( 0 | w^T)
(---+----)
( v | B )

bringen, also ohne B zu verändern (natürlich _nicht_ mitttels
Zeilenpermutationen aber das ist ja nun egal). Es ist dann

(0)
(-)
(x)

im Kern von A, also folgt x = 0.
--
Marc
Detlef Müller
2010-11-13 09:49:46 UTC
Permalink
Post by Marc Olschok
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?
"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
[...]
Induktion sollte funktionieren.
Zunächst einmal gibt es in der ersten Spalte einen von 0 verschiedene
Wert, so dass man die Matrix A mittels einer Transposition in die Gestalt
( r | v^T)
(---+----)
( u | B )
bringen kann, so dass r =/= 0 ein Skalar ist, u und v (n-1) Vektoren sind
und B eine (n-1) x (n-1) Matrix ist.
Einmal angenommen man hätte schon gezeigt, dass B regulär ist, dann
kann man nach Induktion B in die gewünschte Gestalt bringen.
Die hierbei verwendeten Permutationen sind natürlich in Sym({2,..,n}),
als kann man sie auch als Permutationen in Sym({1,..,n}) lesen, die
im Stabilisator von 1 liegen. Oder auf deutsch: man kann B so abändern,
dass man die 1. Zeile obiger Matrix unverändert lässt.
Das liefert auch dann das gewünschten Produkt aller Permutationen.
Es bleibt also nur noch zu begründen, dass obiges B regulär ist.
Hm, im 2x2-Beispiel:

( r | v^T) ( 1 | 1 )
(---+----) = (---+---)
( u | B ) ( 1 | 0 )

Ist B nicht regulär.
Vermutlich muß man bei den Permutationen für die erste
Spalte noch aufpassen.
Post by Marc Olschok
...
Gruß,
Detlef
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Carsten Schultz
2010-11-13 09:50:28 UTC
Permalink
Post by Marc Olschok
Post by Stephan Gerlach
Post by WM
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?
"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir fällt zwar was ein, aber das geht über Determinanten und ist IMHO zu
umständlich.
Es geht über das Produkt geeigneter Elementarmatrizen.
... welche hier Permutationsmatrizen sein sollten. Sogar eine einzige
solche Matrix P genügt hier, wie ich auch selber schrieb. Daß man die
gewünschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, weiß ich selber. Die Frage war aber, wie
begründet man die Existenz dieser "passenden" Permutationsmatrix P.
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
Wenn es nur auf die Existenz ankommt, finde ich den Beweis völlig
angemessen.
Post by Marc Olschok
Induktion sollte funktionieren.
Zunächst einmal gibt es in der ersten Spalte einen von 0 verschiedene
Wert, so dass man die Matrix A mittels einer Transposition in die Gestalt
( r | v^T)
(---+----)
( u | B )
bringen kann, so dass r =/= 0 ein Skalar ist, u und v (n-1) Vektoren sind
und B eine (n-1) x (n-1) Matrix ist.
Einmal angenommen man hätte schon gezeigt, dass B regulär ist,
Ist es aber im allgemeinen nicht:

11
10

Gruß

Carsten
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
Stephan Gerlach
2010-11-20 00:12:59 UTC
Permalink
Marc Olschok schrieb:

[...]
Post by Marc Olschok
Induktion sollte funktionieren.
Das dachte ich zunächst auch. Aber egal, wie ich es anstellte - ich fand
immer ein Gegenbeispiel...
Post by Marc Olschok
Zunächst einmal gibt es in der ersten Spalte einen von 0 verschiedene
Wert,
Klar, aber damit kommt man leider nicht weit...
Post by Marc Olschok
so dass man die Matrix A mittels einer Transposition in die Gestalt
( r | v^T)
(---+----)
( u | B )
bringen kann, so dass r =/= 0 ein Skalar ist, u und v (n-1) Vektoren sind
und B eine (n-1) x (n-1) Matrix ist.
Einmal angenommen man hätte schon gezeigt, dass B regulär ist,
... was genau das Problem ist.
Post by Marc Olschok
dann
kann man nach Induktion B in die gewünschte Gestalt bringen.
Schön wär's :-) .
Post by Marc Olschok
Die hierbei verwendeten Permutationen sind natürlich in Sym({2,..,n}),
als kann man sie auch als Permutationen in Sym({1,..,n}) lesen, die
im Stabilisator von 1 liegen. Oder auf deutsch: man kann B so abändern,
dass man die 1. Zeile obiger Matrix unverändert lässt.
Das liefert auch dann das gewünschten Produkt aller Permutationen.
Es bleibt also nur noch zu begründen, dass obiges B regulär ist.
Das funktioniert eben nicht (wie es die bereits geposteten
Gegenbeispiele zeigen).
Post by Marc Olschok
Sei Bx = 0 für einen (n-1) Vektor x.
Ist u = 0, dann ist
(-rv^Tx)
(------)
( x )
im Kern von A, also folgt x = 0.
Du meintest bestimmt

(-1/r*v^Tx)
(---------)
( x ),

dieser Vektor ist tatsächlich im Kern von A.
Post by Marc Olschok
Ist u =/= 0, dann kann man A in die Gestalt
( 0 | w^T)
(---+----)
( v | B )
bringen,
Genau das ist wahrscheinlich, was am (Gegen-)Beispiel

A = (1 1)
(1 0)

nicht funktioniert.
--
Post by Marc Olschok
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Marc Olschok
2010-11-20 02:14:28 UTC
Permalink
Post by Stephan Gerlach
[...]
Post by Marc Olschok
Induktion sollte funktionieren.
Das dachte ich zunächst auch. Aber egal, wie ich es anstellte - ich fand
immer ein Gegenbeispiel...
Post by Marc Olschok
Zunächst einmal gibt es in der ersten Spalte einen von 0 verschiedene
Wert,
Klar, aber damit kommt man leider nicht weit...
Post by Marc Olschok
so dass man die Matrix A mittels einer Transposition in die Gestalt
( r | v^T)
(---+----)
( u | B )
bringen kann, so dass r =/= 0 ein Skalar ist, u und v (n-1) Vektoren sind
und B eine (n-1) x (n-1) Matrix ist.
Einmal angenommen man hätte schon gezeigt, dass B regulär ist,
... was genau das Problem ist.
Richtig. Wie ja auch Carsten, Detlef und Du schon mit dem Beispiel
(1 1)
(1 0)
demonstrierten. Mir kam dieses Beispiel auch erst in den Sinn als
ich den Beitrag schon lange versandt hatte. Seitdem denke ich ab
und zu noch mal über einen Reparaturversuch nach, komme aber auf
keine zündende Idee.

Wenn man den Induktionsbeweis noch retten will, muss man sich zumindest
von der Idee verabschieden, die Faktoren der gesuchten Permutation
schrittweise aus immer kleineren Untergruppen der S_n wählen zu
können.

Wenn etwa a_1,1 bis a_k-1,k-1 bereits ungleich 0 sind und
die Matrix die Form

a_1,1 ... a_1,k-1 a_1,k ...
. ... . .
. ... . .
a_k-1,1 ... a_k-1,k-1 a_k-1,k ...
a_k,1 ... a_k,k-1 0 ...
. ... . .
. ... . .

hat, braucht man also eine Folge k=i[0], i[1], ..., i[m]
mit i[m] >= k, so dass stets a_i[n],i[n+1] ungleich 0 ist.
Je nachdem, ob i[m] = k oder i[m] > k gilt, ist dann
entweder ( i[m-1] ... i[1] k ) oder ( i[m] i[m-1] ... i[1] k )
eine geeignete Permutation (in Zykelschreibweise) der Zeilen,
so dass nun alle Diagonaleinträge a'_1,1 bis a'_k,k ungleich 0 sind.

Für
(1 1)
(1 0)
sieht man natürlich sofort, dass die Folge 2, 1 dass gewünschte
leistet. Im Prinzip kann man das Verfahren auch programmieren.
Aber ich sehe noch keinen Beweis dafür, dass es immer erfolgreich ist.

Außerdem glaube ich mittlerweile, dass der Beweis mittels Determinante
nicht nur eleganter ist als solche Induktionsversuche, sondern auch
konzeptionell klarer ist, weil damit demonstriert wird, dass die
dadurch beschriebene Eigenschaft echt stärker als Invertierbarkeit ist.
--
Marc
WM
2010-11-20 12:49:05 UTC
Permalink
Post by Stephan Gerlach
[...]
Post by Marc Olschok
Induktion sollte funktionieren.
Das dachte ich zunächst auch. Aber egal, wie ich es anstellte - ich fand
immer ein Gegenbeispiel...
Post by Marc Olschok
Zunächst einmal gibt es in der ersten Spalte einen von 0 verschiedene
Wert,
Klar, aber damit kommt man leider nicht weit...
Da die Matrix umkehrbar vorausgesetzt ist, sind die Zeilenvektoren
linear unabhängig. Folglich muss in jeder Spalte ein Element =/=
stehen.

Gäbe es nun nur n Zeilen, die benötigt würden, um n+1 Zeilen mit
Diagonalelementen =/= 0 zu versorgen, dann wäre eine der restlichen
Zeilen nicht linear unabhängig von den anderen.


Bsp:
1100
1010
0001
xxxx

Enthalten hier nur die ersten beiden Zeilen die drei ersten
Diagonalelemente =/= 0, dann muss die letzte Zeile von der Form 000a
sein. Widerspruch.
Für größere Matrizen ist der Beweis analog. Enthalten nur n Zeilen die
ersten n+1 Diagonalelemente =/= 0, so müssen die restlichen Zeilen
eine linear abhängige Zeile enthalten. Also kann immer die gewünschte
Umordnung mit Elementarmatrizen erfolgen.

Um nun die Konstruktion zu automatisieren, bringt man zuerst eine
Zeile mit a_i1 =/= 0 nach oben. Gibt es nur eine, ist das die
endgültige Konfiguration. Sind alle anderen Elemente dieser Zeile 0,
ebenfalls. Das geht mit Elementarmatrizen. Dann wählt man eine Zeile
mit a_k2 =/= 0, benutzt sie als zweite Zeile usw. Stößt man irgendwo
auf das Problem eines fehlenden Diagonalelementes, muss man umordnen.
Wegen der linearen Unabhängigkeit der Zeilen findet man immer eine
geeignete.

Gruß, WM
WM
2010-11-13 09:47:28 UTC
Permalink
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begr ndung f r folgende Bemerkung?
"Gegeben sei eine invertierbare n n-Matrix A. Dann existiert immer eine
n n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, da auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir f llt zwar was ein, aber das geht ber Determinanten und ist IMHO zu
umst ndlich.
Es geht ber das Produkt geeigneter Elementarmatrizen.
... welche hier Permutationsmatrizen sein sollten. Sogar eine einzige
solche Matrix P genügt hier, wie ich auch selber schrieb.
Es gibt drei Elementaroperationen, von denen jede eine spezielle
Elementarmatrix besitzt, die sich sofort aus der Einheitsmatrix
ergeben (z. B. Zeilenvertauschung oder Multiplikation einer Zeile mit
einer Zahl). In der Regel genügt aber keine einzelne Matrix, um die
gewünschte Permutation zu erzielen, sondern man benötigt ein Produkt
von mehreren Matrizen.
Post by Stephan Gerlach
Da man die
gew nschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, wei ich selber. Die Frage war aber, wie
begr ndet man die Existenz dieser "passenden" Permutationsmatrix P.
Man begründet sie mit der Assoziatitvität der Matrixmultiplikation für
das Produkt der Elementarmatrizen und die Einheitsmatrix:

http://www.hs-augsburg.de/~mueckenh/Mathematerial/M11.PPT#362,55,Folie
55

Konstruktiv und ohne Determinante.

Gruß, WM
Carsten Schultz
2010-11-13 10:00:12 UTC
Permalink
Post by WM
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begr ndung f r folgende Bemerkung?
"Gegeben sei eine invertierbare n n-Matrix A. Dann existiert immer eine
n n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, da auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir f llt zwar was ein, aber das geht ber Determinanten und ist IMHO zu
umst ndlich.
Es geht ber das Produkt geeigneter Elementarmatrizen.
... welche hier Permutationsmatrizen sein sollten. Sogar eine einzige
solche Matrix P genügt hier, wie ich auch selber schrieb.
Es gibt drei Elementaroperationen, von denen jede eine spezielle
Elementarmatrix besitzt, die sich sofort aus der Einheitsmatrix
ergeben (z. B. Zeilenvertauschung oder Multiplikation einer Zeile mit
einer Zahl). In der Regel genügt aber keine einzelne Matrix, um die
gewünschte Permutation zu erzielen, sondern man benötigt ein Produkt
von mehreren Matrizen.
Post by Stephan Gerlach
Da man die
gew nschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, wei ich selber. Die Frage war aber, wie
begr ndet man die Existenz dieser "passenden" Permutationsmatrix P.
Man begründet sie mit der Assoziatitvität der Matrixmultiplikation für
http://www.hs-augsburg.de/~mueckenh/Mathematerial/M11.PPT#362,55,Folie
55
Konstruktiv und ohne Determinante.
Versuch doch, erst einmal die Frage zu verstehen.
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
WM
2010-11-13 11:44:30 UTC
Permalink
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begr ndung f r folgende Bemerkung?
"Gegeben sei eine invertierbare n n-Matrix A. Dann existiert immer eine
n n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, da auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir f llt zwar was ein, aber das geht ber Determinanten und ist IMHO zu
umst ndlich.
Es geht ber das Produkt geeigneter Elementarmatrizen.
... welche hier Permutationsmatrizen sein sollten. Sogar eine einzige
solche Matrix P genügt hier, wie ich auch selber schrieb.
Es gibt drei Elementaroperationen, von denen jede eine spezielle
Elementarmatrix besitzt, die sich sofort aus der Einheitsmatrix
ergeben (z. B. Zeilenvertauschung oder Multiplikation einer Zeile mit
einer Zahl). In der Regel genügt aber keine einzelne Matrix, um die
gewünschte Permutation zu erzielen, sondern man benötigt ein Produkt
von mehreren Matrizen.
Post by Stephan Gerlach
Da man die
gew nschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, wei ich selber. Die Frage war aber, wie
begr ndet man die Existenz dieser "passenden" Permutationsmatrix P.
Man begründet sie mit der Assoziatitvität der Matrixmultiplikation für
http://www.hs-augsburg.de/~mueckenh/Mathematerial/M11.PPT#362,55,Folie
55
Konstruktiv und ohne Determinante.
Versuch doch, erst einmal die Frage zu verstehen.
Wäre Deine mathematische Unbildung nicht gar so universell, so hättest
Du Dir wenigstens diese Bemerkung gespart.

Gegeben ist eine invertierbare Matrix A. Das bedeutet nach Definition,
man kann sie mit Elementarmatrizen zur Einheitsmatrix umformen. Das
Produkt P der verwendeten Elementarmatrizen ist immer regulär (und
damit auch im Allgemeinen). Und die Einheitsmatrix P*A = I enthält
Einsen und nur Einsen in der Diagonalen.

Gruß, WM
Karl8heinz
2010-11-13 11:48:25 UTC
Permalink
Post by WM
Post by Carsten Schultz
Versuch doch, erst einmal die Frage zu verstehen.
Wäre Deine mathematische Unbildung nicht gar so universell,
so hättest Du Dir wenigstens diese Bemerkung gespart.
Strengt euch doch endlich mal ein bisschen an, wenn ihr mit
einem ordentlichen Professor Doktor der Mathematik reden wollt.
Carsten Schultz
2010-11-13 12:06:24 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begr ndung f r folgende Bemerkung?
"Gegeben sei eine invertierbare n n-Matrix A. Dann existiert immer eine
n n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
^^^^^^^^^^^^^^^^^^
Post by WM
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
die Zeilen von A derart vertauscht, da auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir f llt zwar was ein, aber das geht ber Determinanten und ist IMHO zu
umst ndlich.
Es geht ber das Produkt geeigneter Elementarmatrizen.
... welche hier Permutationsmatrizen sein sollten. Sogar eine einzige
^^^^^^^^^^^^^^^^^^^^
Post by WM
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
solche Matrix P genügt hier, wie ich auch selber schrieb.
Es gibt drei Elementaroperationen, von denen jede eine spezielle
Elementarmatrix besitzt, die sich sofort aus der Einheitsmatrix
ergeben (z. B. Zeilenvertauschung oder Multiplikation einer Zeile mit
einer Zahl). In der Regel genügt aber keine einzelne Matrix, um die
gewünschte Permutation zu erzielen, sondern man benötigt ein Produkt
von mehreren Matrizen.
Post by Stephan Gerlach
Da man die
gew nschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, wei ich selber. Die Frage war aber, wie
begr ndet man die Existenz dieser "passenden" Permutationsmatrix P.
Man begründet sie mit der Assoziatitvität der Matrixmultiplikation für
http://www.hs-augsburg.de/~mueckenh/Mathematerial/M11.PPT#362,55,Folie
55
Konstruktiv und ohne Determinante.
Versuch doch, erst einmal die Frage zu verstehen.
Siehe meine Hilfestellung dazu oben.
Post by WM
Wäre Deine mathematische Unbildung nicht gar so universell, so hättest
Du Dir wenigstens diese Bemerkung gespart.
Gegeben ist eine invertierbare Matrix A. Das bedeutet nach Definition,
man kann sie mit Elementarmatrizen zur Einheitsmatrix umformen. Das
Produkt P der verwendeten Elementarmatrizen ist immer regulär (und
damit auch im Allgemeinen). Und die Einheitsmatrix P*A = I enthält
Einsen und nur Einsen in der Diagonalen.
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
WM
2010-11-13 13:05:44 UTC
Permalink
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begr ndung f r folgende Bemerkung?
"Gegeben sei eine invertierbare n n-Matrix A. Dann existiert immer eine
n n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
           ^^^^^^^^^^^^^^^^^^>>>>>> die Zeilen von A derart vertauscht, da auf der Hauptdiagonalen der
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir f llt zwar was ein, aber das geht ber Determinanten und ist IMHO zu
umst ndlich.
Es geht ber das Produkt geeigneter Elementarmatrizen.
... welche hier Permutationsmatrizen sein sollten. Sogar eine einzige
                     ^^^^^^^^^^^^^^^^^^^^
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
solche Matrix P genügt hier, wie ich auch selber schrieb.
Es gibt drei Elementaroperationen, von denen jede eine spezielle
Elementarmatrix besitzt, die sich sofort aus der Einheitsmatrix
ergeben (z. B. Zeilenvertauschung oder Multiplikation einer Zeile mit
einer Zahl). In der Regel genügt aber keine einzelne Matrix, um die
gewünschte Permutation zu erzielen, sondern man benötigt ein Produkt
von mehreren Matrizen.
Post by Stephan Gerlach
Da man die
gew nschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, wei ich selber. Die Frage war aber, wie
begr ndet man die Existenz dieser "passenden" Permutationsmatrix P.
Man begründet sie mit der Assoziatitvität der Matrixmultiplikation für
http://www.hs-augsburg.de/~mueckenh/Mathematerial/M11.PPT#362,55,Folie
55
Konstruktiv und ohne Determinante.
Versuch doch, erst einmal die Frage zu verstehen.
Siehe meine Hilfestellung dazu oben.
Und? Hast Du schon einmal eine Permutationsmatrix mit eigenen Augen
gesehen? Hast Du auch schon einmal eine Elementarmatrix gesehen, die
nichts weiter tut als zwei Zeilen zu vertauschen? Und hast Du auch
schon einmal das Produkt solcher Matrizen gesehen?

Falls ja, dann frage ich mich, was Dein Hinweis bedeuten soll.

Vielleicht fällt Dir zusätzlich noch auf, dass die von Dir als
Hinderungsgrund genannte Matrix B
11
10
mit einer Permutationsmatrix E auf die Form
10
11
gebracht werden kann? Und dass alle schon vorher verwendeten Matrizen
P mit E multipliziert wieder eine Permutationsmatrix E*P ergeben?

Gruß, WM
Carsten Schultz
2010-11-13 13:14:23 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begr ndung f r folgende Bemerkung?
"Gegeben sei eine invertierbare n n-Matrix A. Dann existiert immer eine
n n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
^^^^^^^^^^^^^^^^^^>>>>>> die Zeilen von A derart vertauscht, da auf der Hauptdiagonalen der
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir f llt zwar was ein, aber das geht ber Determinanten und ist IMHO zu
umst ndlich.
Es geht ber das Produkt geeigneter Elementarmatrizen.
... welche hier Permutationsmatrizen sein sollten. Sogar eine einzige
^^^^^^^^^^^^^^^^^^^^
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
solche Matrix P genügt hier, wie ich auch selber schrieb.
Es gibt drei Elementaroperationen, von denen jede eine spezielle
Elementarmatrix besitzt, die sich sofort aus der Einheitsmatrix
ergeben (z. B. Zeilenvertauschung oder Multiplikation einer Zeile mit
einer Zahl). In der Regel genügt aber keine einzelne Matrix, um die
gewünschte Permutation zu erzielen, sondern man benötigt ein Produkt
von mehreren Matrizen.
Post by Stephan Gerlach
Da man die
gew nschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, wei ich selber. Die Frage war aber, wie
begr ndet man die Existenz dieser "passenden" Permutationsmatrix P.
Man begründet sie mit der Assoziatitvität der Matrixmultiplikation für
http://www.hs-augsburg.de/~mueckenh/Mathematerial/M11.PPT#362,55,Folie
55
Konstruktiv und ohne Determinante.
Versuch doch, erst einmal die Frage zu verstehen.
Siehe meine Hilfestellung dazu oben.
Und? Hast Du schon einmal eine Permutationsmatrix mit eigenen Augen
gesehen? Hast Du auch schon einmal eine Elementarmatrix gesehen, die
nichts weiter tut als zwei Zeilen zu vertauschen? Und hast Du auch
schon einmal das Produkt solcher Matrizen gesehen?
Falls ja, dann frage ich mich, was Dein Hinweis bedeuten soll.
Dass nicht jede Elementarmatrix eine Permutationsmatrix ist und dass Du
eine invertierbare Matrix im allgemeinen nicht alleine mit
Zeilenvertauschungen auf Diagonalgestalt bringen kannst.
Post by WM
Vielleicht fällt Dir zusätzlich noch auf, dass die von Dir als
Hinderungsgrund genannte Matrix B
11
10
mit einer Permutationsmatrix E auf die Form
10
11
gebracht werden kann?
Vielleicht liest Du einfach mal, bevor Du zitierst. Das Beispiel war
ein Gegenbeispiel gegen eine andere Behauptung. Dass sich jede
invertierbare Matrix durch Zeilenvertauschungen, also durch
Multiplikation mit einer Permutationsmatrix, in eine Form bringen lässt,
in der keine Null auf der Diagonalen steht, ist unbestritten. Der
einfache Beweis wurde im Ursprungsposting erwähnt und später ausgeführt.
Post by WM
Und dass alle schon vorher verwendeten Matrizen
P mit E multipliziert wieder eine Permutationsmatrix E*P ergeben?
Was Du nicht sagst!
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
WM
2010-11-13 13:23:31 UTC
Permalink
Post by Carsten Schultz
Post by WM
Falls ja, dann frage ich mich, was Dein Hinweis bedeuten soll.
Dass nicht jede Elementarmatrix eine Permutationsmatrix ist und dass Du
eine invertierbare Matrix im allgemeinen nicht alleine mit
Zeilenvertauschungen auf Diagonalgestalt bringen kannst.
Das wurde ja auch nicht gefordert. Aber mit der Konstruktion unter
Verwendung aller Elementarmatrizen kann man die Diagonalgestalt
erhalten und somit konstruktiv beweisen, dass auch bei Verzicht auf
Faktoren ungleich 1 überall Diagonalelemente vorhanden sein müssen.
Post by Carsten Schultz
Post by WM
Vielleicht fällt Dir zusätzlich noch auf, dass die von Dir als
Hinderungsgrund genannte Matrix B
11
10
mit einer Permutationsmatrix E auf die Form
10
11
gebracht werden kann?
Vielleicht liest Du einfach mal, bevor Du zitierst.  Das Beispiel war
ein Gegenbeispiel gegen eine andere Behauptung.  Dass sich jede
invertierbare Matrix durch Zeilenvertauschungen, also durch
Multiplikation mit einer Permutationsmatrix, in eine Form bringen lässt,
in der keine Null auf der Diagonalen steht, ist unbestritten.  Der
einfache Beweis wurde im Ursprungsposting erwähnt und später ausgeführt.
Post by WM
Und dass alle schon vorher verwendeten Matrizen
P mit E multipliziert wieder eine Permutationsmatrix E*P ergeben?
Was Du nicht sagst!
Das ist eben das Prinzip, das dem einfachen konstruktiven Beweis ohne
Determinante zugrundeliegt. Jetzt hast Du es auch verstanden? Das
freut mich.

Gruß, WM
Karlheinz
2010-11-13 13:37:50 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by WM
Und dass alle schon vorher verwendeten Matrizen
P mit E multipliziert wieder eine Permutationsmatrix E*P ergeben?
Was Du nicht sagst!
Das ist eben das Prinzip, das dem einfachen konstruktiven Beweis ohne
Determinante zugrundeliegt. Jetzt hast Du es auch verstanden? Das
freut mich.
Mich ebenfalls!

Endlich hat mal einer was vom Professor Doktor gelernt, auch wenn
es beide den Samstag gekostet hat.
Carsten Schultz
2010-11-13 13:39:21 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by WM
Falls ja, dann frage ich mich, was Dein Hinweis bedeuten soll.
Dass nicht jede Elementarmatrix eine Permutationsmatrix ist und dass Du
eine invertierbare Matrix im allgemeinen nicht alleine mit
Zeilenvertauschungen auf Diagonalgestalt bringen kannst.
Das wurde ja auch nicht gefordert. Aber mit der Konstruktion unter
Verwendung aller Elementarmatrizen kann man die Diagonalgestalt
erhalten und somit konstruktiv beweisen, dass auch bei Verzicht auf
Faktoren ungleich 1 überall Diagonalelemente vorhanden sein müssen.
Post by Carsten Schultz
Post by WM
Vielleicht fällt Dir zusätzlich noch auf, dass die von Dir als
Hinderungsgrund genannte Matrix B
11
10
mit einer Permutationsmatrix E auf die Form
10
11
gebracht werden kann?
Vielleicht liest Du einfach mal, bevor Du zitierst. Das Beispiel war
ein Gegenbeispiel gegen eine andere Behauptung. Dass sich jede
invertierbare Matrix durch Zeilenvertauschungen, also durch
Multiplikation mit einer Permutationsmatrix, in eine Form bringen lässt,
in der keine Null auf der Diagonalen steht, ist unbestritten. Der
einfache Beweis wurde im Ursprungsposting erwähnt und später ausgeführt.
Post by WM
Und dass alle schon vorher verwendeten Matrizen
P mit E multipliziert wieder eine Permutationsmatrix E*P ergeben?
Was Du nicht sagst!
Das ist eben das Prinzip, das dem einfachen konstruktiven Beweis ohne
Determinante zugrundeliegt.
Du hast keinen solchen Beweis geliefert. Macht aber nichts, es erwartet
von Dir ja auch niemand Mathematik.
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
WM
2010-11-13 13:43:56 UTC
Permalink
Post by Carsten Schultz
Post by WM
Das ist eben das Prinzip, das dem einfachen konstruktiven Beweis ohne
Determinante zugrundeliegt.
Du hast keinen solchen Beweis geliefert.
Doch noch nicht verstanden? Dann gebe ich auf!
Post by Carsten Schultz
 Macht aber nichts, es erwartet
von Dir ja auch niemand Mathematik.
Sollte ich tausende von Euros Monat für Monat geschenkt bekommen?

Gruß, WM
Roalto
2010-11-20 13:14:14 UTC
Permalink
On Sat, 13 Nov 2010 05:43:56 -0800 (PST), WM
Post by WM
Post by Carsten Schultz
Post by WM
Das ist eben das Prinzip, das dem einfachen konstruktiven Beweis ohne
Determinante zugrundeliegt.
Du hast keinen solchen Beweis geliefert.
Doch noch nicht verstanden? Dann gebe ich auf!
Post by Carsten Schultz
 Macht aber nichts, es erwartet
von Dir ja auch niemand Mathematik.
Sollte ich tausende von Euros Monat für Monat geschenkt bekommen?
Na, ja. Es ist ja hinlänglich bekannt, dass diese Gesellschaft es sich
leisten kann tausende von Dummköpfen und Dumpfbacken in Parlamenten
und Fachhochschulen oder sonstwo, deren Lebensleistung darin besteht
nicht verstanden zu haben, worüber sie sabbeln, mit durchzufüttern.
Post by WM
Gruß, WM
Viel Spass weiterhin
Rolf
--
Wo Frauen geehrt werden,
sind die Götter zufrieden.
Karlheinz
2010-11-13 13:47:48 UTC
Permalink
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by WM
Falls ja, dann frage ich mich, was Dein Hinweis bedeuten soll.
Dass nicht jede Elementarmatrix eine Permutationsmatrix ist und dass Du
eine invertierbare Matrix im allgemeinen nicht alleine mit
Zeilenvertauschungen auf Diagonalgestalt bringen kannst.
Das wurde ja auch nicht gefordert. Aber mit der Konstruktion unter
Verwendung aller Elementarmatrizen kann man die Diagonalgestalt
erhalten und somit konstruktiv beweisen, dass auch bei Verzicht auf
Faktoren ungleich 1 überall Diagonalelemente vorhanden sein müssen.
Post by Carsten Schultz
Post by WM
Vielleicht fällt Dir zusätzlich noch auf, dass die von Dir als
Hinderungsgrund genannte Matrix B
11
10
mit einer Permutationsmatrix E auf die Form
10
11
gebracht werden kann?
Vielleicht liest Du einfach mal, bevor Du zitierst. Das Beispiel war
ein Gegenbeispiel gegen eine andere Behauptung. Dass sich jede
invertierbare Matrix durch Zeilenvertauschungen, also durch
Multiplikation mit einer Permutationsmatrix, in eine Form bringen lässt,
in der keine Null auf der Diagonalen steht, ist unbestritten. Der
einfache Beweis wurde im Ursprungsposting erwähnt und später ausgeführt.
Post by WM
Und dass alle schon vorher verwendeten Matrizen
P mit E multipliziert wieder eine Permutationsmatrix E*P ergeben?
Was Du nicht sagst!
Das ist eben das Prinzip, das dem einfachen konstruktiven Beweis ohne
Determinante zugrundeliegt.
Du hast keinen solchen Beweis geliefert. Macht aber nichts, es erwartet
von Dir ja auch niemand Mathematik.
Eben! Man kann sich auch prima über alles andere mit dem Proffessor
unterhalten: du bist z.B. süchtig danach, seine gescheiten Worte
zu vernehmen.
Stephan Gerlach
2010-11-20 00:32:36 UTC
Permalink
Post by Carsten Schultz
Post by WM
Das ist eben das Prinzip, das dem einfachen konstruktiven Beweis ohne
Determinante zugrundeliegt.
Du hast keinen solchen Beweis geliefert. Macht aber nichts, es erwartet
von Dir ja auch niemand Mathematik.
Interessant in dem Zusammenhang ist, daß dies anscheinend auch in Fällen
auftreten kann, wo es nicht um das WM-Thema Nummer 1 "unendlich gibt's
sowieso nicht" geht.
--
Post by Carsten Schultz
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Stephan Gerlach
2010-11-20 00:30:45 UTC
Permalink
Post by WM
Aber mit der Konstruktion unter
Verwendung aller Elementarmatrizen kann man die Diagonalgestalt
erhalten
Ich wollte aber nur die Zeilen von A permutieren!
*Nicht* auf "die übliche, bekannte" Diagonalgestalt (oder
Dreiecks-Gestalt) bringen, bei welcher i.a. nicht mehr viel davon zu
erkennen ist, wie die Zeilen von A "früher" mal aussahen.
--
Post by WM
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Jutta Gut
2010-11-13 16:36:09 UTC
Permalink
Post by WM
Es gibt drei Elementaroperationen, von denen jede eine spezielle
Elementarmatrix besitzt, die sich sofort aus der Einheitsmatrix
ergeben (z. B. Zeilenvertauschung oder Multiplikation einer Zeile mit
einer Zahl). In der Regel genügt aber keine einzelne Matrix, um die
gewünschte Permutation zu erzielen, sondern man benötigt ein Produkt
von mehreren Matrizen.
Das Produkt von mehreren Matrizen ist doch eine Matrix.

Grüße
Jutta
WM
2010-11-13 17:36:55 UTC
Permalink
Post by Jutta Gut
Post by WM
Es gibt drei Elementaroperationen, von denen jede eine spezielle
Elementarmatrix besitzt, die sich sofort aus der Einheitsmatrix
ergeben (z. B. Zeilenvertauschung oder Multiplikation einer Zeile mit
einer Zahl). In der Regel genügt aber keine einzelne Matrix, um die
gewünschte Permutation zu erzielen, sondern man benötigt ein Produkt
von mehreren Matrizen.
Das Produkt von mehreren Matrizen ist doch eine Matrix.
Will sagen: In der Regel genügt aber keine einzelne Elementarmatrix
(die nur zwei Zeilen vertauscht).

Gruß, WM
WM
2010-11-13 17:56:08 UTC
Permalink
Post by WM
Post by Jutta Gut
Das Produkt von mehreren Matrizen ist doch eine Matrix.
Will sagen: In der Regel genügt aber keine einzelne Elementarmatrix
(die nur zwei Zeilen vertauscht).
Herzlichen Dank für die Hilfe lieber Herr Professor Doktor Mückenheim.
JürgenR
2010-11-13 19:41:37 UTC
Permalink
Post by WM
Post by Jutta Gut
Post by WM
Es gibt drei Elementaroperationen, von denen jede eine spezielle
Elementarmatrix besitzt, die sich sofort aus der Einheitsmatrix
ergeben (z. B. Zeilenvertauschung oder Multiplikation einer Zeile mit
einer Zahl). In der Regel genügt aber keine einzelne Matrix, um die
gewünschte Permutation zu erzielen, sondern man benötigt ein Produkt
von mehreren Matrizen.
Das Produkt von mehreren Matrizen ist doch eine Matrix.
Will sagen: In der Regel genügt aber keine einzelne Elementarmatrix
(die nur zwei Zeilen vertauscht).
Und es genügt auch nicht das Produkt von beliebig vielen Elementarmatrizen.
Post by WM
Gruß, WM
WM
2010-11-20 12:57:22 UTC
Permalink
Post by WM
Post by Jutta Gut
Post by WM
Es gibt drei Elementaroperationen, von denen jede eine spezielle
Elementarmatrix besitzt, die sich sofort aus der Einheitsmatrix
ergeben (z. B. Zeilenvertauschung oder Multiplikation einer Zeile mit
einer Zahl). In der Regel genügt aber keine einzelne Matrix, um die
gewünschte Permutation zu erzielen, sondern man benötigt ein Produkt
von mehreren Matrizen.
Das Produkt von mehreren Matrizen ist doch eine Matrix.
Will sagen: In der Regel genügt aber keine einzelne Elementarmatrix
(die nur zwei Zeilen vertauscht).
Und es genügt auch nicht das Produkt von beliebig  vielen Elementarmatrizen.
Mal wieder auf Unendlichkeitstrip?

Gruß, WM
Stephan Gerlach
2010-11-20 00:21:53 UTC
Permalink
Post by WM
In der Regel genügt aber keine einzelne Matrix, um die
gewünschte Permutation zu erzielen, sondern man benötigt ein Produkt
von mehreren Matrizen.
Für eine Permutation (und genau darum ging es; *nicht* um Multiplikation
einer Zeile mit einer Zahl oder Addition verschiedener Zeilen) genügt
AFAIK eigentlich schon eine einzelne Matrix, welche passenderweise
'Permutationsmatrix' genannt wird. Sie zeichnet sich dadurch aus, daß in
jeder Zeile und Spalte dieser Matrix genau eine 1 vorkommt; ansonsten
nur 0-en.
Post by WM
Post by Stephan Gerlach
Da man die
gew nschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, wei ich selber. Die Frage war aber, wie
begr ndet man die Existenz dieser "passenden" Permutationsmatrix P.
Man begründet sie mit der Assoziatitvität der Matrixmultiplikation für
http://www.hs-augsburg.de/~mueckenh/Mathematerial/M11.PPT#362,55,Folie
55
Könntest du das Gewünschte bitte am Beispiel der Matrix

(1 0 1 0)
A = (5 0 0 0)
(7 2 0 9)
(8 1 0 2)

vorführen. Also wie konkret führt hier die Assoziativität der
Matrixmultiplikation für das Produkt der Elementarmatrizen zur Existenz
der gewünschten Permutation.
--
Post by WM
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
WM
2010-11-20 10:36:13 UTC
Permalink
In der Regel gen gt aber keine einzelne Matrix, um die
gew nschte Permutation zu erzielen, sondern man ben tigt ein Produkt
von mehreren Matrizen.
F r eine Permutation (und genau darum ging es; *nicht* um Multiplikation
einer Zeile mit einer Zahl oder Addition verschiedener Zeilen) gen gt
AFAIK eigentlich schon eine einzelne Matrix, welche passenderweise
'Permutationsmatrix' genannt wird. Sie zeichnet sich dadurch aus, da in
jeder Zeile und Spalte dieser Matrix genau eine 1 vorkommt; ansonsten
nur 0-en.
Selbstverständlich ist die gesuchte Matrix ein Produkt von
Elementarmatrizen. Als ich Obiges schrieb, bezog ich mich auf
Elementarmatrizen. Ein verständiger Leser hätte das erkannt.
Post by Stephan Gerlach
Da man die
gew nschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, wei ich selber. Die Frage war aber, wie
begr ndet man die Existenz dieser "passenden" Permutationsmatrix P.
Man begr ndet sie mit der Assoziatitvit t der Matrixmultiplikation f r
http://www.hs-augsburg.de/~mueckenh/Mathematerial/M11.PPT#362,55,Folie
55
K nntest du das Gew nschte bitte am Beispiel der Matrix
(1 0 1 0)
A = (5 0 0 0)
(7 2 0 9)
(8 1 0 2)
Du vertauschst zuerst Zeilen 1 und 2. Dann, in der resultierenden
Matrix also, Zeilen 2 und 3. Die benötigten Elementarmatrizen
entstehen aus der Einheitsmatrix

I =
1000
0100
0010
0001

durch eben dieselben Vertauschungen:

E1=
0100
1000
0010
0001

E2=
1000
0010
0100
0001

E2*E1*A = P*A besitzt die gewünschte Diagonalform.
Andere Lösungen sind möglich.


Gruß. WM
Carsten Schultz
2010-11-20 10:53:01 UTC
Permalink
Post by WM
In der Regel gen gt aber keine einzelne Matrix, um die
gew nschte Permutation zu erzielen, sondern man ben tigt ein Produkt
von mehreren Matrizen.
F r eine Permutation (und genau darum ging es; *nicht* um Multiplikation
einer Zeile mit einer Zahl oder Addition verschiedener Zeilen) gen gt
AFAIK eigentlich schon eine einzelne Matrix, welche passenderweise
'Permutationsmatrix' genannt wird. Sie zeichnet sich dadurch aus, da in
jeder Zeile und Spalte dieser Matrix genau eine 1 vorkommt; ansonsten
nur 0-en.
Selbstverständlich ist die gesuchte Matrix ein Produkt von
Elementarmatrizen. Als ich Obiges schrieb, bezog ich mich auf
Elementarmatrizen. Ein verständiger Leser hätte das erkannt.
Du bist derjenige, der in diesem Thread nur Dinge schreibt, die nichts
zu der Frage beitragen und allen anderen schon klar sind. Trotzdem
behandelst Du andere von oben herab. Deine Unfähigkeit ist nur traurig,
Dein Benehmen aber ist widerlich. Dass Du nicht in der Lage zu sein
scheinst, dieses zu ändern, entwertet auch Deine vor kurzem gegebene
Entschuldigung.

Gruß

Carsten
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
WM
2010-11-20 11:33:35 UTC
Permalink
Post by Carsten Schultz
Post by WM
In der Regel gen gt aber keine einzelne Matrix, um die
gew nschte Permutation zu erzielen, sondern man ben tigt ein Produkt
von mehreren Matrizen.
F r eine Permutation (und genau darum ging es; *nicht* um Multiplikation
einer Zeile mit einer Zahl oder Addition verschiedener Zeilen) gen gt
AFAIK eigentlich schon eine einzelne Matrix, welche passenderweise
'Permutationsmatrix' genannt wird. Sie zeichnet sich dadurch aus, da in
jeder Zeile und Spalte dieser Matrix genau eine 1 vorkommt; ansonsten
nur 0-en.
Selbstverständlich ist die gesuchte Matrix ein Produkt von
Elementarmatrizen. Als ich Obiges schrieb, bezog ich mich auf
Elementarmatrizen. Ein verständiger Leser hätte das erkannt.
Du bist derjenige, der in diesem Thread nur Dinge schreibt, die nichts
zu der Frage beitragen und allen anderen schon klar sind.
Stephan Gerlach schien dies aber nicht klar zu sein.
Post by Carsten Schultz
 Trotzdem
behandelst Du andere von oben herab.
Als er an anderer Stelle Dir beistimmte:

CS: Du hast keinen solchen Beweis geliefert. Macht aber nichts, es
erwartet von Dir ja auch niemand Mathematik.

SG: Interessant in dem Zusammenhang ist, daß dies anscheinend auch in
Fällen auftreten kann, wo es nicht um das WM-Thema Nummer 1 "unendlich
gibt's sowieso nicht" geht.

da hattet Ihr offenbar beide nicht verstanden, wie der konstruktive
Beweis funktioniert.
Post by Carsten Schultz
 Deine Unfähigkeit ist nur traurig,
Möchtest Du Deine falsche Beschuldigung durch Löschung meiner
korrekten Konstruktion "beweisen"?

Gruß, WM
Carsten Schultz
2010-11-20 12:00:16 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by WM
In der Regel gen gt aber keine einzelne Matrix, um die
gew nschte Permutation zu erzielen, sondern man ben tigt ein Produkt
von mehreren Matrizen.
F r eine Permutation (und genau darum ging es; *nicht* um Multiplikation
einer Zeile mit einer Zahl oder Addition verschiedener Zeilen) gen gt
AFAIK eigentlich schon eine einzelne Matrix, welche passenderweise
'Permutationsmatrix' genannt wird. Sie zeichnet sich dadurch aus, da in
jeder Zeile und Spalte dieser Matrix genau eine 1 vorkommt; ansonsten
nur 0-en.
Selbstverständlich ist die gesuchte Matrix ein Produkt von
Elementarmatrizen. Als ich Obiges schrieb, bezog ich mich auf
Elementarmatrizen. Ein verständiger Leser hätte das erkannt.
Du bist derjenige, der in diesem Thread nur Dinge schreibt, die nichts
zu der Frage beitragen und allen anderen schon klar sind.
Stephan Gerlach schien dies aber nicht klar zu sein.
Post by Carsten Schultz
Trotzdem
behandelst Du andere von oben herab.
CS: Du hast keinen solchen Beweis geliefert. Macht aber nichts, es
erwartet von Dir ja auch niemand Mathematik.
SG: Interessant in dem Zusammenhang ist, daß dies anscheinend auch in
Fällen auftreten kann, wo es nicht um das WM-Thema Nummer 1 "unendlich
gibt's sowieso nicht" geht.
da hattet Ihr offenbar beide nicht verstanden, wie der konstruktive
Beweis funktioniert.
Post by Carsten Schultz
Deine Unfähigkeit ist nur traurig,
Möchtest Du Deine falsche Beschuldigung durch Löschung meiner
korrekten Konstruktion "beweisen"?
Vielleicht solltest erst einmal versuchen, zu verstehen, was bewiesen
werden sollte.
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
Jutta Gut
2010-11-13 16:44:26 UTC
Permalink
Post by Stephan Gerlach
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*, so
wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu stünde,
daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine Permutation
dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Vielleicht sitze ich auf der Leitung, aber ich sehe nicht, wieso det(A) = 0
sein soll, Eine 0 in der Hauptdiagonalen bedeutet doch nicht, dass die ganze
Determinante 0 ist. Siehe z.B. die Matrix
(1 2 3)
(1 1 1)
(1 1 0)
mig der Determinante 1.

Grüße
Jutta
Carsten Schultz
2010-11-13 16:57:19 UTC
Permalink
Post by Jutta Gut
Post by Stephan Gerlach
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen
der Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale
*hätte*, so wäre nach obiger Formel det(A) = 0, was aber im
Widerspruch dazu stünde, daß A regulär vorausgesetzt wurde. Also muß
(mindestens) eine Permutation dabei sein, wo keine 0 auf der
Hauptdiagonalen steht.
Vielleicht sitze ich auf der Leitung, aber ich sehe nicht, wieso det(A)
= 0 sein soll, Eine 0 in der Hauptdiagonalen bedeutet doch nicht, dass
die ganze Determinante 0 ist. Siehe z.B. die Matrix
(1 2 3)
(1 1 1)
(1 1 0)
mig der Determinante 1.
Ich glaube, Du hast das oben hervorgehobene ‚jede‘ übersehen. Jeder
Summand in der obigen Formel ist das Produkt der Einträge auf der
Diagonalen einer Matrix, die durch eine Zeilenpermutation aus der
ursprünglich hervor geht.

Gruß

Carsten
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
Jutta Gut
2010-11-13 18:42:57 UTC
Permalink
Post by Carsten Schultz
Post by Jutta Gut
Vielleicht sitze ich auf der Leitung, aber ich sehe nicht, wieso det(A)
= 0 sein soll, Eine 0 in der Hauptdiagonalen bedeutet doch nicht, dass
die ganze Determinante 0 ist. Siehe z.B. die Matrix
(1 2 3)
(1 1 1)
(1 1 0)
mit der Determinante 1.
Ich glaube, Du hast das oben hervorgehobene ‚jede‘ übersehen. Jeder
Summand in der obigen Formel ist das Produkt der Einträge auf der
Diagonalen einer Matrix, die durch eine Zeilenpermutation aus der
ursprünglich hervor geht.
Ich habe es zwar nicht übersehen, aber dieser Gedankenschritt hat mir
gefehlt.

Danke
Jutta
Stephan Gerlach
2010-11-17 00:36:20 UTC
Permalink
Post by Jutta Gut
Post by Stephan Gerlach
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen
der Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale
*hätte*, so wäre nach obiger Formel det(A) = 0, was aber im
Widerspruch dazu stünde, daß A regulär vorausgesetzt wurde. Also muß
(mindestens) eine Permutation dabei sein, wo keine 0 auf der
Hauptdiagonalen steht.
Vielleicht sitze ich auf der Leitung, aber ich sehe nicht, wieso det(A)
= 0 sein soll, Eine 0 in der Hauptdiagonalen bedeutet doch nicht, dass
die ganze Determinante 0 ist. Siehe z.B. die Matrix
(1 2 3)
(1 1 1)
(1 1 0)
mig der Determinante 1.
Es gibt aber eine (Zeilen-)Permutation dieser Matrix, wo auf der
Hauptdiagonalen *keine* 0 mehr steht:
(1 2 3)
(1 1 0)
(1 1 1)
D.h. *nicht* *jede* Permutation der Zeilen deiner ursprünglichen Matrix
hat nur 0-en auf der Hauptdiagonale. Somit ist die Voraussetzung
"...Falls *jede* Permutation der Zeilen der Matrix A [...] eine 0 in der
Hauptdiagonale *hätte*..."
ohnehin nicht erfüllt :-) .

Ansonsten hat Carsten das Wesentliche dazu geschrieben.
--
Post by Jutta Gut
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Carsten Schultz
2010-11-13 17:08:07 UTC
Permalink
Post by Stephan Gerlach
Post by WM
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?
"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir fällt zwar was ein, aber das geht über Determinanten und ist IMHO zu
umständlich.
Es geht über das Produkt geeigneter Elementarmatrizen.
... welche hier Permutationsmatrizen sein sollten. Sogar eine einzige
solche Matrix P genügt hier, wie ich auch selber schrieb. Daß man die
gewünschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, weiß ich selber. Die Frage war aber, wie
begründet man die Existenz dieser "passenden" Permutationsmatrix P.
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
Ersetzt Du in diesem Argument die obige Formel durch den
Entwicklungssatz, so erhältst Du zumindest ein polynomielles Verfahren,
um die Permutation zu finden: Suche in der ersten Spalte eine
Nicht-Null, so dass nach Streichen der entsprechenden Zeile und der
ersten Spalte eine invertierbare Matrix übrig bleibt. Setze rekursiv fort.

Gruß

Carsten
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
Stephan Gerlach
2010-11-20 00:38:41 UTC
Permalink
[...]
Post by Carsten Schultz
Post by Stephan Gerlach
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
Ersetzt Du in diesem Argument die obige Formel durch den
Entwicklungssatz, so erhältst Du zumindest ein polynomielles Verfahren,
um die Permutation zu finden: Suche in der ersten Spalte eine
Nicht-Null, so dass nach Streichen der entsprechenden Zeile und der
ersten Spalte eine invertierbare Matrix übrig bleibt. Setze rekursiv fort.
Man muß aber schon nach einer "passenden" Nicht-Null in der ersten
Spalte suchen, nicht die "erstbeste" Nicht-Null funktioniert
zwangsläufig (so war es vermutlich auch gemeint).
Wobei dies BTW vermutlich sogar den gewünschten Induktionsbeweis liefern
sollte, wie von Marc Olschok bereits versucht. Naja, ganz ohne
Determinante kommt das auch nicht aus...
--
Post by Carsten Schultz
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
WM
2010-11-20 13:05:46 UTC
Permalink
Post by Stephan Gerlach
[...]
Post by Carsten Schultz
Post by Stephan Gerlach
Ich hätte als Idee, folgende Darstellung der Determinante
det(A)  =  Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
                            sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
Ersetzt Du in diesem Argument die obige Formel durch den
Entwicklungssatz, so erhältst Du zumindest ein polynomielles Verfahren,
um die Permutation zu finden:  Suche in der ersten Spalte eine
Nicht-Null, so dass nach Streichen der entsprechenden Zeile und der
ersten Spalte eine invertierbare Matrix übrig bleibt.  Setze rekursiv fort.
Man muß aber schon nach einer "passenden" Nicht-Null in der ersten
Spalte suchen, nicht die "erstbeste" Nicht-Null funktioniert
zwangsläufig (so war es vermutlich auch gemeint).
Wobei dies BTW vermutlich sogar den gewünschten Induktionsbeweis liefern
sollte, wie von Marc Olschok bereits versucht. Naja, ganz ohne
Determinante kommt das auch nicht aus...
Doch! Es genügt die lineare Unabhängigkeit. Sei eine NxN-Matrix
gegeben.
Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen, dann müssen alle
Elemente der restlichen N-n Zeilen auf N-(n+1) Spalten verteilt sein.
Damit ist mindestens eine der restlichen N-n Zeilen nicht linear
unabhängig.

Gruß, WM
Carsten Schultz
2010-11-20 14:21:14 UTC
Permalink
Post by WM
Post by Stephan Gerlach
[...]
Post by Carsten Schultz
Post by Stephan Gerlach
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
Ersetzt Du in diesem Argument die obige Formel durch den
Entwicklungssatz, so erhältst Du zumindest ein polynomielles Verfahren,
um die Permutation zu finden: Suche in der ersten Spalte eine
Nicht-Null, so dass nach Streichen der entsprechenden Zeile und der
ersten Spalte eine invertierbare Matrix übrig bleibt. Setze rekursiv fort.
Man muß aber schon nach einer "passenden" Nicht-Null in der ersten
Spalte suchen, nicht die "erstbeste" Nicht-Null funktioniert
zwangsläufig (so war es vermutlich auch gemeint).
Wobei dies BTW vermutlich sogar den gewünschten Induktionsbeweis liefern
sollte, wie von Marc Olschok bereits versucht. Naja, ganz ohne
Determinante kommt das auch nicht aus...
Doch! Es genügt die lineare Unabhängigkeit. Sei eine NxN-Matrix
gegeben.
Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen, dann müssen alle
Elemente der restlichen N-n Zeilen auf N-(n+1) Spalten verteilt sein.
Damit ist mindestens eine der restlichen N-n Zeilen nicht linear
unabhängig.
Das ist zwar schwer verständlich und unvollständig, führt aber zu dem
Gedanken, dass die Behauptung aus dem Heiratssatz folgt.

Aus dem Heiratssatz ergibt sich nämlich, dass aus der Nichtexistenz
einer Permutation der gesuchten Art folgen würde, dass es eine Menge von
Zeilen gibt, so dass die Anzahl der Spalten, in denen eine dieser Zeilen
einen Eintrag ungleich Null hat, kleiner als die Anzahl dieser Zeilen
ist. Diese Zeilen müssen dann in der Tat linear abhängig sein.

Konstruktiver ist es dadurch allerdings auch nicht geworden.

Gruß

Carsten
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
WM
2010-11-21 08:26:10 UTC
Permalink
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
[...]
Post by Carsten Schultz
Post by Stephan Gerlach
Ich hätte als Idee, folgende Darstellung der Determinante
det(A)  =  Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
                            sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
Ersetzt Du in diesem Argument die obige Formel durch den
Entwicklungssatz, so erhältst Du zumindest ein polynomielles Verfahren,
um die Permutation zu finden:  Suche in der ersten Spalte eine
Nicht-Null, so dass nach Streichen der entsprechenden Zeile und der
ersten Spalte eine invertierbare Matrix übrig bleibt.  Setze rekursiv fort.
Man muß aber schon nach einer "passenden" Nicht-Null in der ersten
Spalte suchen, nicht die "erstbeste" Nicht-Null funktioniert
zwangsläufig (so war es vermutlich auch gemeint).
Wobei dies BTW vermutlich sogar den gewünschten Induktionsbeweis liefern
sollte, wie von Marc Olschok bereits versucht. Naja, ganz ohne
Determinante kommt das auch nicht aus...
Doch! Es genügt die lineare Unabhängigkeit. Sei eine NxN-Matrix
gegeben.
Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen, dann müssen alle
Elemente der restlichen N-n Zeilen auf N-(n+1) Spalten verteilt sein.
Damit ist mindestens eine der restlichen N-n Zeilen nicht linear
unabhängig.
Das ist zwar schwer verständlich und unvollständig, führt aber zu dem
Gedanken, dass die Behauptung aus dem Heiratssatz folgt.
Aus dem Heiratssatz ergibt sich nämlich, dass aus der Nichtexistenz
einer Permutation der gesuchten Art folgen würde, dass es eine Menge von
Zeilen gibt, so dass die Anzahl der Spalten, in denen eine dieser Zeilen
einen Eintrag ungleich Null hat, kleiner als die Anzahl dieser Zeilen
ist.  Diese Zeilen müssen dann in der Tat linear abhängig sein.
Konstruktiver ist es dadurch allerdings auch nicht geworden.
Lieber Carsten,

meine obige Schilderung sollte kein Beweis sein, sondern eine Skizze,
die zeigt, weshalb meine ursprüngliche Antwort an Stephan

Es geht über das Produkt geeigneter Elementarmatrizen.
http://www.oldenbourg-verlag.de/wissenschaftsverlag/mathematik-ersten...
p. 92ff

die Du leider nicht verstanden hast oder nicht verstehen wolltest,
einen konstruktiven Beweis beinhaltet. Das, was ich skizziert habe,
ist die Voraussetzung für meinen Ansatz, die äquivalent mit der
Forderung der Umkehrbarkeit ist.

Solche Skizzen werden in der Regel auch von Studenten verstanden, die
noch nicht in die Materie eingedrungen sind. Allerdings vermittele ich
sie in der Vorlesung für Nichtmathematiker meistens nicht mit n und
Pünktchen, sondern ganz konkret, z. B. in der Form:

123
004
00x

und frage dann, ob die Zeilen linear unabhängig sein können. Ich
finde, dass dies die didaktisch erfolgreichste Methode der
Wissensvermittlung ist.

Gruß, WM
Carsten Schultz
2010-11-21 14:47:41 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
[...]
Post by Carsten Schultz
Post by Stephan Gerlach
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
Ersetzt Du in diesem Argument die obige Formel durch den
Entwicklungssatz, so erhältst Du zumindest ein polynomielles Verfahren,
um die Permutation zu finden: Suche in der ersten Spalte eine
Nicht-Null, so dass nach Streichen der entsprechenden Zeile und der
ersten Spalte eine invertierbare Matrix übrig bleibt. Setze rekursiv fort.
Man muß aber schon nach einer "passenden" Nicht-Null in der ersten
Spalte suchen, nicht die "erstbeste" Nicht-Null funktioniert
zwangsläufig (so war es vermutlich auch gemeint).
Wobei dies BTW vermutlich sogar den gewünschten Induktionsbeweis liefern
sollte, wie von Marc Olschok bereits versucht. Naja, ganz ohne
Determinante kommt das auch nicht aus...
Doch! Es genügt die lineare Unabhängigkeit. Sei eine NxN-Matrix
gegeben.
Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen, dann müssen alle
Elemente der restlichen N-n Zeilen auf N-(n+1) Spalten verteilt sein.
Damit ist mindestens eine der restlichen N-n Zeilen nicht linear
unabhängig.
Das ist zwar schwer verständlich und unvollständig, führt aber zu dem
Gedanken, dass die Behauptung aus dem Heiratssatz folgt.
Aus dem Heiratssatz ergibt sich nämlich, dass aus der Nichtexistenz
einer Permutation der gesuchten Art folgen würde, dass es eine Menge von
Zeilen gibt, so dass die Anzahl der Spalten, in denen eine dieser Zeilen
einen Eintrag ungleich Null hat, kleiner als die Anzahl dieser Zeilen
ist. Diese Zeilen müssen dann in der Tat linear abhängig sein.
Konstruktiver ist es dadurch allerdings auch nicht geworden.
Lieber Carsten,
meine obige Schilderung sollte kein Beweis sein, sondern eine Skizze,
die zeigt, weshalb meine ursprüngliche Antwort an Stephan
Es geht über das Produkt geeigneter Elementarmatrizen.
http://www.oldenbourg-verlag.de/wissenschaftsverlag/mathematik-ersten...
p. 92ff
die Du leider nicht verstanden hast oder nicht verstehen wolltest,
einen konstruktiven Beweis beinhaltet.
Es ist wohl eher so, dass Du noch immer nicht begriffen hast, dass
nichts von dem, was Du hier geschrieben hast, einen wesentlichen
Gedanken für einen Beweis beisteuert. Bewiesen hast Du höchstens Dinge,
die ohnehin allen anderen hier klar sind. Ich habe aber auch kein
Interesse daran, Dir zu erklären, warum das, was Du schreibst, das
Problem nicht löst.

Gruß

Carsten
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
WM
2010-11-21 15:16:47 UTC
Permalink
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
[...]
Post by Carsten Schultz
Post by Stephan Gerlach
Ich hätte als Idee, folgende Darstellung der Determinante
det(A)  =  Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
                            sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
Ersetzt Du in diesem Argument die obige Formel durch den
Entwicklungssatz, so erhältst Du zumindest ein polynomielles Verfahren,
um die Permutation zu finden:  Suche in der ersten Spalte eine
Nicht-Null, so dass nach Streichen der entsprechenden Zeile und der
ersten Spalte eine invertierbare Matrix übrig bleibt.  Setze rekursiv fort.
Man muß aber schon nach einer "passenden" Nicht-Null in der ersten
Spalte suchen, nicht die "erstbeste" Nicht-Null funktioniert
zwangsläufig (so war es vermutlich auch gemeint).
Wobei dies BTW vermutlich sogar den gewünschten Induktionsbeweis liefern
sollte, wie von Marc Olschok bereits versucht. Naja, ganz ohne
Determinante kommt das auch nicht aus...
Doch! Es genügt die lineare Unabhängigkeit. Sei eine NxN-Matrix
gegeben.
Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen, dann müssen alle
Elemente der restlichen N-n Zeilen auf N-(n+1) Spalten verteilt sein.
Damit ist mindestens eine der restlichen N-n Zeilen nicht linear
unabhängig.
Das ist zwar schwer verständlich und unvollständig, führt aber zu dem
Gedanken, dass die Behauptung aus dem Heiratssatz folgt.
Aus dem Heiratssatz ergibt sich nämlich, dass aus der Nichtexistenz
einer Permutation der gesuchten Art folgen würde, dass es eine Menge von
Zeilen gibt, so dass die Anzahl der Spalten, in denen eine dieser Zeilen
einen Eintrag ungleich Null hat, kleiner als die Anzahl dieser Zeilen
ist.  Diese Zeilen müssen dann in der Tat linear abhängig sein.
Konstruktiver ist es dadurch allerdings auch nicht geworden.
Lieber Carsten,
meine obige Schilderung sollte kein Beweis sein, sondern eine Skizze,
die zeigt, weshalb meine ursprüngliche Antwort an Stephan
Es geht über das Produkt geeigneter Elementarmatrizen.
http://www.oldenbourg-verlag.de/wissenschaftsverlag/mathematik-ersten...
p. 92ff
die Du leider nicht verstanden hast oder nicht verstehen wolltest,
einen konstruktiven Beweis beinhaltet.
Es ist wohl eher so, dass Du noch immer nicht begriffen hast, dass
nichts von dem, was Du hier geschrieben hast, einen wesentlichen
Gedanken für einen Beweis beisteuert.  Bewiesen hast Du höchstens Dinge,
die ohnehin allen anderen hier klar sind.  Ich habe aber auch kein
Interesse daran, Dir zu erklären, warum das, was Du schreibst, das
Problem nicht löst.
Du sagtest: Das ist zwar schwer verständlich und unvollständig, führt
aber zu dem Gedanken, dass die Behauptung aus dem Heiratssatz folgt.

Nein, da braucht es keinen Heiratssatz. Das ist ein Skizze, die jedem
Mathematiker, der den Fedanken der linearen Unabhängigkeit kennt,
wenn er schon nicht von selbst drauf gekommen ist, sofort einleuchtet.
Meine Lösung ist ein konstruktiver Beweis. Ich wollte das in meinem
letzten Beitrag nicht so unhöflich formulieren, aber da Du es offenbar
anders nicht merkst ...

Na so vermutlich auch nicht.

EOD

Gruß, WM
Carsten Schultz
2010-11-21 15:34:42 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
[...]
Post by Carsten Schultz
Post by Stephan Gerlach
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
Ersetzt Du in diesem Argument die obige Formel durch den
Entwicklungssatz, so erhältst Du zumindest ein polynomielles Verfahren,
um die Permutation zu finden: Suche in der ersten Spalte eine
Nicht-Null, so dass nach Streichen der entsprechenden Zeile und der
ersten Spalte eine invertierbare Matrix übrig bleibt. Setze rekursiv fort.
Man muß aber schon nach einer "passenden" Nicht-Null in der ersten
Spalte suchen, nicht die "erstbeste" Nicht-Null funktioniert
zwangsläufig (so war es vermutlich auch gemeint).
Wobei dies BTW vermutlich sogar den gewünschten Induktionsbeweis liefern
sollte, wie von Marc Olschok bereits versucht. Naja, ganz ohne
Determinante kommt das auch nicht aus...
Doch! Es genügt die lineare Unabhängigkeit. Sei eine NxN-Matrix
gegeben.
Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen, dann müssen alle
Elemente der restlichen N-n Zeilen auf N-(n+1) Spalten verteilt sein.
Damit ist mindestens eine der restlichen N-n Zeilen nicht linear
unabhängig.
Das ist zwar schwer verständlich und unvollständig, führt aber zu dem
Gedanken, dass die Behauptung aus dem Heiratssatz folgt.
Aus dem Heiratssatz ergibt sich nämlich, dass aus der Nichtexistenz
einer Permutation der gesuchten Art folgen würde, dass es eine Menge von
Zeilen gibt, so dass die Anzahl der Spalten, in denen eine dieser Zeilen
einen Eintrag ungleich Null hat, kleiner als die Anzahl dieser Zeilen
ist. Diese Zeilen müssen dann in der Tat linear abhängig sein.
Konstruktiver ist es dadurch allerdings auch nicht geworden.
Lieber Carsten,
meine obige Schilderung sollte kein Beweis sein, sondern eine Skizze,
die zeigt, weshalb meine ursprüngliche Antwort an Stephan
Es geht über das Produkt geeigneter Elementarmatrizen.
http://www.oldenbourg-verlag.de/wissenschaftsverlag/mathematik-ersten...
p. 92ff
die Du leider nicht verstanden hast oder nicht verstehen wolltest,
einen konstruktiven Beweis beinhaltet.
Es ist wohl eher so, dass Du noch immer nicht begriffen hast, dass
nichts von dem, was Du hier geschrieben hast, einen wesentlichen
Gedanken für einen Beweis beisteuert. Bewiesen hast Du höchstens Dinge,
die ohnehin allen anderen hier klar sind. Ich habe aber auch kein
Interesse daran, Dir zu erklären, warum das, was Du schreibst, das
Problem nicht löst.
Du sagtest: Das ist zwar schwer verständlich und unvollständig, führt
aber zu dem Gedanken, dass die Behauptung aus dem Heiratssatz folgt.
Nein, da braucht es keinen Heiratssatz. Das ist ein Skizze, die jedem
Mathematiker, der den Fedanken der linearen Unabhängigkeit kennt,
wenn er schon nicht von selbst drauf gekommen ist, sofort einleuchtet.
Meine Lösung ist ein konstruktiver Beweis.
Dann formuliere Deine Argumentation doch einfach noch einmal
verständlich. Ich glaube, hier konnte bisher niemand in dem, was Du
geschrieben hast, etwas entdecken, das das Problem löst. Sind wir alle
so schwer von Begriff?


Ich wollte das in meinem
Post by WM
letzten Beitrag nicht so unhöflich formulieren, aber da Du es offenbar
anders nicht merkst ...
Na so vermutlich auch nicht.
EOD
Gruß, WM
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
Ralf Bader
2010-11-23 04:48:28 UTC
Permalink
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
[...]
Post by Carsten Schultz
Post by Stephan Gerlach
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] *
a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der
Zeilen der Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der
Hauptdiagonale *hätte*, so wäre nach obiger Formel det(A) = 0, was
aber im Widerspruch dazu stünde, daß A regulär vorausgesetzt
wurde. Also muß (mindestens) eine Permutation dabei sein, wo keine
0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser)
nicht konstruktiv. Ich vermute, daß es auch eine Begründung gibt,
die ohne Determinante auskommt.
Ersetzt Du in diesem Argument die obige Formel durch den
Entwicklungssatz, so erhältst Du zumindest ein polynomielles Verfahren,
um die Permutation zu finden: Suche in der ersten Spalte eine
Nicht-Null, so dass nach Streichen der entsprechenden Zeile und der
ersten Spalte eine invertierbare Matrix übrig bleibt. Setze rekursiv fort.
Man muß aber schon nach einer "passenden" Nicht-Null in der ersten
Spalte suchen, nicht die "erstbeste" Nicht-Null funktioniert
zwangsläufig (so war es vermutlich auch gemeint).
Wobei dies BTW vermutlich sogar den gewünschten Induktionsbeweis
liefern sollte, wie von Marc Olschok bereits versucht. Naja, ganz
ohne Determinante kommt das auch nicht aus...
Doch! Es genügt die lineare Unabhängigkeit. Sei eine NxN-Matrix
gegeben.
Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen, dann müssen alle
Elemente der restlichen N-n Zeilen auf N-(n+1) Spalten verteilt sein.
Damit ist mindestens eine der restlichen N-n Zeilen nicht linear
unabhängig.
Das ist zwar schwer verständlich und unvollständig, führt aber zu dem
Gedanken, dass die Behauptung aus dem Heiratssatz folgt.
Aus dem Heiratssatz ergibt sich nämlich, dass aus der Nichtexistenz
einer Permutation der gesuchten Art folgen würde, dass es eine Menge
von Zeilen gibt, so dass die Anzahl der Spalten, in denen eine dieser
Zeilen einen Eintrag ungleich Null hat, kleiner als die Anzahl dieser
Zeilen
ist. Diese Zeilen müssen dann in der Tat linear abhängig sein.
Konstruktiver ist es dadurch allerdings auch nicht geworden.
Lieber Carsten,
meine obige Schilderung sollte kein Beweis sein, sondern eine Skizze,
die zeigt, weshalb meine ursprüngliche Antwort an Stephan
Es geht über das Produkt geeigneter Elementarmatrizen.
http://www.oldenbourg-verlag.de/wissenschaftsverlag/mathematik-
ersten...
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by WM
p. 92ff
die Du leider nicht verstanden hast oder nicht verstehen wolltest,
einen konstruktiven Beweis beinhaltet.
Es ist wohl eher so, dass Du noch immer nicht begriffen hast, dass
nichts von dem, was Du hier geschrieben hast, einen wesentlichen
Gedanken für einen Beweis beisteuert. Bewiesen hast Du höchstens Dinge,
die ohnehin allen anderen hier klar sind. Ich habe aber auch kein
Interesse daran, Dir zu erklären, warum das, was Du schreibst, das
Problem nicht löst.
Du sagtest: Das ist zwar schwer verständlich und unvollständig, führt
aber zu dem Gedanken, dass die Behauptung aus dem Heiratssatz folgt.
Nein, da braucht es keinen Heiratssatz. Das ist ein Skizze, die jedem
Mathematiker, der den Fedanken der linearen Unabhängigkeit kennt,
wenn er schon nicht von selbst drauf gekommen ist, sofort einleuchtet.
Meine Lösung ist ein konstruktiver Beweis.
Dann formuliere Deine Argumentation doch einfach noch einmal
verständlich. Ich glaube, hier konnte bisher niemand in dem, was Du
geschrieben hast, etwas entdecken, das das Problem löst. Sind wir alle
so schwer von Begriff?
Ich wollte das in meinem
Post by WM
letzten Beitrag nicht so unhöflich formulieren, aber da Du es offenbar
anders nicht merkst ...
Na so vermutlich auch nicht.
EOD
Gruß, WM
Mückenheim meint folgendes:
1. Es sei M eine invertierbare kxk-Matrix. Aus M soll durch
Zeilenvertauschungen eine Matrix N gebildet werden, in der alle
Diagonaleinträge !=0 sind.
2. Angenommen, es sei nicht möglich, durch Zeilenvertauschungen zu
erreichen, daß die ersten n+1 (<=k) Diagonaleinträge !=0 werden.
3. Dann gibt es in M höchstens n Zeilen, in denen unter den ersten n+1
Einträgen solche auftreten, die !=0 sind.
4.Die Einträge !=0 der restlichen
k-n Zeilen befinden sich sämtlich in k-n-1 Spalten, und das geht wg.
linearer Unabhängigkeit nicht.

Worauf der Schluß 2 beruht ist mir unklar, und dem Schreiber, der ihn in der
Formulierung
"Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen,"
versteckt, ist womöglich nicht einmal klar, daß da eine nicht ganz
offensichtliche Behauptung enthalten ist. Daß der Schreiber auf der banalen
Folgerung 4 deutlich intensiver herumreitet als auf dem problematischen
punkt 3 spricht auch nicht dafür, daß er sein Argument sonderlich durchdacht
hätte.


Ralf
Carsten Schultz
2010-11-23 15:34:22 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by WM
Post by Stephan Gerlach
[...]
Post by Carsten Schultz
Post by Stephan Gerlach
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] *
a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der
Zeilen der Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der
Hauptdiagonale *hätte*, so wäre nach obiger Formel det(A) = 0, was
aber im Widerspruch dazu stünde, daß A regulär vorausgesetzt
wurde. Also muß (mindestens) eine Permutation dabei sein, wo keine
0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser)
nicht konstruktiv. Ich vermute, daß es auch eine Begründung gibt,
die ohne Determinante auskommt.
Ersetzt Du in diesem Argument die obige Formel durch den
Entwicklungssatz, so erhältst Du zumindest ein polynomielles Verfahren,
um die Permutation zu finden: Suche in der ersten Spalte eine
Nicht-Null, so dass nach Streichen der entsprechenden Zeile und der
ersten Spalte eine invertierbare Matrix übrig bleibt. Setze
rekursiv fort.
Man muß aber schon nach einer "passenden" Nicht-Null in der ersten
Spalte suchen, nicht die "erstbeste" Nicht-Null funktioniert
zwangsläufig (so war es vermutlich auch gemeint).
Wobei dies BTW vermutlich sogar den gewünschten Induktionsbeweis
liefern sollte, wie von Marc Olschok bereits versucht. Naja, ganz
ohne Determinante kommt das auch nicht aus...
Doch! Es genügt die lineare Unabhängigkeit. Sei eine NxN-Matrix
gegeben.
Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen, dann müssen alle
Elemente der restlichen N-n Zeilen auf N-(n+1) Spalten verteilt sein.
Damit ist mindestens eine der restlichen N-n Zeilen nicht linear
unabhängig.
Das ist zwar schwer verständlich und unvollständig, führt aber zu dem
Gedanken, dass die Behauptung aus dem Heiratssatz folgt.
Aus dem Heiratssatz ergibt sich nämlich, dass aus der Nichtexistenz
einer Permutation der gesuchten Art folgen würde, dass es eine Menge
von Zeilen gibt, so dass die Anzahl der Spalten, in denen eine dieser
Zeilen einen Eintrag ungleich Null hat, kleiner als die Anzahl dieser
Zeilen
ist. Diese Zeilen müssen dann in der Tat linear abhängig sein.
Konstruktiver ist es dadurch allerdings auch nicht geworden.
Lieber Carsten,
meine obige Schilderung sollte kein Beweis sein, sondern eine Skizze,
die zeigt, weshalb meine ursprüngliche Antwort an Stephan
Es geht über das Produkt geeigneter Elementarmatrizen.
http://www.oldenbourg-verlag.de/wissenschaftsverlag/mathematik-
ersten...
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by WM
p. 92ff
die Du leider nicht verstanden hast oder nicht verstehen wolltest,
einen konstruktiven Beweis beinhaltet.
Es ist wohl eher so, dass Du noch immer nicht begriffen hast, dass
nichts von dem, was Du hier geschrieben hast, einen wesentlichen
Gedanken für einen Beweis beisteuert. Bewiesen hast Du höchstens Dinge,
die ohnehin allen anderen hier klar sind. Ich habe aber auch kein
Interesse daran, Dir zu erklären, warum das, was Du schreibst, das
Problem nicht löst.
Du sagtest: Das ist zwar schwer verständlich und unvollständig, führt
aber zu dem Gedanken, dass die Behauptung aus dem Heiratssatz folgt.
Nein, da braucht es keinen Heiratssatz. Das ist ein Skizze, die jedem
Mathematiker, der den Fedanken der linearen Unabhängigkeit kennt,
wenn er schon nicht von selbst drauf gekommen ist, sofort einleuchtet.
Meine Lösung ist ein konstruktiver Beweis.
Dann formuliere Deine Argumentation doch einfach noch einmal
verständlich. Ich glaube, hier konnte bisher niemand in dem, was Du
geschrieben hast, etwas entdecken, das das Problem löst. Sind wir alle
so schwer von Begriff?
Ich wollte das in meinem
Post by WM
letzten Beitrag nicht so unhöflich formulieren, aber da Du es offenbar
anders nicht merkst ...
Na so vermutlich auch nicht.
EOD
Gruß, WM
1. Es sei M eine invertierbare kxk-Matrix. Aus M soll durch
Zeilenvertauschungen eine Matrix N gebildet werden, in der alle
Diagonaleinträge !=0 sind.
2. Angenommen, es sei nicht möglich, durch Zeilenvertauschungen zu
erreichen, daß die ersten n+1 (<=k) Diagonaleinträge !=0 werden.
3. Dann gibt es in M höchstens n Zeilen, in denen unter den ersten n+1
Einträgen solche auftreten, die !=0 sind.
4.Die Einträge !=0 der restlichen
k-n Zeilen befinden sich sämtlich in k-n-1 Spalten, und das geht wg.
linearer Unabhängigkeit nicht.
Worauf der Schluß 2 beruht ist mir unklar, und dem Schreiber, der ihn in der
Formulierung
"Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen,"
versteckt, ist womöglich nicht einmal klar, daß da eine nicht ganz
offensichtliche Behauptung enthalten ist.
Zumal der Schluss von 2 auf 3 falsch ist, wenn man M nicht als
invertierbar voraussetzt. Aber Professor Mückenheim drückt sich ja
immer so ungenau aus, dass er nach langer Diskussion immer behaupten
kann, etwas anderes gemeint zu haben.
Post by WM
Daß der Schreiber auf der banalen
Folgerung 4 deutlich intensiver herumreitet als auf dem problematischen
punkt 3 spricht auch nicht dafür, daß er sein Argument sonderlich durchdacht
hätte.
Ganz genau. Und in seinen ersten Beiträgen hier schien er sogar nur den
Zusammenhang zwischen Zeilenvertauschungen und Permutationsmatrizen
erklären zu wollen, der ohnehin jedem klar. Und auch dabei waren wieder
Äußerungen, die wahrscheinlich nur ihre Unverständlichkeit davor bewahrt
hat, falsch zu sein.

Gruß

Carsten
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
WM
2010-11-23 17:30:09 UTC
Permalink
Post by Carsten Schultz
Post by Ralf Bader
1. Es sei M eine invertierbare kxk-Matrix. Aus M soll durch
Zeilenvertauschungen eine Matrix N gebildet werden, in der alle
Diagonaleinträge !=0 sind.
2. Angenommen, es sei nicht möglich, durch Zeilenvertauschungen zu
erreichen, daß die ersten n+1 (<=k) Diagonaleinträge !=0 werden.
3. Dann gibt es in M höchstens n Zeilen, in denen unter den ersten n+1
Einträgen solche auftreten, die !=0 sind.
4.Die Einträge !=0 der restlichen
k-n Zeilen befinden sich sämtlich in k-n-1 Spalten, und das geht wg.
linearer Unabhängigkeit nicht.
Worauf der Schluß 2 beruht ist mir unklar, und dem Schreiber, der ihn in der
Formulierung
"Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen,"
versteckt, ist womöglich nicht einmal klar, daß da eine nicht ganz
offensichtliche Behauptung enthalten ist.
Zumal der Schluss von 2 auf 3 falsch ist, wenn man M nicht als
invertierbar voraussetzt.
Er zeigt, dass M nicht invertierbar ist, wenn er zutrifft.
Post by Carsten Schultz
Post by Ralf Bader
Daß der Schreiber auf der banalen
Folgerung 4 deutlich intensiver herumreitet als auf dem problematischen
punkt 3 spricht auch nicht dafür, daß er sein Argument sonderlich durchdacht
hätte.
Ganz genau. Und in seinen ersten Beiträgen hier schien er sogar nur den
Zusammenhang zwischen Zeilenvertauschungen und Permutationsmatrizen
erklären zu wollen, der ohnehin jedem klar. Und auch dabei waren wieder
Äußerungen, die wahrscheinlich nur ihre Unverständlichkeit davor bewahrt
hat, falsch zu sein.
Also, gerade heute habe ich diesen Stoff in der Vorlesung erklärt. So
unbeholfen wie Du hier, hat sich aber niemand dort angestellt, obwohl
die Hörer keine Mathematiker waren.

Noch einmal von der Pike auf:

Sei eine NxN-Matrix gegegeben.

Wenn es nicht möglich ist, das n-te Diagonalelement =/= 0 zu erzeugen,
dann gibt es entweder überhaupt kein Elemente =/= 0 in der n-ten
Spalte, oder es wurden schon alle Elemente a_jn =/= 0 dieser Spalte in
den ersten n-1 Zeilen verwendet.

In diesem Falle, muss man eine dieser Zeilen zur n-ten machen und sie
durch eine andere mit entsprechendem Diagonalelement =/= 0 ersetzen.
Und eventuell solange fortfahren, bis das gewünschte Ergebnis erreicht
ist.

Dies geht nur dann nicht, wenn alle für die ersten n Zeilen in Frage
kommenden Diagonalelemente =/= 0 in weniger als n Zeilen enthalten
sind, z. B. in n -1 Zeilen.

Bsp:
1100
1010
0001
0001

Dann können aber die restlichen N-(n-1) Zeilen in keiner der ersten n
Spalten Elemente =/= 0 enthalten (denn sonst wären ja die für die
ersten n Zeilen in Frage kommenden Diagonalelemente =/= 0 nicht in
weniger als n Zeilen enthalten). Also können hier N-(n-1) = N - n + 1
Zeilen nur in N - n Spalten Elemente =/= 0 enthalten. Damit sind sie
nicht linear unabhängig.

Gruß, WM
JürgenR
2010-11-23 18:57:11 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by Ralf Bader
1. Es sei M eine invertierbare kxk-Matrix. Aus M soll durch
Zeilenvertauschungen eine Matrix N gebildet werden, in der alle
Diagonaleinträge !=0 sind.
2. Angenommen, es sei nicht möglich, durch Zeilenvertauschungen zu
erreichen, daß die ersten n+1 (<=k) Diagonaleinträge !=0 werden.
3. Dann gibt es in M höchstens n Zeilen, in denen unter den ersten n+1
Einträgen solche auftreten, die !=0 sind.
4.Die Einträge !=0 der restlichen
k-n Zeilen befinden sich sämtlich in k-n-1 Spalten, und das geht wg.
linearer Unabhängigkeit nicht.
Worauf der Schluß 2 beruht ist mir unklar, und dem Schreiber, der ihn in der
Formulierung
"Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen,"
versteckt, ist womöglich nicht einmal klar, daß da eine nicht ganz
offensichtliche Behauptung enthalten ist.
Zumal der Schluss von 2 auf 3 falsch ist, wenn man M nicht als
invertierbar voraussetzt.
Er zeigt, dass M nicht invertierbar ist, wenn er zutrifft.
Post by Carsten Schultz
Post by Ralf Bader
Daß der Schreiber auf der banalen
Folgerung 4 deutlich intensiver herumreitet als auf dem problematischen
punkt 3 spricht auch nicht dafür, daß er sein Argument sonderlich durchdacht
hätte.
Ganz genau. Und in seinen ersten Beiträgen hier schien er sogar nur den
Zusammenhang zwischen Zeilenvertauschungen und Permutationsmatrizen
erklären zu wollen, der ohnehin jedem klar. Und auch dabei waren wieder
Äußerungen, die wahrscheinlich nur ihre Unverständlichkeit davor bewahrt
hat, falsch zu sein.
Also, gerade heute habe ich diesen Stoff in der Vorlesung erklärt. So
unbeholfen wie Du hier, hat sich aber niemand dort angestellt, obwohl
die Hörer keine Mathematiker waren.
Sei eine NxN-Matrix gegegeben.
Wenn es nicht möglich ist, das n-te Diagonalelement =/= 0 zu erzeugen,
dann gibt es entweder überhaupt kein Elemente =/= 0 in der n-ten
Spalte, oder es wurden schon alle Elemente a_jn =/= 0 dieser Spalte in
den ersten n-1 Zeilen verwendet.
In diesem Falle, muss man eine dieser Zeilen zur n-ten machen und sie
durch eine andere mit entsprechendem Diagonalelement =/= 0 ersetzen.
Und eventuell solange fortfahren, bis das gewünschte Ergebnis erreicht
ist.
Dies geht nur dann nicht, wenn alle für die ersten n Zeilen in Frage
kommenden Diagonalelemente =/= 0 in weniger als n Zeilen enthalten
sind, z. B. in n -1 Zeilen.
1100
1010
0001
0001
Dann können aber die restlichen N-(n-1) Zeilen in keiner der ersten n
Spalten Elemente =/= 0 enthalten (denn sonst wären ja die für die
ersten n Zeilen in Frage kommenden Diagonalelemente =/= 0 nicht in
weniger als n Zeilen enthalten). Also können hier N-(n-1) = N - n + 1
Zeilen nur in N - n Spalten Elemente =/= 0 enthalten. Damit sind sie
nicht linear unabhängig.
Daraus folgt zwingend (falls ich den Schwurbelbeweisversuch richtig
verstanden habe), dass im Fall wo man N-1 Diagonalelemente =/= 0
erzeugen kann, aber nicht das N-te, die letzte Zeile nur Nullen
enthalten kann. Da werden die unbeholfensten Matheologen Ihnen
aber mühelos ein Gegenbeispiel liefern.
Vielleicht finden Sie den Fehler selber - dann können Sie sich morgen in
Ihrer Mathestunde entschuldigen.
Post by WM
Gruß, WM
WM
2010-11-23 20:05:57 UTC
Permalink
Post by JürgenR
Post by WM
Post by Carsten Schultz
Post by Ralf Bader
1. Es sei M eine invertierbare kxk-Matrix. Aus M soll durch
Zeilenvertauschungen eine Matrix N gebildet werden, in der alle
Diagonaleinträge !=0 sind.
2. Angenommen, es sei nicht möglich, durch Zeilenvertauschungen zu
erreichen, daß die ersten n+1 (<=k) Diagonaleinträge !=0 werden.
3. Dann gibt es in M höchstens n Zeilen, in denen unter den ersten n+1
Einträgen solche auftreten, die !=0 sind.
4.Die Einträge !=0 der restlichen
k-n Zeilen befinden sich sämtlich in k-n-1 Spalten, und das geht wg.
linearer Unabhängigkeit nicht.
Worauf der Schluß 2 beruht ist mir unklar, und dem Schreiber, der ihn in der
Formulierung
 "Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
 erzeugen, weil sie nur in n Zeilen vorkommen,"
versteckt, ist womöglich nicht einmal klar, daß da eine nicht ganz
offensichtliche Behauptung enthalten ist.
Zumal der Schluss von 2 auf 3 falsch ist, wenn man M nicht als
invertierbar voraussetzt.
Er zeigt, dass M nicht invertierbar ist, wenn er zutrifft.
Post by Carsten Schultz
Post by Ralf Bader
Daß der Schreiber auf der banalen
Folgerung 4 deutlich intensiver herumreitet als auf dem problematischen
punkt 3 spricht auch nicht dafür, daß er sein Argument sonderlich durchdacht
hätte.
Ganz genau.  Und in seinen ersten Beiträgen hier schien er sogar nur den
Zusammenhang zwischen Zeilenvertauschungen und Permutationsmatrizen
erklären zu wollen, der ohnehin jedem klar.  Und auch dabei waren wieder
Äußerungen, die wahrscheinlich nur ihre Unverständlichkeit davor bewahrt
hat, falsch zu sein.
Also, gerade heute habe ich diesen Stoff in der Vorlesung erklärt. So
unbeholfen wie Du hier, hat sich aber niemand dort angestellt, obwohl
die Hörer keine Mathematiker waren.
Sei eine NxN-Matrix gegegeben.
Wenn es nicht möglich ist, das n-te Diagonalelement =/= 0 zu erzeugen,
dann gibt es entweder überhaupt kein Elemente =/= 0 in der n-ten
Spalte, oder es wurden schon alle Elemente a_jn =/= 0 dieser Spalte in
den ersten n-1 Zeilen verwendet.
In diesem Falle, muss man eine dieser Zeilen zur n-ten machen und sie
durch eine andere mit entsprechendem Diagonalelement =/= 0 ersetzen.
Und eventuell solange fortfahren, bis das gewünschte Ergebnis erreicht
ist.
Dies geht nur dann nicht, wenn alle für die ersten n Zeilen in Frage
kommenden Diagonalelemente =/= 0 in weniger als n Zeilen enthalten
sind, z. B. in n -1 Zeilen.
1100
1010
0001
0001
Dann können aber die restlichen N-(n-1) Zeilen in keiner der ersten n
Spalten Elemente =/= 0  enthalten  (denn sonst wären ja die für die
ersten n Zeilen in Frage kommenden Diagonalelemente =/= 0 nicht in
weniger als n Zeilen enthalten). Also können hier N-(n-1) = N - n + 1
Zeilen nur in N - n Spalten Elemente =/= 0 enthalten. Damit sind sie
nicht linear unabhängig.
Daraus folgt zwingend (falls ich den Schwurbelbeweisversuch richtig
verstanden habe), dass  im Fall wo man N-1 Diagonalelemente =/= 0
erzeugen kann,
Du hast das natürlich wieder einmal falsch verstanden. Dabei hätte
doch schon ein Blick auf das Beispiel genügt.
Post by JürgenR
Post by WM
1100
1010
0001
0001
Enthält da eine Zeile nur Nullen? Trotzdem kann man nur N-1 = 3
Diagonalelemente =/= 0 erzeugen.
Post by JürgenR
aber nicht das N-te, die letzte Zeile nur Nullen
enthalten kann. Da werden die unbeholfensten Matheologen Ihnen
aber mühelos ein Gegenbeispiel liefern.
Vielleicht finden Sie den Fehler selber - dann können Sie sich morgen in
Ihrer Mathestunde entschuldigen.
Frisch ans Werk. Bis morgen früh 7:55 müsstest Du das Gegenbeispiel
aber vorlegen.

Gruß, WM
JürgenR
2010-11-23 21:59:29 UTC
Permalink
Post by WM
Post by JürgenR
Post by WM
Post by Carsten Schultz
Post by Ralf Bader
1. Es sei M eine invertierbare kxk-Matrix. Aus M soll durch
Zeilenvertauschungen eine Matrix N gebildet werden, in der alle
Diagonaleinträge !=0 sind.
2. Angenommen, es sei nicht möglich, durch Zeilenvertauschungen zu
erreichen, daß die ersten n+1 (<=k) Diagonaleinträge !=0 werden.
3. Dann gibt es in M höchstens n Zeilen, in denen unter den ersten n+1
Einträgen solche auftreten, die !=0 sind.
4.Die Einträge !=0 der restlichen
k-n Zeilen befinden sich sämtlich in k-n-1 Spalten, und das geht wg.
linearer Unabhängigkeit nicht.
Worauf der Schluß 2 beruht ist mir unklar, und dem Schreiber, der
ihn
in der
Formulierung
"Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen,"
versteckt, ist womöglich nicht einmal klar, daß da eine nicht ganz
offensichtliche Behauptung enthalten ist.
Zumal der Schluss von 2 auf 3 falsch ist, wenn man M nicht als
invertierbar voraussetzt.
Er zeigt, dass M nicht invertierbar ist, wenn er zutrifft.
Post by Carsten Schultz
Post by Ralf Bader
Daß der Schreiber auf der banalen
Folgerung 4 deutlich intensiver herumreitet als auf dem
problematischen
punkt 3 spricht auch nicht dafür, daß er sein Argument sonderlich durchdacht
hätte.
Ganz genau. Und in seinen ersten Beiträgen hier schien er sogar nur den
Zusammenhang zwischen Zeilenvertauschungen und Permutationsmatrizen
erklären zu wollen, der ohnehin jedem klar. Und auch dabei waren wieder
Äußerungen, die wahrscheinlich nur ihre Unverständlichkeit davor bewahrt
hat, falsch zu sein.
Also, gerade heute habe ich diesen Stoff in der Vorlesung erklärt. So
unbeholfen wie Du hier, hat sich aber niemand dort angestellt, obwohl
die Hörer keine Mathematiker waren.
Sei eine NxN-Matrix gegegeben.
Wenn es nicht möglich ist, das n-te Diagonalelement =/= 0 zu erzeugen,
dann gibt es entweder überhaupt kein Elemente =/= 0 in der n-ten
Spalte, oder es wurden schon alle Elemente a_jn =/= 0 dieser Spalte in
den ersten n-1 Zeilen verwendet.
In diesem Falle, muss man eine dieser Zeilen zur n-ten machen und sie
durch eine andere mit entsprechendem Diagonalelement =/= 0 ersetzen.
Und eventuell solange fortfahren, bis das gewünschte Ergebnis erreicht
ist.
Dies geht nur dann nicht, wenn alle für die ersten n Zeilen in Frage
kommenden Diagonalelemente =/= 0 in weniger als n Zeilen enthalten
sind, z. B. in n -1 Zeilen.
1100
1010
0001
0001
Dann können aber die restlichen N-(n-1) Zeilen in keiner der ersten n
Spalten Elemente =/= 0 enthalten (denn sonst wären ja die für die
ersten n Zeilen in Frage kommenden Diagonalelemente =/= 0 nicht in
weniger als n Zeilen enthalten). Also können hier N-(n-1) = N - n + 1
Zeilen nur in N - n Spalten Elemente =/= 0 enthalten. Damit sind sie
nicht linear unabhängig.
Daraus folgt zwingend (falls ich den Schwurbelbeweisversuch richtig
verstanden habe), dass im Fall wo man N-1 Diagonalelemente =/= 0
erzeugen kann,
Du hast das natürlich wieder einmal falsch verstanden. Dabei hätte
doch schon ein Blick auf das Beispiel genügt.
Post by JürgenR
Post by WM
1100
1010
0001
0001
Enthält da eine Zeile nur Nullen? Trotzdem kann man nur N-1 = 3
Diagonalelemente =/= 0 erzeugen.
Post by JürgenR
aber nicht das N-te, die letzte Zeile nur Nullen
enthalten kann. Da werden die unbeholfensten Matheologen Ihnen
aber mühelos ein Gegenbeispiel liefern.
Vielleicht finden Sie den Fehler selber - dann können Sie sich morgen in
Ihrer Mathestunde entschuldigen.
Frisch ans Werk. Bis morgen früh 7:55 müsstest Du das Gegenbeispiel
aber vorlegen.
Gruß, WM
Sie haben es ja eben selber geliefert, ohne es zu merken.
Schauen Sie doch mal Ihren "Beweis" an: Wenn er richtig wäre,
müsste die letzte Zeile aus Nullen bestehen - das ist aber
in Wirklichkeit nicht notwendig. Deshalb ist Ihr Beweis Quatsch.
Macht aber nichts - Ihre Beweise sind fast immer Quatsch.
WM
2010-11-24 06:49:12 UTC
Permalink
Post by JürgenR
Post by JürgenR
Daraus folgt zwingend (falls ich den Schwurbelbeweisversuch richtig
verstanden habe), dass  im Fall wo man N-1 Diagonalelemente =/= 0
erzeugen kann,
Du hast das nat rlich wieder einmal falsch verstanden. Dabei h tte
doch schon ein Blick auf das Beispiel gen gt.
Post by JürgenR
1100
1010
0001
0001
Enth lt da eine Zeile nur Nullen? Trotzdem kann man nur N-1 = 3
Diagonalelemente =/= 0 erzeugen.
Post by JürgenR
aber nicht das N-te, die letzte Zeile nur Nullen
enthalten kann. Da werden die unbeholfensten Matheologen Ihnen
aber m helos ein Gegenbeispiel liefern.
Vielleicht finden Sie den Fehler selber - dann k nnen Sie sich morgen in
Ihrer Mathestunde entschuldigen.
Frisch ans Werk. Bis morgen fr h 7:55 müsstest Du das Gegenbeispiel
aber vorlegen.
Sie haben es ja eben selber geliefert, ohne es zu merken.
Schauen Sie doch mal Ihren "Beweis" an: Wenn er richtig wäre,
müsste die letzte Zeile aus Nullen bestehen - das ist aber
in Wirklichkeit nicht notwendig. Deshalb ist Ihr Beweis Quatsch.
1) Mein *Beweis* besteht in der Konstruktion einer Diagonale mit
ausschließlich nicht verschwindenden Elementen. Das ist mit
Elementarmatrizen möglich, die Permutationsmatrizen sind und deren
Produkt ebenfalls eine Permutationsmatrix ist.

So viel zum Verständnis des Wortes "Beweis" in diesem Zusammenhang.

2) Obiges ist kein "Beweis", sondern eine Skizze, die zeigt, weshalb
mein Beweis richtig ist. Wenn die Konstruktion nämlich nicht
funktioniert, so kann man stets n Spalten finden, deren
nichtverschwindende Elemente auf höchstens n-1 Zeilen verteilt sind.
Dann können in der restlichen Zeilen nicht linear unabhängig sein.

3) Das ist oben anhand einer speziellen Matrix demonstriert. Dort ist
es nicht möglich, mehr als drei nichtverschwindende Diagonalelemente
zu erzeugen, denn drei Spalten enthalten nur in zwei Zeilen
nichtverschwindende Elemente.

4) Aus welchen Gründen das Verschwinden einer der vier Zeilen für
diese Überlegung erforderlich sein sollte, bleibt mir unerfindlich.

5) Dass faktisch keine der vier Zeilen verschwindet, kann jeder sehen,
der diese Matrix anschaut.

Sorry, mit Deinen Argumenten möcht ich meine heutige Vorlesung lieber
nicht schmücken. Aber nun kommen wir auch schon zur Determinante.

Gruß, WM
Carsten Schultz
2010-11-24 09:00:59 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by Ralf Bader
1. Es sei M eine invertierbare kxk-Matrix. Aus M soll durch
Zeilenvertauschungen eine Matrix N gebildet werden, in der alle
Diagonaleinträge !=0 sind.
2. Angenommen, es sei nicht möglich, durch Zeilenvertauschungen zu
erreichen, daß die ersten n+1 (<=k) Diagonaleinträge !=0 werden.
3. Dann gibt es in M höchstens n Zeilen, in denen unter den ersten n+1
Einträgen solche auftreten, die !=0 sind.
4.Die Einträge !=0 der restlichen
k-n Zeilen befinden sich sämtlich in k-n-1 Spalten, und das geht wg.
linearer Unabhängigkeit nicht.
Worauf der Schluß 2 beruht ist mir unklar, und dem Schreiber, der ihn in der
Formulierung
"Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen,"
versteckt, ist womöglich nicht einmal klar, daß da eine nicht ganz
offensichtliche Behauptung enthalten ist.
Zumal der Schluss von 2 auf 3 falsch ist, wenn man M nicht als
invertierbar voraussetzt.
Er zeigt, dass M nicht invertierbar ist, wenn er zutrifft.
???
Post by WM
Post by Carsten Schultz
Post by Ralf Bader
Daß der Schreiber auf der banalen
Folgerung 4 deutlich intensiver herumreitet als auf dem problematischen
punkt 3 spricht auch nicht dafür, daß er sein Argument sonderlich durchdacht
hätte.
Ganz genau. Und in seinen ersten Beiträgen hier schien er sogar nur den
Zusammenhang zwischen Zeilenvertauschungen und Permutationsmatrizen
erklären zu wollen, der ohnehin jedem klar. Und auch dabei waren wieder
Äußerungen, die wahrscheinlich nur ihre Unverständlichkeit davor bewahrt
hat, falsch zu sein.
Also, gerade heute habe ich diesen Stoff in der Vorlesung erklärt.
Welchen Stoff? Tatsächlich die Aussage, um die es hier geht?
Post by WM
So
unbeholfen wie Du hier, hat sich aber niemand dort angestellt, obwohl
die Hörer keine Mathematiker waren.
Deine Hörer sind halt an Wischiwaschierklärungen anstelle von Beweisen
gewohnt und fordern daher keine Beweise ein.
Post by WM
Sei eine NxN-Matrix gegegeben.
Wenn es nicht möglich ist, das n-te Diagonalelement =/= 0 zu erzeugen,
Was bedeutet das?
Post by WM
dann gibt es entweder überhaupt kein Elemente =/= 0 in der n-ten
Spalte, oder es wurden schon alle Elemente a_jn =/= 0 dieser Spalte in
den ersten n-1 Zeilen verwendet.
Ah, anscheinend sind wir hier schon mitten in einer nicht näher
spezifizierten Konstruktion.
Post by WM
In diesem Falle, muss man eine dieser Zeilen zur n-ten machen und sie
durch eine andere mit entsprechendem Diagonalelement =/= 0 ersetzen.
Und eventuell solange fortfahren, bis das gewünschte Ergebnis erreicht
ist.
Du gibst also auch kein Verfahren an, wie man die Permutation findet
außer „probier halt und verwende Backtracking, wenn nötig“.
Post by WM
Dies geht nur dann nicht, wenn alle für die ersten n Zeilen in Frage
kommenden Diagonalelemente =/= 0 in weniger als n Zeilen enthalten
sind, z. B. in n -1 Zeilen.
Ah, hier kommt jetzt anscheinend eine Aussage, wenn auch eine
unbewiesene. Du scheinst etwas der folgenden Art zu sagen.

(*) Ist A=(a_ij) eine NxN-Matrix, die die Eigenschaft M erfüllt,
so existiert eine Permutation p aus S_N, so dass
a_{p(r),r} /= 0 für alle r.

Du hast die Kontraposition der Aussage formuliert. Dabei scheint die
Eigenschaft folgende zu sein:

Eigenschaft M:
Für alle n, 1 <= n <= N gilt
#{i | Ex. j mit 1<=j<=n und a_ij /= 0} >= n.

Habe ich das Deinem Text richtig entnommen?
Post by WM
1100
1010
0001
0001
Dann können aber die restlichen N-(n-1) Zeilen in keiner der ersten n
Spalten Elemente =/= 0 enthalten (denn sonst wären ja die für die
ersten n Zeilen in Frage kommenden Diagonalelemente =/= 0 nicht in
weniger als n Zeilen enthalten). Also können hier N-(n-1) = N - n + 1
Zeilen nur in N - n Spalten Elemente =/= 0 enthalten. Damit sind sie
nicht linear unabhängig.
Das ist nun die folgende Aussage:

(**) Jede invertierbare NxN-Matrix besitzt die Eigenschaft M.

Diesen Teil hast Du tatsächlich bewiesen, wenn ich denn richtig
interpretiert habe, was Eigenschaft M ist.

Es fehlen also noch die Klarstellung, ob die Eigenschaft M die richtige
ist, und ein Beweis von (*).

Gruß

Carsten
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
WM
2010-11-24 10:40:19 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by Ralf Bader
1. Es sei M eine invertierbare kxk-Matrix. Aus M soll durch
Zeilenvertauschungen eine Matrix N gebildet werden, in der alle
Diagonaleinträge !=0 sind.
2. Angenommen, es sei nicht möglich, durch Zeilenvertauschungen zu
erreichen, daß die ersten n+1 (<=k) Diagonaleinträge !=0 werden.
3. Dann gibt es in M höchstens n Zeilen, in denen unter den ersten n+1
Einträgen solche auftreten, die !=0 sind.
4.Die Einträge !=0 der restlichen
k-n Zeilen befinden sich sämtlich in k-n-1 Spalten, und das geht wg.
linearer Unabhängigkeit nicht.
Worauf der Schluß 2 beruht ist mir unklar, und dem Schreiber, der ihn in der
Formulierung
 "Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
 erzeugen, weil sie nur in n Zeilen vorkommen,"
versteckt, ist womöglich nicht einmal klar, daß da eine nicht ganz
offensichtliche Behauptung enthalten ist.
Zumal der Schluss von 2 auf 3 falsch ist, wenn man M nicht als
invertierbar voraussetzt.
Er zeigt, dass M nicht invertierbar ist, wenn er zutrifft.
???
Wenn M nicht invertierbar ist, dann besitzt es nicht nur linear
unabhängige Zeilen.
Du hast also absoluten Unsinn geredet.
Post by WM
Post by Carsten Schultz
Post by Ralf Bader
Daß der Schreiber auf der banalen
Folgerung 4 deutlich intensiver herumreitet als auf dem problematischen
punkt 3 spricht auch nicht dafür, daß er sein Argument sonderlich durchdacht
hätte.
Ganz genau.  Und in seinen ersten Beiträgen hier schien er sogar nur den
Zusammenhang zwischen Zeilenvertauschungen und Permutationsmatrizen
erklären zu wollen, der ohnehin jedem klar.  Und auch dabei waren wieder
Äußerungen, die wahrscheinlich nur ihre Unverständlichkeit davor bewahrt
hat, falsch zu sein.
Also, gerade heute habe ich diesen Stoff in der Vorlesung erklärt.
Welchen Stoff?  Tatsächlich die Aussage, um die es hier geht?
Die Aussage, dass jede ínvertierbare Matrix mit Elementarmatrizen
invertiert werden kann.
Post by WM
So
unbeholfen wie Du hier, hat sich aber niemand dort angestellt, obwohl
die Hörer keine Mathematiker waren.
Deine Hörer sind halt an Wischiwaschierklärungen anstelle von Beweisen
gewohnt und fordern daher keine Beweise ein.
Post by WM
Sei eine NxN-Matrix gegegeben.
Wenn es nicht möglich ist, das n-te Diagonalelement =/= 0 zu erzeugen,
Was bedeutet das?
Eine Prämisse: Wenn es nicht möglich ist, das n-te Diagonalelement =/=
0 zu erzeugen.
Post by WM
dann gibt es entweder überhaupt kein Elemente =/= 0 in der n-ten
Spalte, oder es wurden schon alle Elemente a_jn =/= 0 dieser Spalte in
den ersten n-1 Zeilen verwendet.
Ah, anscheinend sind wir hier schon mitten in einer nicht näher
spezifizierten Konstruktion.
Du hast den Anschluss verpasst. Das liegt aber an Dir.
Post by WM
In diesem Falle, muss man eine dieser Zeilen zur n-ten machen und sie
durch eine andere mit entsprechendem Diagonalelement =/= 0 ersetzen.
Und eventuell solange fortfahren, bis das gewünschte Ergebnis erreicht
ist.
Du gibst also auch kein Verfahren an, wie man die Permutation findet
außer „probier halt und verwende Backtracking, wenn nötig“.
Hier sollte die Existenz genügen.
Wenn die Matrix nicht diagonalisierbar ist, wenn man also n Zeilen
finden kann, so dass Elemente aus n+1 Spalten nur dort =/= sind, dann
sind die Zeilen nicht linear unabhängig.
Da lineare Unabhängigkeit vorausgesetzt wurde, ist bewiesen: Die
Matrix ist diagonalisierbar.

Versteh' es oder lass' es.

EOD

Gruß, WM
Carsten Schultz
2010-11-24 10:59:59 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by Ralf Bader
1. Es sei M eine invertierbare kxk-Matrix. Aus M soll durch
Zeilenvertauschungen eine Matrix N gebildet werden, in der alle
Diagonaleinträge !=0 sind.
2. Angenommen, es sei nicht möglich, durch Zeilenvertauschungen zu
erreichen, daß die ersten n+1 (<=k) Diagonaleinträge !=0 werden.
3. Dann gibt es in M höchstens n Zeilen, in denen unter den ersten n+1
Einträgen solche auftreten, die !=0 sind.
4.Die Einträge !=0 der restlichen
k-n Zeilen befinden sich sämtlich in k-n-1 Spalten, und das geht wg.
linearer Unabhängigkeit nicht.
Worauf der Schluß 2 beruht ist mir unklar, und dem Schreiber, der ihn in der
Formulierung
"Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen,"
versteckt, ist womöglich nicht einmal klar, daß da eine nicht ganz
offensichtliche Behauptung enthalten ist.
Zumal der Schluss von 2 auf 3 falsch ist, wenn man M nicht als
invertierbar voraussetzt.
Er zeigt, dass M nicht invertierbar ist, wenn er zutrifft.
???
Wenn M nicht invertierbar ist, dann besitzt es nicht nur linear
unabhängige Zeilen.
Du hast also absoluten Unsinn geredet.
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by Ralf Bader
Daß der Schreiber auf der banalen
Folgerung 4 deutlich intensiver herumreitet als auf dem problematischen
punkt 3 spricht auch nicht dafür, daß er sein Argument sonderlich durchdacht
hätte.
Ganz genau. Und in seinen ersten Beiträgen hier schien er sogar nur den
Zusammenhang zwischen Zeilenvertauschungen und Permutationsmatrizen
erklären zu wollen, der ohnehin jedem klar. Und auch dabei waren wieder
Äußerungen, die wahrscheinlich nur ihre Unverständlichkeit davor bewahrt
hat, falsch zu sein.
Also, gerade heute habe ich diesen Stoff in der Vorlesung erklärt.
Welchen Stoff? Tatsächlich die Aussage, um die es hier geht?
Die Aussage, dass jede ínvertierbare Matrix mit Elementarmatrizen
invertiert werden kann.
Das, was Du damit meinst, war hier ohnehin von Anfang an jedem klar. Es
hat nur nichts mit dem Problem zu tun.
Post by WM
Post by Carsten Schultz
Post by WM
So
unbeholfen wie Du hier, hat sich aber niemand dort angestellt, obwohl
die Hörer keine Mathematiker waren.
Deine Hörer sind halt an Wischiwaschierklärungen anstelle von Beweisen
gewohnt und fordern daher keine Beweise ein.
Post by WM
Sei eine NxN-Matrix gegegeben.
Wenn es nicht möglich ist, das n-te Diagonalelement =/= 0 zu erzeugen,
Was bedeutet das?
Eine Prämisse: Wenn es nicht möglich ist, das n-te Diagonalelement =/=
0 zu erzeugen.
Post by Carsten Schultz
Post by WM
dann gibt es entweder überhaupt kein Elemente =/= 0 in der n-ten
Spalte, oder es wurden schon alle Elemente a_jn =/= 0 dieser Spalte in
den ersten n-1 Zeilen verwendet.
Ah, anscheinend sind wir hier schon mitten in einer nicht näher
spezifizierten Konstruktion.
Du hast den Anschluss verpasst. Das liegt aber an Dir.
Post by Carsten Schultz
Post by WM
In diesem Falle, muss man eine dieser Zeilen zur n-ten machen und sie
durch eine andere mit entsprechendem Diagonalelement =/= 0 ersetzen.
Und eventuell solange fortfahren, bis das gewünschte Ergebnis erreicht
ist.
Du gibst also auch kein Verfahren an, wie man die Permutation findet
außer „probier halt und verwende Backtracking, wenn nötig“.
Hier sollte die Existenz genügen.
Wenn die Matrix nicht diagonalisierbar ist,
Wir geben mal eben einem Standardbegriff eine neue Bedeutung...
Post by WM
wenn man also n Zeilen
finden kann, so dass Elemente aus n+1 Spalten nur dort =/= sind, dann
sind die Zeilen nicht linear unabhängig.
Hier wird wieder eine Implikation behauptet und nicht bewiesen. Ist das
oben die von mir formulierte Eigenschaft M (die Du gelöscht hast) oder
eine andere?
Post by WM
Da lineare Unabhängigkeit vorausgesetzt wurde, ist bewiesen: Die
Matrix ist diagonalisierbar.
Versteh' es oder lass' es.
EOD
Schön, dass Du gerade auf den Teil, der die wesentliche Mathematik
beinhaltet, nicht eingehst. Wundert mich das? Wohl kaum.

Gruß

Carsten
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
JürgenR
2010-11-24 11:53:39 UTC
Permalink
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by Ralf Bader
1. Es sei M eine invertierbare kxk-Matrix. Aus M soll durch
Zeilenvertauschungen eine Matrix N gebildet werden, in der alle
Diagonaleinträge !=0 sind.
2. Angenommen, es sei nicht möglich, durch Zeilenvertauschungen zu
erreichen, daß die ersten n+1 (<=k) Diagonaleinträge !=0 werden.
3. Dann gibt es in M höchstens n Zeilen, in denen unter den ersten n+1
Einträgen solche auftreten, die !=0 sind.
4.Die Einträge !=0 der restlichen
k-n Zeilen befinden sich sämtlich in k-n-1 Spalten, und das geht wg.
linearer Unabhängigkeit nicht.
Worauf der Schluß 2 beruht ist mir unklar, und dem Schreiber, der ihn in der
Formulierung
"Wenn es nicht möglich ist, die ersten n+1 Diagonalelemente =/= 0 zu
erzeugen, weil sie nur in n Zeilen vorkommen,"
versteckt, ist womöglich nicht einmal klar, daß da eine nicht ganz
offensichtliche Behauptung enthalten ist.
Zumal der Schluss von 2 auf 3 falsch ist, wenn man M nicht als
invertierbar voraussetzt.
Er zeigt, dass M nicht invertierbar ist, wenn er zutrifft.
???
Wenn M nicht invertierbar ist, dann besitzt es nicht nur linear
unabhängige Zeilen.
Du hast also absoluten Unsinn geredet.
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Post by Ralf Bader
Daß der Schreiber auf der banalen
Folgerung 4 deutlich intensiver herumreitet als auf dem
problematischen
punkt 3 spricht auch nicht dafür, daß er sein Argument sonderlich durchdacht
hätte.
Ganz genau. Und in seinen ersten Beiträgen hier schien er sogar nur den
Zusammenhang zwischen Zeilenvertauschungen und Permutationsmatrizen
erklären zu wollen, der ohnehin jedem klar. Und auch dabei waren wieder
Äußerungen, die wahrscheinlich nur ihre Unverständlichkeit davor bewahrt
hat, falsch zu sein.
Also, gerade heute habe ich diesen Stoff in der Vorlesung erklärt.
Welchen Stoff? Tatsächlich die Aussage, um die es hier geht?
Die Aussage, dass jede ínvertierbare Matrix mit Elementarmatrizen
invertiert werden kann.
Das, was Du damit meinst, war hier ohnehin von Anfang an jedem klar. Es
hat nur nichts mit dem Problem zu tun.
Post by WM
Post by Carsten Schultz
Post by WM
So
unbeholfen wie Du hier, hat sich aber niemand dort angestellt, obwohl
die Hörer keine Mathematiker waren.
Deine Hörer sind halt an Wischiwaschierklärungen anstelle von Beweisen
gewohnt und fordern daher keine Beweise ein.
Post by WM
Sei eine NxN-Matrix gegegeben.
Wenn es nicht möglich ist, das n-te Diagonalelement =/= 0 zu erzeugen,
Was bedeutet das?
Eine Prämisse: Wenn es nicht möglich ist, das n-te Diagonalelement =/=
0 zu erzeugen.
Post by Carsten Schultz
Post by WM
dann gibt es entweder überhaupt kein Elemente =/= 0 in der n-ten
Spalte, oder es wurden schon alle Elemente a_jn =/= 0 dieser Spalte in
den ersten n-1 Zeilen verwendet.
Ah, anscheinend sind wir hier schon mitten in einer nicht näher
spezifizierten Konstruktion.
Du hast den Anschluss verpasst. Das liegt aber an Dir.
Post by Carsten Schultz
Post by WM
In diesem Falle, muss man eine dieser Zeilen zur n-ten machen und sie
durch eine andere mit entsprechendem Diagonalelement =/= 0 ersetzen.
Und eventuell solange fortfahren, bis das gewünschte Ergebnis erreicht
ist.
Du gibst also auch kein Verfahren an, wie man die Permutation findet
außer „probier halt und verwende Backtracking, wenn nötig“.
Hier sollte die Existenz genügen.
Wenn die Matrix nicht diagonalisierbar ist,
Wir geben mal eben einem Standardbegriff eine neue Bedeutung...
Post by WM
wenn man also n Zeilen
finden kann, so dass Elemente aus n+1 Spalten nur dort =/= sind, dann
sind die Zeilen nicht linear unabhängig.
Hier wird wieder eine Implikation behauptet und nicht bewiesen. Ist das
oben die von mir formulierte Eigenschaft M (die Du gelöscht hast) oder
eine andere?
Post by WM
Da lineare Unabhängigkeit vorausgesetzt wurde, ist bewiesen: Die
Matrix ist diagonalisierbar.
Versteh' es oder lass' es.
EOD
Schön, dass Du gerade auf den Teil, der die wesentliche Mathematik
beinhaltet, nicht eingehst. Wundert mich das? Wohl kaum.
Er kann es einfach nicht.
Cantor ist schuld und die bösen Matheologen.

Eigenartig dass solche Spinner oft gerade Cantor als
Hauptfeind wählen.
Post by Carsten Schultz
Gruß
Carsten
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
Roalto
2010-11-24 19:01:19 UTC
Permalink
[Snip]
Er kann es einfach nicht.
Cantor ist schuld und die bösen Matheologen.
Eigenartig dass solche Spinner oft gerade Cantor als
Hauptfeind wählen.
Eigenartig? Eigentlich nicht.
Mathespinner wie wm,as,rs etc.nehmen Cantor,
Physiker Einstein.
Der Grund ist einfach, sie verstehen es nicht!

Viel Spass weiterhin
Rolf

--
Wo Frauen geehrt werden,
sind die Götter zufrieden.
WM
2010-11-25 07:31:52 UTC
Permalink
Post by Roalto
[Snip]
Er kann es einfach nicht.
Cantor ist schuld und die bösen Matheologen.
Eigenartig dass solche Spinner oft gerade Cantor als
Hauptfeind wählen.
Eigenartig? Eigentlich nicht.
Mathespinner wie wm,as,rs etc.nehmen Cantor,
Physiker Einstein.
Der Grund ist einfach, sie verstehen es nicht!
Manche verstehen manches nicht. Zum Beispiel, verstehe ich nicht, wie
jemand daran zweifeln kann, dass Valentina Tereschkowa die erste Frau
war, die leiblich in den Himmel aufgefahren ist:
http://www.spzeitung.ru/2009/06/erste-kosmonautin-valentina-tereschkowa-der-welt-erhalt-russischen-staatspreis/

Andere wieder verstehen nicht, wie es zugeht, dass jemand die Zeilen
einer 10x10-Matrix, in der Elemente =/= 0 aus 9 Spalten nur in einer
einzigen Spalte vorkommen, sofort als linear abhängig und damit die
Matrix als nicht umkehrbar erkennen kann.

0000010000
0000010000
0000010000
0000010000
1111111111
0000010000
0000010000
0000010000
0000010000
0000010000

Die Erkenntnisfähigkeiten sind eben ungleichmäßig verteilt.

Gruß, WM
WM
2010-11-25 07:35:48 UTC
Permalink
Post by Roalto
[Snip]
Er kann es einfach nicht.
Cantor ist schuld und die bösen Matheologen.
Eigenartig dass solche Spinner oft gerade Cantor als
Hauptfeind wählen.
Eigenartig? Eigentlich nicht.
Mathespinner wie wm,as,rs etc.nehmen Cantor,
Physiker Einstein.
Der Grund ist einfach, sie verstehen es nicht!
Manche verstehen manches nicht. Zum Beispiel verstehe ich nicht, wie
jemand daran zweifeln kann, dass Valentina Tereschkowa die erste Frau
war, die leiblich in den Himmel aufgefahren ist:
http://www.spzeitung.ru/2009/06/erste-kosmonautin-valentina-tereschko...

Andere wieder verstehen nicht, wie es zugeht, dass jemand die Zeilen
einer 10x10-Matrix, in der Elemente =/= 0 aus 9 Spalten nur in einer
einzigen Zeile vorkommen, sofort als linear abhängig und damit die
Matrix als nicht umkehrbar erkennen kann.

0000010000
0000010000
0000010000
0000010000
1111111111
0000010000
0000010000
0000010000
0000010000
0000010000

Die Erkenntnisfähigkeiten sind eben ungleichmäßig verteilt.

Gruß, WM
Carsten Schultz
2010-11-25 08:17:58 UTC
Permalink
Post by WM
Andere wieder verstehen nicht, wie es zugeht, dass jemand die Zeilen
einer 10x10-Matrix, in der Elemente =/= 0 aus 9 Spalten nur in einer
einzigen Zeile vorkommen, sofort als linear abhängig und damit die
Matrix als nicht umkehrbar erkennen kann.
0000010000
0000010000
0000010000
0000010000
1111111111
0000010000
0000010000
0000010000
0000010000
0000010000
Du hast die Kritik an dem, was Du hier einen Beweis genannt hast, immer
noch nicht verstanden.
Post by WM
Die Erkenntnisfähigkeiten sind eben ungleichmäßig verteilt.
In der Tat.
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
r***@online.de
2010-11-26 17:28:10 UTC
Permalink
On Wed, 24 Nov 2010 23:35:48 -0800 (PST), WM
Post by WM
Post by Roalto
[Snip]
Er kann es einfach nicht.
Cantor ist schuld und die bösen Matheologen.
Eigenartig dass solche Spinner oft gerade Cantor als
Hauptfeind wählen.
Eigenartig? Eigentlich nicht.
Mathespinner wie wm,as,rs etc.nehmen Cantor,
Physiker Einstein.
Der Grund ist einfach, sie verstehen es nicht!
Manche verstehen manches nicht. Zum Beispiel verstehe ich nicht, wie
jemand daran zweifeln kann, dass Valentina Tereschkowa die erste Frau
http://www.spzeitung.ru/2009/06/erste-kosmonautin-valentina-tereschko...
Andere wieder verstehen nicht, wie es zugeht, dass jemand die Zeilen
einer 10x10-Matrix, in der Elemente =/= 0 aus 9 Spalten nur in einer
einzigen Zeile vorkommen, sofort als linear abhängig und damit die
Matrix als nicht umkehrbar erkennen kann.
Ach, Mückenheim, alter Lachsack!
Post by WM
Die Erkenntnisfähigkeiten sind eben ungleichmäßig verteilt.
Das sieht man sofort.
Post by WM
Gruß, WM
Viel Spass weiterhin
Rolf
Ralf Bader
2010-11-21 06:10:04 UTC
Permalink
Post by Stephan Gerlach
Post by WM
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?
"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir fällt zwar was ein, aber das geht über Determinanten und ist IMHO zu
umständlich.
Es geht über das Produkt geeigneter Elementarmatrizen.
... welche hier Permutationsmatrizen sein sollten. Sogar eine einzige
solche Matrix P genügt hier, wie ich auch selber schrieb. Daß man die
gewünschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, weiß ich selber. Die Frage war aber, wie
begründet man die Existenz dieser "passenden" Permutationsmatrix P.
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
Aus einer von vornherein beschränkten endlichen Anzahl von Möglichkeiten
eine auswählen zu müssen, ist konstruktiv.


Ralf
Stephan Gerlach
2010-11-21 18:52:08 UTC
Permalink
Post by Ralf Bader
Post by Stephan Gerlach
Post by WM
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?
"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir fällt zwar was ein, aber das geht über Determinanten und ist IMHO zu
umständlich.
Es geht über das Produkt geeigneter Elementarmatrizen.
... welche hier Permutationsmatrizen sein sollten. Sogar eine einzige
solche Matrix P genügt hier, wie ich auch selber schrieb. Daß man die
gewünschte Permutation durch Von-Links-Multiplikation einer
Elementarmatrix erreicht, weiß ich selber. Die Frage war aber, wie
begründet man die Existenz dieser "passenden" Permutationsmatrix P.
Ich hätte als Idee, folgende Darstellung der Determinante
det(A) = Summe_{alle Permutationen [i_1,...,i_n] der Zahlen 1,...,n}
sign[i_1,...,i_n] * a_{i_1,1}*...*a_{i_n,n}
zu nehmen und dann zu begründen: Falls *jede* Permutation der Zeilen der
Matrix A = (a_{ij})_{i,j=1 bis n} eine 0 in der Hauptdiagonale *hätte*,
so wäre nach obiger Formel det(A) = 0, was aber im Widerspruch dazu
stünde, daß A regulär vorausgesetzt wurde. Also muß (mindestens) eine
Permutation dabei sein, wo keine 0 auf der Hauptdiagonalen steht.
Allerdings ist dieser "Beweis" ("Begründung" paßt wohl besser) nicht
konstruktiv. Ich vermute, daß es auch eine Begründung gibt, die ohne
Determinante auskommt.
Aus einer von vornherein beschränkten endlichen Anzahl von Möglichkeiten
eine auswählen zu müssen, ist konstruktiv.
OK, wenn man' so sieht, hast du recht...
"Probiere alle(!) Möglichkeiten durch, bis die gewünschte Möglichkeit
kommt."
Allerdings braucht man mit diesem Algorithmus u.U. n! Versuche :-) .
--
Post by Ralf Bader
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
WM
2010-11-22 07:52:54 UTC
Permalink
Post by Stephan Gerlach
Post by Ralf Bader
Aus einer von vornherein beschränkten endlichen Anzahl von Möglichkeiten
eine auswählen zu müssen, ist konstruktiv.
OK, wenn man' so sieht, hast du recht...
"Probiere alle(!) Möglichkeiten durch, bis die gewünschte Möglichkeit
kommt."
Allerdings braucht man mit diesem Algorithmus u.U. n! Versuche :-) .
Ich habe für die von Dir gestellte Aufgabe nur einen Versuch
gebraucht. Natürlich kannst Du's Glück nennen. Wie dem auch sei: Hat
er Dir eingeleuchtet? Oder sind da noch weitere Erklärungen vonnöten?

Gruß, WM
Ralf Bader
2010-11-24 16:04:38 UTC
Permalink
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?
"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir fällt zwar was ein, aber das geht über Determinanten und ist IMHO zu
umständlich.
Ob das elegant ist, weiß ich nicht, aber die Antwort auf die Frage sieht
jetzt so aus:
Es sei M eine nxn-Matrix mit Einträgen m_ij.
Behauptung 1: Genau dann läßt sich aus M durch Zeilenvertauschungen eine
Matrix N mit ausschließlich nichtverschwindeneden Diagonaleinträgen
gewinnen, wenn folgende Bedingung erfüllt ist:
Zu beliebigen k (<=n) Indices i1,...,ik gibt es immer Indices j1,...,jk, so
daß die Matrixeinträge m_ir,jr !=0 sind (1<=r<=k)
Dies ergibt sich aus dem von Carsten schultz bereits genannten Heiratssatz;
der Matrix M entspricht ein bipartiter Graph mit Eckenmenge
{a1,...,an,b1,...,bn} korrespondierend zu den Zeilen bzw Spalten von M, und
einer Kante {ai,bj} genau dann, wenn m_ij != 0.

Behauptung 2: Ist M regulär, so ist die obige Bedingung erfüllt. das ergibt
sich aus dem Determinantenargument.

Behauptung 3: Die Zeilenpermutation läßt sich, sofern existent, mit
Berechnungsaufwand O(n^(3/2)) finden. Siehe dazu Schrijver, Combinatorial
Optimization, Chaps. 16,22


Ralf
Ralf Bader
2010-11-25 00:50:05 UTC
Permalink
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?
"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir fällt zwar was ein, aber das geht über Determinanten und ist IMHO zu
umständlich.
Über Eleganz läßt sich streiten, aber die Antwort auf die Frage sieht
jetzt so aus:

Es sei M eine nxn-Matrix mit Einträgen m_ij. Ist I = {i_1,...,i_k} eine
Menge von (Zeilen-)Indices, so sei I* = {j| es gibt ein i e I mit m_ij !=0}

Behauptung 1: Genau dann läßt sich aus M durch Zeilenvertauschungen eine
Matrix N mit ausschließlich nichtverschwindenden Diagonaleinträgen
gewinnen, wenn für jede Menge I von (Zeilen-)Indices gilt: |I*| >= |I|.
Dies ergibt sich aus dem von Carsten Schultz bereits genannten Heiratssatz;
der Matrix M entspricht ein bipartiter Graph G mit Eckenmenge
{a1,...,an} u {b1,...,bn} = A u B korrespondierend zu den Zeilen bzw Spalten
von M, und einer Kante {ai,bj} genau dann, wenn m_ij != 0. Nach Heiratssatz
gibt es unter der obigen Bedingung eine Permutation j:{1,...,n}->{1,...,n},
so daß G Kanten {a_i,b_j(i)} enthält, 1<=i<=n. Damit führt j als
Zeilenpermutation von M zum gewünschten Resultat.

Behauptung 2: Ist M regulär, so ist die obige Bedingung erfüllt.
Das ergibt sich aus dem Determinantenargument.

Behauptung 3: Die Zeilenpermutation j läßt sich, sofern existent, mit
Berechnungsaufwand O(n^(3/2)) finden.
Siehe Schrijver, Combinatorial Optimization A, Chaps. 16 und 22.

Behauptung 4: Herr Professor Mückenheim ist zu doof, um zu erkennen, daß es
an dem Heiratssatz etwas zu beweisen gibt.
Das folgt im Lichte des Obigen aus seinem depperten Gefasel in diesem
Thread.


Ralf
JürgenR
2010-11-25 06:02:15 UTC
Permalink
Post by Ralf Bader
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?
"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir fällt zwar was ein, aber das geht über Determinanten und ist IMHO zu
umständlich.
Über Eleganz läßt sich streiten, aber die Antwort auf die Frage sieht
Es sei M eine nxn-Matrix mit Einträgen m_ij. Ist I = {i_1,...,i_k} eine
Menge von (Zeilen-)Indices, so sei I* = {j| es gibt ein i e I mit m_ij !=0}
Behauptung 1: Genau dann läßt sich aus M durch Zeilenvertauschungen eine
Matrix N mit ausschließlich nichtverschwindenden Diagonaleinträgen
gewinnen, wenn für jede Menge I von (Zeilen-)Indices gilt: |I*| >= |I|.
Dies ergibt sich aus dem von Carsten Schultz bereits genannten
Heiratssatz;
der Matrix M entspricht ein bipartiter Graph G mit Eckenmenge
{a1,...,an} u {b1,...,bn} = A u B korrespondierend zu den Zeilen bzw Spalten
von M, und einer Kante {ai,bj} genau dann, wenn m_ij != 0. Nach Heiratssatz
gibt es unter der obigen Bedingung eine Permutation
j:{1,...,n}->{1,...,n},
so daß G Kanten {a_i,b_j(i)} enthält, 1<=i<=n. Damit führt j als
Zeilenpermutation von M zum gewünschten Resultat.
Ist das nicht viel komplizierter als notwendig?
Wenn die Determinante nicht verschwindet, gibt es immer
n Elemente, die alle =/= 0 sind und von denen weder 2 zur
selben Spalte, noch 2 zur selben Reihe gehören.
Post by Ralf Bader
Behauptung 2: Ist M regulär, so ist die obige Bedingung erfüllt.
Das ergibt sich aus dem Determinantenargument.
Behauptung 3: Die Zeilenpermutation j läßt sich, sofern existent, mit
Berechnungsaufwand O(n^(3/2)) finden.
Siehe Schrijver, Combinatorial Optimization A, Chaps. 16 und 22.
Behauptung 4: Herr Professor Mückenheim ist zu doof, um zu erkennen, daß es
an dem Heiratssatz etwas zu beweisen gibt.
Das folgt im Lichte des Obigen aus seinem depperten Gefasel in diesem
Thread.
Ralf
Ralf Bader
2010-11-26 01:29:00 UTC
Permalink
Post by JürgenR
Post by Ralf Bader
Post by Stephan Gerlach
Gibt es eine besonders elegante/einfache Begründung für folgende Bemerkung?
"Gegeben sei eine invertierbare n×n-Matrix A. Dann existiert immer eine
n×n-Permutationsmatrix P derart, welche durch Linksmultiplikation P*A
die Zeilen von A derart vertauscht, daß auf der Hauptdiagonalen der
zeilen-permutierten Matrix (also P*A) keine 0-en stehen."
Mir fällt zwar was ein, aber das geht über Determinanten und ist IMHO zu
umständlich.
Über Eleganz läßt sich streiten, aber die Antwort auf die Frage sieht
Es sei M eine nxn-Matrix mit Einträgen m_ij. Ist I = {i_1,...,i_k} eine
Menge von (Zeilen-)Indices, so sei I* = {j| es gibt ein i e I mit m_ij !=0}
Behauptung 1: Genau dann läßt sich aus M durch Zeilenvertauschungen eine
Matrix N mit ausschließlich nichtverschwindenden Diagonaleinträgen
gewinnen, wenn für jede Menge I von (Zeilen-)Indices gilt: |I*| >= |I|.
Dies ergibt sich aus dem von Carsten Schultz bereits genannten Heiratssatz;
der Matrix M entspricht ein bipartiter Graph G mit Eckenmenge
{a1,...,an} u {b1,...,bn} = A u B korrespondierend zu den Zeilen bzw Spalten
von M, und einer Kante {ai,bj} genau dann, wenn m_ij != 0. Nach Heiratssatz
gibt es unter der obigen Bedingung eine Permutation
j:{1,...,n}->{1,...,n},
so daß G Kanten {a_i,b_j(i)} enthält, 1<=i<=n. Damit führt j als
Zeilenpermutation von M zum gewünschten Resultat.
Ist das nicht viel komplizierter als notwendig?
Wenn die Determinante nicht verschwindet, gibt es immer
n Elemente, die alle =/= 0 sind und von denen weder 2 zur
selben Spalte, noch 2 zur selben Reihe gehören.
Das mit dem Heiratssatz zeigt die Anwendbarkeit der unten erwähnten
graphentheoretischen Algorithmen, um die Permutation tatsächlich angeben zu
können - mit etwas weniger Aufwand als einer blinden Suche unter n!
Möglichkeiten.
Post by JürgenR
Post by Ralf Bader
Behauptung 2: Ist M regulär, so ist die obige Bedingung erfüllt.
Das ergibt sich aus dem Determinantenargument.
Behauptung 3: Die Zeilenpermutation j läßt sich, sofern existent, mit
Berechnungsaufwand O(n^(3/2)) finden.
Siehe Schrijver, Combinatorial Optimization A, Chaps. 16 und 22.
Ralf
WM
2010-11-26 09:59:55 UTC
Permalink
Post by JürgenR
Post by Ralf Bader
Heiratssatz;
der Matrix M entspricht ein bipartiter Graph G mit Eckenmenge
{a1,...,an} u {b1,...,bn} = A u B korrespondierend zu den Zeilen bzw Spalten
von M, und einer Kante {ai,bj} genau dann, wenn m_ij != 0. Nach Heiratssatz
gibt es unter der obigen Bedingung eine Permutation
j:{1,...,n}->{1,...,n},
so daß G Kanten {a_i,b_j(i)} enthält, 1<=i<=n. Damit führt j als
Zeilenpermutation von M zum gewünschten Resultat.
Ist das nicht viel komplizierter als notwendig?
Natürlich, hier fehlt das mathematische Verständnis.
Post by JürgenR
Wenn die Determinante nicht verschwindet, gibt es immer
n Elemente, die alle =/= 0 sind und von denen weder 2 zur
selben Spalte, noch 2 zur selben Reihe gehören.
Die Determinante zu verwenden, hatte der OP ausdrücklich
ausgeschlossen, weil zu kompliziert.

Der Beweis ist ganz simpel, wenn man bedenkt, dass die Matrix, da als
umkehrbar vorausgesetzt, quadratisch sein muss, NxN, also genau so
viele Zeilen wie Spalten besitzen muss, und wenn man sich fragt, was
eine Füllung der Diagonale mit Elementen =/= 0 verhindern kann. Die
Idee, mit Zeilen und Spalten zu jonglieren, löst das Problem sofort.

Wenn es nicht gelingt, die Elemente =/= 0 durch einfache
Zeilenvertauschungen auf die Diagonale zu bringen, dann gibt es immer
ein n, so dass alle Elemente =/= 0 aus n Spalten in nur n-1 Zeilen
existieren. Dann gibt es noch N-(n-1) Zeilen, in denen nur Elemente =/
= 0 aus den übrigen N-n Spalten vorhanden sind.

N-n+1 Zeilen mit Elementen =/= 0 aus nur N-n Spalten sind notwendig
linear abhängig. Damit ist die Matrix nicht umkehrbar.

Also gilt: Können nicht alle Elemente auf der Diagonale durch
Umordnung =/= 0 gemacht werden, dann ist die Matrix nicht umkehrbar.
Und damit gilt auch die Kontraposition: Ist die Matrix umkehrbar, dann
kann die gewünschte Diagonale erzeugt werden. qed.

Wer aber meint, seine mathematische Befähigung unter Beweis stellen zu
müssen, indem er auch hier davon ausgeht, dass 1 + 1 = 2 noch bewiesen
werden müsste, der soll es halt beweisen. Nur wird er ganz gewiss
keine Lücke in meinem Beweis finden, ganz einfach weil man ihn mit
einem normalen Maß von Intelligenz nachvollziehen kann, ja ihn sogar
selbst hätte finden können (sollen).

Gruß, WM
Carsten Schultz
2010-11-27 12:15:59 UTC
Permalink
Post by WM
Post by JürgenR
Post by Ralf Bader
Heiratssatz;
der Matrix M entspricht ein bipartiter Graph G mit Eckenmenge
{a1,...,an} u {b1,...,bn} = A u B korrespondierend zu den Zeilen bzw Spalten
von M, und einer Kante {ai,bj} genau dann, wenn m_ij != 0. Nach Heiratssatz
gibt es unter der obigen Bedingung eine Permutation
j:{1,...,n}->{1,...,n},
so daß G Kanten {a_i,b_j(i)} enthält, 1<=i<=n. Damit führt j als
Zeilenpermutation von M zum gewünschten Resultat.
Ist das nicht viel komplizierter als notwendig?
Natürlich, hier fehlt das mathematische Verständnis.
Du pöbelst wieder einmal nur herum.
Post by WM
Post by JürgenR
Wenn die Determinante nicht verschwindet, gibt es immer
n Elemente, die alle =/= 0 sind und von denen weder 2 zur
selben Spalte, noch 2 zur selben Reihe gehören.
Die Determinante zu verwenden, hatte der OP ausdrücklich
ausgeschlossen, weil zu kompliziert.
Der Beweis ist ganz simpel, wenn man bedenkt, dass die Matrix, da als
umkehrbar vorausgesetzt, quadratisch sein muss, NxN, also genau so
viele Zeilen wie Spalten besitzen muss, und wenn man sich fragt, was
eine Füllung der Diagonale mit Elementen =/= 0 verhindern kann. Die
Idee, mit Zeilen und Spalten zu jonglieren, löst das Problem sofort.
Wenn es nicht gelingt, die Elemente =/= 0 durch einfache
Zeilenvertauschungen auf die Diagonale zu bringen, dann gibt es immer
ein n, so dass alle Elemente =/= 0 aus n Spalten in nur n-1 Zeilen
existieren.
Das hast Du nun endlich so formuliert, dass es halbwegs verständlich
ist, aber dieser Teil müsste natürlich bewiesen werden. Wie jetzt schon
mehrfach erwähnt wurde, ist das aber ein Spezialfall des Heiratssatzes
(mit dem es einer Deiner früheren Aussagen nach nichts zu tun hat), es
ist also richtig.

Dein „Beweis“ des Heiratssatzes wäre wahrscheinlich: Die Bedingung ist
notwendig. Ich sehe nicht, was ansonsten noch notwendig sein sollte.
Also ist die Bedingung auch hinreichend.

Aber zum Glück gibt es ja schon Beweise des Heiratssatzes.
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
WM
2010-11-27 12:36:45 UTC
Permalink
Post by Carsten Schultz
Post by WM
Post by JürgenR
Post by Ralf Bader
Heiratssatz;
der Matrix M entspricht ein bipartiter Graph G mit Eckenmenge
{a1,...,an} u {b1,...,bn} = A u B korrespondierend zu den Zeilen bzw Spalten
von M, und einer Kante {ai,bj} genau dann, wenn m_ij != 0. Nach Heiratssatz
gibt es unter der obigen Bedingung eine Permutation
j:{1,...,n}->{1,...,n},
so daß G Kanten {a_i,b_j(i)} enthält, 1<=i<=n. Damit führt j als
Zeilenpermutation von M zum gewünschten Resultat.
Ist das nicht viel komplizierter als notwendig?
Natürlich, hier fehlt das mathematische Verständnis.
Du pöbelst wieder einmal nur herum.
Es geht um Bader. Das sagt alles.
Post by Carsten Schultz
Post by WM
Post by JürgenR
Wenn die Determinante nicht verschwindet, gibt es immer
n Elemente, die alle =/= 0 sind und von denen weder 2 zur
selben Spalte, noch 2 zur selben Reihe gehören.
Die Determinante zu verwenden, hatte der OP ausdrücklich
ausgeschlossen, weil zu kompliziert.
Der Beweis ist ganz simpel, wenn man bedenkt, dass die Matrix, da als
umkehrbar vorausgesetzt, quadratisch sein muss, NxN, also genau so
viele Zeilen wie Spalten besitzen muss, und wenn man sich fragt, was
eine Füllung der Diagonale mit Elementen =/= 0 verhindern kann. Die
Idee, mit Zeilen und Spalten zu jonglieren, löst das Problem sofort.
Wenn es nicht gelingt, die Elemente =/= 0 durch einfache
Zeilenvertauschungen auf die Diagonale zu bringen, dann gibt es immer
ein n, so dass alle Elemente =/= 0 aus n Spalten in nur n-1 Zeilen
existieren.
Das hast Du nun endlich so formuliert, dass es halbwegs verständlich
ist,
Ich habe diesen Gedanken schon x-mal in diesem Thread dargestellt. Er
ist von solcher Schlichtheit, dass ich mir wirklich nicht vorstellen
kann, wie man ihn nicht verstehen kann. Sorry. Geht nicht.
Post by Carsten Schultz
aber dieser Teil müsste natürlich bewiesen werden.
Da müsste überhaupt nichts beweisen werden. Wenn Du das nicht glaubst,
dann konstruiere doch ein Gegenbeispiel! (Natürlich meinen manche
auch, 1 + 1 = 2 müsse bewiesen werden. Diese Ansicht ist falsch. Und
man kann sie auch nicht beweisen. Man kann das höchstens als notwendig
"empfinden".)
Post by Carsten Schultz
 Wie jetzt schon
mehrfach erwähnt wurde, ist das aber ein Spezialfall des Heiratssatzes
(mit dem es einer Deiner früheren Aussagen nach nichts zu tun hat), es
ist also richtig.
Man *benötigt* keinen weiteren Satz, um zu erkennen, dass es ein n
gibt, so dass Elemente aus n Spalten nur in n-1 Zeilen sind, wenn die
Diagonalisierung (hier im Sinne der Aufgabe gemeint) nicht gelingt.
Andernfalls würde man sie doch einfach durchführen können!

Da gibt es nichts zu beweisen!

Man diagonalisiert und diagonalisiert und irgendwann geht es nicht
weiter. Warum nicht? Weil die benutzten Elemente in zu wenigen Zeilen
sind! Sonst ginge es ja weiter.

Gruß, WM
Carsten Schultz
2010-11-27 13:18:22 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by WM
Post by JürgenR
Post by Ralf Bader
Heiratssatz;
der Matrix M entspricht ein bipartiter Graph G mit Eckenmenge
{a1,...,an} u {b1,...,bn} = A u B korrespondierend zu den Zeilen bzw Spalten
von M, und einer Kante {ai,bj} genau dann, wenn m_ij != 0. Nach Heiratssatz
gibt es unter der obigen Bedingung eine Permutation
j:{1,...,n}->{1,...,n},
so daß G Kanten {a_i,b_j(i)} enthält, 1<=i<=n. Damit führt j als
Zeilenpermutation von M zum gewünschten Resultat.
Ist das nicht viel komplizierter als notwendig?
Natürlich, hier fehlt das mathematische Verständnis.
Du pöbelst wieder einmal nur herum.
Es geht um Bader. Das sagt alles.
Post by Carsten Schultz
Post by WM
Post by JürgenR
Wenn die Determinante nicht verschwindet, gibt es immer
n Elemente, die alle =/= 0 sind und von denen weder 2 zur
selben Spalte, noch 2 zur selben Reihe gehören.
Die Determinante zu verwenden, hatte der OP ausdrücklich
ausgeschlossen, weil zu kompliziert.
Der Beweis ist ganz simpel, wenn man bedenkt, dass die Matrix, da als
umkehrbar vorausgesetzt, quadratisch sein muss, NxN, also genau so
viele Zeilen wie Spalten besitzen muss, und wenn man sich fragt, was
eine Füllung der Diagonale mit Elementen =/= 0 verhindern kann. Die
Idee, mit Zeilen und Spalten zu jonglieren, löst das Problem sofort.
Wenn es nicht gelingt, die Elemente =/= 0 durch einfache
Zeilenvertauschungen auf die Diagonale zu bringen, dann gibt es immer
ein n, so dass alle Elemente =/= 0 aus n Spalten in nur n-1 Zeilen
existieren.
Das hast Du nun endlich so formuliert, dass es halbwegs verständlich
ist,
Ich habe diesen Gedanken schon x-mal in diesem Thread dargestellt. Er
ist von solcher Schlichtheit, dass ich mir wirklich nicht vorstellen
kann, wie man ihn nicht verstehen kann. Sorry. Geht nicht.
Post by Carsten Schultz
aber dieser Teil müsste natürlich bewiesen werden.
Da müsste überhaupt nichts beweisen werden. Wenn Du das nicht glaubst,
dann konstruiere doch ein Gegenbeispiel!
Habe ich die Richtigkeit der Aussage bezweifelt?
Post by WM
(Natürlich meinen manche
auch, 1 + 1 = 2 müsse bewiesen werden. Diese Ansicht ist falsch. Und
man kann sie auch nicht beweisen. Man kann das höchstens als notwendig
"empfinden".)
Post by Carsten Schultz
Wie jetzt schon
mehrfach erwähnt wurde, ist das aber ein Spezialfall des Heiratssatzes
(mit dem es einer Deiner früheren Aussagen nach nichts zu tun hat), es
ist also richtig.
Man *benötigt* keinen weiteren Satz, um zu erkennen, dass es ein n
gibt, so dass Elemente aus n Spalten nur in n-1 Zeilen sind, wenn die
Diagonalisierung (hier im Sinne der Aufgabe gemeint) nicht gelingt.
Andernfalls würde man sie doch einfach durchführen können!
Da gibt es nichts zu beweisen!
Man diagonalisiert und diagonalisiert und irgendwann geht es nicht
weiter. Warum nicht? Weil die benutzten Elemente in zu wenigen Zeilen
sind! Sonst ginge es ja weiter.
Dass Du das für einen Beweis hältst, glaube ich Dir sogar.
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
WM
2010-11-27 14:27:13 UTC
Permalink
Post by Carsten Schultz
Post by WM
Da müsste überhaupt nichts beweisen werden. Wenn Du das nicht glaubst,
dann konstruiere doch ein Gegenbeispiel!
Habe ich die Richtigkeit der Aussage bezweifelt?
Du hast des öfteren bezweifelt, dass ich überhaupt zum Thema rede.
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
 Wie jetzt schon
mehrfach erwähnt wurde, ist das aber ein Spezialfall des Heiratssatzes
(mit dem es einer Deiner früheren Aussagen nach nichts zu tun hat), es
ist also richtig.
Man *benötigt* keinen weiteren Satz, um zu erkennen, dass es ein n
gibt, so dass Elemente aus n Spalten nur in n-1 Zeilen sind, wenn die
Diagonalisierung (hier im Sinne der Aufgabe gemeint) nicht gelingt.
Andernfalls würde man sie doch einfach durchführen können!
Da gibt es nichts zu beweisen!
Man diagonalisiert und diagonalisiert und irgendwann geht es nicht
weiter. Warum nicht? Weil die benutzten Elemente in zu wenigen Zeilen
sind! Sonst ginge es ja weiter.
Dass Du das für einen Beweis hältst, glaube ich Dir sogar.
Behauptungen, die man nicht widerlegen kann, weil sie offenbar richtig
sind, sind Beweise.

Die Zergliederung von Beweisen in Teilschritte ist nur nach Maßgabe
des Fassungsvermögen des Lesers erforderlich. So gesehen, dürftest Du
Dich eigentlich geschmeichelt fühlen. (Aber ich hätte wirklich nicht
geglaubt, jemand aus Mathematikerkreisen könnte da Einsichtsprobleme
haben.)

Gruß, WM
Carsten Schultz
2010-11-27 15:01:29 UTC
Permalink
Post by WM
Post by Carsten Schultz
Post by WM
Da müsste überhaupt nichts beweisen werden. Wenn Du das nicht glaubst,
dann konstruiere doch ein Gegenbeispiel!
Habe ich die Richtigkeit der Aussage bezweifelt?
Du hast des öfteren bezweifelt, dass ich überhaupt zum Thema rede.
Du hast auch viel nebensächliches in diesem Thread geschrieben.
Post by WM
Post by Carsten Schultz
Post by WM
Post by Carsten Schultz
Wie jetzt schon
mehrfach erwähnt wurde, ist das aber ein Spezialfall des Heiratssatzes
(mit dem es einer Deiner früheren Aussagen nach nichts zu tun hat), es
ist also richtig.
Man *benötigt* keinen weiteren Satz, um zu erkennen, dass es ein n
gibt, so dass Elemente aus n Spalten nur in n-1 Zeilen sind, wenn die
Diagonalisierung (hier im Sinne der Aufgabe gemeint) nicht gelingt.
Andernfalls würde man sie doch einfach durchführen können!
Da gibt es nichts zu beweisen!
Man diagonalisiert und diagonalisiert und irgendwann geht es nicht
weiter. Warum nicht? Weil die benutzten Elemente in zu wenigen Zeilen
sind! Sonst ginge es ja weiter.
Dass Du das für einen Beweis hältst, glaube ich Dir sogar.
Behauptungen, die man nicht widerlegen kann, weil sie offenbar richtig
sind, sind Beweise.
Der Heiratssatz ist plausibel und richtig, aber nicht offensichtlich.

Andererseits gibt es auch viele falsche Aussagen, die Du für offenbar
richtig hältst.
Post by WM
Die Zergliederung von Beweisen in Teilschritte ist nur nach Maßgabe
des Fassungsvermögen des Lesers erforderlich. So gesehen, dürftest Du
Dich eigentlich geschmeichelt fühlen. (Aber ich hätte wirklich nicht
geglaubt, jemand aus Mathematikerkreisen könnte da Einsichtsprobleme
haben.)
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
Alois Steindl
2010-11-29 10:03:27 UTC
Permalink
Post by WM
Da müsste überhaupt nichts beweisen werden. Wenn Du das nicht glaubst,
dann konstruiere doch ein Gegenbeispiel! (Natürlich meinen manche
auch, 1 + 1 = 2 müsse bewiesen werden. Diese Ansicht ist falsch. Und
man kann sie auch nicht beweisen. Man kann das höchstens als notwendig
"empfinden".)
Herrlich!
Mit dieser Argumentation hätte sich Wiles jahrelange Mühen erspart:
"Wer's nicht glaubt, soll ein Gegenbeispiel bringen!"

Hätte Fermat allerdings auch schon so agiert, dann hätte der Beweis auf
den Rand des Manuskripts gepasst und niemand hätte sich am Problem die
Zähne ausgepissen.

Jetzt bleibt nur noch abzuwarten, ob WM einen entsprechenden Beweis der
Goldbachvermutung einreicht.

Alois
--
Alois Steindl, Tel.: +43 (1) 58801 / 32558
Inst. for Mechanics and Mechatronics Fax.: +43 (1) 58801 / 32598
Vienna University of Technology, A-1040 Wiedner Hauptstr. 8-10
Roland Franzius
2010-11-29 12:05:16 UTC
Permalink
Post by Alois Steindl
Post by WM
Da müsste überhaupt nichts beweisen werden. Wenn Du das nicht glaubst,
dann konstruiere doch ein Gegenbeispiel! (Natürlich meinen manche
auch, 1 + 1 = 2 müsse bewiesen werden. Diese Ansicht ist falsch. Und
man kann sie auch nicht beweisen. Man kann das höchstens als notwendig
"empfinden".)
Herrlich!
"Wer's nicht glaubt, soll ein Gegenbeispiel bringen!"
Hätte Fermat allerdings auch schon so agiert, dann hätte der Beweis auf
den Rand des Manuskripts gepasst und niemand hätte sich am Problem die
Zähne ausgepissen.
Jetzt bleibt nur noch abzuwarten, ob WM einen entsprechenden Beweis der
Goldbachvermutung einreicht.
Wenn also bei einem quadratischen Gleichungssystem in Zeile z_n die
Variable x_n nicht vorkommt, so vertauscht man die Zeile n mit einer
anderen Zeile z_m, so dass die Variable x_m in Zeile n auftritt und x_n
in Zeile m auftritt.

Geht das nicht, so existieren mindestens zwei Zeilen m und n, die beide
frei von x_m und x_m sind. Dann kann man durch Zeilen- und
Spaltenvertauschungen die Matrix auf Blockdiagonalform mit
2x2-Nullmatrix oben links bringen. Dann verschwinden alle Minoren. Nur
dieses Lemma ist beweiswürdig im Sinne einer Übungsaufgabe über den
Entwicklungssatz, insbesondere natürlich für allgemeinere
Koeffizientenklassen. Ansatzweise würde man einfach sagen, die Abbildung
ist im Unterraum (x_m,x_n) die Nullabbildung. Betrachtet als Koeffizent
der Volumenform des n-dimensionalen Raumes muss sie dann verschwinden.

Diese halbwegs einsichtigen Tatsachen, die zB Euler oder Jacobi gar
nicht erst expliziert haben würden, möchte man also als ein naives Gemüt
mit dem Beweis von Wiles gleichsetzen.

Insbesondere die niveaumäßig fixierte, ewig pepertuierte Lehrtätigkeit
sieht in derlei Beweisen ihre Erfüllung während der normale Mensch in
der Forschungarbeit Wert auf die Vermeidung solcher Beweise durch
Vertrauen auf die Intelligenz des Lesers, zarte Hinweise oder
Quellenbelege legt.
--
Roland Franzius
Ralf Bader
2010-11-30 03:36:07 UTC
Permalink
Post by Roland Franzius
Post by Alois Steindl
Post by WM
Da müsste überhaupt nichts beweisen werden. Wenn Du das nicht glaubst,
dann konstruiere doch ein Gegenbeispiel! (Natürlich meinen manche
auch, 1 + 1 = 2 müsse bewiesen werden. Diese Ansicht ist falsch. Und
man kann sie auch nicht beweisen. Man kann das höchstens als notwendig
"empfinden".)
Herrlich!
"Wer's nicht glaubt, soll ein Gegenbeispiel bringen!"
Hätte Fermat allerdings auch schon so agiert, dann hätte der Beweis auf
den Rand des Manuskripts gepasst und niemand hätte sich am Problem die
Zähne ausgepissen.
Jetzt bleibt nur noch abzuwarten, ob WM einen entsprechenden Beweis der
Goldbachvermutung einreicht.
Wenn also bei einem quadratischen Gleichungssystem in Zeile z_n die
Variable x_n nicht vorkommt, so vertauscht man die Zeile n mit einer
anderen Zeile z_m, so dass die Variable x_m in Zeile n auftritt und x_n
in Zeile m auftritt.
Geht das nicht, so existieren mindestens zwei Zeilen m und n, die beide
frei von x_m und x_m sind. Dann kann man durch Zeilen- und
Spaltenvertauschungen die Matrix auf Blockdiagonalform mit
2x2-Nullmatrix oben links bringen. Dann verschwinden alle Minoren. Nur
dieses Lemma ist beweiswürdig im Sinne einer Übungsaufgabe über den
Entwicklungssatz, insbesondere natürlich für allgemeinere
Koeffizientenklassen. Ansatzweise würde man einfach sagen, die Abbildung
ist im Unterraum (x_m,x_n) die Nullabbildung. Betrachtet als Koeffizent
der Volumenform des n-dimensionalen Raumes muss sie dann verschwinden.
Diese halbwegs einsichtigen Tatsachen, die zB Euler oder Jacobi gar
nicht erst expliziert haben würden, möchte man also als ein naives Gemüt
mit dem Beweis von Wiles gleichsetzen.
Insbesondere die niveaumäßig fixierte, ewig pepertuierte Lehrtätigkeit
sieht in derlei Beweisen ihre Erfüllung während der normale Mensch in
der Forschungarbeit Wert auf die Vermeidung solcher Beweise durch
Vertrauen auf die Intelligenz des Lesers, zarte Hinweise oder
Quellenbelege legt.
Daß in Alois Steindls Bemerkung nicht die relative Flachheit dieser
Matrizenaufgabe oder auch des Heiratssatzes mit einem Gebirge wie dem
Wiles-Taylorschen Beweis gleichgesetzt wird, sondern diese im Gegenteil auf
den gigantischen Komplexitätsunterschied zwischen diesen beiden Beweisen
abhebt, der aber gerade bei der Mückenheimschen Methode, zutreffende
Allaussagen durch eine nichtssagende Floskel zu "beweisen", unter den Tisch
fällt, dies also könnte man auch dann erkennen, wenn man gelegentlich m
und n verwechselt.
Roland Franzius
2010-11-30 06:58:33 UTC
Permalink
Post by Ralf Bader
Post by Roland Franzius
Post by Alois Steindl
Post by WM
Da müsste überhaupt nichts beweisen werden. Wenn Du das nicht glaubst,
dann konstruiere doch ein Gegenbeispiel! (Natürlich meinen manche
auch, 1 + 1 = 2 müsse bewiesen werden. Diese Ansicht ist falsch. Und
man kann sie auch nicht beweisen. Man kann das höchstens als notwendig
"empfinden".)
Herrlich!
"Wer's nicht glaubt, soll ein Gegenbeispiel bringen!"
Hätte Fermat allerdings auch schon so agiert, dann hätte der Beweis auf
den Rand des Manuskripts gepasst und niemand hätte sich am Problem die
Zähne ausgepissen.
Jetzt bleibt nur noch abzuwarten, ob WM einen entsprechenden Beweis der
Goldbachvermutung einreicht.
Wenn also bei einem quadratischen Gleichungssystem in Zeile z_n die
Variable x_n nicht vorkommt, so vertauscht man die Zeile n mit einer
anderen Zeile z_m, so dass die Variable x_m in Zeile n auftritt und x_n
in Zeile m auftritt.
Geht das nicht, so existieren mindestens zwei Zeilen m und n, die beide
frei von x_m und x_m sind. Dann kann man durch Zeilen- und
Spaltenvertauschungen die Matrix auf Blockdiagonalform mit
2x2-Nullmatrix oben links bringen. Dann verschwinden alle Minoren. Nur
dieses Lemma ist beweiswürdig im Sinne einer Übungsaufgabe über den
Entwicklungssatz, insbesondere natürlich für allgemeinere
Koeffizientenklassen. Ansatzweise würde man einfach sagen, die Abbildung
ist im Unterraum (x_m,x_n) die Nullabbildung. Betrachtet als Koeffizent
der Volumenform des n-dimensionalen Raumes muss sie dann verschwinden.
Diese halbwegs einsichtigen Tatsachen, die zB Euler oder Jacobi gar
nicht erst expliziert haben würden, möchte man also als ein naives Gemüt
mit dem Beweis von Wiles gleichsetzen.
Insbesondere die niveaumäßig fixierte, ewig pepertuierte Lehrtätigkeit
sieht in derlei Beweisen ihre Erfüllung während der normale Mensch in
der Forschungarbeit Wert auf die Vermeidung solcher Beweise durch
Vertrauen auf die Intelligenz des Lesers, zarte Hinweise oder
Quellenbelege legt.
Daß in Alois Steindls Bemerkung nicht die relative Flachheit dieser
Matrizenaufgabe oder auch des Heiratssatzes mit einem Gebirge wie dem
Wiles-Taylorschen Beweis gleichgesetzt wird, sondern diese im Gegenteil auf
den gigantischen Komplexitätsunterschied zwischen diesen beiden Beweisen
abhebt, der aber gerade bei der Mückenheimschen Methode, zutreffende
Allaussagen durch eine nichtssagende Floskel zu "beweisen", unter den Tisch
fällt, dies also könnte man auch dann erkennen, wenn man gelegentlich m
und n verwechselt.
Bei den Dauergesprächspartnern von WM gestatte ich mir, fehlende
Intelligenz gepaart mit Langeweile als Normalzustand anzunehmen.

Ob der Augsburger das Wort Beweis oder Steindl das Wort Wiles benutzt,
bewegt sich auf etwa demselben Niveau, dh sie haben nicht die geringste
Ahnung von der Materie. Im letzteren Fall kann man allenfalls annehmen,
das das die meisten betrifft, im ersteren Fall eben nur diejenigen, die
ihre Übungsaufgaben im Grundkurs nie selbständig gelöst haben.
--
Roland Franzius
Loading...