File r36/doc/LINALG.TEX artifact 01faafeb24 part of check-in e08999f63f


\documentstyle[11pt,reduce,fancyheadings]{article}
\title{A Linear Algebra package for \REDUCE{}}
\author{Matt Rebbeck \\
        Konrad-Zuse-Zentrum f\"ur Informationstechnik Berlin}
\date{July 1994}

\def\foottitle{The Linear Algebra Package}
\pagestyle{fancy}
\lhead[]{{\footnotesize\leftmark}{}}
\rhead[]{\thepage}
\setlength{\headrulewidth}{0.6pt}
\setlength{\footrulewidth}{0.6pt}
\cfoot{}
\rfoot{\small\foottitle}

%decided against using these.
%\def\ltri{$\triangleleft$}
%\def\rtri{$\triangleright$}
%\newcommand{\tribound}[1]{\rtri#1\ltri}

\def\exprlist  {expr$_{1}$,expr$_{2}$, \ldots ,expr$_{{\tt n}}$}
\def\lineqlist {lin\_eqn$_{1}$,lin\_eqn$_{2}$, \ldots ,lin\_eqn$_{n}$}
\def\matlist   {mat$_{1}$,mat$_{2}$, \ldots ,mat$_{n}$}
\def\veclist   {vec$_{1}$,vec$_{2}$, \ldots ,vec$_{n}$}

\def\lazyfootnote{\footnote{If you're feeling lazy then the \{\}'s can
                  be omitted.}}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\begin{document}
\maketitle
\index{Linear Algebra package}

\section{Introduction}
This package provides a selection of functions that are useful
in the world of linear algebra. These functions are described
alphabetically in section 3 of this document and are labelled 3.1 to
3.51. They can be classified into four sections(n.b: the numbers after
the dots signify the function label in section 3).

\subsection{Basic matrix handling}

\begin{center}
\begin{tabular}{l l l l l l}
add\_columns     & \ldots & 3.1  &
add\_rows        & \ldots & 3.2  \\
add\_to\_columns & \ldots & 3.3  &
add\_to\_rows    & \ldots & 3.4  \\
augment\_columns & \ldots & 3.5  &
char\_poly       & \ldots & 3.9  \\
column\_dim      & \ldots & 3.12  &
copy\_into       & \ldots & 3.14 \\
diagonal         & \ldots & 3.15 &
extend           & \ldots & 3.16 \\
find\_companion  & \ldots & 3.17  &
get\_columns     & \ldots & 3.18 \\
get\_rows        & \ldots & 3.19 &
hermitian\_tp    & \ldots & 3.21 \\
matrix\_augment  & \ldots & 3.28 &
matrix\_stack    & \ldots & 3.30 \\
minor            & \ldots & 3.31 &
mult\_columns    & \ldots & 3.32 \\
mult\_rows       & \ldots & 3.33 &
pivot            & \ldots & 3.34 \\
remove\_columns  & \ldots & 3.37 &
remove\_rows     & \ldots & 3.38 \\
row\_dim         & \ldots & 3.39 &
rows\_pivot      & \ldots & 3.40 \\
stack\_rows      & \ldots & 3.43 &
sub\_matrix      & \ldots & 3.44 \\
swap\_columns    & \ldots & 3.46 &
swap\_entries    & \ldots & 3.47 \\
swap\_rows       & \ldots & 3.48 &
\end{tabular}
\end{center}

\subsection{Constructors}

Functions that create matrices.

\begin{center}
\begin{tabular}{l l l l l l}
band\_matrix       & \ldots & 3. 6 &
block\_matrix      & \ldots & 3. 7 \\
char\_matrix       & \ldots & 3. 8 &
coeff\_matrix      & \ldots & 3. 11 \\
companion          & \ldots & 3. 13 &
hessian            & \ldots & 3. 22 \\
hilbert            & \ldots & 3. 23 &
jacobian           & \ldots & 3. 24 \\
jordan\_block      & \ldots & 3. 25 &
make\_identity     & \ldots & 3. 27 \\
random\_matrix     & \ldots & 3. 36 &
toeplitz           & \ldots & 3. 50 \\
Vandermonde        & \ldots & 3. 51 &
Kronecker\_Product & \ldots & 3. 52
\end{tabular}
\end{center}

\subsection{High level algorithms}

\begin{center}
\begin{tabular}{l l l l l l}
char\_poly       & \ldots & 3.9 &
cholesky         & \ldots & 3.10 \\
gram\_schmidt    & \ldots & 3.20 &
lu\_decom        & \ldots & 3.26 \\
pseudo\_inverse  & \ldots & 3.35 &
simplex          & \ldots & 3.41 \\
svd              & \ldots & 3.45 &
\end{tabular}
\end{center}

\vspace*{5mm}
There is a separate {\small NORMFORM}[1] package for computing
the following matrix normal forms in \REDUCE.

\begin{center}
smithex, smithex\_int, frobenius, ratjordan, jordansymbolic, jordan.
\end{center}

\subsection{Predicates}

\begin{center}
\begin{tabular}{l l l l l l}
matrixp     & \ldots & 3.29 &
squarep     & \ldots & 3.42 \\
symmetricp  & \ldots & 3.49 &
\end{tabular}
\end{center}

\subsection*{Note on examples:}

In the examples the matrix ${\cal A}$ will be

\begin{flushleft}
\begin{math}
{\cal A} = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9
\end{array} \right)
\end{math}
\end{flushleft}


\subsection*{Notation}

Throughout ${\cal I}$ is used to indicate the identity matrix and
${\cal A}^T$ to indicate the transpose of the matrix ${\cal A}$.

\section{Getting started}

If you have not used matrices within {\REDUCE} before then the
following may be helpful.

\subsection*{Creating matrices}

Initialisation of matrices takes the following syntax:

{\tt mat1 := mat((a,b,c),(d,e,f),(g,h,i));}

will produce

\begin{flushleft}
\begin{math}
mat1 := \left( \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i
\end{array} \right)
\end{math}
\end{flushleft}

\subsection*{Getting at the entries}

The (i,$\,$j)'th entry can be accessed by:

{\tt mat1(i,j);}

\subsection*{Loading the linear\_algebra package}

The package is loaded by:

{\tt load\_package linalg;}


\section{What's available}

\subsection{add\_columns, add\_rows}

%{\bf How to use it:}

\hspace*{0.175in} {\tt add\_columns(${\cal A}$,c1,c2,expr);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ & :- & a matrix. \\
c1,c2      & :- & positive integers. \\
expr       & :- & a scalar expression.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
\parbox[t]{0.95\linewidth}{{\tt add\_columns} replaces column c2 of
${\cal A}$ by expr $*$ column(${\cal A}$,c1) $+$ column(${\cal A}$,c2).}

{\tt add\_rows} performs the equivalent task on the rows of ${\cal A}$.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\begin{math}
\hspace*{0.16in}
\begin{array}{ccc}
{\tt add\_columns}({\cal A},1,2,x) & = &
\left( \begin{array}{ccc} 1 & x+2 & 3 \\ 4 & 4*x+5 & 6 \\ 7 & 7*x+8 & 9
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\vspace*{0.1in}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt add\_rows}({\cal A},2,3,5) & = &
\left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 27 & 33 & 39
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt add\_to\_columns}, {\tt add\_to\_rows},
{\tt mult\_columns}, {\tt mult\_rows}.


\subsection{add\_rows}

\hspace*{0.175in} see: {\tt add\_columns}.


\subsection{add\_to\_columns, add\_to\_rows}

%{\bf How to use it:}

\hspace*{0.175in} {\tt add\_to\_columns(${\cal A}$,column\_list,expr);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$   &:-& a matrix. \\
column\_list &:-& a positive integer or a list of positive integers. \\
expr        &:-& a scalar expression.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt add\_to\_columns} adds expr to each column specified in
column\_list of ${\cal A}$.

{\tt add\_to\_rows} performs the equivalent task on the rows of
${\cal A}$.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
\begin{array}{ccc}
{\tt add\_to\_columns}({\cal A},\{1,2\},10) & = &
\left( \begin{array}{ccc} 11 & 12 & 3 \\ 14 & 15 & 6 \\ 17 & 18 & 9
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\vspace*{0.1in}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
\begin{array}{ccc}
{\tt add\_to\_rows}({\cal A},2,-x) & = &
\left( \begin{array}{ccc} 1 & 2 & 3 \\ -x+4 & -x+5 & -x+6 \\ 7 & 8 & 9
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in}
{\tt add\_columns}, {\tt add\_rows}, {\tt mult\_rows},
{\tt mult\_columns}.


\subsection{add\_to\_rows}

\hspace*{0.175in} see: {\tt add\_to\_columns}.


\subsection{augment\_columns, stack\_rows}

%{\bf How to use it:}

\hspace*{0.175in} {\tt augment\_columns(${\cal A}$,column\_list);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$  &:-& a matrix. \\
column\_list &:-&  either a positive integer or a list of positive
                   integers.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt augment\_columns} gets hold of the columns of ${\cal A}$ specified
in column\_list and sticks them together.

{\tt stack\_rows} performs the same task on rows of
                ${\cal A}$.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt augment\_columns}({\cal A},\{1,2\}) & = &
\left( \begin{array}{cc} 1 & 2 \\ 4 & 5 \\ 7 & 8
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\vspace*{0.1in}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt stack\_rows}({\cal A},\{1,3\}) & = &
\left( \begin{array}{ccc} 1 & 2 & 3 \\ 7 & 8 & 9
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt get\_columns}, {\tt get\_rows},
{\tt sub\_matrix}.


\subsection{band\_matrix}

%{\bf How to use it:}

\hspace*{0.175in} {\tt band\_matrix(expr\_list,square\_size);}

\hspace*{0.1in}
\begin{tabular}{l l l}
expr\_list  \hspace*{0.088in} &:-& \parbox[t]{.72\linewidth}
{either a single scalar expression or a list of an odd number of scalar
expressions.}
\end{tabular}

\vspace*{0.04in}
\hspace*{0.1in}
\begin{tabular}{l l l}
square\_size &:-& a positive integer.
\end{tabular}


{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
                {\tt band\_matrix} creates a square matrix of dimension
                square\_size. The diagonal consists of the middle expr
                of the expr\_list. The exprs to the left of this fill
                the required number of sub\_diagonals and the exprs
                to the right the super\_diagonals.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt band\_matrix}(\{x,y,z\},6) & = &
\left( \begin{array}{cccccc} y & z & 0 & 0 & 0 & 0 \\ x & y & z & 0 & 0
& 0 \\ 0 & x & y & z & 0 & 0 \\ 0 & 0 & x & y & z & 0 \\ 0 & 0 & 0 & x &
 y & z \\ 0 & 0 & 0 & 0 & x & y
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt diagonal}.


\subsection{block\_matrix}

%{\bf How to use it:}

\hspace*{0.175in} {\tt block\_matrix(r,c,matrix\_list);}

\hspace*{0.1in}
\begin{tabular}{l l l}
r,c          &:-& positive integers. \\
matrix\_list &:-& a list of matrices.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt block\_matrix} creates a matrix that consists of r by c matrices
filled from the matrix\_list row wise.

\end{addtolength}


{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\cal B} = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1
\end{array} \right), &
{\cal C} = \left( \begin{array}{c} 5 \\ 5
\end{array} \right), &
{\cal D} = \left( \begin{array}{cc} 22 & 33 \\ 44 & 55
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\vspace*{0.175in}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt block\_matrix}(2,3,\{{\cal B,C,D,D,C,B}\}) & = &
\left( \begin{array}{ccccc} 1 & 0 & 5 & 22 & 33 \\ 0 & 1 & 5 & 44 & 55
\\
22 & 33 & 5 & 1 & 0 \\ 44 & 55 & 5 & 0 & 1
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}


