Es sein eine beliebige zweistellige Relation zwischen den Elementen einer endlichen Menge und den Elementen einer endlichen Menge . Weiterhin sei eine beliebige zweielementige Menge, deren Elemente man als Wahrheitswerte interpretiert, also etwa für den Booleschen Halbring. Dann versteht man unter der Inzidenzmatrix von die -Matrix über mit genau dann, wenn das Paar in der Relation enthalten ist. Dann ist die zu transponierte Matrix genau die Inzidenzmatrix der zu inversen Relation . Weiterhin ist genau dann eine Funktion, wenn in jeder Zeile von genau eine Koordinate den Wert 1 hat. Diese Funktion ist genau dann injektiv (surjektiv), wenn in jeder Spalte von höchstens (mindestens) eine Koordinate den Wert 1 besitzt.
Für wird quadratisch und offensichtlich ist genau dann symmetrisch, wenn dies auf zutrifft. Weiterhin ist genau dann reflexiv (irreflexiv), wenn die Hauptdiagonalelemente von 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.