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 GraphSearch.
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.
Related concepts (11)
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.
Group ring
In algebra, a group ring is a free module and at the same time a ring, constructed in a natural way from any given ring and any given group. As a free module, its ring of scalars is the given ring, and its basis is the set of elements of the given group. As a ring, its addition law is that of the free module and its multiplication extends "by linearity" the given group law on the basis. Less formally, a group ring is a generalization of a given group, by attaching to each element of the group a "weighting factor" from a given ring.
Quiver (mathematics)
In graph theory, a quiver is a directed graph where loops and multiple arrows between two vertices are allowed, in other words a multidigraph. They are commonly used in representation theory: a representation V of a quiver assigns a vector space V(x) to each vertex x of the quiver and a linear map V(a) to each arrow a. In , a quiver can be understood to be the underlying structure of a , but without composition or a designation of identity morphisms. That is, there is a forgetful functor from Cat to Quiv.