\subsection{char\_matrix}

%{\bf How to use it:}

\hspace*{0.175in} {\tt char\_matrix(${\cal A},\lambda$);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a square matrix. \\
$\lambda$  &:-& a symbol or algebraic expression.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt char\_matrix} creates the characteristic matrix ${\cal C}$ of
${\cal A}$.

This is ${\cal C} = \lambda * {\cal I} - {\cal A}$.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt char\_matrix}({\cal A},x) & = &
\left( \begin{array}{ccc} x-1 & -2 & -3 \\ -4 & x-5 & -6 \\ -7 & -8 &
x-9
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt char\_poly}.


\subsection{char\_poly}

%{\bf How to use it:}

\hspace*{0.175in} {\tt char\_poly(${\cal A},\lambda$);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a square matrix. \\
$\lambda$ &:-& a symbol or algebraic expression.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt char\_poly} finds the characteristic polynomial of
                ${\cal A}$.

This is the determinant of $\lambda * {\cal I} - {\cal A}$.

\end{addtolength}

{\bf Examples:}

\hspace*{0.175in}
{\tt char\_poly({\cal A},$x$) $= x^3-15*x^2-18*x$}

{\bf Related functions:}

\hspace*{0.175in} {\tt char\_matrix}.


\subsection{cholesky}

%{\bf How to use it:}

\hspace*{0.175in} {\tt cholesky(${\cal A}$);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a positive definite matrix containing numeric entries.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt cholesky} computes the cholesky decomposition of ${\cal A}$.

