# S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
 It is currently Thu, 23 May 2013 15:32:40 UTC

 All times are UTC [ DST ]

 Page 1 of 1 [ 5 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: DeterminantsPosted: Thu, 26 Feb 2009 14:13:04 UTC
 S.O.S. Oldtimer

Joined: Thu, 30 Oct 2008 10:47:09 UTC
Posts: 182
Let A be a nxn matrix whose entries are from {0,1}. Find the probability that the determinant of A is not zero.

I manage to get the sample space as . So when n=3, there are 512 determinants to compute. I know most of them are zero but I haven't find a systematic way to count the number of matrix whose det are nonzero.

Any idea ?

Top

 Post subject: Re: DeterminantsPosted: Thu, 26 Feb 2009 15:03:47 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6007
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
Beta wrote:
Let A be a nxn matrix whose entries are from {0,1}. Find the probability that the determinant of A is not zero.

I manage to get the sample space as . So when n=3, there are 512 determinants to compute. I know most of them are zero but I haven't find a systematic way to count the number of matrix whose det are nonzero.

Any idea ?

Characteristic 2 is just the order of GL_n(F_2), which is easy.

Characteristic 0 is a hard exercise in inclusion-exclusion because you don't have the symmetry characteristic 2 gives.

Top

 Post subject: Posted: Thu, 26 Feb 2009 17:49:05 UTC
 S.O.S. Oldtimer

Joined: Thu, 30 Oct 2008 10:47:09 UTC
Posts: 182
Oops, I've no idea what's GL_n(F_2).
And characteristics too...

Top

 Post subject: Posted: Thu, 26 Feb 2009 19:53:31 UTC
 Member of the 'S.O.S. Math' Hall of Fame

Joined: Mon, 23 Feb 2009 23:20:33 UTC
Posts: 1049
The entries in a matrix have to come from somewhere.

If they all come from {0, 1}, and we adopt the convention that 1+1 = 0 (i.e. adopt mod 2 arithmetic), we can say they come from a "finite field" of order 2. The order is the number of elements.

There are rules about finite fields which lead to the fact that the order is always a power of a prime number. The prime number is the "characteristic".

If the field has an infinite number of elements, we say the characteristic is 0.

is a general linear group on a finite field of 2 elements, so it can be considered as the set of all 2x2 matrices with entries from {0,1} and non-zero determinants.

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

Now, to count the number of matrices with non-zero determinant: no row can be a multiple of any other.

The second row can't be a multiple of the first. So it can't be 0 times the first row, or 1 times the first row.

The third row can't be a combination of the first or the second. So it can't be all zeroes, or 1 times the first row, or 1 times the second row, or the first row plus the second row.

Et cetera.

So there are (2^n)-1 possibilities for the first row, (2^n)-2 possibilities for the second row, (2^n)-4 possibilities for the third row, (2^n)-8 possibilities for the fourth row... et cetera.

For the last row there are possibilities.

Multiply these numbers together and you should get the number of matrices with non-zero determinant. Divide by the number of possible matrices. And that's it.

Last edited by aswoods on Sat, 28 Feb 2009 16:08:40 UTC, edited 2 times in total.

Top

 Post subject: Posted: Fri, 27 Feb 2009 02:42:59 UTC
 S.O.S. Oldtimer

Joined: Thu, 30 Oct 2008 10:47:09 UTC
Posts: 182
Thanks for the explanations.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 5 posts ]

 All times are UTC [ DST ]

#### Who is online

Users browsing this forum: No registered users

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ High School and College Mathematics    Algebra    Geometry and Trigonometry    Calculus    Matrix Algebra    Differential Equations    Probability and Statistics    Proposed Problems Applications    Physics, Chemistry, Engineering, etc.    Computer Science    Math for Business and Economics Advanced Mathematics    Foundations    Algebra and Number Theory    Analysis and Topology    Applied Mathematics    Other Topics in Advanced Mathematics Other Topics    Administrator Announcements    Comments and Suggestions for S.O.S. Math    Posting Math Formulas with LaTeX    Miscellaneous
Privacy Statement | Search the "old" CyberBoard

users online during the last hour