Initial population.

1 files changed, 382 insertions, 0 deletions

diff --git a/src/algebra/algcat.spad.pamphlet b/src/algebra/algcat.spad.pamphlet
new file mode 100644
index 00000000..5c028319
--- /dev/null
+++ b/src/algebra/algcat.spad.pamphlet
@@ -0,0 +1,382 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra algcat.spad}
+\author{Barry Trager, Claude Quitte, Manuel Bronstein}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{category FINRALG FiniteRankAlgebra}
+<<category FINRALG FiniteRankAlgebra>>=
+)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
+       [parts coordinates(x*b(i+m),b) for i in 1..rank()]$List(List R)
+
+@
+\section{category FRAMALG FramedAlgebra}
+<<category FRAMALG FramedAlgebra>>=
+)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()
+   regularRepresentation x == regularRepresentation(x, 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>>=
+)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>>=
+)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>>=
+)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}