Incidence algebra explained

In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered setand 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.

Definition

A locally finite poset is one in which every closed interval

[''a, 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

(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 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 and posets being special kinds of categories.

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, 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, scaling and multiplication.^[1]

Special elements

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

\delta(a, b) = \begin{cases} 1 & if a = b, \\ 0 & if a \ne b. \end{cases}

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 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:

\mu(x,y) = \begin{cases} {} 1 & if x = y\\[ 6 pt] \displaystyle - \sum _{z} \mu(x,z) & for x<y \\ {} 0 & otherwise . \end{cases}

Multiplying by μ is analogous to differentiation, and is called Möbius inversion.

The square of the zeta function gives the number of elements in an interval:$$\backslash zeta^2(x,y)\; =\; \backslash sum\_\; \backslash zeta(x,z)\backslash ,\backslash zeta(z,y)\; =\; \backslash sum\_\; 1\; =\; \backslash \#[x,y].$$

Examples

Positive integers ordered by divisibility

The convolution associated to the incidence algebra for intervals [1, ''n''] becomes the Dirichlet convolution, hence 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.

Finite subsets of some set E, ordered by inclusion

The Möbius function is $$\backslash mu(S,T)=(-1)^$$

whenever S and T are finite subsets of E with S ⊆ T, and Möbius inversion is called the principle of inclusion-exclusion.

Geometrically, this is a hypercube: 2 ^{E} = \{ 0 , 1 \} ^{E.}

Natural numbers with their usual order

The Möbius function is and Möbius inversion is called the (backwards) difference operator.

Geometrically, this corresponds to the discrete number line.

The convolution of functions in the incidence algebra corresponds to multiplication of formal power series: see the discussion of reduced incidence algebras below. The Möbius function corresponds to the sequence (1, −1, 0, 0, 0, ...) of coefficients of the formal power series 1&thinsp;− t, and the zeta function corresponds to the sequence of coefficients (1, 1, 1, 1, ...) of the formal power series ( 1 - t) ^{-1} = 1 + t + t ^{2} + t ^{3} + … , which is inverse. The delta function in this incidence algebra similarly corresponds to the formal power series 1.

Finite sub-multisets of some multiset E, ordered by inclusion

The above three examples can be unified and generalized by considering a multiset E, and finite sub-multisets S and T of E. The Möbius function is

This generalizes the positive integers ordered by divisibility by a positive integer corresponding to its multiset of prime factors with multiplicity, e.g., 12 corresponds to the multiset \{ 2 , 2 , 3 \}.

This generalizes the natural numbers with their usual order by a natural number corresponding to a multiset of one underlying element and cardinality equal to that number, e.g., 3 corresponds to the multiset

\{ 1 , 1 , 1 \}.

Subgroups of a finite p-group G, ordered by inclusion

The Möbius function is $$\backslash mu\_G(H\_1,H\_2)\; =\; (-1)^\; p^$$ if H _{1} is a normal subgroup of H _{2} and H _{2/H} _{1} \cong (\Z/p\Z) ^{k} and it is 0 otherwise. This is a theorem of Weisner (1935).

Partitions of a set

Partially order the set of all partitions of a finite set by saying σ ≤ τ if σ is a finer partition than τ. In particular, let τ have t blocks which respectively split into s₁, ..., s_t finer blocks of σ, which has a total of s = s₁ + ⋅⋅⋅ + s_t blocks. Then the Möbius function is: $$\backslash mu(\backslash sigma,\backslash tau)\; =(-1)^(s\_11)!\; \backslash dots\; (s\_t1)!$$

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). The reason for this terminology is the following: If P has a 0 and 1, then μ(0,1) is the reduced Euler characteristic of the simplicial complex whose faces are chains in P \ . This can be shown using Philip Hall's theorem, relating the value of μ(0,1) to the number of chains of length i.

Reduced incidence algebras

The reduced incidence algebra consists of functions which assign the same value to any two intervals which are equivalent in an appropriate sense, usually meaning isomorphic as posets. 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. Thus the Möbius function is also in the reduced incidence algebra.

Reduced incidence algebras were introduced by Doubillet, Rota, and Stanley to give a natural construction of various rings of generating functions.^[2]

Natural numbers and ordinary generating functions

For the poset

( N ,\leq), the reduced incidence algebra consists of functions f(a,b) invariant under translation, f(a + k,b + k) = f(a,b) for all k \ge 0 , so as to have the same value on isomorphic intervals [''a''+''k'', ''b''+''k''] and [''a'', ''b'']. Let t denote the function with t(a, a+1) = 1 and t(a, b) = 0 otherwise, a kind of invariant delta function on isomorphism classes of intervals. Its powers in the incidence algebra are the other invariant delta functions t^&thinsp;n(a, a+n) = 1 and t^&thinsp;n(x, y) = 0 otherwise. These form a basis for the reduced incidence algebra, and we may write any invariant function as style f = \sum _{n\ge} f( 0 ,n)t ^{n} . This notation makes clear the isomorphism between the reduced incidence algebra and the ring of formal power series R[[t]] over the scalars R, also known as the ring of ordinary generating functions. We may write the zeta function as \zeta =1+ t + t ^{2+ …} = \tfrac 1 { 1- t}, the reciprocal of the Möbius function \mu =1- t.

Subset poset and exponential generating functions

For the Boolean poset of finite subsets

S\subset\{ 1 , 2 , 3 ,\ldots\} ordered by inclusion S\subset T , the reduced incidence algebra consists of invariant functions f(S,T), defined to have the same value on isomorphic intervals [''S'',''T''] and [''S''′,''T''&hairsp;′] with |T \ S| = |T&hairsp;′ \ S′|. Again, let t denote the invariant delta function with t(S,T) = 1 for |T \ S| = 1 and t(S,T) = 0 otherwise. Its powers are:$$t^n(S,T)\; =\backslash ,\; \backslash sum\; t(T\_0,T\_1)\backslash ,t(T\_1,T\_2)\; \backslash dots\; t(T\_,T\_n)\; =\; \backslash left\backslash$$

Notes and References

1. Kolegov. N. A.. Markova. O. V.. August 2019. Systems of Generators of Matrix Incidence Algebras over Finite Fields. Journal of Mathematical Sciences. en. 240. 6. 783–798. 10.1007/s10958-019-04396-6. 198443199 . 1072-3374.
2. Peter Doubilet, Gian-Carlo Rota and Richard Stanley: On the Foundations of Combinatorics (VI): The Idea of Generating Function, Berkeley Symposium on Math. Statist. and Prob., Proc. Sixth Berkeley Symposium on Math. Statist. and Prob., Vol. 2 (Univ. of Calif. Press, 1972), 267-318, available online in open access

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Incidence algebra".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.