Coverage for /usr/lib/python3/dist-packages/sympy/polys/agca/homomorphisms.py: 29%

1"""

2Computations with homomorphisms of modules and rings.

4This module implements classes for representing homomorphisms of rings and

5their modules. Instead of instantiating the classes directly, you should use

6the function ``homomorphism(from, to, matrix)`` to create homomorphism objects.

7"""

10from sympy.polys.agca.modules import (Module, FreeModule, QuotientModule,

11 SubModule, SubQuotientModule)

12from sympy.polys.polyerrors import CoercionFailed

14# The main computational task for module homomorphisms is kernels.

15# For this reason, the concrete classes are organised by domain module type.

18class ModuleHomomorphism:

19 """

20 Abstract base class for module homomoprhisms. Do not instantiate.

22 Instead, use the ``homomorphism`` function:

24 >>> from sympy import QQ

25 >>> from sympy.abc import x

26 >>> from sympy.polys.agca import homomorphism

28 >>> F = QQ.old_poly_ring(x).free_module(2)

29 >>> homomorphism(F, F, [[1, 0], [0, 1]])

30 Matrix([

31 [1, 0], : QQ[x]**2 -> QQ[x]**2

32 [0, 1]])

34 Attributes:

36 - ring - the ring over which we are considering modules

37 - domain - the domain module

38 - codomain - the codomain module

39 - _ker - cached kernel

40 - _img - cached image

42 Non-implemented methods:

44 - _kernel

45 - _image

46 - _restrict_domain

47 - _restrict_codomain

48 - _quotient_domain

49 - _quotient_codomain

50 - _apply

51 - _mul_scalar

52 - _compose

53 - _add

54 """

56 def __init__(self, domain, codomain):

57 if not isinstance(domain, Module):

58 raise TypeError('Source must be a module, got %s' % domain)

59 if not isinstance(codomain, Module):

60 raise TypeError('Target must be a module, got %s' % codomain)

61 if domain.ring != codomain.ring:

62 raise ValueError('Source and codomain must be over same ring, '

63 'got %s != %s' % (domain, codomain))

64 self.domain = domain

65 self.codomain = codomain

66 self.ring = domain.ring

67 self._ker = None

68 self._img = None

70 def kernel(self):

71 r"""

72 Compute the kernel of ``self``.

74 That is, if ``self`` is the homomorphism `\phi: M \to N`, then compute

75 `ker(\phi) = \{x \in M | \phi(x) = 0\}`. This is a submodule of `M`.

77 Examples

78 ========

80 >>> from sympy import QQ

81 >>> from sympy.abc import x

82 >>> from sympy.polys.agca import homomorphism

84 >>> F = QQ.old_poly_ring(x).free_module(2)

85 >>> homomorphism(F, F, [[1, 0], [x, 0]]).kernel()

86 <[x, -1]>

87 """

88 if self._ker is None:

89 self._ker = self._kernel()

90 return self._ker

92 def image(self):

93 r"""

94 Compute the image of ``self``.

96 That is, if ``self`` is the homomorphism `\phi: M \to N`, then compute

97 `im(\phi) = \{\phi(x) | x \in M \}`. This is a submodule of `N`.

99 Examples

100 ========

101

102 >>> from sympy import QQ

103 >>> from sympy.abc import x

104 >>> from sympy.polys.agca import homomorphism

105

106 >>> F = QQ.old_poly_ring(x).free_module(2)

107 >>> homomorphism(F, F, [[1, 0], [x, 0]]).image() == F.submodule([1, 0])

108 True

109 """

110 if self._img is None:

111 self._img = self._image()

112 return self._img

113

114 def _kernel(self):

115 """Compute the kernel of ``self``."""

116 raise NotImplementedError

117

118 def _image(self):

119 """Compute the image of ``self``."""

120 raise NotImplementedError

121

122 def _restrict_domain(self, sm):

123 """Implementation of domain restriction."""

124 raise NotImplementedError

125

126 def _restrict_codomain(self, sm):

127 """Implementation of codomain restriction."""

