% Hill2.tex

\section{Determinants}

\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 Hill starts 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}\index{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.

Hill defines even and odd permutations in terms of inversions. Another way of
defining them is to use the idea of a permutation matrix (see Section 1.5
and exercise 25 on page 87 of Hill). 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 {\bf even} if the matrix is a
product of an {\em even} number of elementary permutation matrices, and is
{\bf odd} if the matrix is a product of an {\em 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 2.6} 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{verbatim}
# Hill, Section 2.1, Example 8, p94
> with(linalg):
> A:= matrix([ [a11,a12],
>              [a21,a22] ]):
> det(A);
                               a11 a22 - a12 a21

# The formula for the determinant 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{verbatim}

\noindent As mentioned in Section 1.6, {\em the determinant is never used in
solving large sets of linear equations}.  (See the comments on page 95 of Hill).

\eject
\subsection{Evaluating Determinants}
The following facts about determinants simplify their evaluation.
\begin{verbatim}
# Hill, Section 2.2, Evaluating Determinants.
> with(linalg):
# Instead of checking some of the numerical examples in Hill, we illustrate
# the results of some of his 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 2.7 (p97). If a square matrix A has a row of all zeros then det(A)=0.
#
# Example
> A0:=matrix([ [a11,a12],
>              [0  ,  0] ]):
> det(A0);
                                       0

# THEOREM 2.8 (p98). Let A be an n by n (upper or lower) triangular matrix.
#   Then det(A) is the product of the diagonal entries of A.
#
# Example
> U:=matrix([ [a11,a12,a13],
>             [  0,a22,a23],
>             [  0,  0,a33] ]):
> det(U);
                                  a11 a22 a33

# In particular, determinants of elementary matrices are as in Hill Theorem 2.9
#
# THEOREM 2.10 (p99). If E is an elementary n by n matrix and
#   A is any n by n matrix,  then det(evalm(E&*A)) = det(E)*det(A).
#
# COROLLARY 2.11 (p100). Let A be an n by n matrix.
# (a) If B is obtained from A by adding a multiple of one row of A
#     to another row, then  det(B) = det(A).
# (b) If B is obtained from A by multiplying a row of A
#     by the number m, then  det(B) = m*det(A).
# (c) If B is obtained from A by interchanging two rows of A,
#     then  det(B) = -det(A).
#
# Examples
> B:=addrow( A,1,2,m):                        simplify( det(B)-det(A) );
                                       0

> B:=mulrow(A, 1, m):                         simplify( det(B)-m*det(A) );
                                       0

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

# Several applications of Corollary 2.11(b) yield
# THEOREM 2.27 (p108). If A is an n by n matrix, then det(k*A) = k^n*det(A).
#
> simplify( det(k*A) - k^2*det(A) );
                                       0
\end{verbatim}
As Hill observes, these provide an efficient way of evaluating the determinant
of a matrix $A$: reduce $A$ to Echelon form (as in Gaussian elimination),
using Corollary 2.11(c) to note changes in the sign of $\det(A)$. The final
step (by Theorem 2.8) consists in multiplying the diagonal elements of $A$.

This method of finding a determinant is illustrated in Hill, \S 2.2,
Example 5 (p101).

\setcounter{theorem}{11}
\begin{theorem} If one row of a square matrix A is a multiple of another,
  then det(A)=0.
\end{theorem}

\subsection{Properties of the Determinant}
Hill gives three useful properties. 

\begin{verbatim}
# Hill, Section 2.3, Properties of the Determinant
# We continue with the general 2 by 2 matrices of Hill, Section 2.2
#
# THEOREM 2.13 (p104). 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 (as mentioned on page 105 of Hill) the above theorem is never
# used to test a matrix for invertibility.
########################################################################
#
# THEOREM 2.20 (p105). If A and B are n by n matrices,
#   then  det(evalm(A&*B)) = det(A)*det(B).
#
> B:=matrix([ [b11,b12],
>             [b21,b22] ]):
> simplify( det(evalm(A&*B)) - det(A)*det(B) );
                                       0

# THEOREM 2.25 (p106). If A is an n by n matrix, det(transpose(A)) = det(A).
> simplify( det(transpose(A))-det(A) );
                                       0
\end{verbatim}
A useful way of viewing theorem 2.25 of Hill is the following {\bf 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}
In particular, this principle applied to Corollary 2.11 of Hill yields
a corresponding result for column operations (theorem 2.26 of Hill).

\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.
\medskip

\headq{Definitions 2.29 and 2.32.} Let $A_{ij}$ be the $(n-1)\times (n-1)$
submatrix of the matrix $A$ obtained by deleting the $i$-th row and $j$-th
column of $A$.  Then
  \begin{eqnarray*}
    &\mbox{(a)\quad the ($i,j$)'th {\bf cofactor} of $A$ is} &\qquad\qquad
                               C_{ij} = (-1)^{i+j} \det(A_{ij}) \\
    &\mbox{(b)\quad the {\bf adjoint} of $A$ is the matrix} &\qquad\qquad
                      adj(A) = (\ C_{ji}\ ) = (\ C_{ij}\ )^T
  \end{eqnarray*}

\setcounter{theorem}{29}
\begin{theorem} Let $A$ be an $n\times n$ matrix. Then
  $\det(A)$ can be computed by ``expanding by cofactors'' along any row:
    $$ \det(A) = a_{i1}C_{i1} + a_{i2}C_{i2} +\cdots + a_{in}C_{in} .$$
\end{theorem}

\begin{verbatim}
# The expansion of a 3 by 3 determinant along its third row, and its adjoint
> 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

> adjA:= adjoint(A);
           [  a22 a33 - a23 a32   - a12 a33 + a13 a32   a12 a23 - a13 a22  ]
           [                                                               ]
   adjA := [ - a21 a33 + a23 a31   a11 a33 - a13 a31   - a11 a23 + a13 a21 ]
           [                                                               ]
           [  a21 a32 - a22 a31   - a11 a32 + a12 a31   a11 a22 - a12 a21  ]

# This is the transpose of the matrix of cofactors.  For example
> adjA[1,3] - det(A31),                             adjA[2,3] + det(A32);
                                      0, 0

# THEOREM 2.33 (p116). If A is an n by n matrix, then  A adj(A) = det(A) Id.
# For example,
> equal( evalm( A&*adjA), det(A)*diag(1,1,1) );
                                      true
\end{verbatim}

Although this method of inverting matrices, and Cramer's rule for solving a
set of linear equations, are theoretically useful, neither is used for
floating point numerical methods for large matrices as Gaussian elimination
is more efficient.

\setcounter{theorem}{39}
\begin{theorem} Suppose $A$ is an $n\times n$ matrix and $n$ is large.
  Then solving the system $AX = B$ by Cramer's rule takes roughly $n+1$ times
  as much work as solving by Gaussian elimination.
\end{theorem}

\medbreak
\subsection{Applications}
Hill mentions several applications of the determinant which are used in other 
areas of Mathematics. We give some definitions before looking at the Maple code.

\smallskip
\subsubsection*{Wronskians}
If $f_1(x),f_2(x),\ldots f_n(x)$ are $n$ functions of the variable $x$, then
there is a function $\b f=[\rowi{f}{n}]$ from $\DoubleR$ to $\DoubleR^n$. Hill
defines the {\bf Wronskian} of \b f to be the determinant of 
the $n\times n$ matrix
  $$ \left( \left({d\over dx}\right)^{j-1}f_i(x)\right).$$
Wronskians are very useful in checking whether a set of $n$ solutions of a
differential equation of degree $n$ is linearly independent
(and so form a basis for all the solutions).  Release 2 of Maple V uses
the term {\tt Wronskian}\index{Wronskian} for the matrix itself.

\smallskip
\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 {\bf Jacobian} matrix 
and its determinant is called the Jacobian determinant.
Maple reserves the term {\tt jacobian}\index{jacobian} for the Jacobian matrix.

\smallskip
\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=[\rowi{x}{n}]$, each of which
can be written as a function $x_i(\b u)$ of the variables $\b u=[\rowi{u}{n}]$,
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$$
\def\rowi#1#2{#1_1,#1_2,\ldots #1_{#2}}

\headq{Area and Volume} may both be found using Maple's {\tt geom3d} package.
\begin{verbatim}
# 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
\end{verbatim}
\goodbreak
\begin{verbatim}
# A similar formula can be used to find the volume of a tetrahedron:
> c:= vector( [c1,c2,c3] ):
> with(geom3d):
> point3d(A,a1,a2,a3),      point3d(B,b1,b2,b3),      point3d(C,c1,c2,c3):
> point3d(Q,0,0,0):           #  Note that O  is a reserved word in Maple
> tetrahedron(QABC, [Q, A, B, C]):
\end{verbatim}
\goodbreak
\begin{verbatim}
> simplify( volume(QABC) + det(augment(ab,c))/6 );
                                       0

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

# and Maple V (from Release 2 on) has a  Wronskian  command:
> Wr:= Wronskian( vector([exp(x),exp(-x)]), x );
                                [ exp(x)   exp(- x)  ]
                          Wr := [                    ]
                                [ exp(x)  - exp(- x) ]

# If you only have a copy of Maple V or earlier,
# a wronskian command can easily be written:
> wronskian:= proc(f,x)    #  f  should be a vector of functions of  x
>     local Wr,Wi,i;
>     Wi:= f;        Wr:= f;
>     for i from 3 to nops(f) do
>         Wi:= map(diff,Wi,x);        Wr:= augment(Wr,Wi);
>     od:
>     evalm( transpose(Wr) );
> end:
> Wr:= wronskian( vector([exp(x),exp(-x)]), x );
                                [ exp(x)   exp(- x)  ]
                          Wr := [                    ]
                                [ exp(x)  - exp(- x) ]

# Hill (and many other authors) use `Wronskian' for the determinant of this:
> simplify( det(Wr) );
                                       -2

\end{verbatim}

\vfill
\eject
