|
|
| Autor |
Nachricht |
Xardas
Full Member
Anmeldungsdatum: 09.05.2005
Beiträge: 118
|
 Verfasst am: 08 Jan 2012 - 21:27:51 Titel: Determinante von großen Matrizen berechnen. |
|
|
Hallo,
ich habe ein "kleines" Problem
Gegeben ist eine quadratische Matrix aus F2^(n x n). n=2012
Die Matrix sieht wie die Einheitsmatrix aus. Nur dass Auf der Diagonalen die 0en stehen und sonst nur 1en.
Wie geh ich da jetzt vor?
Mit LaPlace bin ich wahrscheinlich in in einem Jahr noch nicht fertig.
Und mit Gauß 2012 Zeilen in Stufenform bringen ist glaube ich auch etwas aufwendiger.
Hat ihr einen Tipp, wie ich da anfangen soll? |
|
 |
Thebozz-mismo
Senior Member
Anmeldungsdatum: 13.08.2006
Beiträge: 554
|
| Verfasst am: 08 Jan 2012 - 21:53:04 Titel: |
|
|
Hallo
Ich hab zwar keine Lösung parat, aber vielleicht eine Idee.
Berechne doch mal für kleine n, also (n=1,2,3,4,5) die Determinante. Vielleicht kann man eine allgemeingültige Formel herleiten(eventuell für gerade und ungerade unterscheiden) und diese dann per vollständige Induktion beweisen.
Vielleicht kann man auch die Matrix in Dreiecksform bringen und dann haste auch leicht die Determinante.
Du kannst ja mal deine Ideen bzw. Ansätze posten.
Eine Frage habe ich noch. Was bedeutet F^2, bzw. um welche Matrizen handelt es sich(um invertierbare, etc. )?
Vielleicht fällt mir morgen noch was Besseres dazu ein.
Gruß
TheBozzmismo
_________________
Hab einen schönen Tag!
TheBozz-mismo |
|
|
Ol@f
Senior Member
Anmeldungsdatum: 05.09.2007
Beiträge: 367
|
| Verfasst am: 08 Jan 2012 - 21:56:20 Titel: |
|
|
Rechne mal die Determinante von einer 2x2, 4x4 Matrix der gleichen Form aus. Am besten mit dem Gauß-Algorithmus. Dann wirst du mit Sicherheit ein Muster erkennen und sehen wie es eben bei einer 2012x2012 Matrix funktioniert.
Edit. Zu langsam :I Ich nehme ma an, dass mit F2, der entsprechende Körper gemeint ist.
_________________
Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch. (Bertrand Russell) |
|
|
Xardas
Full Member
Anmeldungsdatum: 09.05.2005
Beiträge: 118
|
| Verfasst am: 08 Jan 2012 - 22:06:50 Titel: |
|
|
F_" ist ein Körper mit zwei Elementen {0,1}.
Als für Matrizen mit
det(n=2) = 1
det(n=3) = 0
det(n=4) = 1
Also ich geh davon aus das, es immer so weiter geht. |
|
|
Ol@f
Senior Member
Anmeldungsdatum: 05.09.2007
Beiträge: 367
|
| Verfasst am: 08 Jan 2012 - 22:22:08 Titel: |
|
|
Jep, sollte passen. Hast du das Muster erkannt? Ich persönlich fand es für n=6 sehr eindeutig. Du musst ja letzten Endes nur zeigen, dass die Matrix vollen Rang hat, da die Determinante, dann 1 sein muss. Außerdem kannst du beliebig Zeilen tauschen ohne, dass sich die Determinante ändert.
Kleiner Tipp: Du musst am Anfang geschickt tauschen, dann paar Zeilen addieren, dann wieder geschickt tauschen, und nochmal Zeilen addieren. Dann bist du schon fertig.
_________________
Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch. (Bertrand Russell) |
|
|
Xardas
Full Member
Anmeldungsdatum: 09.05.2005
Beiträge: 118
|
| Verfasst am: 08 Jan 2012 - 22:48:56 Titel: |
|
|
Erstmal Danke für die Antworten.
Das Problem ist, ich erkenne da kein Muster.
Bis auf dass für ungerade n die Determinante 0 und für gerade n 1 ist.
Aber ich wüsste nicht was ich da tauschen soll.
Also bei n=3 sieht man ja, dass die Vektoren linear abhängig sind.
Also kann der rang da nicht voll sein.
Hmm....bei n=6 seh auch kein Muster.
Was bringt mir das Zeilen tauschen?
Okay. die Determinante bleibt gleich, aber am einfachsten wäre es, ich könnte die Matrix in eine Dreiecksform bringen.
Ich versuch da mal ein Muster zu finden. |
|
|
Ol@f
Senior Member
Anmeldungsdatum: 05.09.2007
Beiträge: 367
|
| Verfasst am: 08 Jan 2012 - 22:56:50 Titel: |
|
|
| Xardas hat folgendes geschrieben: |
Hmm....bei n=6 seh auch kein Muster.
Was bringt mir das Zeilen tauschen?
Okay. die Determinante bleibt gleich, aber am einfachsten wäre es, ich könnte die Matrix in eine Dreiecksform bringen.
|
Ja, das ist das Ziel. Übrigens lass n=3 bzw. alle ungeraden n's weg. Die sind für die Aufgabe irrelavant.
Hier noch der erste Schritt... Ich hoffe, ich verrate da nicht schon zu viel.
| Code: | 1 1 1 1 1 0
1 1 1 1 0 1
1 1 1 0 1 1
1 1 0 1 1 1
1 0 1 1 1 1
0 1 1 1 1 1
|
_________________
Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch. (Bertrand Russell) |
|
|
cyrix42
God of Posting
Anmeldungsdatum: 14.08.2006
Beiträge: 21523
|
| Verfasst am: 08 Jan 2012 - 23:06:09 Titel: |
|
|
Man kann ziemlich einfach zeigen, dass die Matrix regulär ist:
Wählt man (n=2012 ist gerade) eine ungerade Anzahl an Spaltenvektoren aus und addiert diese, erhält man einen Vektor versch. vom Nullvektor. Dazu betrachte man eine Komponente i, die verschieden von jeder "Spaltennummer" der ausgewählten Matrix ist. Dort wird dann ungerade oft 1 addiert, ist also 1.
Wählt man dagegen eine gerade Anzahl > 0 an Spaltenvektoren aus, betrachte man eine Komponente, die der Spalten-nr. einer ausgewählten Spalte entspricht. Dort wird einmal 0 und ungerade oft 1 addiert, d.h. die Summe dieser Spalten ist wieder versch. vom Nullvektor, d.h. die Matrix ist regulär, hat also Determinabte 1.
Bemerkung: Analog kann zeigen, dass für alle geraden n die Matrix vollen Rang n; und für ungerade n-1 besitzt.
Cyrix
_________________
Die Wurzel
-- |
|
|
Xardas
Full Member
Anmeldungsdatum: 09.05.2005
Beiträge: 118
|
| Verfasst am: 08 Jan 2012 - 23:28:21 Titel: |
|
|
| Ol@f hat folgendes geschrieben: |
| Code: |
1 1 1 1 1 0
1 1 1 1 0 1
1 1 1 0 1 1
1 1 0 1 1 1
1 0 1 1 1 1
0 1 1 1 1 1
|
|
Okay...soweit bin ich inzwischen auch.
Und jetzt würde ich einfach die Zeilen irgendwie so addieren, dass ich unterhalb der Diagonalen nur noch 0en stehen habe. Aber dazu hätte ich die Zeilen ja nicht erst tauschen müssen. 
Ich seh da einfach nichts.
| Code: |
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0
1 1 1 0 1 1 Z2+Z5 1 1 1 0 1 1 Z3+Z4 0 0 1 1 0 0 Z4+Z5+Z6 0 0 1 1 0 0
0 1 0 1 1 1 -----> 1 1 0 1 1 1 -----> 1 1 0 1 1 1 -----> 0 0 0 1 1 1
1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1
0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1
|
Oder wie? Ich meine Wenn ich dass jetzt für 2012 Zeilen mache...naja dauert das auch etwas länger.
Oder wie hast du das gemacht? |
|
|
Xardas
Full Member
Anmeldungsdatum: 09.05.2005
Beiträge: 118
|
| Verfasst am: 08 Jan 2012 - 23:39:24 Titel: |
|
|
| cyrix42 hat folgendes geschrieben: | Man kann ziemlich einfach zeigen, dass die Matrix regulär ist:
Wählt man (n=2012 ist gerade) eine ungerade Anzahl an Spaltenvektoren aus und addiert diese, erhält man einen Vektor versch. vom Nullvektor. Dazu betrachte man eine Komponente i, die verschieden von jeder "Spaltennummer" der ausgewählten Matrix ist. Dort wird dann ungerade oft 1 addiert, ist also 1.
Wählt man dagegen eine gerade Anzahl > 0 an Spaltenvektoren aus, betrachte man eine Komponente, die der Spalten-nr. einer ausgewählten Spalte entspricht. Dort wird einmal 0 und ungerade oft 1 addiert, d.h. die Summe dieser Spalten ist wieder versch. vom Nullvektor, d.h. die Matrix ist regulär, hat also Determinabte 1.
Bemerkung: Analog kann zeigen, dass für alle geraden n die Matrix vollen Rang n; und für ungerade n-1 besitzt.
Cyrix |
Wie hab ich das zu verstehen?
| Code: |
1 1 1 1 1 0
1 1 1 1 0 1
1 1 1 0 1 1
1 1 0 1 1 1
1 0 1 1 1 1
0 1 1 1 1 1
|
Also soll ich jetzt hier die 6 Spalten vektoren addieren?
Dann kommt da der Vektor [1 1 1 1 1 1] bei raus. |
|
|
Ol@f
Senior Member
Anmeldungsdatum: 05.09.2007
Beiträge: 367
|
| Verfasst am: 08 Jan 2012 - 23:43:22 Titel: |
|
|
Hm, ich versteh nicht, warum du da so umständlich rumrechnest. Du willst ja, dass in der k-Spalte alle Einträge gleich Null sind, deren Zeilenindex größer als der Spaltenindex ist.
Konkret: Rechne 1. Zeile + 2 Zeile, 1Z+3Z,...,1Z+5Z
| Code: |
1 1 1 1 1 0
0 0 0 0 1 1
0 0 0 1 0 1
0 0 1 0 0 1
0 1 0 0 0 1
0 1 1 1 1 1
|
Jetzt haben wir schonmal die erste Spalte so, wie wir es wollen. Wie kriegen wir das jetzt für die restlichen hin?
_________________
Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch. (Bertrand Russell) |
|
|
Xardas
Full Member
Anmeldungsdatum: 09.05.2005
Beiträge: 118
|
| Verfasst am: 09 Jan 2012 - 00:06:12 Titel: |
|
|
Warum kompliziert? Keine Ahnung. Weil ich die "einfach" Variante einfach nicht gesehen habe.
Ich seh da auch kein System. sorry.
Also ich würde bei der zweiten Spalte...keine Ahnung. Z5+Z6 und dann Z2 und Z6 tauschen. Aber das ist wohl auch wieder zu kompliziert 
| Code: |
1 1 1 1 1 0
0 1 1 1 1 1
0 0 0 1 0 1
0 0 1 0 0 1
0 0 1 1 1 0
0 0 0 0 1 1
|
|
|
|
Ol@f
Senior Member
Anmeldungsdatum: 05.09.2007
Beiträge: 367
|
| Verfasst am: 09 Jan 2012 - 00:10:44 Titel: |
|
|
| Xardas hat folgendes geschrieben: |
Also ich würde bei der zweiten Spalte...keine Ahnung. Z5+Z6 und dann Z2 und Z6 tauschen. Aber das ist wohl auch wieder zu kompliziert
|
Z5+Z6 klingt doch schonmal gut. Die anderen 1 in der letzten Zeile kriegst du analog weg. Also
| Code: |
1 1 1 1 1 0
0 0 0 0 1 1
0 0 0 1 0 1
0 0 1 0 0 1
0 1 0 0 0 1
0 0 0 0 0 [color=red]1[/color]
|
Beim roten Eintrag solltest du dir klar machen, warum das so ist.
Was musst du nun machen?
Edit. Hm, das rot geht nicht im Code
_________________
Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch. (Bertrand Russell) |
|
|
Xardas
Full Member
Anmeldungsdatum: 09.05.2005
Beiträge: 118
|
| Verfasst am: 09 Jan 2012 - 00:21:13 Titel: |
|
|
Okay. Nachdem ich Z5+ Z6 gerchnet habe, addiere ich Z2...Z5 zu Z6.
| Code: | 1 1 1 1 1 0
0 0 0 0 1 1
0 0 0 1 0 1
0 0 1 0 0 1
0 1 0 0 0 1
0 0 0 0 0 1 |
Und jetzt kann ich doch einfach Z6 zu allen anderen Zeilen dazu addieren
| Code: |
1 1 1 1 1 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0
0 0 0 0 0 1 |
Und nun kann ich die Zeilen vertauschen. Und dann ist die Determinante das Produkt der Hauptdiagonale. |
|
|
Ol@f
Senior Member
Anmeldungsdatum: 05.09.2007
Beiträge: 367
|
| Verfasst am: 09 Jan 2012 - 00:31:55 Titel: |
|
|
| Zitat: | | Und jetzt kann ich doch einfach Z6 zu allen anderen Zeilen dazu addieren. |
Der Schritt ist überflüssig, wir brauchen doch nur eine obere Dreiecksmatrix. Sonst aber richtig. Weißt du nun wie es für n=2012 oder allgemein für gerade n geht?
_________________
Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch. (Bertrand Russell) |
|
|
Xardas
Full Member
Anmeldungsdatum: 09.05.2005
Beiträge: 118
|
| Verfasst am: 09 Jan 2012 - 00:42:18 Titel: |
|
|
Ehrlich gesagt nicht wirklich...
Aber ich versuch es einfach mal.
Vertausche ich erst die Zeilen
| Code: | 1 2 3 ... n
n 2011 2010 ... 1
|
Als nächstes addiere ich die 1. Zeile zu den Zeilen 2...n.
Dann addiere ich zu der vorletzten Zeile die letze hinzu.
Nun noch Z2...Z_(n-1) zu Z_n addieren.
Dadurch ensteht dann die obere Dreiecksmatrix und ich kann die Determinante berechnen. |
|
|
Ol@f
Senior Member
Anmeldungsdatum: 05.09.2007
Beiträge: 367
|
| Verfasst am: 09 Jan 2012 - 00:46:25 Titel: |
|
|
| Xardas hat folgendes geschrieben: | Ehrlich gesagt nicht wirklich...
Aber ich versuch es einfach mal.
Vertausche ich erst die Zeilen
| Code: | 1 2 3 ... n
n 2011 2010 ... 1
|
Als nächstes addiere ich die 1. Zeile zu den Zeilen 2...n.
Dann addiere ich zu der vorletzten Zeile die letze hinzu.
Nun noch Z2...Z_(n-1) zu Z_n addieren. Hier musst du noch erklären, warum in der 2011 Zeile und Spalte eine 1 und nicht eine 0 steht. Danach das Tauschen nicht vergessen..
Dadurch ensteht dann die obere Dreiecksmatrix und ich kann die Determinante berechnen. |
Schreib es dir doch mal im Allgemeinen Fall doch mal auf und mache die gleichen Umformungen...
_________________
Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch. (Bertrand Russell) |
|
|
Xardas
Full Member
Anmeldungsdatum: 09.05.2005
Beiträge: 118
|
| Verfasst am: 09 Jan 2012 - 01:26:09 Titel: |
|
|
Dann probier ich das nochmal:
Originalmatrix: n ist gerade
| Code: |
0 1 . . . 1
1 0 .
. .
. .
. 0 .
1 . . . 1 0
|
Schritt 1: Vertausche Zeilen
| Code: |
1 2 3 ... n
n 2011 2010 ... 1 |
| Code: |
1 1 . . . 0
1 0 1
. .
. .
1 0 1
0 . . . 1 1
|
2. Schritt Zu Z_i wir Z_1 addiert. Wobei i=2 bis (n-1) ist.
In der ersten Zeile werden dadurch alle Einträge unter der führenden 1 zu 0.
| Code: |
1 . . . 1 0
0 1 1
. . .
. 1 .
0 1 . . . 1
|
3. Schritt: Addieren zu Z_n Z_i, wobei i jeweils wie 2 bis (n-1) ist.
Da in der Spalte n eine gerade Anzahl von 1en addiert wird. bleibt der Eintrag in der letzten Zeile erhalten. Bei den anderen Einträgen wird jeweils eine 1 addiert, daher werden die Einträge zu 0.
| Code: |
1 . . . 1 0
0 1 1
. . .
. 1 .
0 . . . 0 1
|
4. Schritt: Vertauschen der Zeilen 2 bis (n-1)
| Code: |
2 ... n-1
n-1 ... 2
|
Dadurch erhält man die obere Dreiecksmatrix. Auf dessen Hauptdiagonalen stehen als Einträge nur noch 1en.
Daher ist die Determinante = 1 |
|
|
|
Home
FAQ
Regeln
Suchen
Registrieren
Login