128 raise NotImplementedError

129

130 def _quotient_domain(self, sm):

131 """Implementation of domain quotient."""

132 raise NotImplementedError

133

134 def _quotient_codomain(self, sm):

135 """Implementation of codomain quotient."""

136 raise NotImplementedError

137

138 def restrict_domain(self, sm):

139 """

140 Return ``self``, with the domain restricted to ``sm``.

141

142 Here ``sm`` has to be a submodule of ``self.domain``.

143

144 Examples

145 ========

146

147 >>> from sympy import QQ

148 >>> from sympy.abc import x

149 >>> from sympy.polys.agca import homomorphism

150

151 >>> F = QQ.old_poly_ring(x).free_module(2)

152 >>> h = homomorphism(F, F, [[1, 0], [x, 0]])

153 >>> h

154 Matrix([

155 [1, x], : QQ[x]**2 -> QQ[x]**2

156 [0, 0]])

157 >>> h.restrict_domain(F.submodule([1, 0]))

158 Matrix([

159 [1, x], : <[1, 0]> -> QQ[x]**2

160 [0, 0]])

161

162 This is the same as just composing on the right with the submodule

163 inclusion:

164

165 >>> h * F.submodule([1, 0]).inclusion_hom()

166 Matrix([

167 [1, x], : <[1, 0]> -> QQ[x]**2

168 [0, 0]])

169 """

170 if not self.domain.is_submodule(sm):

171 raise ValueError('sm must be a submodule of %s, got %s'

172 % (self.domain, sm))

173 if sm == self.domain:

174 return self

175 return self._restrict_domain(sm)

176

177 def restrict_codomain(self, sm):

178 """

179 Return ``self``, with codomain restricted to to ``sm``.

180

181 Here ``sm`` has to be a submodule of ``self.codomain`` containing the

182 image.

183

184 Examples

185 ========

186

187 >>> from sympy import QQ

188 >>> from sympy.abc import x

189 >>> from sympy.polys.agca import homomorphism

190

191 >>> F = QQ.old_poly_ring(x).free_module(2)

192 >>> h = homomorphism(F, F, [[1, 0], [x, 0]])

193 >>> h

194 Matrix([

195 [1, x], : QQ[x]**2 -> QQ[x]**2

196 [0, 0]])

197 >>> h.restrict_codomain(F.submodule([1, 0]))

198 Matrix([

199 [1, x], : QQ[x]**2 -> <[1, 0]>

200 [0, 0]])

201 """

202 if not sm.is_submodule(self.image()):

203 raise ValueError('the image %s must contain sm, got %s'

204 % (self.image(), sm))

205 if sm == self.codomain:

206 return self

207 return self._restrict_codomain(sm)

208

209 def quotient_domain(self, sm):

210 """

211 Return ``self`` with domain replaced by ``domain/sm``.

212

213 Here ``sm`` must be a submodule of ``self.kernel()``.

214

215 Examples

216 ========

217

218 >>> from sympy import QQ

219 >>> from sympy.abc import x

220 >>> from sympy.polys.agca import homomorphism

221

222 >>> F = QQ.old_poly_ring(x).free_module(2)

223 >>> h = homomorphism(F, F, [[1, 0], [x, 0]])

224 >>> h

225 Matrix([

226 [1, x], : QQ[x]**2 -> QQ[x]**2

227 [0, 0]])

228 >>> h.quotient_domain(F.submodule([-x, 1]))

229 Matrix([

230 [1, x], : QQ[x]**2/<[-x, 1]> -> QQ[x]**2

231 [0, 0]])

232 """

233 if not self.kernel().is_submodule(sm):

234 raise ValueError('kernel %s must contain sm, got %s' %

235 (self.kernel(), sm))

236 if sm.is_zero():

237 return self

238 return self._quotient_domain(sm)

239

240 def quotient_codomain(self, sm):

