> < ^ Date: Thu, 23 Aug 2001 17:55:20 +0100 (BST)
> < ^ From: Derek Holt <dfh@maths.warwick.ac.uk >
> < ^ Subject: Re: question about determinant

Dear Gap-Forum,

Stefan Kohl wrote:

Thomas Breuer wrote:

Currently the GAP function `DeterminantMat' assumes that nonzero
elements in the ring spanned by the matrix entries can be inverted.

If this does not hold, as in your example, we know no other method
for computing a determinant than summing certain products over the
symmetric group or writing the determinant recursively in terms of
determinants of smaller matrices.

Is only no better method known, or is there in fact a theorem that states
that in 'general', there is no more efficient way to compute the determinant ?

Best wishes,

Stefan

There is a polynomial time fraction-free method of computing determinants
due to Bareiss that works in an arbitrary integral domain. It is described
in Sections 9.2, 9.3 of "Algorithms for Computer Algebra" by Geddes,
Czapor and Labahn. I don't have any direct knowledge or experience of it
myself though!

Derek Holt.


> < [top]