"""
Computations with homomorphisms of modules and rings.
This module implements classes for representing homomorphisms of rings and
their modules. Instead of instantiating the classes directly, you should use
the function ``homomorphism(from, to, matrix)`` to create homomorphism objects.
"""
from __future__ import print_function, division
from sympy.polys.agca.modules import (Module, FreeModule, QuotientModule,
SubModule, SubQuotientModule)
from sympy.polys.polyerrors import CoercionFailed
from sympy.core.compatibility import range
# The main computational task for module homomorphisms is kernels.
# For this reason, the concrete classes are organised by domain module type.
[docs]class ModuleHomomorphism(object):
"""
Abstract base class for module homomoprhisms. Do not instantiate.
Instead, use the ``homomorphism`` function:
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> F = QQ.old_poly_ring(x).free_module(2)
>>> homomorphism(F, F, [[1, 0], [0, 1]])
Matrix([
[1, 0], : QQ[x]**2 -> QQ[x]**2
[0, 1]])
Attributes:
- ring - the ring over which we are considering modules
- domain - the domain module
- codomain - the codomain module
- _ker - cached kernel
- _img - cached image
Non-implemented methods:
- _kernel
- _image
- _restrict_domain
- _restrict_codomain
- _quotient_domain
- _quotient_codomain
- _apply
- _mul_scalar
- _compose
- _add
"""
def __init__(self, domain, codomain):
if not isinstance(domain, Module):
raise TypeError('Source must be a module, got %s' % domain)
if not isinstance(codomain, Module):
raise TypeError('Target must be a module, got %s' % codomain)
if domain.ring != codomain.ring:
raise ValueError('Source and codomain must be over same ring, '
'got %s != %s' % (domain, codomain))
self.domain = domain
self.codomain = codomain
self.ring = domain.ring
self._ker = None
self._img = None
[docs] def kernel(self):
r"""
Compute the kernel of ``self``.
That is, if ``self`` is the homomorphism `\phi: M \to N`, then compute
`ker(\phi) = \{x \in M | \phi(x) = 0\}`. This is a submodule of `M`.
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> F = QQ.old_poly_ring(x).free_module(2)
>>> homomorphism(F, F, [[1, 0], [x, 0]]).kernel()
<[x, -1]>
"""
if self._ker is None:
self._ker = self._kernel()
return self._ker
[docs] def image(self):
r"""
Compute the image of ``self``.
That is, if ``self`` is the homomorphism `\phi: M \to N`, then compute
`im(\phi) = \{\phi(x) | x \in M \}`. This is a submodule of `N`.
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> F = QQ.old_poly_ring(x).free_module(2)
>>> homomorphism(F, F, [[1, 0], [x, 0]]).image() == F.submodule([1, 0])
True
"""
if self._img is None:
self._img = self._image()
return self._img
def _kernel(self):
"""Compute the kernel of ``self``."""
raise NotImplementedError
def _image(self):
"""Compute the image of ``self``."""
raise NotImplementedError
def _restrict_domain(self, sm):
"""Implementation of domain restriction."""
raise NotImplementedError
def _restrict_codomain(self, sm):
"""Implementation of codomain restriction."""
raise NotImplementedError
def _quotient_domain(self, sm):
"""Implementation of domain quotient."""
raise NotImplementedError
def _quotient_codomain(self, sm):
"""Implementation of codomain quotient."""
raise NotImplementedError
[docs] def restrict_domain(self, sm):
"""
Return ``self``, with the domain restricted to ``sm``.
Here ``sm`` has to be a submodule of ``self.domain``.
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> F = QQ.old_poly_ring(x).free_module(2)
>>> h = homomorphism(F, F, [[1, 0], [x, 0]])
>>> h
Matrix([
[1, x], : QQ[x]**2 -> QQ[x]**2
[0, 0]])
>>> h.restrict_domain(F.submodule([1, 0]))
Matrix([
[1, x], : <[1, 0]> -> QQ[x]**2
[0, 0]])
This is the same as just composing on the right with the submodule
inclusion:
>>> h * F.submodule([1, 0]).inclusion_hom()
Matrix([
[1, x], : <[1, 0]> -> QQ[x]**2
[0, 0]])
"""
if not self.domain.is_submodule(sm):
raise ValueError('sm must be a submodule of %s, got %s'
% (self.domain, sm))
if sm == self.domain:
return self
return self._restrict_domain(sm)
[docs] def restrict_codomain(self, sm):
"""
Return ``self``, with codomain restricted to to ``sm``.
Here ``sm`` has to be a submodule of ``self.codomain`` containing the
image.
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> F = QQ.old_poly_ring(x).free_module(2)
>>> h = homomorphism(F, F, [[1, 0], [x, 0]])
>>> h
Matrix([
[1, x], : QQ[x]**2 -> QQ[x]**2
[0, 0]])
>>> h.restrict_codomain(F.submodule([1, 0]))
Matrix([
[1, x], : QQ[x]**2 -> <[1, 0]>
[0, 0]])
"""
if not sm.is_submodule(self.image()):
raise ValueError('the image %s must contain sm, got %s'
% (self.image(), sm))
if sm == self.codomain:
return self
return self._restrict_codomain(sm)
[docs] def quotient_domain(self, sm):
"""
Return ``self`` with domain replaced by ``domain/sm``.
Here ``sm`` must be a submodule of ``self.kernel()``.
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> F = QQ.old_poly_ring(x).free_module(2)
>>> h = homomorphism(F, F, [[1, 0], [x, 0]])
>>> h
Matrix([
[1, x], : QQ[x]**2 -> QQ[x]**2
[0, 0]])
>>> h.quotient_domain(F.submodule([-x, 1]))
Matrix([
[1, x], : QQ[x]**2/<[-x, 1]> -> QQ[x]**2
[0, 0]])
"""
if not self.kernel().is_submodule(sm):
raise ValueError('kernel %s must contain sm, got %s' %
(self.kernel(), sm))
if sm.is_zero():
return self
return self._quotient_domain(sm)
[docs] def quotient_codomain(self, sm):
"""
Return ``self`` with codomain replaced by ``codomain/sm``.
Here ``sm`` must be a submodule of ``self.codomain``.
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> F = QQ.old_poly_ring(x).free_module(2)
>>> h = homomorphism(F, F, [[1, 0], [x, 0]])
>>> h
Matrix([
[1, x], : QQ[x]**2 -> QQ[x]**2
[0, 0]])
>>> h.quotient_codomain(F.submodule([1, 1]))
Matrix([
[1, x], : QQ[x]**2 -> QQ[x]**2/<[1, 1]>
[0, 0]])
This is the same as composing with the quotient map on the left:
>>> (F/[(1, 1)]).quotient_hom() * h
Matrix([
[1, x], : QQ[x]**2 -> QQ[x]**2/<[1, 1]>
[0, 0]])
"""
if not self.codomain.is_submodule(sm):
raise ValueError('sm must be a submodule of codomain %s, got %s'
% (self.codomain, sm))
if sm.is_zero():
return self
return self._quotient_codomain(sm)
def _apply(self, elem):
"""Apply ``self`` to ``elem``."""
raise NotImplementedError
def __call__(self, elem):
return self.codomain.convert(self._apply(self.domain.convert(elem)))
def _compose(self, oth):
"""
Compose ``self`` with ``oth``, that is, return the homomorphism
obtained by first applying then ``self``, then ``oth``.
(This method is private since in this syntax, it is non-obvious which
homomorphism is executed first.)
"""
raise NotImplementedError
def _mul_scalar(self, c):
"""Scalar multiplication. ``c`` is guaranteed in self.ring."""
raise NotImplementedError
def _add(self, oth):
"""
Homomorphism addition.
``oth`` is guaranteed to be a homomorphism with same domain/codomain.
"""
raise NotImplementedError
def _check_hom(self, oth):
"""Helper to check that oth is a homomorphism with same domain/codomain."""
if not isinstance(oth, ModuleHomomorphism):
return False
return oth.domain == self.domain and oth.codomain == self.codomain
def __mul__(self, oth):
if isinstance(oth, ModuleHomomorphism) and self.domain == oth.codomain:
return oth._compose(self)
try:
return self._mul_scalar(self.ring.convert(oth))
except CoercionFailed:
return NotImplemented
# NOTE: _compose will never be called from rmul
__rmul__ = __mul__
def __div__(self, oth):
try:
return self._mul_scalar(1/self.ring.convert(oth))
except CoercionFailed:
return NotImplemented
__truediv__ = __div__
def __add__(self, oth):
if self._check_hom(oth):
return self._add(oth)
return NotImplemented
def __sub__(self, oth):
if self._check_hom(oth):
return self._add(oth._mul_scalar(self.ring.convert(-1)))
return NotImplemented
[docs] def is_injective(self):
"""
Return True if ``self`` is injective.
That is, check if the elements of the domain are mapped to the same
codomain element.
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> F = QQ.old_poly_ring(x).free_module(2)
>>> h = homomorphism(F, F, [[1, 0], [x, 0]])
>>> h.is_injective()
False
>>> h.quotient_domain(h.kernel()).is_injective()
True
"""
return self.kernel().is_zero()
[docs] def is_surjective(self):
"""
Return True if ``self`` is surjective.
That is, check if every element of the codomain has at least one
preimage.
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> F = QQ.old_poly_ring(x).free_module(2)
>>> h = homomorphism(F, F, [[1, 0], [x, 0]])
>>> h.is_surjective()
False
>>> h.restrict_codomain(h.image()).is_surjective()
True
"""
return self.image() == self.codomain
[docs] def is_isomorphism(self):
"""
Return True if ``self`` is an isomorphism.
That is, check if every element of the codomain has precisely one
preimage. Equivalently, ``self`` is both injective and surjective.
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> F = QQ.old_poly_ring(x).free_module(2)
>>> h = homomorphism(F, F, [[1, 0], [x, 0]])
>>> h = h.restrict_codomain(h.image())
>>> h.is_isomorphism()
False
>>> h.quotient_domain(h.kernel()).is_isomorphism()
True
"""
return self.is_injective() and self.is_surjective()
[docs] def is_zero(self):
"""
Return True if ``self`` is a zero morphism.
That is, check if every element of the domain is mapped to zero
under self.
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> F = QQ.old_poly_ring(x).free_module(2)
>>> h = homomorphism(F, F, [[1, 0], [x, 0]])
>>> h.is_zero()
False
>>> h.restrict_domain(F.submodule()).is_zero()
True
>>> h.quotient_codomain(h.image()).is_zero()
True
"""
return self.image().is_zero()
def __eq__(self, oth):
try:
return (self - oth).is_zero()
except TypeError:
return False
def __ne__(self, oth):
return not (self == oth)
class MatrixHomomorphism(ModuleHomomorphism):
"""
Helper class for all homomoprhisms which are expressed via a matrix.
That is, for such homomorphisms ``domain`` is contained in a module
generated by finitely many elements `e_1, \dots, e_n`, so that the
homomorphism is determined uniquely by its action on the `e_i`. It
can thus be represented as a vector of elements of the codomain module,
or potentially a supermodule of the codomain module
(and hence conventionally as a matrix, if there is a similar interpretation
for elements of the codomain module).
Note that this class does *not* assume that the `e_i` freely generate a
submodule, nor that ``domain`` is even all of this submodule. It exists
only to unify the interface.
Do not instantiate.
Attributes:
- matrix - the list of images determining the homomorphism.
NOTE: the elements of matrix belong to either self.codomain or
self.codomain.container
Still non-implemented methods:
- kernel
- _apply
"""
def __init__(self, domain, codomain, matrix):
ModuleHomomorphism.__init__(self, domain, codomain)
if len(matrix) != domain.rank:
raise ValueError('Need to provide %s elements, got %s'
% (domain.rank, len(matrix)))
converter = self.codomain.convert
if isinstance(self.codomain, (SubModule, SubQuotientModule)):
converter = self.codomain.container.convert
self.matrix = tuple(converter(x) for x in matrix)
def _sympy_matrix(self):
"""Helper function which returns a sympy matrix ``self.matrix``."""
from sympy.matrices import Matrix
c = lambda x: x
if isinstance(self.codomain, (QuotientModule, SubQuotientModule)):
c = lambda x: x.data
return Matrix([[self.ring.to_sympy(y) for y in c(x)] for x in self.matrix]).T
def __repr__(self):
lines = repr(self._sympy_matrix()).split('\n')
t = " : %s -> %s" % (self.domain, self.codomain)
s = ' '*len(t)
n = len(lines)
for i in range(n // 2):
lines[i] += s
lines[n // 2] += t
for i in range(n//2 + 1, n):
lines[i] += s
return '\n'.join(lines)
def _restrict_domain(self, sm):
"""Implementation of domain restriction."""
return SubModuleHomomorphism(sm, self.codomain, self.matrix)
def _restrict_codomain(self, sm):
"""Implementation of codomain restriction."""
return self.__class__(self.domain, sm, self.matrix)
def _quotient_domain(self, sm):
"""Implementation of domain quotient."""
return self.__class__(self.domain/sm, self.codomain, self.matrix)
def _quotient_codomain(self, sm):
"""Implementation of codomain quotient."""
Q = self.codomain/sm
converter = Q.convert
if isinstance(self.codomain, SubModule):
converter = Q.container.convert
return self.__class__(self.domain, self.codomain/sm,
[converter(x) for x in self.matrix])
def _add(self, oth):
return self.__class__(self.domain, self.codomain,
[x + y for x, y in zip(self.matrix, oth.matrix)])
def _mul_scalar(self, c):
return self.__class__(self.domain, self.codomain, [c*x for x in self.matrix])
def _compose(self, oth):
return self.__class__(self.domain, oth.codomain, [oth(x) for x in self.matrix])
class FreeModuleHomomorphism(MatrixHomomorphism):
"""
Concrete class for homomorphisms with domain a free module or a quotient
thereof.
Do not instantiate; the constructor does not check that your data is well
defined. Use the ``homomorphism`` function instead:
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> F = QQ.old_poly_ring(x).free_module(2)
>>> homomorphism(F, F, [[1, 0], [0, 1]])
Matrix([
[1, 0], : QQ[x]**2 -> QQ[x]**2
[0, 1]])
"""
def _apply(self, elem):
if isinstance(self.domain, QuotientModule):
elem = elem.data
return sum(x * e for x, e in zip(elem, self.matrix))
def _image(self):
return self.codomain.submodule(*self.matrix)
def _kernel(self):
# The domain is either a free module or a quotient thereof.
# It does not matter if it is a quotient, because that won't increase
# the kernel.
# Our generators {e_i} are sent to the matrix entries {b_i}.
# The kernel is essentially the syzygy module of these {b_i}.
syz = self.image().syzygy_module()
return self.domain.submodule(*syz.gens)
class SubModuleHomomorphism(MatrixHomomorphism):
"""
Concrete class for homomorphism with domain a submodule of a free module
or a quotient thereof.
Do not instantiate; the constructor does not check that your data is well
defined. Use the ``homomorphism`` function instead:
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> M = QQ.old_poly_ring(x).free_module(2)*x
>>> homomorphism(M, M, [[1, 0], [0, 1]])
Matrix([
[1, 0], : <[x, 0], [0, x]> -> <[x, 0], [0, x]>
[0, 1]])
"""
def _apply(self, elem):
if isinstance(self.domain, SubQuotientModule):
elem = elem.data
return sum(x * e for x, e in zip(elem, self.matrix))
def _image(self):
return self.codomain.submodule(*[self(x) for x in self.domain.gens])
def _kernel(self):
syz = self.image().syzygy_module()
return self.domain.submodule(
*[sum(xi*gi for xi, gi in zip(s, self.domain.gens))
for s in syz.gens])
[docs]def homomorphism(domain, codomain, matrix):
r"""
Create a homomorphism object.
This function tries to build a homomorphism from ``domain`` to ``codomain``
via the matrix ``matrix``.
Examples
========
>>> from sympy import QQ
>>> from sympy.abc import x
>>> from sympy.polys.agca import homomorphism
>>> R = QQ.old_poly_ring(x)
>>> T = R.free_module(2)
If ``domain`` is a free module generated by `e_1, \dots, e_n`, then
``matrix`` should be an n-element iterable `(b_1, \dots, b_n)` where
the `b_i` are elements of ``codomain``. The constructed homomorphism is the
unique homomorphism sending `e_i` to `b_i`.
>>> F = R.free_module(2)
>>> h = homomorphism(F, T, [[1, x], [x**2, 0]])
>>> h
Matrix([
[1, x**2], : QQ[x]**2 -> QQ[x]**2
[x, 0]])
>>> h([1, 0])
[1, x]
>>> h([0, 1])
[x**2, 0]
>>> h([1, 1])
[x**2 + 1, x]
If ``domain`` is a submodule of a free module, them ``matrix`` determines
a homomoprhism from the containing free module to ``codomain``, and the
homomorphism returned is obtained by restriction to ``domain``.
>>> S = F.submodule([1, 0], [0, x])
>>> homomorphism(S, T, [[1, x], [x**2, 0]])
Matrix([
[1, x**2], : <[1, 0], [0, x]> -> QQ[x]**2
[x, 0]])
If ``domain`` is a (sub)quotient `N/K`, then ``matrix`` determines a
homomorphism from `N` to ``codomain``. If the kernel contains `K`, this
homomorphism descends to ``domain`` and is returned; otherwise an exception
is raised.
>>> homomorphism(S/[(1, 0)], T, [0, [x**2, 0]])
Matrix([
[0, x**2], : <[1, 0] + <[1, 0]>, [0, x] + <[1, 0]>, [1, 0] + <[1, 0]>> -> QQ[x]**2
[0, 0]])
>>> homomorphism(S/[(0, x)], T, [0, [x**2, 0]])
Traceback (most recent call last):
...
ValueError: kernel <[1, 0], [0, 0]> must contain sm, got <[0,x]>
"""
def freepres(module):
"""
Return a tuple ``(F, S, Q, c)`` where ``F`` is a free module, ``S`` is a
submodule of ``F``, and ``Q`` a submodule of ``S``, such that
``module = S/Q``, and ``c`` is a conversion function.
"""
if isinstance(module, FreeModule):
return module, module, module.submodule(), lambda x: module.convert(x)
if isinstance(module, QuotientModule):
return (module.base, module.base, module.killed_module,
lambda x: module.convert(x).data)
if isinstance(module, SubQuotientModule):
return (module.base.container, module.base, module.killed_module,
lambda x: module.container.convert(x).data)
# an ordinary submodule
return (module.container, module, module.submodule(),
lambda x: module.container.convert(x))
SF, SS, SQ, _ = freepres(domain)
TF, TS, TQ, c = freepres(codomain)
# NOTE this is probably a bit inefficient (redundant checks)
return FreeModuleHomomorphism(SF, TF, [c(x) for x in matrix]
).restrict_domain(SS).restrict_codomain(TS
).quotient_codomain(TQ).quotient_domain(SQ)