241 """

242 Return ``self`` with codomain replaced by ``codomain/sm``.

243

244 Here ``sm`` must be a submodule of ``self.codomain``.

245

246 Examples

247 ========

248

249 >>> from sympy import QQ

250 >>> from sympy.abc import x

251 >>> from sympy.polys.agca import homomorphism

252

253 >>> F = QQ.old_poly_ring(x).free_module(2)

254 >>> h = homomorphism(F, F, [[1, 0], [x, 0]])

255 >>> h

256 Matrix([

257 [1, x], : QQ[x]**2 -> QQ[x]**2

258 [0, 0]])

259 >>> h.quotient_codomain(F.submodule([1, 1]))

260 Matrix([

261 [1, x], : QQ[x]**2 -> QQ[x]**2/<[1, 1]>

262 [0, 0]])

263

264 This is the same as composing with the quotient map on the left:

265

266 >>> (F/[(1, 1)]).quotient_hom() * h

267 Matrix([

268 [1, x], : QQ[x]**2 -> QQ[x]**2/<[1, 1]>

269 [0, 0]])

270 """

271 if not self.codomain.is_submodule(sm):

272 raise ValueError('sm must be a submodule of codomain %s, got %s'

273 % (self.codomain, sm))

274 if sm.is_zero():

275 return self

276 return self._quotient_codomain(sm)

277

278 def _apply(self, elem):

279 """Apply ``self`` to ``elem``."""

280 raise NotImplementedError

281

282 def __call__(self, elem):

283 return self.codomain.convert(self._apply(self.domain.convert(elem)))

284

285 def _compose(self, oth):

286 """

287 Compose ``self`` with ``oth``, that is, return the homomorphism

288 obtained by first applying then ``self``, then ``oth``.

289

290 (This method is private since in this syntax, it is non-obvious which

291 homomorphism is executed first.)

292 """

293 raise NotImplementedError

294

295 def _mul_scalar(self, c):

296 """Scalar multiplication. ``c`` is guaranteed in self.ring."""

297 raise NotImplementedError

298

299 def _add(self, oth):

300 """

301 Homomorphism addition.

302 ``oth`` is guaranteed to be a homomorphism with same domain/codomain.

303 """

304 raise NotImplementedError

305

306 def _check_hom(self, oth):

307 """Helper to check that oth is a homomorphism with same domain/codomain."""

308 if not isinstance(oth, ModuleHomomorphism):

309 return False

310 return oth.domain == self.domain and oth.codomain == self.codomain

311

312 def __mul__(self, oth):

313 if isinstance(oth, ModuleHomomorphism) and self.domain == oth.codomain:

314 return oth._compose(self)

315 try:

316 return self._mul_scalar(self.ring.convert(oth))

317 except CoercionFailed:

318 return NotImplemented

319

320 # NOTE: _compose will never be called from rmul

321 __rmul__ = __mul__

322

323 def __truediv__(self, oth):

324 try:

325 return self._mul_scalar(1/self.ring.convert(oth))

326 except CoercionFailed:

327 return NotImplemented

328

329 def __add__(self, oth):

330 if self._check_hom(oth):

331 return self._add(oth)

332 return NotImplemented

333

334 def __sub__(self, oth):

335 if self._check_hom(oth):

336 return self._add(oth._mul_scalar(self.ring.convert(-1)))

337 return NotImplemented

338

339 def is_injective(self):

340 """

341 Return True if ``self`` is injective.

342

343 That is, check if the elements of the domain are mapped to the same

344 codomain element.

345

346 Examples

347 ========

348

349 >>> from sympy import QQ

350 >>> from sympy.abc import x

351 >>> from sympy.polys.agca import homomorphism

352

353 >>> F = QQ.old_poly_ring(x).free_module(2)

354 >>> h = homomorphism(F, F, [[1, 0], [x, 0]])

355 >>> h.is_injective()

356 False

357 >>> h.quotient_domain(h.kernel()).is_injective()

358 True

359 """

360 return self.kernel().is_zero()

361

362 def is_surjective(self):

