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.
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
( f ∗ g ) ( a , b ) = ∑ a ≤ x ≤ b f ( a , x ) g ( x , b ) . {\displaystyle (f*g)(a,b)=\sum _{a~\leq ~x~\leq ~b}f(a,x)g(x,b).}
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.
Upper-triangular matrices 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. Then, functions f as above, from intervals to scalars, can be thought of as matrices Aij, where Aij = f(si, sj) whenever i ≤ j, and Aij = 0 otherwise. 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.
Special elements The multiplicative identity element of the incidence algebra is the delta function, defined by
δ ( a , b ) = { 1 if a = b , 0 if a ≠ b . {\displaystyle \delta (a,b)={\begin{cases}1&{\text{if }}a=b,\\0&{\text{if }}a\neq b.\end{cases}}}
The zeta function of an incidence algebra is the constant function ζ(a, b) = 1 for every nonempty 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:
μ ( x , y ) = {
1 if x = y − ∑ z : x ≤ z < y μ ( x , z ) for x < y
0 otherwise . {\displaystyle \mu (x,y)={\begin{cases}{}\qquad 1&{\text{if }}x=y\\[6pt]\displaystyle -\!\!\!\!\sum _{z\,:\,x\,\leq \,z\,<\,y}\mu (x,z)&{\text{for }}x<y\\{}\qquad 0&{\text{otherwise }}.\end{cases}}}
Multiplying by μ is analogous to differentiation, and is called Möbius inversion. The square of the zeta function gives the number of elements in an interval:
… excerpt ends here. Continue reading the full article.
