\documentclass{article} \usepackage{open-axiom} \begin{document} \title{src/algebra algcat.spad} \author{Barry Trager, Claude Quitte, Manuel Bronstein} \maketitle \begin{abstract} \end{abstract} \tableofcontents \eject \section{category FINRALG FiniteRankAlgebra} <>= import CommutativeRing import Algebra import UnivariatePolynomialCategory import PositiveInteger import Vector import Matrix )abbrev category FINRALG FiniteRankAlgebra ++ Author: Barry Trager ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ A FiniteRankAlgebra is an algebra over a commutative ring R which ++ is a free R-module of finite rank. FiniteRankAlgebra(R:CommutativeRing, UP:UnivariatePolynomialCategory R): Category == Algebra R with rank : () -> PositiveInteger ++ rank() returns the rank of the algebra. regularRepresentation : (% , Vector %) -> Matrix R ++ regularRepresentation(a,basis) returns the matrix of the ++ linear map defined by left multiplication by \spad{a} with respect ++ to the basis \spad{basis}. trace : % -> R ++ trace(a) returns the trace of the regular representation ++ of \spad{a} with respect to any basis. norm : % -> R ++ norm(a) returns the determinant of the regular representation ++ of \spad{a} with respect to any basis. coordinates : (%, Vector %) -> Vector R ++ coordinates(a,basis) returns the coordinates of \spad{a} with ++ respect to the basis \spad{basis}. coordinates : (Vector %, Vector %) -> Matrix R ++ coordinates([v1,...,vm], basis) returns the coordinates of the ++ vi's with to the basis \spad{basis}. The coordinates of vi are ++ contained in the ith row of the matrix returned by this ++ function. represents : (Vector R, Vector %) -> % ++ represents([a1,..,an],[v1,..,vn]) returns \spad{a1*v1 + ... + an*vn}. discriminant : Vector % -> R ++ discriminant([v1,..,vn]) returns ++ \spad{determinant(traceMatrix([v1,..,vn]))}. traceMatrix : Vector % -> Matrix R ++ traceMatrix([v1,..,vn]) is the n-by-n matrix ( Tr(vi * vj) ) characteristicPolynomial: % -> UP ++ characteristicPolynomial(a) returns the characteristic ++ polynomial of the regular representation of \spad{a} with respect ++ to any basis. if R has Field then minimalPolynomial : % -> UP ++ minimalPolynomial(a) returns the minimal polynomial of \spad{a}. if R has CharacteristicZero then CharacteristicZero if R has CharacteristicNonZero then CharacteristicNonZero add discriminant v == determinant traceMatrix v coordinates(v:Vector %, b:Vector %) == m := new(#v, #b, 0)$Matrix(R) for i in minIndex v .. maxIndex v for j in minRowIndex m .. repeat setRow!(m, j, coordinates(qelt(v, i), b)) m represents(v, b) == m := minIndex v - 1 +/[v(i+m) * b(i+m) for i in 1..rank()] traceMatrix v == matrix [[trace(v.i*v.j) for j in minIndex v..maxIndex v]$List(R) for i in minIndex v .. maxIndex v]$List(List R) regularRepresentation(x, b) == m := minIndex b - 1 matrix [members coordinates(x*b(i+m),b) for i in 1..rank()]$List(List R) @ \section{category FRAMALG FramedAlgebra} <>= import CommutativeRing import UnivariatePolynomialCategory import Vector )abbrev category FRAMALG FramedAlgebra ++ Author: Barry Trager ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ A \spadtype{FramedAlgebra} is a \spadtype{FiniteRankAlgebra} together ++ with a fixed R-module basis. FramedAlgebra(R:CommutativeRing, UP:UnivariatePolynomialCategory R): Category == FiniteRankAlgebra(R, UP) with --operations basis : () -> Vector % ++ basis() returns the fixed R-module basis. coordinates : % -> Vector R ++ coordinates(a) returns the coordinates of \spad{a} with respect to the ++ fixed R-module basis. coordinates : Vector % -> Matrix R ++ coordinates([v1,...,vm]) returns the coordinates of the ++ vi's with to the fixed basis. The coordinates of vi are ++ contained in the ith row of the matrix returned by this ++ function. represents : Vector R -> % ++ represents([a1,..,an]) returns \spad{a1*v1 + ... + an*vn}, where ++ v1, ..., vn are the elements of the fixed basis. convert : % -> Vector R ++ convert(a) returns the coordinates of \spad{a} with respect to the ++ fixed R-module basis. convert : Vector R -> % ++ convert([a1,..,an]) returns \spad{a1*v1 + ... + an*vn}, where ++ v1, ..., vn are the elements of the fixed basis. traceMatrix : () -> Matrix R ++ traceMatrix() is the n-by-n matrix ( \spad{Tr(vi * vj)} ), where ++ v1, ..., vn are the elements of the fixed basis. discriminant : () -> R ++ discriminant() = determinant(traceMatrix()). regularRepresentation : % -> Matrix R ++ regularRepresentation(a) returns the matrix of the linear ++ map defined by left multiplication by \spad{a} with respect ++ to the fixed basis. --attributes --separable <=> discriminant() ~= 0 add convert(x:%):Vector(R) == coordinates(x) convert(v:Vector R):% == represents(v) traceMatrix() == traceMatrix basis() discriminant() == discriminant basis() coordinates(x:%) == coordinates(x, basis()) represents x == represents(x, basis()) coordinates(v:Vector %) == m := new(#v, rank(), 0)$Matrix(R) for i in minIndex v .. maxIndex v for j in minRowIndex m .. repeat setRow!(m, j, coordinates qelt(v, i)) m regularRepresentation x == m := new(n := rank(), n, 0)$Matrix(R) b := basis() for i in minIndex b .. maxIndex b for j in minRowIndex m .. repeat setRow!(m, j, coordinates(x * qelt(b, i))) m characteristicPolynomial x == mat00 := (regularRepresentation x) mat0 := map(#1 :: UP,mat00)$MatrixCategoryFunctions2(R, Vector R, Vector R, Matrix R, UP, Vector UP,Vector UP, Matrix UP) mat1 : Matrix UP := scalarMatrix(rank(),monomial(1,1)$UP) determinant(mat1 - mat0) if R has Field then -- depends on the ordering of results from nullSpace, also see FFP minimalPolynomial(x:%):UP == y:%:=1 n:=rank() m:Matrix R:=zero(n,n+1) for i in 1..n+1 repeat setColumn!(m,i,coordinates(y)) y:=y*x v:=first nullSpace(m) +/[monomial(v.(i+1),i) for i in 0..#v-1] @ \section{category MONOGEN MonogenicAlgebra} <>= import CommutativeRing import UnivariatePolynomialCategory import FramedAlgebra import FullyRetractableTo import FullyLinearlyExplicitRingOver )abbrev category MONOGEN MonogenicAlgebra ++ Author: Barry Trager ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ A \spadtype{MonogenicAlgebra} is an algebra of finite rank which ++ can be generated by a single element. MonogenicAlgebra(R:CommutativeRing, UP:UnivariatePolynomialCategory R): Category == Join(FramedAlgebra(R, UP), CommutativeRing, ConvertibleTo UP, FullyRetractableTo R, FullyLinearlyExplicitRingOver R) with generator : () -> % ++ generator() returns the generator for this domain. definingPolynomial: () -> UP ++ definingPolynomial() returns the minimal polynomial which ++ \spad{generator()} satisfies. reduce : UP -> % ++ reduce(up) converts the univariate polynomial up to an algebra ++ element, reducing by the \spad{definingPolynomial()} if necessary. convert : UP -> % ++ convert(up) converts the univariate polynomial up to an algebra ++ element, reducing by the \spad{definingPolynomial()} if necessary. lift : % -> UP ++ lift(z) returns a minimal degree univariate polynomial up such that ++ \spad{z=reduce up}. if R has Finite then Finite if R has Field then Field DifferentialExtension R reduce : Fraction UP -> Union(%, "failed") ++ reduce(frac) converts the fraction frac to an algebra element. derivationCoordinates: (Vector %, R -> R) -> Matrix R ++ derivationCoordinates(b, ') returns M such that \spad{b' = M b}. if R has FiniteFieldCategory then FiniteFieldCategory add convert(x:%):UP == lift x convert(p:UP):% == reduce p generator() == reduce monomial(1, 1)$UP norm x == resultant(definingPolynomial(), lift x) retract(x:%):R == retract lift x retractIfCan(x:%):Union(R, "failed") == retractIfCan lift x basis() == [reduce monomial(1,i)$UP for i in 0..(rank()-1)::NonNegativeInteger] characteristicPolynomial(x:%):UP == characteristicPolynomial(x)$CharacteristicPolynomialInMonogenicalAlgebra(R,UP,%) if R has Finite then size() == size()$R ** rank() random() == represents [random()$R for i in 1..rank()]$Vector(R) if R has Field then reduce(x:Fraction UP) == reduce(numer x) exquo reduce(denom x) differentiate(x:%, d:R -> R) == p := definingPolynomial() yprime := - reduce(map(d, p)) / reduce(differentiate p) reduce(map(d, lift x)) + yprime * reduce differentiate lift x derivationCoordinates(b, d) == coordinates(map(differentiate(#1, d), b), b) recip x == (bc := extendedEuclidean(lift x, definingPolynomial(), 1)) case "failed" => "failed" reduce(bc.coef1) @ \section{package CPIMA CharacteristicPolynomialInMonogenicalAlgebra} <>= import CommutativeRing import UnivariatePolynomialCategory import MonogenicAlgebra )abbrev package CPIMA CharacteristicPolynomialInMonogenicalAlgebra ++ Author: Claude Quitte ++ Date Created: 10/12/93 ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ This package implements characteristicPolynomials for monogenic algebras ++ using resultants CharacteristicPolynomialInMonogenicalAlgebra(R : CommutativeRing, PolR : UnivariatePolynomialCategory(R), E : MonogenicAlgebra(R, PolR)): with characteristicPolynomial : E -> PolR ++ characteristicPolynomial(e) returns the characteristic polynomial ++ of e using resultants == add Pol ==> SparseUnivariatePolynomial import UnivariatePolynomialCategoryFunctions2(R, PolR, PolR, Pol(PolR)) XtoY(Q : PolR) : Pol(PolR) == map(monomial(#1, 0), Q) P : Pol(PolR) := XtoY(definingPolynomial()$E) X : Pol(PolR) := monomial(monomial(1, 1)$PolR, 0) characteristicPolynomial(x : E) : PolR == Qx : PolR := lift(x) -- on utilise le fait que resultant_Y (P(Y), X - Qx(Y)) return resultant(P, X - XtoY(Qx)) @ \section{package NORMMA NormInMonogenicAlgebra} <>= import GcdDomain import UnivariatePolynomialCategory import MonogenicAlgebra )abbrev package NORMMA NormInMonogenicAlgebra ++ Author: Manuel Bronstein ++ Date Created: 23 February 1995 ++ Date Last Updated: 23 February 1995 ++ Basic Functions: norm ++ Description: ++ This package implements the norm of a polynomial with coefficients ++ in a monogenic algebra (using resultants) NormInMonogenicAlgebra(R, PolR, E, PolE): Exports == Implementation where R: GcdDomain PolR: UnivariatePolynomialCategory R E: MonogenicAlgebra(R, PolR) PolE: UnivariatePolynomialCategory E SUP ==> SparseUnivariatePolynomial Exports ==> with norm: PolE -> PolR ++ norm q returns the norm of q, ++ i.e. the product of all the conjugates of q. Implementation ==> add import UnivariatePolynomialCategoryFunctions2(R, PolR, PolR, SUP PolR) PolR2SUP: PolR -> SUP PolR PolR2SUP q == map(#1::PolR, q) defpol := PolR2SUP(definingPolynomial()$E) norm q == p:SUP PolR := 0 while q ~= 0 repeat p := p + monomial(1,degree q)$PolR * PolR2SUP lift leadingCoefficient q q := reductum q primitivePart resultant(p, defpol) @ \section{License} <>= --Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. --All rights reserved. -- --Redistribution and use in source and binary forms, with or without --modification, are permitted provided that the following conditions are --met: -- -- - Redistributions of source code must retain the above copyright -- notice, this list of conditions and the following disclaimer. -- -- - Redistributions in binary form must reproduce the above copyright -- notice, this list of conditions and the following disclaimer in -- the documentation and/or other materials provided with the -- distribution. -- -- - Neither the name of The Numerical ALgorithms Group Ltd. nor the -- names of its contributors may be used to endorse or promote products -- derived from this software without specific prior written permission. -- --THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS --IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED --TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A --PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER --OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, --EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, --PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR --PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF --LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING --NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS --SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. @ <<*>>= <> <> <> <> <> <> @ \eject \begin{thebibliography}{99} \bibitem{1} nothing \end{thebibliography} \end{document}