Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Incidence algebra
Summary
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.