Incidence algebra

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. 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. An incidence algebra is analogous to a group algebra; indeed, both the group algebra and the incidence algebra are special cases of a , defined analogously; groups and posets being special kinds of . 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.