Determinant

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
uws8505
Posts: 58
Joined: Tue Sep 30, 2008 3:13 pm
Location: South Korea

Determinant

Let a1,a2,...,a100 be random integers between -10 and 10, inclusive.
What is the probability of getting zero as the determinant of
┌a1  a2  a3  a4  ... a10 ┐
│a11 a12 a13 a14 ... a20 │
│a21 a22 a23 a24 ... a30 │
│... ... ... ... ... ... │
└a91 a92 a93 a94 ... a100┘
p.s. is there any efficient algorithm that computes the determinant of a square matrix?
Math and Programming are complements

daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Determinant

Depends on what you call efficient. Since the naive algorithm is O(n!), I'd say O(n3) would count as efficient, wouldn't it?
Then there is an efficient algorithm to compute the determinant, use Gau&szlig; elimination to transform the matrix into upper (or lower) triangular form, keeping track of swappings and multiplication of rows/columns by a scalar, then multiply the entries on the diagonal.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

rmillika
Posts: 39
Joined: Thu Apr 05, 2007 4:37 pm

Re: Determinant

Numerical Recipes (available on-line) shows how to reduce this to nlog27, but comments that the bookkeeping involved probably makes it not worthwhile
Sorry, that was matrix multiply, not determinant
Last edited by rmillika on Thu Apr 09, 2009 10:37 pm, edited 2 times in total.

hisoka-san
Posts: 20
Joined: Sun Jan 25, 2009 6:14 pm

Re: Determinant

probably check for non-zero determinant can be faster than computing it. By the way,
the rank of the matrix made of random coefficients is one of the tests of Marsaglia
battery of the randomness tests.

hisoka-san
Posts: 20
Joined: Sun Jan 25, 2009 6:14 pm

Re: Determinant

Monte-Carlo simulation gives a 14.4% chance that Det is zero in your case.