\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra lindep.spad}
\author{Manuel Bronstein}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{package LINDEP LinearDependence}
<<package LINDEP LinearDependence>>=
)abbrev package LINDEP LinearDependence
++ Test for linear dependence
++ Author: Manuel Bronstein
++ Date Created: ???
++ Date Last Updated: 14 May 1991
++ Description: Test for linear dependence.
LinearDependence(S, R): Exports == Implementation where
  S: IntegralDomain
  R: Join(Ring,LinearlyExplicitRingOver S)

  Q ==> Fraction S

  Exports ==> with
    linearlyDependent?: Vector R -> Boolean
      ++ \spad{linearlyDependent?([v1,...,vn])} returns true if
      ++ the vi's are linearly dependent over S, false otherwise.
    linearDependence  : Vector R -> Union(Vector S, "failed")
      ++ \spad{linearDependence([v1,...,vn])} returns \spad{[c1,...,cn]} if
      ++ \spad{c1*v1 + ... + cn*vn = 0} and not all the ci's are 0,
      ++ "failed" if the vi's are linearly independent over S.
    if S has Field then
      solveLinear: (Vector R, R) -> Union(Vector S, "failed")
        ++ \spad{solveLinear([v1,...,vn], u)} returns \spad{[c1,...,cn]}
        ++ such that \spad{c1*v1 + ... + cn*vn = u},
        ++ "failed" if no such ci's exist in S.
    else
      solveLinear: (Vector R, R) -> Union(Vector Q, "failed")
        ++ \spad{solveLinear([v1,...,vn], u)} returns \spad{[c1,...,cn]}
        ++ such that \spad{c1*v1 + ... + cn*vn = u},
        ++ "failed" if no such ci's exist in the quotient field of S.

  Implementation ==> add
    aNonZeroSolution: Matrix S -> Union(Vector S, "failed")

    aNonZeroSolution m ==
      every?(zero?, v := first nullSpace m) => "failed"
      v

    linearlyDependent? v ==
      zero?(n := #v) => true
      one? n => zero?(v(minIndex v))
      positive? nullity reducedSystem transpose v

    linearDependence v ==
      zero?(n := #v) => empty()
      one? n =>
        zero?(v(minIndex v)) => new(1, 1)
        "failed"
      aNonZeroSolution reducedSystem transpose v

    if S has Field then
      solveLinear(v:Vector R, c:R):Union(Vector S, "failed") ==
        zero? c => new(#v, 0)
        empty? v => "failed"
        sys := reducedSystem(transpose v, new(1, c))
        particularSolution(sys.mat, sys.vec)$LinearSystemMatrixPackage(S,
                                           Vector S, Vector S, Matrix S)

    else
      solveLinear(v:Vector R, c:R):Union(Vector Q, "failed") ==
        zero? c => new(#v, 0)
        empty? v => "failed"
        sys := reducedSystem(transpose v, new(1, c))
        particularSolution(map(#1::Q, sys.mat)$MatrixCategoryFunctions2(S,
               Vector S,Vector S,Matrix S,Q,Vector Q,Vector Q,Matrix Q),
                  map(#1::Q, sys.vec)$VectorFunctions2(S, Q)
                                    )$LinearSystemMatrixPackage(Q,
                                           Vector Q, Vector Q, Matrix Q)

@
\section{package ZLINDEP IntegerLinearDependence}
<<package ZLINDEP IntegerLinearDependence>>=
)abbrev package ZLINDEP IntegerLinearDependence
++ Test for linear dependence over the integers
++ Author: Manuel Bronstein
++ Date Created: ???
++ Date Last Updated: 14 May 1991
++ Description: Test for linear dependence over the integers.
IntegerLinearDependence(R): Exports == Implementation where
  R: Join(Ring,LinearlyExplicitRingOver Integer)

  Z ==> Integer

  Exports ==> with
    linearlyDependentOverZ?: Vector R -> Boolean
      ++ \spad{linearlyDependentOverZ?([v1,...,vn])} returns true if the
      ++ vi's are linearly dependent over the integers, false otherwise.
    linearDependenceOverZ  : Vector R -> Union(Vector Z, "failed")
      ++ \spad{linearlyDependenceOverZ([v1,...,vn])} returns
      ++ \spad{[c1,...,cn]} if
      ++ \spad{c1*v1 + ... + cn*vn = 0} and not all the ci's are 0, "failed"
      ++ if the vi's are linearly independent over the integers.
    solveLinearlyOverQ     : (Vector R, R) ->
                                      Union(Vector Fraction Z, "failed")
      ++ \spad{solveLinearlyOverQ([v1,...,vn], u)} returns \spad{[c1,...,cn]}
      ++ such that \spad{c1*v1 + ... + cn*vn = u},
      ++ "failed" if no such rational numbers ci's exist.

  Implementation ==> add
    import LinearDependence(Z, R)

    linearlyDependentOverZ? v == linearlyDependent? v
    linearDependenceOverZ   v == linearDependence v
    solveLinearlyOverQ(v, c)  == solveLinear(v, c)

@
\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>>

<<package LINDEP LinearDependence>>
<<package ZLINDEP IntegerLinearDependence>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}