Neo would get lost in this Matrix

Let N N be the number of 2015 2015 by 2015 2015 matrices in which each entry is either a 0 0 or a 1 1 and each row and column contains an odd number of 1 1 's.

What is ( log 2 N ) ( m o d 1000 ) (\log_{2} N) \pmod{1000} ?

Image Credit: Wikimedia Matrix Numbers by Jamie Zawinski


The answer is 196.

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.

2 solutions

Configure the upper left 2014 2014 by 2014 2014 submatrix arbitrarily. Once we have a configuration, we can then fill the entries with indices ( i , 2015 ) (i,2015) and ( 2015 , j ) (2015,j) for i , j = 1 , 2 , . . . . , 2014 i,j = 1, 2, .... , 2014 accordingly in order to satisfy the odd number of 1 1 's requirement for these rows and columns.

Once this is done, we can then fill the entry with index ( 2015 , 2015 ) (2015,2015) accordingly so that the 2015 2015 th row satisfies the "odd" requirement. But what happens to the 2015 2015 th column as a result? Now since we have filled 2015 2015 rows each with an odd number of 1 1 's there are an odd number of 1 1 's in the completed matrix. We have already filled 2014 2014 columns with an odd number of 1 1 's, so these 2014 2014 columns have an even number of 1 1 's. Thus to end up with an odd number of 1 1 's in total, the 2015 2015 th column must also have an odd number of 1 1 's, thus satisfying the given "odd" condition.

This "extension" of the 2014 2014 by 2014 2014 submatrix is unique, so any solution 2015 2015 by 2015 2015 matrix must correspond uniquely to one of these submatrices. We thus have a one-to-one correspondence, and since there are 2 201 4 2 2^{2014^{2}} submatrices, we have that N = 2 201 4 2 . N = 2^{2014^{2}}. (This should be read as 2^(2014^2); the LaTeX gets quite small with an exponential "tower" like this.)

Therefore ( log 2 N ) ( m o d 1000 ) 201 4 2 ( m o d 1000 ) 1 4 2 ( m o d 1000 ) = 196 . (\log_{2} N) \pmod{1000} \equiv 2014^{2} \pmod{1000} \equiv 14^{2} \pmod{1000} = \boxed{196}.

Nice question sir , I learnt something new today :)

Uchiha Robert - 6 years, 3 months ago

That's very nice.

I had a complicated argument that involved A v = v A{\bf v} = {\bf v} and A T v = v A^T {\bf v} = {\bf v} , where v \bf v is the all-ones vector (all arithmetic done in Z / 2 Z {\mathbb Z}/2{\mathbb Z} , of course). Then conjugating A A by an orthogonal matrix P P with entries in Z / 2 Z {\mathbb Z}/2{\mathbb Z} such that P v P{\bf v} is the first standard basis vector shows that you can assume that v \bf v is the first standard basis vector e 1 {\bf e}_1 without changing the count. (That's the tricky part.)

The set of A A such that A e 1 = e 1 A{\bf e}_1 = {\bf e}_1 and A T e 1 = e 1 A^T{\bf e}_1 = {\bf 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 201 4 2 2^{2014^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.

Patrick Corn - 6 years, 2 months ago
Sanyam Sood
May 22, 2015

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

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...