open-axiom repository from github
\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}
<<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}
<<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}
<<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}
<<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}
<<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}
<<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.
@
<<*>>=
<<license>>
<<category FINRALG FiniteRankAlgebra>>
<<category FRAMALG FramedAlgebra>>
<<category MONOGEN MonogenicAlgebra>>
<<package CPIMA CharacteristicPolynomialInMonogenicalAlgebra>>
<<package NORMMA NormInMonogenicAlgebra>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}