All possible pictures look the same -- we just took the standard picture where the cell (a,b)
is black iff a&b, then we permuted the rows, and then we permuted the columns.
Given the input, we need to check whether we can permute it back.
This can be done in many ways.

One possibility: in a valid picture there have to be exactly
N rows such that the number of ones in that row is exactly 2^(n-1). These rows have to correspond
to indices that have only one bit set: 1, 2, 4, 8, etc. (and by symmetry it does not matter which
one is which). Knowing these, we can compute the exact value for each column. Now do the same with
columns and rows flipped, and you have the only possible pair of candidate permutations (or you
already know that the answer is "Impossible"). If you got this far, verify whether the permutations
you found actually produce the input, and you are done.

Another possibility is to reduce the matrix into a canonical form. Take the standard picture
where the cell (a,b) is black iff a&b. Sort its rows. Sort its columns. Repeat X times.
Now do the same with the picture given in the input. Finally, compare the two pictures
you got. (Exercise: How large should X be to be sure that all valid pictures have already
converged into the same form?)