Division free determinants
In computing the determinant of a matrix over a commutative ring in general, one can count on only addition, taking additive inverses and multiplication. The current situation in GAP for such matrices requires the elements of the ring to have multiplicative inverses. While the resulting determinant is fraction free, it still requires division for ring elements.
Together with two of my honor students, we have implemented in GAP a version of Mahajan and Vinay 's algorithm to compute the determinant of a matrix over a commutative ring without division. This algorithm can be found in the paper by M. Mahajan and V. Vinay, Determinant: Combinatorics, Algorithms, and Complexity, Chicago Journal of Theoretical Computer Science, Volume 1997, Article 5.
The Mahajan and Vinay algorithm has a runtime of O(n^4) for an n x n matrix. However, the fraction-free method in GAP has run time O(n^3) so unless division is impossible with the ring element of the matrix or if matrix division is very expensive (like with polynomial rings) the fraction-free method will be significantly faster.
Our implementation is in the file divfreedet.g.txt.
To install our code at the gap prompt type:
gap> Read("divfreedet.g");
which will declare the operation DeterminantMatDivFree and install a method for it.
We have developed a test file determinant.tst.txt which randomly generates four Vandermonde matrices each over a different commutative ring: the integers, the Gaussian integers, a group ring, and a polynomial ring. We first compute analytically the determinant of the matrix, then compute the determinant with the installed method and compare the results.
Comments are welcome.
GAP Semigroup Development Effort
Here is my summary report of my visit to St. Andrews University last summer. Any comments, clarifications, or corrections are welcome. I will try to incorporate them into the document.
Computing the congruence lattice of finite universal algebras
I have written a GAP package to compute the congruence lattice of a given finite algebra. This package is currently under revision. Write me if you need a copy.
Computing the nonabelian tensor square of finitely presented groups
In my paper with M. Bacon and L.-C. Kappe, On the nonabelian tensor square of 2-Engel groups, Archiv der Mathematik 69 (1997) 353-364, we compute the nonabelian tensor square of the free 2-Engel group of rank 3. We use the notion of a crossed pairing to help us to make this computation. I wrote a GAP program to do most of these computations. I plan to extend this GAP program to compute the nonabelian tensor square of free 2-Engel groups with higher rank and to extend the analysis to free nilpotent groups of class 3.
Ron Brown at University of Wales, Bangor has put together a series of web pages on higher dimensional group theory which includes an introduction and bibliography on to the nonabelian tensor product.
This work is being funded in part by ARSAF Grant A6D-1001 and an ADVANTAGE Undergraduate Research Grant both from the University of Evansville.
Please send comments to rfmorse@evansville.edu