% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\IntegerLinearDependenceXmpTitle}{IntegerLinearDependence}
\newcommand{\IntegerLinearDependenceXmpNumber}{9.35}
%
% =====================================================================
\begin{page}{IntegerLinearDependenceXmpPage}{9.35 IntegerLinearDependence}
% =====================================================================
\beginscroll


The elements \texht{$v_1, \dots,v_n$}{\spad{v1,...,vn}}
of a module \spad{M} over a ring \spad{R} are
%-% \HDindex{linear dependence}{IntegerLinearDependenceXmpPage}{9.35}{IntegerLinearDependence}
said to be {\it linearly dependent over \spad{R}} if there exist
\texht{$c_1,\dots,c_n$}{\spad{c1, ..., cn}} in \spad{R},
not all \smath{0},
such that \texht{$c_1 v_1 + \dots c_n v_n = 0$}{\spad{c1*v1 + ... + cn*vn = 0}}.
If such \texht{$c_i$}{\spad{ci}}'s exist,
they form what is called a {\it linear dependence
relation over \spad{R}} for the \texht{$v_i$}{\spad{vi}}'s.

The package \spadtype{IntegerLinearDependence} provides functions
for testing whether some elements of a module over the integers are
linearly dependent over the integers, and to find the linear
dependence relations, if any.
%
\xtc{
Consider the domain of two by two square matrices with integer entries.
}{
\spadpaste{M := SQMATRIX(2,INT) \bound{M}}
}
%
%
\xtc{
Now create three such matrices.
}{
\spadpaste{m1: M := squareMatrix matrix [[1, 2], [0, -1]] \free{M}\bound{m1}}
}
\xtc{
}{
\spadpaste{m2: M := squareMatrix matrix [[2, 3], [1, -2]] \free{M}\bound{m2}}
}
\xtc{
}{
\spadpaste{m3: M := squareMatrix matrix [[3, 4], [2, -3]] \free{M}\bound{m3}}
}
%
%
\xtc{
This tells you whether \spad{m1}, \spad{m2} and \spad{m3} are linearly
dependent over the integers.
}{
\spadpaste{linearlyDependentOverZ? vector [m1, m2, m3] \free{m1 m2 m3}}
}
%
%
\xtc{
Since they are linearly dependent, you can ask for the dependence
relation.
}{
\spadpaste{c := linearDependenceOverZ vector [m1, m2, m3] \free{m1 m2 m3}\bound{c}}
}
%
%
\xtc{
This means that the following linear combination should be \spad{0}.
}{
\spadpaste{c.1 * m1 + c.2 * m2 + c.3 * m3 \free{c m1 m2 m3}}
}
%
When a given set of elements are linearly dependent over \spad{R}, this
also means that at least one of them can be rewritten as a linear
combination of the others with coefficients in the quotient field of
\spad{R}.
%
\xtc{
To express a given element in terms of other elements, use the operation
\spadfunFrom{solveLinearlyOverQ}{IntegerLinearDependence}.
}{
\spadpaste{solveLinearlyOverQ(vector [m1, m3], m2) \free{m1 m2 m3}}
}
\endscroll
\autobuttons
\end{page}
%