In
order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article int ...
, 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
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series ...
used in
combinatorics and
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
.
Definition
A locally finite
poset
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
is one in which every
closed interval
In mathematics, a (real) interval is a set of real numbers that contains all real numbers lying between any two numbers of the set. For example, the set of numbers satisfying is an interval which contains , , and all numbers in between. Other ...
:
'a, b''=
is
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
.
The members of the incidence algebra are the
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
s ''f'' assigning to each
nonempty
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
interval
'a, b''a scalar ''f''(''a'', ''b''), which is taken from the ''
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
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
In mathematics (in particular, functional analysis), convolution is a mathematical operation on two functions ( and ) that produces a third function (f*g) that expresses how the shape of one is modified by the other. The term ''convolution'' ...
defined by
:
An incidence algebra is finite-dimensional
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is b ...
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
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
and
posets being special kinds of
categories
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
*Category of being
* ''Categories'' (Aristotle)
*Category (Kant)
* Categories (Peirce)
* ...
.
Upper-Triangular Matrices
Consider the case of a partial order ≤ over any -element set . We enumerate as , and in such a way that the enumeration is compatible with the order ≤ on , that is, implies , which is always possible.
Then, functions as above, from intervals to scalars, can be thought of as
matrices
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
, where whenever , and otherwise''.'' Since we arranged 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 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
In mathematics, matrix addition is the operation of adding two matrices by adding the corresponding entries together. However, there are other operations which could also be considered addition for matrices, such as the direct sum and the Kroneck ...
, scaling and
multiplication.
Special elements
The multiplicative identity element of the incidence algebra is the
delta function
In mathematics, the Dirac delta distribution ( distribution), also known as the unit impulse, is a generalized function or distribution over the real numbers, whose value is zero everywhere except at zero, and whose integral over the entire ...
, defined by
:
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 mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers.
Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...
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:
: