# Incidence Algebras¶

class sage.combinat.posets.incidence_algebras.IncidenceAlgebra(R, P, prefix='I')

The incidence algebra of a poset.

Let $$P$$ be a poset and $$R$$ be a commutative unital associative ring. The incidence algebra $$I_P$$ is the algebra of functions $$\alpha \colon P \times P \to R$$ such that $$\alpha(x, y) = 0$$ if $$x \not\leq y$$ where multiplication is given by convolution:

$(\alpha \ast \beta)(x, y) = \sum_{x \leq k \leq y} \alpha(x, k) \beta(k, y).$

This has a natural basis given by indicator functions for the interval $$[a, b]$$, i.e. $$X_{a,b}(x,y) = \delta_{ax} \delta_{by}$$. The incidence algebra is a unital algebra with the identity given by the Kronecker delta $$\delta(x, y) = \delta_{xy}$$. The Möbius function of $$P$$ is another element of $$I_p$$ whose inverse is the $$\zeta$$ function of the poset (so $$\zeta(x, y) = 1$$ for every interval $$[x, y]$$).

Todo

Implement the incidence coalgebra.

REFERENCES:

class Element

Bases: sage.modules.with_basis.indexed_element.IndexedFreeModuleElement

An element of an incidence algebra.

is_unit()

Return if self is a unit.

EXAMPLES:

sage: P = posets.BooleanLattice(2)
sage: I = P.incidence_algebra(QQ)
sage: mu = I.moebius()
sage: mu.is_unit()
True
sage: zeta = I.zeta()
sage: zeta.is_unit()
True
sage: x = mu - I.zeta() + I[2,2]
sage: x.is_unit()
False
sage: y = I.moebius() + I.zeta()
sage: y.is_unit()
True


This depends on the base ring:

sage: I = P.incidence_algebra(ZZ)
sage: y = I.moebius() + I.zeta()
sage: y.is_unit()
False

to_matrix()

Return self as a matrix.

We define a matrix $$M_{xy} = \alpha(x, y)$$ for some element $$\alpha \in I_P$$ in the incidence algebra $$I_P$$ and we order the elements $$x,y \in P$$ by some linear extension of $$P$$. This defines an algebra (iso)morphism; in particular, multiplication in the incidence algebra goes to matrix multiplication.

EXAMPLES:

sage: P = posets.BooleanLattice(2)
sage: I = P.incidence_algebra(QQ)
sage: I.moebius().to_matrix()
[ 1 -1 -1  1]
[ 0  1  0 -1]
[ 0  0  1 -1]
[ 0  0  0  1]
sage: I.zeta().to_matrix()
[1 1 1 1]
[0 1 0 1]
[0 0 1 1]
[0 0 0 1]

delta()

Return the element $$1$$ in self (which is the Kronecker delta $$\delta(x, y)$$).

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: I = P.incidence_algebra(QQ)
sage: I.one()
I[0, 0] + I[1, 1] + I[2, 2] + I[3, 3] + I[4, 4] + I[5, 5]
+ I[6, 6] + I[7, 7] + I[8, 8] + I[9, 9] + I[10, 10]
+ I[11, 11] + I[12, 12] + I[13, 13] + I[14, 14] + I[15, 15]

moebius()

Return the Möbius function of self.

EXAMPLES:

sage: P = posets.BooleanLattice(2)
sage: I = P.incidence_algebra(QQ)
sage: I.moebius()
I[0, 0] - I[0, 1] - I[0, 2] + I[0, 3] + I[1, 1]
- I[1, 3] + I[2, 2] - I[2, 3] + I[3, 3]

one()

Return the element $$1$$ in self (which is the Kronecker delta $$\delta(x, y)$$).

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: I = P.incidence_algebra(QQ)
sage: I.one()
I[0, 0] + I[1, 1] + I[2, 2] + I[3, 3] + I[4, 4] + I[5, 5]
+ I[6, 6] + I[7, 7] + I[8, 8] + I[9, 9] + I[10, 10]
+ I[11, 11] + I[12, 12] + I[13, 13] + I[14, 14] + I[15, 15]

poset()

Return the defining poset of self.

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: I = P.incidence_algebra(QQ)
sage: I.poset()
Finite lattice containing 16 elements
sage: I.poset() == P
True

product_on_basis(A, B)

Return the product of basis elements indexed by A and B.

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: I = P.incidence_algebra(QQ)
sage: I.product_on_basis((1, 3), (3, 11))
I[1, 11]
sage: I.product_on_basis((1, 3), (2, 2))
0

reduced_subalgebra(prefix='R')

Return the reduced incidence subalgebra.

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: I = P.incidence_algebra(QQ)
sage: I.reduced_subalgebra()
Reduced incidence algebra of Finite lattice containing 16 elements
over Rational Field

some_elements()

Return a list of elements of self.

EXAMPLES:

