# Source code for sympy.polys.agca.homomorphisms

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

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

"""
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__

if self._check_hom(oth):
return NotImplemented

def __sub__(self, oth):
if self._check_hom(oth):
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, \ldots, 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])

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, \ldots, e_n, then
matrix should be an n-element iterable (b_1, \ldots, 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)