Matrices Count
How many 4 × 4 matrices with entries from { 0 , 1 } have odd determinant?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
"The number of bases....." - I cant understand this part .Can u explain a little bit ?
Log in to reply
That's the plural of basis .
A vector space over a field has, if finite dimensional, a basis , which is a set of vectors in the space such that every element of the space can be written uniquely as a linear combination of the elements of the basis. Have a hunt for a book on Linear Algebra, and the theory of finite-dimensional vector spaces.
Log in to reply
What is the general version of this formula ?
Log in to reply
@Kushal Bose – The most general finite field contains p n elements for some prime number p and some integer n . You are asking for the number of bases for an N dimensional space over the field with p n elements.
The first element of the basis must be a nonzero vector. There are p n N − 1 of these.
The second element of the basis cannot belong to the span of the first vector. There are p n vectors in that span, so there are p n N − p n choices.
The third element of the basis cannot belong to the span of the first two vectors. This span contains p 2 n elements, so there are p n N − p 2 n choices for the third basis element.
I will leave completing the argument to you, now.
Can u suggest a good book on Linear Algebra and Finite dimensional vector spaces ???If u have a pdf can u send me ????
Amazing! I just wrote code (in Matlab) to get the answer lol XD. I'm not sure how we were suppose to do this one, but I tried considering a set of combinations, building your way up from 2x2 matrices (which had 6), but it was more tedious than I was willing to deal with. A=zeros(4,4); counter=0; for i = 0:(2^16-1) for j=0:15 A(floor(j/4)+1,j-4*floor(j/4)+1)=mod(floor(i/2^j),2); end if mod(abs(det(A)),2)==1 counter = counter + 1; end end
Log in to reply
Thinking about the "number of linearly independent sets of 4 vectors, IE basis" is the right way to go.
In a similar manner, we can extend this argument to Z p , and calculate the number of matrices with determinant 1.
Log in to reply
Oh ok, thanks. That part of linear algebra is outside my current knowledge base I'm afraid.
Log in to reply
@James Wilson – We have an upcoming Linear Algebra course that would help you work through that.
The general case is not that much different from Mark's solution above.
- Can you calculate the number of matrices with a non-zero determinant? Hint: The vectors are linearly dependent.
- Can you create a bijection between matrices with non-zero determinant i , j . Hint: Multiply the first row by i j − 1 .
- Hence, conclude that there are x matrices of determinant 1.
Log in to reply
@Calvin Lin – Thanks, I've been working on this since you posted it. I can't seem to make my way past step 1. However, looking at steps 2 and 3, I'm a bit confused because I know in this case there are 10,020 matrices with determinant 1, 10,020 with determinant -1, 1200 with determinant -2, 1200 with determinant 2, 60 with determinant -3, and 60 with determinant 3.
Log in to reply
@James Wilson – To clarify, the generalized question is
How many n × n matrices are there in Z p with determinant 1?
Part 1 - Do you see why there are ( p n − 1 ) ( p n − p ) … ( p n − p n − 1 ) matrices with a non-zero determinant?
Log in to reply
@Calvin Lin – Ah ok. To be honest, I have no idea. XD
Log in to reply
@James Wilson – Think about picking the (column) vectors of a matrix, so that the vectors are linearly independent.
How many options are there for the first vector? We only have to avoid the 0 vector, so there are
p
n
−
1
options.
How many options are there for the second vector? We have to avoid the span of the first vector, so there are
p
n
−
p
options.
How many options are there for the third vector? We have to avoid the span of the first and second vector, so there are
p
n
−
p
2
options.
⋮
How many options are there for the last vector? We have to avoid the span of the
n
−
1
other vectors, so there are
p
n
−
p
n
−
1
options.
Hence, by the rule of product, the result follows.
Log in to reply
@Calvin Lin – Ok I get it now! Thanks for your help. :)
Log in to reply
@James Wilson – I still don't understand Steps 2 and 3 for the general case though. Perhaps I'll ponder on it for a while.
@James Wilson – Great. Figure out part 2 and 3 then.
This problem showcases the importance of thinking about linear algebra "correctly" and exploiting their multiple definitions / interpretations.
Log in to reply
@Calvin Lin – Okay. This will give me something to think about for a while.
A matrix has odd determinant if and only if its determinant is congruent to 1 modulo 2 , and hence is nonzero when regarded as an element of the 2 -element field Z 2 .
Thus we want to know the number of nonsingular 4 × 4 matrices over Z 2 , and this is equal to the number of bases for the 4 -dimensional vector space Z 2 4 . This number is ( 2 4 − 1 ) ( 2 4 − 2 ) ( 2 4 − 4 ) ( 2 4 − 8 ) = 2 0 1 6 0 since there are 2 4 − 1 choices for the first basis element, then 2 4 − 2 choices for the second basis element, and so on.