sage: P = posets.BooleanLattice(1)
sage: I = P.incidence_algebra(QQ)
sage: I.some_elements()
[2*I[0, 0] + 2*I[0, 1] + 3*I[1, 1],
I[0, 0] - I[0, 1] + I[1, 1],
I[0, 0] + I[0, 1] + I[1, 1]]

zeta()

Return the $$\zeta$$ function in self.

The $$\zeta$$ function on a poset $$P$$ is given by

$\begin{split}\zeta(x, y) = \begin{cases} 1 & x \leq y, \\ 0 & x \not\leq y. \end{cases}\end{split}$

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: I = P.incidence_algebra(QQ)
sage: I.zeta() * I.moebius() == I.one()
True

class sage.combinat.posets.incidence_algebras.ReducedIncidenceAlgebra(I, prefix='R')

The reduced incidence algebra of a poset.

The reduced incidence algebra $$R_P$$ is a subalgebra of the incidence algebra $$I_P$$ where $$\alpha(x, y) = \alpha(x', y')$$ when $$[x, y]$$ is isomorphic to $$[x', y']$$ as posets. Thus the delta, Möbius, and zeta functions are all elements of $$R_P$$.

class Element

Bases: sage.modules.with_basis.indexed_element.IndexedFreeModuleElement

An element of a reduced incidence algebra.

is_unit()

Return if self is a unit.

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: R = P.incidence_algebra(QQ).reduced_subalgebra()
sage: x = R.an_element()
sage: x.is_unit()
True

lift()

Return the lift of self to the ambient space.

EXAMPLES:

sage: P = posets.BooleanLattice(2)
sage: I = P.incidence_algebra(QQ)
sage: R = I.reduced_subalgebra()
sage: x = R.an_element(); x
2*R[(0, 0)] + 2*R[(0, 1)] + 3*R[(0, 3)]
sage: x.lift()
2*I[0, 0] + 2*I[0, 1] + 2*I[0, 2] + 3*I[0, 3] + 2*I[1, 1]
+ 2*I[1, 3] + 2*I[2, 2] + 2*I[2, 3] + 2*I[3, 3]

to_matrix()

Return self as a matrix.

EXAMPLES:

sage: P = posets.BooleanLattice(2)
sage: R = P.incidence_algebra(QQ).reduced_subalgebra()
sage: mu = R.moebius()
sage: mu.to_matrix()
[ 1 -1 -1  1]
[ 0  1  0 -1]
[ 0  0  1 -1]
[ 0  0  0  1]

delta()

Return the Kronecker delta function in self.

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: R = P.incidence_algebra(QQ).reduced_subalgebra()
sage: R.delta()
R[(0, 0)]

lift()

Return the lift morphism from self to the ambient space.

EXAMPLES:

sage: P = posets.BooleanLattice(2)
sage: R = P.incidence_algebra(QQ).reduced_subalgebra()
sage: R.lift
Generic morphism:
From: Reduced incidence algebra of Finite lattice containing 4 elements over Rational Field
To:   Incidence algebra of Finite lattice containing 4 elements over Rational Field
sage: R.an_element() - R.one()
R[(0, 0)] + 2*R[(0, 1)] + 3*R[(0, 3)]
sage: R.lift(R.an_element() - R.one())
I[0, 0] + 2*I[0, 1] + 2*I[0, 2] + 3*I[0, 3] + I[1, 1]
+ 2*I[1, 3] + I[2, 2] + 2*I[2, 3] + I[3, 3]

moebius()

Return the Möbius function of self.

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: R = P.incidence_algebra(QQ).reduced_subalgebra()
sage: R.moebius()
R[(0, 0)] - R[(0, 1)] + R[(0, 3)] - R[(0, 7)] + R[(0, 15)]

one_basis()

Return the index of the element $$1$$ in self.

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: R = P.incidence_algebra(QQ).reduced_subalgebra()
sage: R.one_basis()
(0, 0)

poset()

Return the defining poset of self.

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: R = P.incidence_algebra(QQ).reduced_subalgebra()
sage: R.poset()
Finite lattice containing 16 elements
sage: R.poset() == P
True

some_elements()

Return a list of elements of self.

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: R = P.incidence_algebra(QQ).reduced_subalgebra()
sage: R.some_elements()
[2*R[(0, 0)] + 2*R[(0, 1)] + 3*R[(0, 3)],
R[(0, 0)] - R[(0, 1)] + R[(0, 3)] - R[(0, 7)] + R[(0, 15)],
R[(0, 0)] + R[(0, 1)] + R[(0, 3)] + R[(0, 7)] + R[(0, 15)]]

zeta()

Return the $$\zeta$$ function in self.

The $$\zeta$$ function on a poset $$P$$ is given by

$\begin{split}\zeta(x, y) = \begin{cases} 1 & x \leq y, \\ 0 & x \not\leq y. \end{cases}\end{split}$

EXAMPLES:

sage: P = posets.BooleanLattice(4)
sage: R = P.incidence_algebra(QQ).reduced_subalgebra()
sage: R.zeta()
R[(0, 0)] + R[(0, 1)] + R[(0, 3)] + R[(0, 7)] + R[(0, 15)]