From: jr@redmink.demon.co.uk (John R Ramsden)
Subject: Re: Lewis Carol and determinants
Date: Sun, 23 Jan 2000 18:14:31 GMT
Newsgroups: sci.math
Summary: [missing]

Brian Sanderson wrote:

> Can anyone give me a reference for Charles Dodson's method
> of calculating determinants by condensation? 

Here are a couple of old posts on this topic:

--------------------------------------------------------------------

From  rchapman@mpce.mq.edu.au Sat Apr 10 18:41:42 1999
Newsgroups: sci.math.research
Subject: Re: Symmetric Toeplitz Determinants
From: Robin Chapman <rchapman@mpce.mq.edu.au>
Date: Sun, 11 Apr 1999 11:41:42 +1000

Brian Stewart wrote:
>
> To define these let $t_0, t_1, \dots, t_n$ be a set of
> independent transcendents over some base field such as $\rational$.

The t_j could just as well be any elements of any commutative ring.

> Define
> $\mathbf{T}_{n+1}$ to be the $(n+1)\times (n+1)$ matrix whose
> $(i,j)$-th entry is $t_{|i-j|}$, and $T_{n+1}$ to be its
> determinant. For convenience let $T_0$ denote $1$.
> 
> The relationship conjectured by Vein and Dale is
>
> The determinant
> 
> |T_{n-1}       T_n|
> |T_n       T_{n-1}|
> 
> is minus the square of the determinant
> 
> t_1 t_0 t_1 t_2           t_{n-2}
> t_2 t_1 t_0 t_1           t_{n-1}
> ....
> .....
> t_n ....                       t_1

This follows *immediately* from Dodgson's condensation formula
applied to the largest determinant T_{n+1}.

Dodgson's rule states that given a square matrix A we have
|A||B| = |A_{00}||A_{11}| - |A_{01}||A_{10}|
where
A_{00} is obtained from A by deleting its first row and first column,
A_{01} is obtained from A by deleting its first row and last column,
A_{10} is obtained from A by deleting its last row and first column,
A_{11} is obtained from A by deleting its last row and last column,
B is obtained from A by deleting its first and last row and first and
last column.

For a recent proof see the article by Doron Zeilberger in the Electronic
Journal of Combinatorics:
http://www.combinatorics.org/Volume_4/Abstracts/v4i2r22ab.html .

I think Dodgson was quite a well-known Oxford mathematician :-)

---------------------------------------------------------------------

From  propp@math.mit.edu Fri Jul 30 08:00:03 1999
Newsgroups: sci.math.research
Subject: Dodgson condensation
From: propp@math.mit.edu (Jim Propp)
Date: 30 Jul 1999 10:00:03 -0500

I have two questions about matrices, which I'll explain, motivate, 
and discuss after giving preliminary formulations.

1) Does there exist k such that for all n>k, the determinant of an
   n-by-n matrix is determined by its connected minors of order n-k
   through n-1?

2) How many addition-subtractions and multiplication/divisions are
   needed in order to compute all the connected minors of a matrix?

A connected m-by-m minor of an n-by-n matrix is obtained by taking
the elements in rows i+1,i+2,...,i+m and columns j+1,j+2,...,j+m
for some i and j between 1 and n-m.  Thus an n-by-n matrix has
(n-m+1)^2 m-by-m minors.

Dodgson's method for computing the determinant of a matrix uses
the recursion

M = (M   M   - M   M  ) / M
      NW  SE    NE  SW     C

where

M   = the determinant of some m-by-m matrix,


M   = the determinant of the northwest (m-1)-by-(m-1) submatrix,
 NW

M   = the determinant of the southeast (m-1)-by-(m-1) submatrix,
 SE

M   = the determinant of the northeast (m-1)-by-(m-1) submatrix,
 NE

M   = the determinant of the southwest (m-1)-by-(m-1) submatrix, and
 SW

M   = the determinant of the central (m-2)-by-(m-2) submatrix (taken
 C    to be 1 if m=2).

This method is fairly efficient when it works, but it fails if it
encounters a connected minor that vanishes, since at the next round
of computations it leads to the indeterminate expression 0/0.

However, in at least the smallest cases, the occurrence of zeroes
actually permits one to calculate the determinant even more rapidly
than in the absence of zeroes.  For instance, consider a 3-by-3
matrix.  Dodgson's method calculates the four 2-by-2 minors and 
the 3-by-3 determinant itself using only 5 addition/subtractions, 
10 multiplications, and 1 division.  But when the central entry
of the 3-by-3 matrix vanishes, we can calculate all the minors
using only 3 addition/subtractions, 8 multiplications, and 0
divisions.

Is it in fact true that the situation in which all minors are
non-zero is the "worst case"?  Is there a simple (or even
complicated) generalization of Dodgson's method that handles
the general case in which zeroes occur?  (Books and articles
on Dodgson's method usually say "If zeroes occur, re-order
the rows and/or columns and re-start the algorithm", which
for present purposes I'm banning.)

That's Question #2.

My Question #1 concerns the form that such an extension of 
Dodgson's algorithm might take.  If (as I suspect) no such
k exists, then it would not be possible to make Dodgson's
algorithm work for general matrices by replacing Dodgson's
"3-stage recurrence" (expressing m-by-m minors in terms of
(m-1)-by-(m-1) minors and (m-2)-by-(m-2) minors) with a k-
stage recurrence for some larger value of k.

Jim Propp
Department of Mathematics
University of Wisconsin

-----------------------------------------------------------


Cheers

---------------------------------------------------------------------------
John R Ramsden    (jr@redmink.demon.co.uk)
---------------------------------------------------------------------------
The new is in the old concealed, the old is in the new revealed.
   St Augustine.
---------------------------------------------------------------------------