From 35ecc332201ce37f6ad1f6ac05b696d8c73c9cb3 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Mon, 7 Dec 2020 11:18:55 -0500 Subject: [PATCH] eja: work towards fixing element subalgebras. --- mjo/eja/eja_element.py | 64 ++++++++++++++++++++++++++----- mjo/eja/eja_element_subalgebra.py | 26 +------------ mjo/eja/eja_subalgebra.py | 2 +- 3 files changed, 57 insertions(+), 35 deletions(-) diff --git a/mjo/eja/eja_element.py b/mjo/eja/eja_element.py index 6181f03..f0f6da7 100644 --- a/mjo/eja/eja_element.py +++ b/mjo/eja/eja_element.py @@ -830,10 +830,7 @@ class FiniteDimensionalEJAElement(IndexedFreeModuleElement): ALGORITHM: - For now, we skip the messy minimal polynomial computation - and instead return the dimension of the vector space spanned - by the powers of this element. The latter is a bit more - straightforward to compute. + ......... SETUP:: @@ -881,12 +878,59 @@ class FiniteDimensionalEJAElement(IndexedFreeModuleElement): True """ - if self.is_zero() and not self.parent().is_trivial(): + n = self.parent().dimension() + + if n == 0: + # The minimal polynomial is an empty product, i.e. the + # constant polynomial "1" having degree zero. + return 0 + elif self.is_zero(): # The minimal polynomial of zero in a nontrivial algebra - # is "t"; in a trivial algebra it's "1" by convention - # (it's an empty product). + # is "t", and is of degree one. + return 1 + elif n == 1: + # If this is a nonzero element of a nontrivial algebra, it + # has degree at least one. It follows that, in an algebra + # of dimension one, the degree must be actually one. return 1 - return self.subalgebra_generated_by().dimension() + + # BEWARE: The subalgebra_generated_by() method uses the result + # of this method to construct a basis for the subalgebra. That + # means, in particular, that we cannot implement this method + # as ``self.subalgebra_generated_by().dimension()``. + + # Algorithm: keep appending (vector representations of) powers + # self as rows to a matrix and echelonizing it. When its rank + # stops increasing, we've reached a redundancy. + + # Given the special cases above, we can assume that "self" is + # nonzero, the algebra is nontrivial, and that its dimension + # is at least two. + M = matrix([(self.parent().one()).to_vector()]) + old_rank = 1 + + # Specifying the row-reduction algorithm can e.g. help over + # AA because it avoids the RecursionError that gets thrown + # when we have to look too hard for a root. + # + # Beware: QQ supports an entirely different set of "algorithm" + # keywords than do AA and RR. + algo = None + from sage.rings.all import QQ + if self.parent().base_ring() is not QQ: + algo = "scaled_partial_pivoting" + + for d in range(1,n): + M = matrix(M.rows() + [(self**d).to_vector()]) + M.echelonize(algo) + new_rank = M.rank() + if new_rank == old_rank: + return new_rank + else: + old_rank = new_rank + + return n + def left_matrix(self): @@ -1320,7 +1364,7 @@ class FiniteDimensionalEJAElement(IndexedFreeModuleElement): result.append( (evalue, proj(A.one()).superalgebra_element()) ) return result - def subalgebra_generated_by(self, orthonormalize_basis=False): + def subalgebra_generated_by(self, **kwargs): """ Return the associative subalgebra of the parent EJA generated by this element. @@ -1368,7 +1412,7 @@ class FiniteDimensionalEJAElement(IndexedFreeModuleElement): """ from mjo.eja.eja_element_subalgebra import FiniteDimensionalEJAElementSubalgebra - return FiniteDimensionalEJAElementSubalgebra(self, orthonormalize_basis) + return FiniteDimensionalEJAElementSubalgebra(self, **kwargs) def subalgebra_idempotent(self): diff --git a/mjo/eja/eja_element_subalgebra.py b/mjo/eja/eja_element_subalgebra.py index 846c13b..ee8e0c6 100644 --- a/mjo/eja/eja_element_subalgebra.py +++ b/mjo/eja/eja_element_subalgebra.py @@ -14,32 +14,10 @@ class FiniteDimensionalEJAElementSubalgebra(FiniteDimensionalEJASubalgebra): # and continually rref() it until the rank stops going # up. When n=10 but the dimension of the algebra is 1, that # can save a shitload of time (especially over AA). - powers = tuple( elt**k for k in range(superalgebra.dimension()) ) - power_vectors = ( p.to_vector() for p in powers ) - P = matrix(superalgebra.base_ring(), power_vectors) - - # Echelonize the matrix ourselves, because otherwise the - # call to P.pivot_rows() below can choose a non-optimal - # row-reduction algorithm. In particular, scaling can - # help over AA because it avoids the RecursionError that - # gets thrown when we have to look too hard for a root. - # - # Beware: QQ supports an entirely different set of "algorithm" - # keywords than do AA and RR. - algo = None - if superalgebra.base_ring() is not QQ: - algo = "scaled_partial_pivoting" - P.echelonize(algorithm=algo) - - # Figure out which powers form a linearly-independent set. - ind_rows = P.pivot_rows() - - # Pick those out of the list of all powers. - basis = tuple(map(powers.__getitem__, ind_rows)) - + powers = tuple( elt**k for k in range(elt.degree()) ) super().__init__(superalgebra, - basis, + powers, associative=True, **kwargs) diff --git a/mjo/eja/eja_subalgebra.py b/mjo/eja/eja_subalgebra.py index 3eee248..8a2a214 100644 --- a/mjo/eja/eja_subalgebra.py +++ b/mjo/eja/eja_subalgebra.py @@ -83,7 +83,7 @@ class FiniteDimensionalEJASubalgebraElement(FiniteDimensionalEJAElement): True """ - return self._superalgebra(self.to_matrix()) + return self.parent().superalgebra()(self.to_matrix()) -- 2.44.2