N be the number of 2 0 1 5 by 2 0 1 5 matrices in which each entry is either a 0 or a 1 and each row and column contains an odd number of 1 's.
LetWhat is ( lo g 2 N ) ( m o d 1 0 0 0 ) ?
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.
Nice question sir , I learnt something new today :)
That's very nice.
I had a complicated argument that involved A v = v and A T v = v , where v is the all-ones vector (all arithmetic done in Z / 2 Z , of course). Then conjugating A by an orthogonal matrix P with entries in Z / 2 Z such that P v is the first standard basis vector shows that you can assume that v is the first standard basis vector e 1 without changing the count. (That's the tricky part.)
The set of A such that A e 1 = e 1 and A T e 1 = e 1 is just the matrices with 1 in the top left corner and then 0's down the first row and first column. There are 2 2 0 1 4 2 of those.
I feel like your argument and my argument are isomorphic, but I don't want to take the time to prove it.
you may fill 2014 columns and rows in any way but last no is definite so as to make odd no of 1 in each row and column . so we get 2 power 2014 sqr whose mod(1000) is 196
Problem Loading...
Note Loading...
Set Loading...
Configure the upper left 2 0 1 4 by 2 0 1 4 submatrix arbitrarily. Once we have a configuration, we can then fill the entries with indices ( i , 2 0 1 5 ) and ( 2 0 1 5 , j ) for i , j = 1 , 2 , . . . . , 2 0 1 4 accordingly in order to satisfy the odd number of 1 's requirement for these rows and columns.
Once this is done, we can then fill the entry with index ( 2 0 1 5 , 2 0 1 5 ) accordingly so that the 2 0 1 5 th row satisfies the "odd" requirement. But what happens to the 2 0 1 5 th column as a result? Now since we have filled 2 0 1 5 rows each with an odd number of 1 's there are an odd number of 1 's in the completed matrix. We have already filled 2 0 1 4 columns with an odd number of 1 's, so these 2 0 1 4 columns have an even number of 1 's. Thus to end up with an odd number of 1 's in total, the 2 0 1 5 th column must also have an odd number of 1 's, thus satisfying the given "odd" condition.
This "extension" of the 2 0 1 4 by 2 0 1 4 submatrix is unique, so any solution 2 0 1 5 by 2 0 1 5 matrix must correspond uniquely to one of these submatrices. We thus have a one-to-one correspondence, and since there are 2 2 0 1 4 2 submatrices, we have that N = 2 2 0 1 4 2 . (This should be read as 2^(2014^2); the LaTeX gets quite small with an exponential "tower" like this.)
Therefore ( lo g 2 N ) ( m o d 1 0 0 0 ) ≡ 2 0 1 4 2 ( m o d 1 0 0 0 ) ≡ 1 4 2 ( m o d 1 0 0 0 ) = 1 9 6 .