Incidence algebra

From Wikipedia, the free encyclopedia

In order theory, a field of mathematics, a locally finite partially ordered set is one for which every closed interval

[a, b] = {x : a ≤ x ≤ b}

within it is finite. For every locally finite poset and every commutative ring with unity (the ring 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

$(f*g)(a, b)=\sum_{a\leq x\leq b}f(a, x)g(x, b).$

This is analogous to the group algebra; indeed, both the group algebra and the incidence algebra are special cases of a categorical algebra, defined analogously; groups and posets being special kinds of categories.

The multiplicative identity element of the incidence algebra is the delta function, defined by

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

An incidence algebra is finite-dimensional if and only if the underlying partially ordered set is finite.

The zeta 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.) The multiplicative inverse of the zeta function is the Möbius function μ(a, b); every value of μ(a, b) is an integral multiple of 1 in the base field.

1 Examples
2 Euler characteristic
3 Reduced incidence algebras
4 Literature

[edit] Examples

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 classical Möbius function introduced into number theory in the 19th century.

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

$\mu(S,T)=(-1)^{\left|T\setminus S\right|}$

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

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

$\mu(x,y)=\left\{\begin{matrix} 1 & \mbox{if }y-x=0, \\ -1 & \mbox{if }y-x=1, \\ 0 & \mbox{if }y-x>1. \end{matrix}\right.$

This corresponds to the sequence (1, −1, 0, 0, 0, ... ) of coefficients of the formal power series 1 − z, and the zeta function in this case corresponds to the sequence of coefficients (1, 1, 1, 1, ... ) of the formal power series (1 − z)⁻¹ = 1 + z + z² + z³ + .... The delta function in this incidence algebra similarly corresponds to the formal power series 1.

Partially order the set of all partitions of a finite set by saying σ ≤ τ if σ is a finer partition than τ. Then the Möbius function is

$\mu(\sigma,\tau)=(-1)^{n-r}(2!)^{r_3}(3!)^{r_4}\cdots((n-1)!)^{r_n}$

where n is the number of blocks in the finer partition σ, r is the number of blocks in the coarser partition τ, and r_i is the number of blocks of τ that contain exactly i blocks of σ.

[edit] 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 0 and 1 of the ring of scalars). The Euler characteristic of a bounded finite poset is μ(0,1); it is always an integer. This concept is related to the classical Euler characteristic.

[edit] Reduced incidence algebras

Any member of an incidence algebra that assigns the same value to any two intervals that are isomorphic to each other as posets is a member of the reduced incidence algebra. This is a subalgebra of the incidence algebra, and it clearly contains the incidence algebra's identity element and zeta function. Any element of the reduced incidence algebra that is invertible in the larger incidence algebra has its inverse in the reduced incidence algebra. As a consequence, the Möbius function is always a member of the reduced incidence algebra. Reduced incidence algebras shed light on the theory of generating functions, as alluded to in the third example above.

[edit] Literature

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. Rota's 1964 paper was:

On the Foundations of Combinatorial Theory I: Theory of Möbius Functions, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, volume 2, pages 340-368.

Retrieved from "http://en.wikipedia.org../../../i/n/c/Incidence_algebra.html"

Categories: Combinatorics | Order theory