363 """

364 Return True if ``self`` is surjective.

365

366 That is, check if every element of the codomain has at least one

367 preimage.

368

369 Examples

370 ========

371

372 >>> from sympy import QQ

373 >>> from sympy.abc import x

374 >>> from sympy.polys.agca import homomorphism

375

376 >>> F = QQ.old_poly_ring(x).free_module(2)

377 >>> h = homomorphism(F, F, [[1, 0], [x, 0]])

378 >>> h.is_surjective()

379 False

380 >>> h.restrict_codomain(h.image()).is_surjective()

381 True

382 """

383 return self.image() == self.codomain

384

385 def is_isomorphism(self):

386 """

387 Return True if ``self`` is an isomorphism.

388

389 That is, check if every element of the codomain has precisely one

390 preimage. Equivalently, ``self`` is both injective and surjective.

391

392 Examples

393 ========

394

395 >>> from sympy import QQ

396 >>> from sympy.abc import x

397 >>> from sympy.polys.agca import homomorphism

398

399 >>> F = QQ.old_poly_ring(x).free_module(2)

400 >>> h = homomorphism(F, F, [[1, 0], [x, 0]])

401 >>> h = h.restrict_codomain(h.image())

402 >>> h.is_isomorphism()

403 False

404 >>> h.quotient_domain(h.kernel()).is_isomorphism()

405 True

406 """

407 return self.is_injective() and self.is_surjective()

408

409 def is_zero(self):

410 """

411 Return True if ``self`` is a zero morphism.

412

413 That is, check if every element of the domain is mapped to zero

414 under self.

415

416 Examples

417 ========

418

419 >>> from sympy import QQ

420 >>> from sympy.abc import x

421 >>> from sympy.polys.agca import homomorphism

422

423 >>> F = QQ.old_poly_ring(x).free_module(2)

424 >>> h = homomorphism(F, F, [[1, 0], [x, 0]])

425 >>> h.is_zero()

426 False

427 >>> h.restrict_domain(F.submodule()).is_zero()

428 True

429 >>> h.quotient_codomain(h.image()).is_zero()

430 True

431 """

432 return self.image().is_zero()

433

434 def __eq__(self, oth):

435 try:

436 return (self - oth).is_zero()

437 except TypeError:

438 return False

439

440 def __ne__(self, oth):

441 return not (self == oth)

442

443

444class MatrixHomomorphism(ModuleHomomorphism):

445 r"""

446 Helper class for all homomoprhisms which are expressed via a matrix.

447

448 That is, for such homomorphisms ``domain`` is contained in a module

449 generated by finitely many elements `e_1, \ldots, e_n`, so that the

450 homomorphism is determined uniquely by its action on the `e_i`. It

451 can thus be represented as a vector of elements of the codomain module,

452 or potentially a supermodule of the codomain module

453 (and hence conventionally as a matrix, if there is a similar interpretation

454 for elements of the codomain module).

455

456 Note that this class does *not* assume that the `e_i` freely generate a

457 submodule, nor that ``domain`` is even all of this submodule. It exists

458 only to unify the interface.

459

460 Do not instantiate.

461

462 Attributes:

463

464 - matrix - the list of images determining the homomorphism.

465 NOTE: the elements of matrix belong to either self.codomain or

466 self.codomain.container

467

468 Still non-implemented methods:

469

470 - kernel

471 - _apply

472 """

473

474 def __init__(self, domain, codomain, matrix):

475 ModuleHomomorphism.__init__(self, domain, codomain)

476 if len(matrix) != domain.rank:

477 raise ValueError('Need to provide %s elements, got %s'

478 % (domain.rank, len(matrix)))

479

480 converter = self.codomain.convert

481 if isinstance(self.codomain, (SubModule, SubQuotientModule)):

482 converter = self.codomain.container.convert

483 self.matrix = tuple(converter(x) for x in matrix)

484

485 def _sympy_matrix(self):

486 """Helper function which returns a SymPy matrix ``self.matrix``."""

487 from sympy.matrices import Matrix

488 c = lambda x: x

489 if isinstance(self.codomain, (QuotientModule, SubQuotientModule)):

490 c = lambda x: x.data

491 return Matrix([[self.ring.to_sympy(y) for y in c(x)] for x in self.matrix]).T

