Inzidenzmatrizen


Es sein R eine beliebige zweistellige Relation zwischen den Elementen x einer endlichen Menge X = {x1,...,xm } und den Elementen y einer endlichen Menge Y = {y1,...,yn }. Weiterhin sei B eine beliebige zweielementige Menge, deren Elemente man als Wahrheitswerte interpretiert, also etwa B = {0,1} für den Booleschen Halbring. Dann versteht man unter der Inzidenzmatrix von R die m x n-Matrix AR = (ai,j ) über B mit ai,j = 1 genau dann, wenn das Paar (xi,yj ) in der Relation R enthalten ist. Dann ist die zu AR transponierte Matrix ART genau die Inzidenzmatrix der zu R inversen Relation R-1. Weiterhin ist R genau dann eine Funktion, wenn in jeder Zeile von AR genau eine Koordinate den Wert 1 hat. Diese Funktion R ist genau dann injektiv (surjektiv), wenn in jeder Spalte von AR höchstens (mindestens) eine Koordinate den Wert 1 besitzt.

Für X = Y wird AR quadratisch und offensichtlich ist R genau dann symmetrisch, wenn dies auf AR zutrifft. Weiterhin ist R genau dann reflexiv (irreflexiv), wenn die Hauptdiagonalelemente von AR alle gleich 1 (gleich 0) sind.


Die Einführung von Inzidenzmatrizen über dem Booleschen Halbring (oder geeigneten anderen algebraischen Strukturen) erlaubt es, Matrizenoperationen bei der Betrachtung von Relationen über endlichen Mengen heranzuziehen. Dadurch wird es möglich, viele Fragestellungen über solche Relationen algorithmisch zu entscheiden.