Incidence Algebras¶

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

Bases: sage.combinat.free_module.CombinatorialFreeModule

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:

Wikipedia article Incidence_algebra

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')¶

Bases: sage.combinat.free_module.CombinatorialFreeModule

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)]

Incidence Algebras¶

Previous topic

Next topic

This Page