492

493 def __repr__(self):

494 lines = repr(self._sympy_matrix()).split('\n')

495 t = " : %s -> %s" % (self.domain, self.codomain)

496 s = ' '*len(t)

497 n = len(lines)

498 for i in range(n // 2):

499 lines[i] += s

500 lines[n // 2] += t

501 for i in range(n//2 + 1, n):

502 lines[i] += s

503 return '\n'.join(lines)

504

505 def _restrict_domain(self, sm):

506 """Implementation of domain restriction."""

507 return SubModuleHomomorphism(sm, self.codomain, self.matrix)

508

509 def _restrict_codomain(self, sm):

510 """Implementation of codomain restriction."""

511 return self.__class__(self.domain, sm, self.matrix)

512

513 def _quotient_domain(self, sm):

514 """Implementation of domain quotient."""

515 return self.__class__(self.domain/sm, self.codomain, self.matrix)

516

517 def _quotient_codomain(self, sm):

518 """Implementation of codomain quotient."""

519 Q = self.codomain/sm

520 converter = Q.convert

521 if isinstance(self.codomain, SubModule):

522 converter = Q.container.convert

523 return self.__class__(self.domain, self.codomain/sm,

524 [converter(x) for x in self.matrix])

525

526 def _add(self, oth):

527 return self.__class__(self.domain, self.codomain,

528 [x + y for x, y in zip(self.matrix, oth.matrix)])

529

530 def _mul_scalar(self, c):

531 return self.__class__(self.domain, self.codomain, [c*x for x in self.matrix])

532

533 def _compose(self, oth):

534 return self.__class__(self.domain, oth.codomain, [oth(x) for x in self.matrix])

535

536

537class FreeModuleHomomorphism(MatrixHomomorphism):

538 """

539 Concrete class for homomorphisms with domain a free module or a quotient

540 thereof.

541

542 Do not instantiate; the constructor does not check that your data is well

543 defined. Use the ``homomorphism`` function instead:

544

545 >>> from sympy import QQ

546 >>> from sympy.abc import x

547 >>> from sympy.polys.agca import homomorphism

548

549 >>> F = QQ.old_poly_ring(x).free_module(2)

550 >>> homomorphism(F, F, [[1, 0], [0, 1]])

551 Matrix([

552 [1, 0], : QQ[x]**2 -> QQ[x]**2

553 [0, 1]])

554 """

555

556 def _apply(self, elem):

557 if isinstance(self.domain, QuotientModule):

558 elem = elem.data

559 return sum(x * e for x, e in zip(elem, self.matrix))

560

561 def _image(self):

562 return self.codomain.submodule(*self.matrix)

563

564 def _kernel(self):

565 # The domain is either a free module or a quotient thereof.

566 # It does not matter if it is a quotient, because that won't increase

567 # the kernel.

568 # Our generators {e_i} are sent to the matrix entries {b_i}.

569 # The kernel is essentially the syzygy module of these {b_i}.

570 syz = self.image().syzygy_module()

571 return self.domain.submodule(*syz.gens)

572

573

574class SubModuleHomomorphism(MatrixHomomorphism):

575 """

576 Concrete class for homomorphism with domain a submodule of a free module

577 or a quotient thereof.

578

579 Do not instantiate; the constructor does not check that your data is well

580 defined. Use the ``homomorphism`` function instead:

581

582 >>> from sympy import QQ

583 >>> from sympy.abc import x

584 >>> from sympy.polys.agca import homomorphism

585

586 >>> M = QQ.old_poly_ring(x).free_module(2)*x

587 >>> homomorphism(M, M, [[1, 0], [0, 1]])

588 Matrix([

589 [1, 0], : <[x, 0], [0, x]> -> <[x, 0], [0, x]>

590 [0, 1]])

591 """

592

593 def _apply(self, elem):

594 if isinstance(self.domain, SubQuotientModule):

595 elem = elem.data

596 return sum(x * e for x, e in zip(elem, self.matrix))

597

598 def _image(self):

599 return self.codomain.submodule(*[self(x) for x in self.domain.gens])

600

601 def _kernel(self):

602 syz = self.image().syzygy_module()

603 return self.domain.submodule(

604 *[sum(xi*gi for xi, gi in zip(s, self.domain.gens))

605 for s in syz.gens])

606

607

608def homomorphism(domain, codomain, matrix):

609 r"""

610 Create a homomorphism object.

611

612 This function tries to build a homomorphism from ``domain`` to ``codomain``

613 via the matrix ``matrix``.

614

615 Examples

616 ========

617

618 >>> from sympy import QQ

619 >>> from sympy.abc import x

620 >>> from sympy.polys.agca import homomorphism

621

622 >>> R = QQ.old_poly_ring(x)

623 >>> T = R.free_module(2)

624

625 If ``domain`` is a free module generated by `e_1, \ldots, e_n`, then

626 ``matrix`` should be an n-element iterable `(b_1, \ldots, b_n)` where

627 the `b_i` are elements of ``codomain``. The constructed homomorphism is the

628 unique homomorphism sending `e_i` to `b_i`.

629

630 >>> F = R.free_module(2)

631 >>> h = homomorphism(F, T, [[1, x], [x**2, 0]])

632 >>> h

633 Matrix([

634 [1, x**2], : QQ[x]**2 -> QQ[x]**2

635 [x, 0]])

636 >>> h([1, 0])

637 [1, x]

638 >>> h([0, 1])

639 [x**2, 0]

640 >>> h([1, 1])

641 [x**2 + 1, x]

642

643 If ``domain`` is a submodule of a free module, them ``matrix`` determines

644 a homomoprhism from the containing free module to ``codomain``, and the

645 homomorphism returned is obtained by restriction to ``domain``.

646

647 >>> S = F.submodule([1, 0], [0, x])

648 >>> homomorphism(S, T, [[1, x], [x**2, 0]])

649 Matrix([

650 [1, x**2], : <[1, 0], [0, x]> -> QQ[x]**2

651 [x, 0]])

652

653 If ``domain`` is a (sub)quotient `N/K`, then ``matrix`` determines a

654 homomorphism from `N` to ``codomain``. If the kernel contains `K`, this

655 homomorphism descends to ``domain`` and is returned; otherwise an exception

656 is raised.

657

658 >>> homomorphism(S/[(1, 0)], T, [0, [x**2, 0]])

659 Matrix([

660 [0, x**2], : <[1, 0] + <[1, 0]>, [0, x] + <[1, 0]>, [1, 0] + <[1, 0]>> -> QQ[x]**2

661 [0, 0]])

662 >>> homomorphism(S/[(0, x)], T, [0, [x**2, 0]])

663 Traceback (most recent call last):

664 ...

665 ValueError: kernel <[1, 0], [0, 0]> must contain sm, got <[0,x]>

666

667 """

668 def freepres(module):

669 """

670 Return a tuple ``(F, S, Q, c)`` where ``F`` is a free module, ``S`` is a

671 submodule of ``F``, and ``Q`` a submodule of ``S``, such that

672 ``module = S/Q``, and ``c`` is a conversion function.

673 """

674 if isinstance(module, FreeModule):

675 return module, module, module.submodule(), lambda x: module.convert(x)

676 if isinstance(module, QuotientModule):

677 return (module.base, module.base, module.killed_module,

678 lambda x: module.convert(x).data)

679 if isinstance(module, SubQuotientModule):

680 return (module.base.container, module.base, module.killed_module,

681 lambda x: module.container.convert(x).data)

682 # an ordinary submodule

683 return (module.container, module, module.submodule(),

684 lambda x: module.container.convert(x))

685

686 SF, SS, SQ, _ = freepres(domain)

687 TF, TS, TQ, c = freepres(codomain)

688 # NOTE this is probably a bit inefficient (redundant checks)

689 return FreeModuleHomomorphism(SF, TF, [c(x) for x in matrix]

690 ).restrict_domain(SS).restrict_codomain(TS

691 ).quotient_codomain(TQ).quotient_domain(SQ)