Ist B eine Inzidenzmatrix eines Graphen G = (V, E) mit |V | = |E|, so gilt det(B) = 0.

Question

Aufgabe: Sei G = (V, E) ein gerichteter Graph ohne Schleifen. Zeigen Sie: Ist B eine Inzidenzmatrix eines Graphen G = (V, E) mit |V | = |E|, so gilt det(B) = 0.

Problem/Ansatz:

Es liegt eine n×n Matrix vor die insgesamt jeweils n mal eine 1 und n mal eine -1 enthält und der Rest sind dann 0er. Ausserdem steht dann in jeder Spalte der Matrix eine 1 und eine -1. Wenn ich nun zeigen kann, das mindestens eine der n Spalten linear abhängig ist, dann gilt Rang(B)<n und das bedeutet, dass det(B)=0 und dann wäre ich fertig, aber beim letzten Schritt fehlt mir die Beweisidee.

Ist das soweit richtig, oder ist der Ansatz komplett falsch, bzw. wie kann ich den letzten Schritt noch beweisen?

Answer 1

Hallo,

betrachte die transportierte Matrix. Diese hat dann in jeder Zeile genau eine 1 und eine -1. Wenn v ein Vektor mit lauter 1 ist, dann gilt \(A^Tv=0\). Damit hat die transportierte Matrix die Determinante 0  damit ebenso A.

Comments

Hallo,

warum folgt aus A^Tv=0 für diesen konkreten Vektor dann, dass die Determinante von A 0 ist?

---

Weil v damit ein nicht-Null-Emelement des Kerns von A^T ist, also A^T Singular ist.

---

Achso stimmt, das hatte ich übersehen, danke für die Antwort.