Encyclopedia > Incidence algebra

  Article Content

Incidence algebra

A partially ordered set is "locally finite" precisely if every closed interval [a, b] within it is finite. For every locally finite poset and every field of scalars there is an incidence algebra, an associative algebra defined as follows. The members of the incidence algebra are the functions f assigning to each interval [a, b] a scalar f(a, b). On this underlying set one defines addition and scalar multiplication pointwise, and "multiplication" in the incidence algebra is a convolution defined by

<math>(f*g)(a, b)=\sum_{a\leq x\leq b}f(a, x)g(x, b).</math>

The multiplicative identity element of the incidence algebra is

\delta(a, b) = \left\{ \begin{matrix} \,1, & \mbox{if } a=b \\ \,0, & \mbox{if } a<b \end{matrix} \right. </math>

An incidence algebra is finite-dimensional if and only if the underlying poset is finite.

The ζ function of an incidence algebra is the constant function ζ(a, b)=1 for every interval [a, b]. One can show that that element is invertible in the incidence algebra (with respect to the convolution defined above). (Generally, a member h of the incidence algebra is invertible if and only if h(x, x) ≠ 0 for every x.) Its multiplicative inverse is the Möbius function μ(a, b); every value of μ(a, b) is an integral multiple of 1 in the base field.


In case the locally finite poset is the set of all positive integers ordered by divisibility, then its Möbius function is μ(a, b)=μ(b/a), where the second "μ" is the classic Möbius function introduced into number theory in the 19th century.

The locally finite poset of all finite subsets of some set E is ordered by inclusion. Here the Möbius function is

whenever S and T are finite subsets of E with ST.

The Möbius function on the set of non-negative integers with their usual order is

1 & \mbox{if }x=y,\qquad \\ -1 & \mbox{if }x+1=y, \\ 0 & \mbox{if }x+1<y. \end{matrix}\right.</math> This corresponds to the sequence (1, -1, 0, 0, 0, ... ) of coefficients of the formal power series 1 - z, and the ζ function in this case corresponds to the sequence of coefficients (1, 1, 1, 1, ... ) of the formal power series (1 - z)-1 = 1 + z + z2 + z3 + .... The δ function in this incidence algebra similarly corresponds to the formal power series 1.

Euler characteristic

A poset is bounded if it has smallest and largest elements, which we call 0 and 1 respectively (not to be confused with the zero and the one of the base field, which, in this paragraph, we take to be Q). The Euler characteristic of a bounded finite poset is μ(0,1); it is always an integer. This concept is related to the classic Euler characteristic.


Incidence algebras of locally finite posets were treated in a number of papers of Gian-Carlo Rota beginning in 1964, and by many later combinatorialists.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Indian reservation

... it is not subject to state law and therefore on many reservations, there are casinos. Indian Reservations in the United States (incomplete} Quinault Indian ...

This page was created in 36.8 ms