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.
Subalgebras called reduced incidence algebras give a natural construction of various types of generating functions used in combinatorics and number theory.
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.
Consider the case of a partial order ≤ over any n-element set S. We enumerate S as s1, …, sn, and in such a way that the enumeration is compatible with the order ≤ on S, that is, si ≤ sj implies i ≤ j, which is always possible.
Since we arranged S in a way consistent with the usual order on the indices of the matrices, they will appear as upper-triangular matrices with a prescribed zero-pattern determined by the incomparable elements in S under ≤.
The incidence algebra of ≤ is then isomorphic to the algebra of upper-triangular matrices with this prescribed zero-pattern and arbitrary (including possibly zero) scalar entries everywhere else, with the operations being ordinary matrix addition, scaling and multiplication.
One can show that ζ is invertible in the incidence algebra (with respect to the convolution defined above).
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 square of the zeta function gives the number of elements in an interval:
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.
The reduced incidence algebra consists of functions which assign the same value to any two intervals which are equivalent in an appropriate sense, usually meaning isomorphic as posets.
Reduced incidence algebras were introduced by Doubillet, Rota, and Stanley to give a natural construction of various rings of generating functions.
Its powers in the incidence algebra are the other invariant delta functions t n(a, a+n) = 1 and t n(x, y) = 0 otherwise.
These form a basis for the reduced incidence algebra, and we may write any invariant function as
This notation makes clear the isomorphism between the reduced incidence algebra and the ring of formal power series
, the reduced incidence algebra consists of invariant functions
This gives a natural isomorphism between the reduced incidence algebra and the ring of exponential generating functions.
Many combinatorial counting sequences involving subsets or labeled objects can be interpreted in terms of the reduced incidence algebra, and computed using exponential generating functions.
Consider the poset D of positive integers ordered by divisibility, denoted by
The product of two invariant delta functions is: since the only non-zero term comes from c = na and b = mc = nma.
Thus, we get an isomorphism from the reduced incidence algebra to the ring of formal Dirichlet series by sending
Many other arithmetic functions arise naturally within the reduced incidence algebra, and equivalently in terms of Dirichlet series.
The product structure of the divisor poset facilitates the computation of its Möbius function.
Unique factorization into primes implies D is isomorphic to an infinite Cartesian product
Now the Möbius function of D is the product of the Möbius functions for the factor posets, computed above, giving the classical formula: The product structure also explains the classical Euler product for the zeta function.
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.