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
be a poset and
be a commutative unital associative ring. The incidence algebra
is the algebra of functions
such that
if
where multiplication is given by convolution:
This has a natural basis given by indicator functions for the interval
, i.e.
. The incidence algebra is a unital algebra with the identity given by the Kronecker delta
. The Mobius function of
is another element of
whose inverse is the
function of the poset (so
for every interval
).
Todo
Implement the incidence coalgebra.
REFERENCES:
-
class
Element
(M, x)¶ Bases:
sage.combinat.free_module.CombinatorialFreeModuleElement
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.mobius() 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.mobius() + I.zeta() sage: y.is_unit() True
This depends on the base ring:
sage: I = P.incidence_algebra(ZZ) sage: y = I.mobius() + I.zeta() sage: y.is_unit() False
-
to_matrix
()¶ Return
self
as a matrix.We define a matrix
for some element
in the incidence algebra
and we order the elements
by some linear extension of
. 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.mobius().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]
TESTS:
We check that this is an algebra (iso)morphism:
sage: P = posets.BooleanLattice(4) sage: I = P.incidence_algebra(QQ) sage: mu = I.mobius() sage: (mu*mu).to_matrix() == mu.to_matrix() * mu.to_matrix() True
-
-
IncidenceAlgebra.
delta
()¶ Return the element
in
self
(which is the Kronecker delta).
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]
-
IncidenceAlgebra.
mobius
()¶ Return the Mobius function of
self
.EXAMPLES:
sage: P = posets.BooleanLattice(2) sage: I = P.incidence_algebra(QQ) sage: I.mobius() 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]
-
IncidenceAlgebra.
one
()¶ Return the element
in
self
(which is the Kronecker delta).
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]
-
IncidenceAlgebra.
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
-
IncidenceAlgebra.
product_on_basis
(A, B)¶ Return the product of basis elements indexed by
A
andB
.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
-
IncidenceAlgebra.
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
-
IncidenceAlgebra.
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]]
-
IncidenceAlgebra.
zeta
()¶ Return the
function in
self
.The
function on a poset
is given by
EXAMPLES:
sage: P = posets.BooleanLattice(4) sage: I = P.incidence_algebra(QQ) sage: I.zeta() * I.mobius() == I.one() True
-
class
-
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
is a subalgebra of the incidence algebra
where
when
is isomorphic to
as posets. Thus the delta, Mobius, and zeta functions are all elements of
.
-
class
Element
(M, x)¶ Bases:
sage.combinat.free_module.CombinatorialFreeModuleElement
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.mobius() sage: mu.to_matrix() [ 1 -1 -1 1] [ 0 1 0 -1] [ 0 0 1 -1] [ 0 0 0 1]
-
-
ReducedIncidenceAlgebra.
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)]
-
ReducedIncidenceAlgebra.
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]
-
ReducedIncidenceAlgebra.
mobius
()¶ Return the Mobius function of
self
.EXAMPLES:
sage: P = posets.BooleanLattice(4) sage: R = P.incidence_algebra(QQ).reduced_subalgebra() sage: R.mobius() R[(0, 0)] - R[(0, 1)] + R[(0, 3)] - R[(0, 7)] + R[(0, 15)]
-
ReducedIncidenceAlgebra.
one_basis
()¶ Return the index of the element
in
self
.EXAMPLES:
sage: P = posets.BooleanLattice(4) sage: R = P.incidence_algebra(QQ).reduced_subalgebra() sage: R.one_basis() (0, 0)
-
ReducedIncidenceAlgebra.
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
-
ReducedIncidenceAlgebra.
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)]]
-
ReducedIncidenceAlgebra.
zeta
()¶ Return the
function in
self
.The
function on a poset
is given by
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)]
-
class