Determinante Adjazenzmatrix < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:19 Mi 16.05.2012 | | Autor: | Cool-Y |
| Aufgabe | | Sei $n [mm] \geq [/mm] 2$ und [mm] $I=\{ M \subset \{1, \ldots , n\}: M \neq \emptyset \}$. [/mm] Dann betrachte die Matrix [mm] $A:=(a_{ij})_{i,j \in I}$ [/mm] mit [mm] $a_{ij}=0$ [/mm] falls $i [mm] \cap [/mm] j = [mm] \emptyset$ [/mm] und [mm] $a_{ij}=1$ [/mm] sonst. Dann gilt [mm] $\det [/mm] (A) =-1$. |
Liebe Matheräumler,
obiges ist keine Übungsaufgabe, die mir gestellt wurde, sondern eine Vermutung meinerseits. Ich habe sie für $n [mm] \leq [/mm] 8$ schon überprüft. Leider sehe ich keinen kurzen Beweis, aber ich denke diese Matrix wurde sicher schon von irgendjemandem untersucht. Ich wäre dankbar, falls mir jemand einen Tipp oder einen Literaturhinweis geben könnte.
Viele Grüße,
Thomas
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:52 Do 17.05.2012 | | Autor: | Cool-Y |
Also ist nicht mehr nötig zu reagieren. Habe einen Beweis gefunden.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:26 Do 17.05.2012 | | Autor: | Cool-Y |
Auf Nachfrage hier noch eine Beweisskizze:
Das ganze funktioniert mit vollständiger Induktion:
Sei [mm] A_n [/mm] eben diese Adjazenzmatrix zur Zahl [mm] n [/mm]. Sortiert man nun die Zeilen und Spalten geschickt, so erhält man:
[mm] A_{n+1} = \begin{pmatrix} A_n & 0 & A_n \\
0 & 1 & 1 \\
A_n & 1 & 1 \end{pmatrix} [/mm].
Mit elementaren Zeilen- und Spaltenumformungen ehält man:
[mm] \begin{pmatrix} A_n & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & -A_n \end{pmatrix} [/mm].
|
|
|
|
