Incidence algebra - Citizendia

In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for any locally finite partially ordered set and commutative ring with unity. Order theory is a branch of Mathematics that studies various kinds of Binary relations that capture the intuitive notion of ordering providing a framework for saying Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics, an associative algebra is a Vector space (or more generally a module) which also allows the multiplication of vectors in a distributive In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement In Ring theory, a branch of Abstract algebra, a commutative ring is a ring in which the multiplication operation has the commutative property

1 Definition
- 1.1 Related concepts
2 Special elements
3 Examples
4 Euler characteristic
5 Reduced incidence algebras
6 Literature

Definition

A locally finite poset is one for which every closed interval

[a, b] = {x : a ≤ x ≤ b}

within it is finite. In Mathematics, an interval is a set of Real numbers with the property that any number that lies between two numbers in the set is also included in the set In Mathematics, a set is called finite if there is a Bijection between the set and some set of the form {1 2.

The commutative ring with unity is called the ring of scalars. In Linear algebra, Real numbers are called Scalars and relate to vectors in a Vector space through the operation of Scalar multiplication

The members of the incidence algebra are the functions f assigning to each interval [a, b] a scalar f(a, b). The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function 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)=\sum_{a\leq x\leq b}f(a, x)g(x, b).$

An incidence algebra is finite-dimensional if and only if the underlying partially ordered set is finite. In Mathematics and in particular Functional analysis, convolution is a mathematical operation on two functions f and In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement

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 categorical algebra, defined analogously; groups and posets being special kinds of categories. In Mathematics, a group ring is a ring R constructed from a ring R and a group G (written multiplicatively In Category theory, a field of Mathematics, a categorical algebra is an Associative algebra, defined for any locally finite category and In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement In Mathematics, a category is a fundamental and abstract way to describe mathematical entities and their relationships

Special elements

The multiplicative identity element of the incidence algebra is the delta function, defined by

$\delta(a, b) = \left\{ \begin{matrix} \,1, & \mbox{if } a=b \\ \,0, & \mbox{if } a<b \end{matrix} \right.$

The zeta function of an incidence algebra is the constant function ζ(a, b) = 1 for every 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 field.

Multiplying by μ is analogous to differentiation, and is called Möbius inversion. In Mathematics, the classic Möbius inversion formula was introduced into Number theory during the 19th century by August Ferdinand Möbius.

Examples

Positive integers ordered by divisibility

The Möbius function is μ(a, b) = μ(b/a), where the second "μ" is the classical Möbius function introduced into number theory in the 19th century. In Mathematics, a divisor of an Integer n, also called a factor of n, is an integer which evenly divides n without For the rational functions defined on the complex numbers see Möbius transformation.

Finite subsets of some set E, ordered by inclusion

The Möbius function is

$\mu(S,T)=(-1)^{\left|T\setminus S\right|}$

whenever S and T are finite subsets of E with S ⊆ T, and Möbius inversion is called the principle of inclusion-exclusion. In combinatorial Mathematics, the inclusion-exclusion principle (also known as the sieve principle) states that if A 1.

Natural numbers with their usual order

The Möbius function is

$\mu(x,y)=\left\{\begin{matrix} 1 & \mbox{if }y-x=0, \\ -1 & \mbox{if }y-x=1, \\ 0 & \mbox{if }y-x>1. \end{matrix}\right.$

and Möbius inversion is called the (backwards) difference operator. In Mathematics, a difference operator maps a function, f ( x) to another function f ( x + a) &minus f ( x

Recall that convolution of sequences corresponds to multiplication of formal power series. In Mathematics, formal power series are devices that make it possible to employ much of the analytical machinery of Power series in settings that do not

The Möbius function corresponds to the sequence (1, −1, 0, 0, 0, . . . ) of coefficients of the formal power series 1 − z, and the zeta function in this case corresponds to the sequence of coefficients (1, 1, 1, 1, . . . ) of the formal power series $(1 - z)^{-1} = 1 + z + z^2 + z^3 + \cdots$ , which is inverse. The delta function in this incidence algebra similarly corresponds to the formal power series 1.

Partitions of a set

Partially order the set of all partitions of a finite set by saying σ ≤ τ if σ is a finer partition than τ. In Mathematics, a partition of a set X is a division of X into non-overlapping " parts " or " blocks " Then the Möbius function is

$\mu(\sigma,\tau)=(-1)^{n-r}(2!)^{r_3}(3!)^{r_4}\cdots((n-1)!)^{r_n}$

where n is the number of blocks in the finer partition σ, r is the number of blocks in the coarser partition τ, and r_i is the number of blocks of τ that contain exactly i blocks of σ.

Euler characteristic

A poset is bounded if it has smallest and largest elements, which we call 0 and 1 respectively (not to be confused with the 0 and 1 of the ring of scalars). The Euler characteristic of a bounded finite poset is μ(0,1); it is always an integer. This concept is related to the classical Euler characteristic. In Mathematics, and more specifically in Algebraic topology and Polyhedral combinatorics, the Euler characteristic is a Topological invariant

Reduced incidence algebras

Any member of an incidence algebra that assigns the same value to any two intervals that are isomorphic to each other as posets is a member of the reduced incidence algebra. This is a subalgebra of the incidence algebra, and it clearly contains the incidence algebra's identity element and zeta function. Any element of the reduced incidence algebra that is invertible in the larger incidence algebra has its inverse in the reduced incidence algebra. As a consequence, the Möbius function is always a member of the reduced incidence algebra. Reduced incidence algebras shed light on the theory of generating functions, as alluded to in the case of the natural numbers above. In Mathematics a generating function is a Formal power series whose coefficients encode information about a Sequence a n

Literature

Incidence algebras of locally finite posets were treated in a number of papers of Gian-Carlo Rota beginning in 1964, and by many later combinatorialists. Gian-Carlo Rota ( April 27, 1932 &ndash April 18, 1999, known as Juan Carlos Rota Year 1964 ( MCMLXIV) was a Leap year starting on Wednesday (link will display full calendar of the 1964 Gregorian calendar. Combinatorics is a branch of Pure mathematics concerning the study of discrete (and usually finite) objects Rota's 1964 paper was:

Rota, Gian-Carlo, On the Foundations of Combinatorial Theory I: Theory of Möbius Functions, vol. 2, pp. 340–368

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents