Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If you have a number of large matrices, and you wish to determine whether each matrix has determinant zero or not, what is the most efficient way to do this in MAGMA

(it appears that calculating the rank is slightly more efficient than calculating the determinant).

**EDIT: **In case it helps, the matrix entries are rational functions in two commuting variables, which come from the coefficients of a power series in a third, noncommuting variable: the aim is to get some sort of indication of when a power series represents a rational function, which requires checking the determinant of progressively larger matrices until it starts being zero. (Although the overall setting is noncommutative, everything in the matrices themselves is commutative so there's no need to worry about left/right determinants, quasi-determinants, etc.)

share|improve this question
1  
What is in these matrices? Integers, rational, floating point numbers? –  Federico Poloni Mar 27 '12 at 18:55
add comment

3 Answers

up vote 2 down vote accepted

I don't know about Magma specifically, but in general, computing the determinant modulo a bunch of primes is the way to go (bunch = enough small primes so that their product exceeds the Hadamard bound, but of course, once the determinant is nonzero modulo some prime, you can safely halt).

EDIT Just a remark: the above is particularly fast for checking that your matrices are NOT singular, since if the determinant is really zero, you will have to do a lot more checking to be sure. On the other hand, computing the rank will ALWAYS be much slower than this.

share|improve this answer
    
Thanks for a quick response. –  dward1996 Mar 27 '12 at 14:18
    
But dward1996 did not say that his matrices have integer entries, did he? –  Federico Poloni Mar 27 '12 at 18:55
1  
He did say "MAGMA", which people do not usually do floating point computations in... –  Igor Rivin Mar 27 '12 at 19:02
add comment

I can guess that both the rank and the determinant are computed through some kind of (pivoted) LU factorization.

If so, in order to compute the determinant, after computing the LU factorization, you have to take the product of the factors on the diagonal of U, so it is not surprising that it takes more time than computing the rank: there are indeed more operations to do.

share|improve this answer
add comment

There are different parameters for the Determinant command when working over the integers. You should take a look at the online documentation:

http://magma.maths.usyd.edu.au/magma/handbook/text/243

It's quite comprehensive.

share|improve this answer
    
I just looked, and I do not see the options as especially useful for the OP's problem, unless the Magma people had put in a special hack for zero-checking. –  Igor Rivin Mar 27 '12 at 19:21
    
There is also the IsSingular() command which could be interesting. But unfortunately the manual does not say anything about the implementation. –  Hans Giebenrath Mar 27 '12 at 19:35
    
Thanks for that. I will give the IsSingular command a try. –  dward1996 Mar 28 '12 at 7:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.