It returns \{${\cal L,U}$\} where ${\cal L}$
is a lower matrix, ${\cal U}$ is an upper matrix, \\ ${\cal A} =
{\cal LU}$, and ${\cal U} = {\cal L}^T$.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
{\cal F} = \left( \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 3 & 1 \\ 0 & 1 &
1
\end{array} \right)
\end{math}
\end{flushleft}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
${\tt cholesky}$({\cal F}) & = &
\left\{ \left( \begin{array}{ccc} 1 & 0 & 0 \\ 1 & \sqrt{2} & 0 \\
0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array} \right), \left(
\begin{array}{ccc} 1 & 1 & 0 \\ 0 & \sqrt{2} & \frac{1}{\sqrt{2}} \\ 0
& 0 & \frac{1}{\sqrt{2}} \end{array} \right)
\right\} \end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt lu\_decom}.


\subsection{coeff\_matrix}

%{\bf How to use it:}

\hspace*{0.175in} {\tt coeff\_matrix(\{\lineqlist{}\});}
\lazyfootnote{}

\hspace*{0.1in}
\begin{tabular}{l l l}
\lineqlist  &:-& \parbox[t]{.435\linewidth}{linear equations. Can be
of the form {\it equation $=$ number} or just {\it equation}.}
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt coeff\_matrix} creates the coefficient matrix
                ${\cal C}$ of the linear equations.

It returns \{${\cal C,X,B}$\} such that ${\cal CX} = {\cal B}$.

\end{addtolength}


{\bf Examples:}

\begin{math}
\hspace*{0.175in}
{\tt coeff\_matrix}(\{x+y+4*z=10,y+x-z=20,x+y+4\}) =
\end{math}

\vspace*{0.1in}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
\left\{ \left( \begin{array}{ccc} 4 & 1 & 1 \\ -1 & 1 & 1 \\ 0 & 1 & 1
\end{array} \right), \left( \begin{array}{c} z \\ y \\ x \end{array}
\right), \left( \begin{array}{c} 10 \\ 20 \\ -4
\end{array} \right) \right\}
\end{math}
\end{flushleft}

\subsection{column\_dim, row\_dim}

%{\bf How to use it:}

\hspace*{0.175in} {\tt column\_dim(${\cal A}$);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\hspace*{0.175in} {\tt column\_dim} finds the column dimension of
                ${\cal A}$.

\hspace*{0.175in} {\tt row\_dim} finds the row dimension of ${\cal A}$.

{\bf Examples:}

\hspace*{0.175in}
{\tt column\_dim}(${\cal A}$) = 3

\subsection{companion}

%{\bf How to use it:}

\hspace*{0.175in} {\tt companion(poly,x);}

\hspace*{0.1in}
\begin{tabular}{l l l}
poly &:-& a monic univariate polynomial in x. \\
x    &:-& the variable.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}


\begin{addtolength}{\leftskip}{0.22in}
                {\tt companion} creates the companion matrix ${\cal C}$
                of poly.

This is the square matrix of dimension n, where n is the degree of poly
w.r.t. x.

The entries of ${\cal C}$ are:
                ${\cal C}$(i,n) = -coeffn(poly,x,i-1) for i = 1
                \ldots n, ${\cal C}$(i,i-1) = 1 for i = 2 \ldots n and
                the rest are 0.

\end{addtolength}


{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt companion}(x^4+17*x^3-9*x^2+11,x) & = &
\left( \begin{array}{cccc} 0 & 0 & 0 & -11 \\ 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 9 \\ 0 & 0 & 1 & -17
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt find\_companion}.


\subsection{copy\_into}

%{\bf How to use it:}

\hspace*{0.175in} {\tt copy\_into(${\cal A,B}$,r,c);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A,B}$ &:-& matrices. \\
r,c          &:-& positive integers.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\hspace*{0.175in} {\tt copy\_into} copies matrix ${\cal A}$ into
                ${\cal B}$ with ${\cal A}$(1,1) at ${\cal B}$(r,c).

{\bf Examples:}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
{\cal G} = \left( \begin{array}{cccc} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0
\end{array} \right)
\end{math}
\end{flushleft}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt copy\_into}({\cal A,G},1,2) & = &
\left( \begin{array}{cccc} 0 & 1 & 2 & 3 \\ 0 & 4 & 5 & 6 \\ 0 & 7 & 8
& 9 \\ 0 & 0 & 0 & 0
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt augment\_columns}, {\tt extend}, {\tt matrix\_augment},
{\tt matrix\_stack}, {\tt stack\_rows}, {\tt sub\_matrix}.

\end{addtolength}


\subsection{diagonal}

%{\bf How to use it:}

\hspace*{0.175in} {\tt diagonal(\{\matlist{}\});}\lazyfootnote{}

\hspace*{0.1in}
\begin{tabular}{l l l}
\matlist &:-& \parbox[t]{.58\linewidth}{each can be either a scalar
expr or a square matrix. }
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\hspace*{0.175in} {\tt diagonal} creates a matrix that contains the
input on the diagonal.

{\bf Examples:}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
{\cal H} = \left( \begin{array}{cc} 66 & 77 \\ 88 & 99
\end{array} \right)
\end{math}
\end{flushleft}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt diagonal}(\{{\cal A},x,{\cal H}\}) & = &
\left( \begin{array}{cccccc} 1 & 2 & 3 & 0 & 0 & 0 \\ 4 & 5 & 6 & 0 & 0
& 0 \\ 7 & 8 & 9 & 0 & 0 & 0 \\ 0 & 0 & 0 & x & 0 & 0 \\ 0 & 0 & 0 & 0
& 66 & 77 \\ 0 & 0 & 0 & 0 & 88 & 99
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt jordan\_block}.


\subsection{extend}

%{\bf How to use it:}

\hspace*{0.175in} {\tt extend(${\cal A}$,r,c,expr);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix. \\
r,c        &:-& positive integers. \\
expr      &:-& algebraic expression or symbol.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
                {\tt extend} returns a copy of ${\cal A}$ that has been
                extended by r rows and c columns. The new entries are
                made equal to expr.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt extend}({\cal A},1,2,x) & = &
\left( \begin{array}{ccccc} 1 & 2 & 3 & x & x \\ 4 & 5 & 6 & x & x
\\ 7 & 8 & 9 & x & x \\ x & x & x & x & x
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\begin{addtolength}{\leftskip}{0.22in}
\parbox[t]{0.95\linewidth}{{\tt copy\_into}, {\tt matrix\_augment},
{\tt matrix\_stack}, {\tt remove\_columns}, {\tt remove\_rows}.}

\end{addtolength}


\subsection{find\_companion}

\hspace*{0.175in} {\tt find\_companion(${\cal A}$,x);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix. \\
x          &:-& the variable.
\end{tabular}

{\bf Synopsis:}

\begin{addtolength}{\leftskip}{0.22in}
  Given a companion matrix, {\tt find\_companion} finds the polynomial
from which it was made.

\end{addtolength}


{\bf Examples:}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
{\cal C} = \left( \begin{array}{cccc} 0 & 0 & 0 & -11 \\ 1 & 0 & 0 & 0
\\ 0 & 1 & 0 & 9 \\ 0 & 0 & 1 & -17
\end{array} \right)
\end{math}
\end{flushleft}

\vspace*{3mm}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
{\tt find\_companion}({\cal C},x) = x^4+17*x^3-9*x^2+11
\end{math}
\end{flushleft}

\vspace*{3mm}

{\bf Related functions:}

\hspace*{0.175in} {\tt companion}.

\subsection{get\_columns, get\_rows}

%{\bf How to use it:}

\hspace*{0.175in} {\tt get\_columns(${\cal A}$,column\_list);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix. \\
c          &:-& either a positive integer or a list of positive
                integers.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt get\_columns} removes the columns of ${\cal A}$ specified in
                column\_list and returns them as a list of column
                matrices.

\end{addtolength}
\hspace*{0.175in} {\tt get\_rows} performs the same task on the rows of
                ${\cal A}$.

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt get\_columns}({\cal A},\{1,3\}) & = &
\left\{
        \left( \begin{array}{c} 1 \\ 4 \\ 7 \end{array} \right),
        \left( \begin{array}{c} 3 \\ 6 \\ 9 \end{array} \right)
\right\}
\end{array}
\end{math}
\end{flushleft}

\vspace*{0.1in}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt get\_rows}({\cal A},2) & = &
\left\{
        \left( \begin{array}{ccc} 4 & 5 & 6 \end{array} \right)
\right\}
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt augment\_columns}, {\tt stack\_rows},
{\tt sub\_matrix}.


\subsection{get\_rows}

\hspace*{0.175in} see: {\tt get\_columns}.


\subsection{gram\_schmidt}

%{\bf How to use it:}

\hspace*{0.175in} {\tt gram\_schmidt(\{\veclist{}\});} \lazyfootnote{}

\hspace*{0.1in}
\begin{tabular}{l l l}
\veclist &:-& \parbox[t]{.62\linewidth}{linearly independent vectors.
                             Each vector must be written as a list,
                             eg:\{1,0,0\}. }
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt gram\_schmidt} performs the gram\_schmidt
                orthonormalisation on the input vectors.

It returns a list of orthogonal normalised vectors.

\end{addtolength}

{\bf Examples:}

\hspace*{0.175in}
{\tt gram\_schmidt(\{\{1,0,0\},\{1,1,0\},\{1,1,1\}\})} =
\{\{1,0,0\},\{0,1,0\},\{0,0,1\}\}

\hspace*{0.175in}
{\tt gram\_schmidt(\{\{1,2\},\{3,4\}\})} $=
\{\{ \frac{1}{{\sqrt{5}}} , \frac{2}{\sqrt{5}} \},
\{ \frac{2*\sqrt{5}}{5} , \frac{-\sqrt{5}}{5} \}\}$

\subsection{hermitian\_tp}

%{\bf How to use it:}

\hspace*{0.175in} {\tt hermitian\_tp(${\cal A}$);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
                {\tt hermitian\_tp} computes the hermitian transpose of
                ${\cal A}$.

This is a matrix in which the (i,$\,$j)'th entry is the conjugate of
the (j,$\,$i)'th entry of ${\cal A}$.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
{\cal J} = \left( \begin{array}{ccc} i+1 & i+2 & i+3 \\ 4 & 5 & 2 \\ 1 &
i & 0
\end{array} \right)
\end{math}
\end{flushleft}

\vspace*{0.1in}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt hermitian\_tp}({\cal J}) & = &
\left( \begin{array}{ccc} -i+1 & 4 & 1 \\ -i+2 & 5 & -i \\-i+3 & 2 & 0
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt tp}\footnote{standard reduce call for the
transpose of a matrix - see {\REDUCE} User's Manual[2].}.


\subsection{hessian}

%{\bf How to use it:}

\hspace*{0.175in} {\tt hessian(expr,variable\_list);}

\hspace*{0.1in}
\begin{tabular}{l l l}
expr           &:-& a scalar expression. \\
variable\_list &:-& either a single variable or a list of variables.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
                {\tt hessian} computes the hessian matrix of expr w.r.t.
                the varibles in variable\_list.

This is an n by n matrix
                where n is the number of variables and the (i,$\,$j)'th
                entry is df(expr,variable\_list(i),variable\_list(j)).

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt hessian}(x*y*z+x^2,\{w,x,y,z\}) & = &
\left( \begin{array}{cccc} 0 & 0 & 0 & 0 \\ 0 & 2 & z & y \\ 0 & z & 0
& x \\ 0 & y & x & 0
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}


{\bf Related functions:}

\hspace*{0.175in} {\tt df}\footnote{standard reduce call for
differentiation - see {\REDUCE} User's Manual[2]}.


\subsection{hilbert}

%{\bf How to use it:}

\hspace*{0.175in} {\tt hilbert(square\_size,expr);}

\hspace*{0.1in}
\begin{tabular}{l l l}
square\_size &:-& a positive integer. \\
expr         &:-& an algebraic expression.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt hilbert} computes the square hilbert matrix of
                dimension square\_size.

This is the symmetric matrix in
                which the (i,$\,$j)'th entry is 1/(i+j-expr).

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt hilbert}(3,y+x) & = &
\left( \begin{array}{ccc} \frac{-1}{x+y-2} & \frac{-1}{x+y-3}
& \frac{-1}{x+y-4} \\ \frac{-1}{x+y-3} & \frac{-1}{x+y-4} &
\frac{-1}{x+y-5} \\ \frac{-1}{x+y-4} & \frac{-1}{x+y-5} &
\frac{-1}{x+y-6}
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}


\subsection{jacobian}

%{\bf How to use it:}

\hspace*{0.175in} {\tt jacobian(expr\_list,variable\_list);}

\hspace*{0.1in}
\begin{tabular}{l l l}
expr\_list   \hspace*{0.175in}  &:-& \parbox[t]{.72\linewidth}{either a
single algebraic expression or a list of algebraic expressions.}
\end{tabular}

\vspace*{0.04in}
\hspace*{0.1in}
\begin{tabular}{l l l}
variable\_list &:-& either a single variable or a list of variables.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt jacobian} computes the jacobian matrix of expr\_list w.r.t.
variable\_list.

This is a matrix whose (i,$\,$j)'th entry is df(expr\_list(i),
variable\_list(j)).

The matrix is n by m where n is the
                number of variables and m the number of expressions.

\end{addtolength}

{\bf Examples:}

\hspace*{0.175in}
{\tt jacobian(\{$x^4,x*y^2,x*y*z^3$\},\{$w,x,y,z$\})} =

\vspace*{0.1in}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
\left( \begin{array}{cccc} 0 & 4*x^3 & 0 & 0 \\ 0 & y^2 & 2*x*y & 0 \\
0 & y*z^3 & x*z^3 & 3*x*y*z^2
\end{array} \right)
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt hessian}, {\tt df}\footnote{standard reduce call
for differentiation - see {\REDUCE} User's Manual[2].}.


\subsection{jordan\_block}

%{\bf How to use it:}

\hspace*{0.175in} {\tt jordan\_block(expr,square\_size);}

\hspace*{0.1in}
\begin{tabular}{l l l}
expr        &:-& an algebraic expression or symbol. \\
square\_size &:-& a positive integer.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt jordan\_block} computes the square jordan block matrix ${\cal J}$
                of dimension square\_size.

The entries of ${\cal J}$ are:
                ${\cal J}$(i,i) = expr for i=1
                \ldots n, ${\cal J}$(i,i+1) = 1 for i=1
                \ldots n-1, and all other entries are 0.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt jordan\_block(x,5)} & = &
\left( \begin{array}{ccccc} x & 1 & 0 & 0 & 0 \\ 0 & x & 1 & 0 & 0 \\ 0
& 0 & x & 1 & 0 \\ 0 & 0 & 0 & x & 1 \\ 0 & 0 & 0 & 0 & x
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt diagonal}, {\tt companion}.


\subsection{lu\_decom}

%{\bf How to use it:}

\hspace*{0.175in} {\tt lu\_decom(${\cal A}$);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& \parbox[t]{.848\linewidth}{a matrix containing either
numeric entries or imaginary entries with numeric coefficients.}
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
              {\tt lu\_decom} performs LU decomposition on ${\cal A}$,
              ie: it returns \{${\cal L,U}$\} where ${\cal L}$
              is a lower diagonal matrix, ${\cal U}$ an upper diagonal
              matrix and ${\cal A} = {\cal LU}$.

\end{addtolength}

{\bf caution:}

\begin{addtolength}{\leftskip}{0.22in}
The algorithm used can swap the rows of ${\cal A}$
                during the calculation. This means that ${\cal LU}$ does
                not equal ${\cal A}$ but a row equivalent of it. Due to
                this, {\tt lu\_decom} returns \{${\cal L,U}$,vec\}. The
                call {\tt convert(${\cal A}$,vec)} will return the
                matrix that has been decomposed, ie: ${\cal LU} = $
                {\tt convert(${\cal A}$,vec)}.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
{\cal K} = \left( \begin{array}{ccc} 1 & 3 & 5 \\ -4 & 3 & 7 \\ 8 & 6 &
4
\end{array} \right)
\end{math}
\end{flushleft}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{cccc}
${\tt lu} := {\tt lu\_decom}$({\cal K}) & = &
\left\{
        \left( \begin{array}{ccc} 8 & 0 & 0 \\ -4 & 6 & 0 \\ 1 & 2.25 &
1.125 1 \end{array} \right),
        \left( \begin{array}{ccc} 1 & 0.75 & 0.5 \\ 0 & 1 & 1.5 \\ 0 &
0 & 1 \end{array} \right),
        [\; 3 \; 2 \; 3 \; ]
\right\}
\end{array}
\end{math}
\end{flushleft}

\vspace*{0.1in}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
${\tt first lu * second lu}$ & = &
        \left( \begin{array}{ccc} 8 & 6 & 4 \\ -4 & 3 & 7 \\ 1 & 3 & 5
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
${\tt convert(${\cal K}$,third lu}$) \hspace*{0.055in} & = &
        \left( \begin{array}{ccc} 8 & 6 & 4 \\ -4 & 3 & 7 \\ 1 & 3 & 5
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\vspace*{0.5in}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
{\cal P} = \left( \begin{array}{ccc} i+1 & i+2 & i+3 \\ 4 & 5 & 2 \\ 1
& i & 0
\end{array} \right)
\end{math}
\end{flushleft}

\begin{eqnarray}
\hspace*{0.22in}
{\tt lu} := {\tt lu\_decom}({\cal P}) & = &
\left\{
        \left( \begin{array}{ccc} 1 & 0 & 0 \\ 4 & -4*i+5 & 0 \\ i+1 &
3 & 0.41463*i+2.26829 \end{array} \right), \right. \nonumber \\ & &
\left. \: \; \,  \left( \begin{array}{ccc} 1 & i & 0 \\ 0 & 1 &
0.19512*i+0.24390 \\ 0 & 0 & 1 \end{array} \right), \hspace*{0.05in}
[\; 3 \; 2 \; 3 \;] \hspace*{0.05in}
\right\} \nonumber
\end{eqnarray}

\vspace*{0.1in}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
${\tt first lu * second lu}$ & = &
        \left( \begin{array}{ccc} 1 & i & 0 \\ 4 & 5 & 2 \\ i+1 & i+2 &
i+3
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
${\tt convert({\cal P},third lu}$) \hspace*{0.1in} & = & \left(
\begin{array}{c c c} 1 & i & 0 \\ 4 & 5 & 2 \\ i+1 & i+2 & i+3
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt cholesky}.


\subsection{make\_identity}

%{\bf How to use it:}

\hspace*{0.175in} {\tt make\_identity(square\_size);}

\hspace*{0.1in}
\begin{tabular}{l l l}
square\_size &:-& a positive integer.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\hspace*{0.175in} {\tt make\_identity} creates the identity matrix of
                dimension square\_size.

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt make\_identity}(4) & = &
        \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0
& 0 & 1 & 0 \\ 0 & 0 & 0 & 1
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt diagonal}.


\subsection{matrix\_augment, matrix\_stack}

%{\bf How to use it:}

\hspace*{0.175in} {\tt matrix\_augment(\{\matlist\});}\lazyfootnote{}

\hspace*{0.1in}
\begin{tabular}{l l l}
\matlist &:-& matrices.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\hspace*{0.175in} {\tt matrix\_augment} sticks the matrices in
                  matrix\_list together horizontally.

\hspace*{0.175in}
{\tt matrix\_stack} sticks the matrices in matrix\_list
                together vertically.

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt matrix\_augment}(\{{\cal A,A}\}) & = &
        \left( \begin{array}{cccccc} 1 & 2 & 3 & 1 & 2 & 3 \\ 4 & 4 & 6
& 4 & 5 & 6 \\ 7 & 8 & 9 & 7 & 8 & 9
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\vspace*{0.1in}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt matrix\_stack}(\{{\cal A,A}\}) & = &
        \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9
\\ 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt augment\_columns}, {\tt stack\_rows},
{\tt sub\_matrix}.


\subsection{matrixp}

%{\bf How to use it:}

\hspace*{0.175in} {\tt matrixp(test\_input);}

\hspace*{0.1in}
\begin{tabular}{l l l}
test\_input &:-& anything you like.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt matrixp} is a boolean function that returns t if
                the input is a matrix and nil otherwise.

\end{addtolength}

{\bf Examples:}

\hspace*{0.175in} {\tt matrixp}(${\cal A}$) = t

\hspace*{0.175in} {\tt matrixp}(doodlesackbanana) = nil

{\bf Related functions:}

\hspace*{0.175in} {\tt squarep}, {\tt symmetricp}.


\subsection{matrix\_stack}

\hspace*{0.175in} see: {\tt matrix\_augment}.


\subsection{minor}

%{\bf How to use it:}

\hspace*{0.175in} {\tt minor(${\cal A}$,r,c);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix. \\
r,c        &:-& positive integers.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
                {\tt minor} computes the (r,c)'th minor of ${\cal A}$.

                This is created by removing the r'th row and the c'th
                column from ${\cal A}$.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt minor}({\cal A},1,3) & = &
        \left( \begin{array}{cc} 4 & 5 \\ 7 & 8
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt remove\_columns}, {\tt remove\_rows}.


\subsection{mult\_columns, mult\_rows}

%{\bf How to use it:}

\hspace*{0.175in} {\tt mult\_columns(${\cal A}$,column\_list,expr);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$   &:-& a matrix. \\
column\_list &:-& a positive integer or a list of positive integers. \\
expr        &:-& an algebraic expression.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt mult\_columns} returns a copy of ${\cal A}$ in which
                the columns specified in column\_list have been
multiplied by expr.

{\tt mult\_rows} performs the same task on the rows of ${\cal A}$.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt mult\_columns}({\cal A},\{1,3\},x) & = &
        \left( \begin{array}{ccc} x & 2 & 3*x \\ 4*x & 5 & 6*x \\ 7*x &
8 & 9*x
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\vspace*{0.1in}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt mult\_rows}({\cal A},2,10) & = &
        \left( \begin{array}{ccc} 1 & 2 & 3 \\ 40 & 50 & 60 \\ 7 & 8 &
9 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt add\_to\_columns}, {\tt add\_to\_rows}.


\subsection{\tt mult\_rows}

\hspace*{0.175in} see: {\tt mult\_columns}.


\subsection{pivot}

%{\bf How to use it:}

\hspace*{0.175in} {\tt pivot(${\cal A}$,r,c);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix. \\
r,c        &:-& positive integers such that ${\cal A}$(r,c) neq 0.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt pivot} pivots ${\cal A}$ about its (r,c)'th entry.

To do this, multiples of the r'th row are added to every
     other row in the matrix.

This means that the c'th column
                will be 0 except for the (r,c)'th entry.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt pivot}({\cal A},2,3) & = &
        \left( \begin{array}{ccc} -1 & -0.5 & 0 \\ 4 & 5 & 6 \\ 1 & 0.5
& 0
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt rows\_pivot}.


\subsection{pseudo\_inverse}

%{\bf How to use it:}

\hspace*{0.175in} {\tt pseudo\_inverse(${\cal A}$);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt pseudo\_inverse}, also known as the Moore-Penrose inverse, computes
the pseudo inverse of ${\cal A}$.

Given the singular value decomposition of ${\cal A}$, i.e: ${\cal A} =
{\cal U}
\sum {\cal V}^T$, then the pseudo inverse ${\cal A}^{-1}$ is defined
by ${\cal A}^{-1} = {\cal V}^T \sum^{-1} {\cal U}$.

Thus ${\cal A}$ $ * $ {\tt pseudo\_inverse}$({\cal A}) = {\cal I}$.

\end{addtolength}

{\bf Examples:}

% \begin{flushleft}
% \hspace*{0.175in}
% \begin{math}
% {\cal R} = \left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 9 & 8 & 7 & 6
% \end{array} \right)
% \end{math}
% \end{flushleft}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt pseudo\_inverse}({\cal A}) & = &
        \left( \begin{array}{cc} -0.2 & 0.1 \\ -0.05 & 0.05 \\ 0.1 & 0
\\ 0.25 & -0.05
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt svd}.

\subsection{random\_matrix}

%{\bf How to use it:}

\hspace*{0.175in} {\tt random\_matrix(r,c,limit);}

\hspace*{0.1in}
\begin{tabular}{l l l}
r,c,$\,$limit &:-& positive integers. \\
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt random\_matrix} creates an r by c matrix with random
                entries in the range $-$limit $<$ entry $<$ limit.

\end{addtolength}

{\bf switches:}

\hspace*{0.1in}
\begin{tabular}{l l l}
{\tt imaginary} \hspace*{0.175in} &:-& \parbox[t]{0.685\linewidth}{if
on then matrix entries are x+i$*$y where $-$limit $<$ x,y $<$ limit.}
\end{tabular}

\vspace*{0.04in}
\hspace*{0.1in}
\begin{tabular}{l l l}
{\tt not\_negative} &:-& \parbox[t]{0.685\linewidth}{if on then 0 $<$
entry $<$ limit. In the imaginary case we have 0 $<$ x,y $<$ limit.}
\end{tabular}

\vspace*{0.04in}
\hspace*{0.1in}
\begin{tabular}{l l l}
{\tt only\_integer} &:-& \parbox[t]{0.685\linewidth}{if on then each
entry is an integer. In the imaginary case x and y are integers.}
\end{tabular}

\vspace*{0.04in}
\hspace*{0.1in}
\begin{tabular}{l l l}
{\tt symmetric} &:-& if on then the matrix is symmetric. \\
{\tt upper\_matrix} &:-& \parbox[t]{0.685\linewidth}{if on then the
matrix is upper triangular.} \\
{\tt lower\_matrix} &:-& if on then the matrix is lower triangular.
\end{tabular}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt random\_matrix}(3,3,10) & = &
        \left( \begin{array}{ccc} -4.729721 & 6.987047 & 7.521383 \\
- 5.224177 & 5.797709 & - 4.321952 \\
- 9.418455 & - 9.94318 & - 0.730980
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\vspace*{0.2in}
\hspace*{0.165in}
{\tt on only\_integer, not\_negative, upper\_matrix, imaginary;}
\begin{flushleft}
\hspace*{0.12in}
\begin{math}
\begin{array}{ccc}
{\tt random\_matrix}(4,4,10) & = &
\left( \begin{array}{cccc} 2*i+5 & 3*i+7 & 7*i+3 & 6 \\ 0 & 2*i+5 &
5*i+1 & 2*i+1 \\ 0 & 0 & 8 & i \\ 0 & 0 & 0& 5*i+9
\end{array} \right)
\end{array}
\end{math}
\end{flushleft}


\subsection{remove\_columns, remove\_rows}

%{\bf How to use it:}

\hspace*{0.175in} {\tt remove\_columns(${\cal A}$,column\_list);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$   &:-& a matrix. \\
column\_list &:-& either a positive integer or a list of
                  positive integers.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\hspace*{0.175in} {\tt remove\_columns} removes the columns specified in
                column\_list from ${\cal A}$.

\hspace*{0.175in} {\tt remove\_rows} performs the same task on the rows
                of ${\cal A}$.

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt remove\_columns}({\cal A},2) & = &
        \left( \begin{array}{cc} 1 & 3 \\ 4 & 6 \\ 7 & 9
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\vspace*{0.1in}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt remove\_rows}({\cal A},\{1,3\}) & = &
        \left( \begin{array}{ccc} 4 & 5 & 6
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}


{\bf Related functions:}

\hspace*{0.175in} {\tt minor}.


\subsection{remove\_rows}

\hspace*{0.175in} see: {\tt remove\_columns}.


\subsection{row\_dim}

\hspace{0.175in} see: {\tt column\_dim}.


\subsection{rows\_pivot}

%{\bf How to use it:}

\hspace*{0.175in} {\tt rows\_pivot(${\cal A}$,r,c,\{row\_list\});}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix. \\
r,c        &:-& positive integers such that ${\cal A}$(r,c) neq 0.\\
row\_list  &:-& positive integer or a list of positive integers.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt rows\_pivot} performs the same task as {\tt pivot} but applies
the pivot only to the rows specified in row\_list.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
{\cal N} = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 &
9 \\1 & 2 & 3 \\ 4 & 5 & 6
\end{array} \right)
\end{math}
\end{flushleft}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt rows\_pivot}({\cal N},2,3,\{4,5\}) & = & \left( \begin{array}
{c c c}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ -0.75 & 0 & 0.75 \\
-0.375 & 0 & 0.375
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt pivot}.


\subsection{simplex}

%{\bf How to use it:}

\hspace*{0.175in} {\tt simplex(max/min,objective function,\{linear
inequalities\});}

\hspace*{0.1in}
\begin{tabular}{l l l}
max/min             & :- & \parbox[t]{.63\linewidth}{either max or min
                           (signifying maximise and minimise).} \\
objective function  & :- & the function you are maximising or
                           minimising. \\
linear inequalities & :- & \parbox[t]{.63\linewidth}{the constraint
                           inequalities. Each one must be of the form
                           {\it sum of variables ($<=,=,>=$) number}.}
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt simplex} applies the revised simplex algorithm to find the
optimal(either maximum or minimum) value of the objective function
under the linear inequality constraints.

It returns \{optimal value,\{ values of variables at this optimal\}\}.

The algorithm implies that all the variables are non-negative.

\end{addtolength}

{\bf Examples:}

\begin{addtolength}{\leftskip}{0.22in}
%\begin{math}
{\tt simplex($max,x+y,\{x>=10,y>=20,x+y<=25\}$);}
%\end{math}

{\tt ***** Error in simplex: Problem has no feasible solution.}

\vspace*{0.2in}

\parbox[t]{0.96\linewidth}{\tt simplex($max,10x+5y+5.5z,\{5x+3z<=200,
x+0.1y+0.5z<=12$,\\
\hspace*{0.55in} $0.1x+0.2y+0.3z<=9, 30x+10y+50z<=1500\}$);}

\vspace*{0.1in}
{\tt $\{525.0,\{x=40.0,y=25.0,z=0\}$\}}

\end{addtolength}


\subsection{squarep}

%{\bf How to use it:}

\hspace*{0.175in} {\tt squarep(${\cal A}$);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt squarep} is a boolean function that returns t if
                the matrix is square and nil otherwise.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
{\cal L} = \left( \begin{array}{ccc} 1 & 3 & 5
\end{array} \right)
\end{math}
\end{flushleft}

\vspace*{0.1in}

\hspace*{0.175in} {\tt squarep}(${\cal A}$) = t

\hspace*{0.175in} {\tt squarep}(${\cal L}$) = nil

{\bf Related functions:}

\hspace*{0.175in} {\tt matrixp}, {\tt symmetricp}.


\subsection{stack\_rows}

\hspace*{0.175in} see: {\tt augment\_columns}.


\subsection{sub\_matrix}

%{\bf How to use it:}

\hspace*{0.175in} {\tt sub\_matrix(${\cal A}$,row\_list,column\_list);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$              &:-& a matrix. \\
row\_list, column\_list &:-& \parbox[t]{.605\linewidth}{either a
positive integer or a list of positive integers.}
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}


\begin{addtolength}{\leftskip}{0.22in}

{\tt sub\_matrix} produces the matrix consisting of the
              intersection of the rows specified in row\_list and the
columns specified in column\_list.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt sub\_matrix}({\cal A},\{1,3\},\{2,3\}) & = &
        \left( \begin{array}{cc} 2 & 3 \\ 8 & 9
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt augment\_columns}, {\tt stack\_rows}.


\subsection{svd (singular value decomposition)}

%{\bf How to use it:}

\hspace*{0.175in} {\tt svd(${\cal A}$);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix containing only numeric entries.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt svd} computes the singular value decomposition of ${\cal A}$.

It returns \{${\cal U},\sum,{\cal V}$\} where ${\cal A} = {\cal U}
\sum {\cal V}^T$ and $\sum = diag(\sigma_{1}, \ldots ,\sigma_{n}). \;
\sigma_{i}$ for $i= (1 \ldots n)$ are the singular values of ${\cal A}$.


n is the column dimension of ${\cal A}$.

The singular values of ${\cal A}$ are the non-negative square roots of
the eigenvalues of ${\cal A}^T {\cal A}$.

${\cal U}$ and ${\cal V}$ are such that ${\cal UU}^T = {\cal VV}^T =
{\cal V}^T {\cal V} = {\cal I}_n$.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
{\cal Q} = \left( \begin{array}{cc} 1 & 3 \\ -4 & 3
\end{array} \right)
\end{math}
\end{flushleft}

\begin{eqnarray}
\hspace*{0.1in}
{\tt svd({\cal Q})} & = &
\left\{
        \left( \begin{array}{cc} 0.289784 & 0.957092 \\ -0.957092 &
0.289784 \end{array} \right), \left( \begin{array}{cc} 5.149162 & 0 \\
0 & 2.913094 \end{array} \right), \right. \nonumber \\ & & \left. \: \;
\, \left( \begin{array}{cc} -0.687215 & 0.726453 \\ -0.726453 &
-0.687215 \end{array} \right)
\right\} \nonumber
\end{eqnarray}


\subsection{swap\_columns, swap\_rows}

%{\bf How to use it:}

\hspace*{0.175in} {\tt swap\_columns(${\cal A}$,c1,c2);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix. \\
c1,c1      &:-& positive integers.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\hspace*{0.175in}
{\tt swap\_columns} swaps column c1 of ${\cal A}$ with column c2.

\hspace*{0.175in} {\tt swap\_rows} performs the same task on 2 rows of
                ${\cal A}$.

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt swap\_columns}({\cal A},2,3) & = &
        \left( \begin{array}{ccc} 1 & 3 & 2 \\ 4 & 6 & 5 \\ 7 & 9 & 8
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt swap\_entries}.


\subsection{swap\_entries}

%{\bf How to use it:}

\hspace*{0.175in} {\tt swap\_entries(${\cal A}$,\{r1,c1\},\{r2,c2\});}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$  &:-& a matrix. \\
r1,c1,r2,c2 &:-& positive integers.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\hspace*{0.175in} {\tt swap\_entries} swaps ${\cal A}$(r1,c1) with
                ${\cal A}$(r2,c2).

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt swap\_entries}({\cal A},\{1,1\},\{3,3\}) & = &
        \left( \begin{array}{ccc} 9 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 1
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

{\bf Related functions:}

\hspace*{0.175in} {\tt swap\_columns}, {\tt swap\_rows}.


\subsection{swap\_rows}

\hspace*{0.175in} see: {\tt swap\_columns}.


\subsection{symmetricp}

%{\bf How to use it:}

\hspace*{0.175in} {\tt symmetricp(${\cal A}$);}

\hspace*{0.1in}
\begin{tabular}{l l l}
${\cal A}$ &:-& a matrix.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt symmetricp} is a boolean function that returns t if the
                matrix is symmetric and nil otherwise.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.175in}
\begin{math}
{\cal M} = \left( \begin{array}{cc} 1 & 2 \\ 2 & 1
\end{array} \right)
\end{math}
\end{flushleft}

\vspace*{0.1in}

\hspace*{0.175in} {\tt symmetricp}(${\cal A}$) = nil

\hspace*{0.175in} {\tt symmetricp}(${\cal M}$) = t

{\bf Related functions:}

\hspace*{0.175in} {\tt matrixp}, {\tt squarep}.


\subsection{toeplitz}

%{\bf How to use it:}

\hspace*{0.175in} {\tt toeplitz(\{\exprlist{}\});} \lazyfootnote{}

\hspace*{0.1in}
\begin{tabular}{l l l}
\exprlist{} &:-& algebraic expressions.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt toeplitz} creates the toeplitz matrix from the
                expression list.

This is a square symmetric matrix in
                which the first expression is placed on the diagonal
                and the i'th expression is placed on the (i-1)'th sub
                and super diagonals.

It has dimension n where n is the
                number of expressions.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt toeplitz}(\{w,x,y,z\}) & = &
        \left( \begin{array}{cccc} w & x & y & z \\ x & w & x & y \\
      y & x & w & x \\ z & y & x & w
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\subsection{Vandermonde}

%{\bf How to use it:}

\hspace*{0.175in} {\tt vandermonde}(\{\exprlist{}\}); \addtocounter
{footnote}{-1}\footnotemark
%\lazyfootnote{}

\hspace*{0.1in}
\begin{tabular}{l l l}
\exprlist{} &:-& algebraic expressions.
\end{tabular}

{\bf Synopsis:} %{\bf What it does:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt Vandermonde} creates the Vandermonde matrix from
                the expression list.

This is the square matrix in which
                the (i,$\,$j)'th entry is expr\_list(i) $^{(j-1)}$.

It has dimension n where n is the number of expressions.

\end{addtolength}

{\bf Examples:}

\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
{\tt vandermonde}(\{x,2*y,3*z\}) & = &
        \left( \begin{array}{ccc} 1 & x & x^2 \\ 1 & 2*y & 4*y^2 \\ 1
& 3*z & 9*z^2
 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\subsection{kronecker\_product}

\hspace*{0.175in} {\tt kronecker\_product}($Mat_1,Mat_2$)

\hspace*{0.1in}
\begin{tabular}{l l l}
$Mat_1,Mat_2$ &:-& Matrices
\end{tabular}

{\bf Synopsis:}

\begin{addtolength}{\leftskip}{0.22in}
{\tt kronecker\_product} creates a matrix containing the Kronecker product
(also called {\tt direct product} or {\tt tensor product}) of its arguments.

\end{addtolength}

{\bf Examples:}
\begin{verbatim}
a1 := mat((1,2),(3,4),(5,6))$
a2 := mat((1,1,1),(2,z,2),(3,3,3))$
kronecker_product(a1,a2);
\end{verbatim}
\begin{flushleft}
\hspace*{0.1in}
\begin{math}
\begin{array}{ccc}
\left( \begin{array}{cccccc} 1 & 1 & 1 & 2 & 2 & 2 \\
2 &  z & 2 & 4  &2*z &4 \\
3 &  3 & 3 & 6  & 6  &6 \\
3 &  3 & 3 & 4  & 4  &4 \\
6 & 3*z& 6 & 8  &4*z &8 \\
9 &  9 & 9 & 12 &12  &12\\
5 &  5 & 5 & 6  & 6  &6 \\
10 &5*z& 10& 12 &6*z &12 \\
15 &15 & 15& 18 &18  &18 \end{array} \right)
\end{array}
\end{math}
\end{flushleft}

\section{Fast Linear Algebra}

By turning the {\tt fast\_la} switch on, the speed of the following
functions will be increased:

\begin{tabular}{l l l l}
   add\_columns    & add\_rows      & augment\_columns & column\_dim  \\
   copy\_into      & make\_identity & matrix\_augment  & matrix\_stack\\
   minor           & mult\_column   &  mult\_row       & pivot        \\
   remove\_columns & remove\_rows   & rows\_pivot      & squarep      \\
   stack\_rows     & sub\_matrix    & swap\_columns    & swap\_entries\\
   swap\_rows      & symmetricp
\end{tabular}

The increase in speed will be insignificant unless you are making a
significant number(i.e: thousands) of calls. When using this switch,
error checking is minimised. This means that illegal input may give
strange error messages. Beware.

\newpage

\section{Acknowledgments}

Many of the ideas for this package came from the Maple[3] Linalg package
[4].

The algorithms for {\tt cholesky}, {\tt lu\_decom}, and {\tt svd} are
taken from the book Linear Algebra - J.H. Wilkinson \& C. Reinsch[5].

The {\tt gram\_schmidt} code comes from Karin Gatermann's Symmetry
package[6] for {\REDUCE}.


\begin{thebibliography}{}
\bibitem{matt} Matt Rebbeck: NORMFORM: A {\REDUCE} package for the
computation of various matrix normal forms. ZIB, Berlin. (1993)
\bibitem{Reduce} Anthony C. Hearn: {\REDUCE} User's Manual 3.6.
        RAND (1995)
\bibitem{Maple} Bruce W. Char\ldots [et al.]: Maple (Computer
        Program). Springer-Verlag (1991)
\bibitem{linalg} Linalg - a linear algebra package for Maple[3].
\bibitem{WiRe} J. H. Wilkinson \& C. Reinsch: Linear Algebra
(volume II). Springer-Verlag (1971)
\bibitem{gat} Karin Gatermann: Symmetry: A {\REDUCE} package for the
computation of linear representations of groups. ZIB, Berlin. (1992)
\end{thebibliography}

\end{document}





REDUCE Historical
REDUCE Sourceforge Project | Historical SVN Repository | GitHub Mirror | SourceHut Mirror | NotABug Mirror | Chisel Mirror | Chisel RSS ]