In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered set and commutative ring with unity.
Contents
Definition
A locally finite poset is one in which every closed interval
[a, b] = {x : a ≤ x ≤ b}is finite.
The members of the incidence algebra are the functions f assigning to each nonempty interval [a, b] a scalar f(a, b), which is taken from the ring of scalars, a commutative ring with unity. On this underlying set one defines addition and scalar multiplication pointwise, and "multiplication" in the incidence algebra is a convolution defined by
An incidence algebra is finite-dimensional if and only if the underlying poset is finite.
Related concepts
An incidence algebra is analogous to a group algebra; indeed, both the group algebra and the incidence algebra are special cases of a category algebra, defined analogously; groups and posets being special kinds of categories.
Special elements
The multiplicative identity element of the incidence algebra is the delta function, defined by
The zeta function of an incidence algebra is the constant function ζ(a, b) = 1 for every interval [a, b]. Multiplying by ζ is analogous to integration.
One can show that ζ 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) is invertible 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 ring.
The Möbius function can also be defined inductively by the following relation:
Multiplying by μ is analogous to differentiation, and is called Möbius inversion.
Examples
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). The reason for this terminology is the following: If P has a 0 and 1, then μ(0,1) is the reduced Euler characteristic of the simplicial complex whose faces are chains in P {0, 1}. This can be shown using Philip Hall's theorem, relating the value of μ(0,1) to the number of chains of length i.
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 case of the natural numbers above.
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: