% FILE anton2.tex

% Anton Chapter 2. 
\section{Determinants}

Material in this chapter is treated in \cite{J} \S1.5.

\subsection{The Determinant Function}

If the matrix $A$ is known to Maple, the determinant of $A$ is obtained by the
function\quad {\tt det(A);}\index{det}.

Below we give some examples practising the use of the {\tt det} function.

There are several ways of defining a determinant, and 
\cite{AR} 
start with one
which depends on the idea of a permutation.
Although Maple will construct all the permutations of a given list, using the
{\tt permute} function in the {\tt combinat} package, and will perform certain
operations on permutations in the {\tt group} package, none of these bears
much relevance to our use of them here.

\cite{AR} defines even and odd permutations in terms of inversions. 
Another way of
defining them is to use the idea of a permutation matrix defined earlier
in these notes.
A permutation matrix can be thought of
either as a product of elementary permutation matrices, or as a matrix with
a single 1 in each row and each column. If the 1 in the $i$'th column
occurs in the $j_i$'th row, then the matrix corresponds to the permutation 
$(j_1, j_2,\ldots j_n)$. This permutation is {\em even} if the matrix is a
product of an even number of elementary permutation matrices, and is {\em odd}
if the matrix is a product of an odd number of elementary permutation matrices.
For example, a permutation corresponding to an elementary permutation matrix is
odd; and the matrix corresponding to $(2,3,1)$ is a product
  $$ \pmatrix{ 0&0&1\cr 1&0&0\cr 0&1&0\cr} = 
     \pmatrix{0&1&0\cr1&0&0\cr0&0&1\cr} \pmatrix{1&0&0\cr0&0&1\cr0&1&0\cr}$$
of two elementary permutation matrices, showing that $(2,3,1)$ is an even
permutation.

\headq{Definition.} If $A=(a_{ij})$ is a square matrix, then $\det A$ is
the sum of all the signed products
  $$ \pm a_{1j_1} a_{2j_2}\ldots a_{nj_n} $$
where the sign is $+$ or $-$ depending on whether the permutation
$(j_1,j_2,\ldots j_n)$ is even or odd.\quad In particular, if $P$ is an
elementary permutation matrix, then $\det P=-1$.

\noindent Other examples are given below.
\begin{maple}
# Section 2.1, Example 7 - AR6 p71; AR7 p83
> with(linalg,matrix,det):
> A:= matrix([ [a11,a12],
               [a21,a22] ]):
> det(A);
                               a11 a22 - a12 a21

# The formula for the det of a 3 by 3 matrix can also be displayed.
> A:= matrix([ [a11,a12,a13],
               [a21,a22,a23],
               [a31,a32,a33] ]):
> det(A);  # This is left to the reader to run.
\end{maple}

\noindent We stress to readers that {\em the determinant is never used in
solving large sets of linear equations}. 
The evaluation of determinants of large matrices should be avoided.

\eject
\subsection{Evaluating Determinants by Row Reduction}

The following facts about determinants simplify their evaluation.
\begin{maple}
# Anton, Section 2.2, Evaluating Determinants.
> with(linalg,det,matrix,mulrow,swaprow,addrow,
              transpose,multiply,inverse,add):
# Instead of merely checking some of the numerical examples in the text,
# we illustrate the results of some of theorems 
# using general 2 by 2 matrices.
#
# We follow our earlier style to deal with matrices with general entries:
> A:=matrix([ [a11,a12],
              [a21,a22] ]):
#
# THEOREM (AR 2.2.1). If A is any square matrix that contains 
# a row of zeros,   then det(A)=0.
#
# Example
> A0:=matrix([ [a11,a12],
               [0  ,  0] ]):
> det(A0);
                                       0

# THEOREM (AR 2.2.2). If A is an n by n triangular matrix, then
# det(A) is the product of the entries on the main diagonal of A.
#
# Example
> U:=matrix([ [a11,a12,a13],
>             [  0,a22,a23],
>             [  0,  0,a33] ]):
> det(U);
                                  a11 a22 a33

# THEOREM (AR 2.2.3). Let A be any n by n matrix.
# (a) If B is obtained from A by multiplying a row of A
#     by the number k, then  det(B) = k*det(A).
# (b) If B is obtained from A by interchanging two rows of A,
#     then  det(B) = -det(A).
# (c) If B is obtained from A by adding a multiple of one row of A
#     to another row, then  det(B) = det(A).
#
# Examples
> B:=mulrow(A, 1, k):                         simplify( det(B)-k*det(A) );
                                       0

> B:=swaprow( A,1,2 ):                        simplify( det(B)+det(A) ); 
                                       0

> B:=addrow( A,1,2,k):                        simplify( det(B)-det(A) );
                                       0
\end{maple}
As \cite{AR} observes, 
this provides an efficient way of evaluating the determinant
$\det(A)$ of a matrix $A$: reduce $A$ to Echelon form (as in Gaussian
elimination), using Theorem 2.2.3 to note any effect on $\det(A)$.  The final
step (by Theorem 2.2.2) consists in multiplying the diagonal elements of 
the echelon matrix.

\smallskip
\headq{EXERCISE.} Work through this method to find the determinant of 
the matrix given in 
[AR6], Section 2.2, Example 6 (p77);
[AR7], Section 2.2, Example 5 (p90).

We can easily ask Maple to check that the answer given in \cite{AR}
is correct.
\begin{maple}
A3p:=matrix([[0, 1,5],
             [3,-6,9],
             [2, 6,1]]);
det(A3p);
# Answer is 165
\end{maple}

The following is an immediate consequence of Theorem 2.2.3.

%\setcounter{theorem}{11}
%\begin{theorem} 
%\par\noindent{\bf THEOREM. }
\theoremNN{\it 
If one row of a square matrix $A$ is a multiple of another,
  then $\det(A)=0$.
}
%\end{theorem*}
\theoremNNEnd

\subsection{Properties of the Determinant Function}
Here are some useful properties. 

\begin{maple}
# AR, Section 2.3, Properties of the Determinant
# We continue with general 2 by 2 matrices
#
# THEOREM (AR6 2.3.1; AR7 2.2.1b). Let A be an n by n matrix.
# Then det(transpose(A))-det(A)=0.
#
> simplify(det(transpose(A))-det(A));
                                       0
\end{maple}

A useful way of viewing the preceding theorem is the following 
{\em principle of duality}:
\begin{quotation}
  For every theorem about determinants, another theorem may be obtained by
  interchanging the words ``row'' and ``column'' wherever they occur.
\end{quotation}

\begin{maple}
# THEOREM (AR6 2.3.3; AR7 2.3.4). Let A and B be n by n matrices.
# Then det(multiply(A,B))-(det(A))*(det(B))=0.
#
> B:=matrix([[b11,b12],
             [b21,b22]]);
> simplify(det(multiply(A,B))-(det(A))*(det(B)));
                                       0

#
# THEOREM (AR6 2.3.4; AR7 2.3.3.). A square matrix A is invertible
#   if and only if det(A) <> 0.
#
> B:= subs( a22=a12*a21/a11, op(A) ):                  inverse(B);
Error, (in inverse) singular matrix
#
########################################################################
# As mentioned earlier, the computation of det involves numerical dangers
# and so the above theorem is never used to test 
# a matrix of floats for invertibility.
########################################################################
\end{maple}

\medbreak
\subsection{Cofactor Expansion; Cramer's Rule}
The next formula allows a definition by induction on the
dimension of the matrix. The determinant of $2\times 2$
(and of $3\times 3$) matrices has been given in the Maple code above.
\smallskip

\headq{Definition.} Let $A_{ij}$ be the $(n-1)\times (n-1)$
matrix obtained by deleting the $i$-th row and $j$-th column of the matrix $A$.
Then the ($i,j$)'th {\em cofactor} of $A$ is 
  $$ C_{ij} = (-1)^{i+j} \det(A_{ij}) .$$

\smallskip

\setcounter{theorem}{0}
\begin{theorem} 
%\par\noindent{\bf THEOREM.}{\it
The determinant of an $n\times n$ matrix  $A$,
$\det(A)$, can be computed by ``expanding by cofactors'' along any row,
that is, multiplying the entries in any row by their cofactors
and adding the resulting products;
that is, for each $1\leq i\leq n$,
$$ \det(A) = a_{i1}C_{i1} + a_{i2}C_{i2} +\cdots + a_{in}C_{in} .$$
\end{theorem}

%\smallskip

\begin{maple}
# An example of the expansion of a 3 by 3 determinant along its third row
> with(linalg):
> A:=matrix([ [a11,a12,a13],
>             [a21,a22,a23],
>             [a31,a32,a33] ]):
> A31:= submatrix(A,[1,2],[2,3]):        A32:= submatrix(A,[1,2],[1,3]):
> A33:= submatrix(A,[1,2],[1,2]):
> simplify( a31*det(A31)-a32*det(A32)+a33*det(A33) - det(A) );
                                       0
\end{maple}

The method of inverting matrices using the {\em adjoint matrix}
(Theorem 2.4.2), and Cramer's rule (Theorem 2.4.3)
for solving a set of linear equations, are theoretically useful formulae.
However, neither is used for floating point numerical methods for large matrices
as row operations (Gaussian elimination) are more efficient.

\smallskip

%\setcounter{theorem}{39}
%\begin{theorem} 
%\par\noindent{\bf THEOREM.}
\theoremNN{\it
Suppose $A$ is an $n\times n$ matrix and $n$ is large.
  Then solving the system $AX = B$ by Cramer's rule,
even with the most efficient methods of determinant evaluation,
 takes roughly $n+1$ times
  as much work as solving by Gaussian elimination.
}
%\end{theorem}
\theoremNNEnd

\medbreak
\subsection*{Applications}

\subsubsection*{AR6 11.1. Curves and surfaces through specified points}

Read [AR] for the theory.
See also [J] \S1.6 p46 for interpolation through
a set of $(x_i,y_i)$ points by $y=p(x)$ where $p$ is a polynomial.

\begin{maple}
with(linalg,det):
# A general conic section through 5 points

prepare_row:= proc(xj,yj):
 [xj^2,xj*yj,yj^2,xj,yj,1]
end:

make_array:= proc(x1,y1,x2,y2,x3,y3,x4,y4,x5,y5):
array(1..6,1..6,
 [prepare_row(x,y),
 prepare_row(x1,y1),
 prepare_row(x2,y2),
 prepare_row(x3,y3),
 prepare_row(x4,y4),
 prepare_row(x5,y5)]):
 end:

# AR S11.1 Example 3 has an orbit of an asteroid example.
# The numbers are nicer in AR S11.1 Q3.
# The equation is lhs=0 where lhs is the following expression
lhEq:=det(make_array(0,0,0,-1,2,0,2,-5,4,-1));
                                              2                2
               lhEq := 160 y + 320 x y + 160 y  - 320 x + 160 x 
#
# by looking at lhs/160 one sees the quadratic terms are a perfect
square.
# This means that the equation lhs=0 represents a parabola.
expand(lhEq/160-(x+y)^2+(x+y)/2+3*(x-y)/2);
                                        0
\end{maple}

\medskip

\subsubsection*{Calculus applications}
There are several applications of the determinant which are used in other 
areas of Mathematics. We give some definitions before looking at the Maple code.

\subsubsection*{Wronskians [J] \S4.3}
Let $f_1(x),f_2(x),\ldots f_n(x)$ be $n$ functions of the variable $x$. These
yield a function $\b f=[\rowi{f}{n}]$ from $\DoubleR$ to $\DoubleR^n$ and the 
{\em Wronskian} of \b f is defined to be the determinant of 
the $n\times n$ matrix
  $$ \left( \left({d\over dx}\right)^{j-1}f_i(x)\right)  .$$
See [AR6], p179; [AR7] p238.
Wronskians are very useful in checking whether a set of $n$ solutions of a
homogeneous linear differential equation of degree $n$ is 
linearly independent (and so form a basis).
From Maple Vr2 the {\tt linalg} package has a 
{\tt Wronskian}\index{Wronskian}
function.

\subsubsection*{Jacobians}
The derivative of a function $\b f=[\rowi{f}{n}]$ of the variables
$\rowi{x}{n}$ is the $n\times n$ matrix
  $$ {d\b f\over d\b x} = \left({\partial f_i\over \partial x_j}\right) $$
of partial derivatives. It is sometimes called the Jacobian matrix 
and its determinant is called the Jacobian determinant.
Maple reserves the term 
{\tt jacobian}\index{jacobian}
for the Jacobian matrix.

\subsubsection*{Multiple integrals}
One important use of the Jacobian is in finding multiple integrals. If
$f(\b x)$ is a function of the variables \b x, each of which can be
written as a function $x_i(\b u)$ of the variables \b u, then
  $$ \int f(\b x)\;dx_1\ldots dx_2 dx_n =
 \int f(\b x(\b u)) \det \left( {d\b x\over d\b u}\right) du_1 du_2\ldots du_n$$

\goodbreak

\headq{Area and Volume} may both be found using Maple's {\tt geom3d} package.
\begin{maple}
# The simplest use of determinants is an easily-remembered formula for the
#    cross product of two vectors:
> with(linalg):
> a:= vector( [a1,a2,a3] ):                       b:= vector( [b1,b2,b3] ):
> basis3:= vector( [i,j,k] ):                     ab:= augment(a,b):
> aXb:= crossprod (a,b):                          dotprod(aXb,basis3);
           (a2 b3 - a3 b2) i + (a3 b1 - a1 b3) j + (a1 b2 - a2 b1) k

> simplify( " - det(augment(ab,basis3)) );
                                       0

# A similar formula can be used to find the volume of a tetrahedron:
> c:= vector( [c1,c2,c3] ):
> with(geom3d):
> A:='A': point3d(A,a1,a2,a3): B:='B': point3d(B,b1,b2,b3): 
> C:='C': point3d(C,c1,c2,c3): O:='O': point3d(O,0,0,0):                        
> tetrahedron(OABC, [O, A, B, C]):
> simplify( volume(OABC) + det(augment(ab,c))/6 );
                                       0

# Maple has a  jacobian  command which can be used to evaluate integrals
# when these require the use, for example, of polar co-ordinates:
> jacobian( [r*cos(theta),r*sin(theta)], [r,theta] );
                         [ cos(theta)  - r sin(theta) ]
                         [                            ]
                         [ sin(theta)   r cos(theta)  ]

\end{maple}

\vfill
\eject
\endinput
\vfill \rightline{AR2.tex}
\end{document}
\end

# Although Maple Vr1 does not have a wronskian command, 
one can easily be written:
\begin{maple}
> wronskian:= proc(f,x)    #  f  should be a vector of functions of  x
>     local W,Wi,i;
>     Wi:= f;        W:= f;
>     for i from 3 to nops(f) do
>         Wi:= map(diff,Wi,x);        W:= augment(W,Wi);
>     od:
>     det(W);
> end:
> wronskian( vector([exp(x),exp(-x)]), x );
                              - 2 exp(x) exp(- x)

> simplify(");
                                       -2
\end{maple}
