Find the number of magical grids.

Here is another way of looking at the problem-

Step-1

Decide the row and the column whose row/column product you want to make $-1$.The rows can be selected in $n$ ways and for each row selected, the column can be selected in $n$ ways: $n^2$ ways in total.

Step-2

Now fill the remaining $(n-1)^2$ cells (none of which belong to your previously selected row or column) randomly. This can be done in $2^{(n-1)^2}$ ways.

Step-3

Now we fill the cells of our selected row and column. Note that after step 2, we end up with a $N \times N$ grid where all the Row and column products are known. Start filling the rows of the grid which only lack one cell. Since all the other elements of that row and the product are known, we can uniquely determine the sign of the number that is to be inserted. Proceed the same with columns and you have finished your cell. In step 3, we do not have any choice and by the end of step 2, in order to have a valid magical grid,we simply fill the grid as per the requirements. In other words, there is only one 1 way of completing Step 3.

By Fundamental Principle of Counting-

Total number of magical grids- $n^2\times 2^{(n-1)^2}$

HINT for now... if you need more, I can give the full solution as long as this is not homework, quiz, etc.

• Given any grid, if you change one cell (from $+1$ to $-1$ or vice versa) it will change the row-product of its row and the column-product of its column, and no other products.

• Given a Magical Grid, where the $i$th row-product and the $j$th column-product are $-1$, then changing the cell $(i,j)$ will result in a grid with all row- and column- products being $+1$. We will call this a Boring Grid. This operation defines a many-to-one mapping from Magical Grids to Boring Grids.

• Can you count the number of Boring Grids?

• Can you then count the number of Magical Grids? Make sure you handle any double (or multiple) counting (if any) when you "reverse" the mapping.

Lemme know if you need more help.

Let's start with all positive grids, i.e. grids that have all positive row-products and column-products, and determine their number. The simplest thing that comes to mind is filling $(N-1)\times(N-1)$ subgrid arbitrary and use the last row and column to fix any sign problem we meet $$ \begin{matrix} 1 & 1 & -1 & ?\\ -1 & 1 & -1 & ?\\ 1 & -1 & 1 & ?\\ ? & ? & ? & ?\\ \end{matrix} $$ Demanding each of the written $N-1$ rows and $N-1$ columns to have positive product we can find $$ \begin{matrix} 1 & 1 & -1 & -1\\ -1 & 1 & -1 & 1\\ 1 & -1 & 1 & -1\\ -1 & -1 & 1 & ?\\ \end{matrix} $$ Now the only concern is the last diagonal cell. The problem is, we do not know signs of the last row and last column products -- they are controlled by the matrix $(N-1)\times(N-1)$. If their products both have $+$ or $-$ sign we're ok -- the last empty cell is well-defined, otherwise we're in trouble.

Here comes the trick -- we will prove lemma: product in the last row and last column, that are formed as described above, always have the same sign. Proof: instead of question mark let's put $x$ to finish the matrix. $$ \begin{matrix} 1 & 1 & -1 & -1\\ -1 & 1 & -1 & 1\\ 1 & -1 & 1 & -1\\ -1 & -1 & 1 & x\\ \end{matrix} $$ Without loss of generality suppose that the last column product is $-x$, while last row product is $+x$. Now consider product of all numbers in the grid. On one hand it is equal to the product of all column-products (except the last one they all are $+1$ by construction) thus $-x$. On the other hand it is equal to the product of all row-products (except the last one they all are $+1$ by construction) thus $+x$. But $x$ should be either $+1$ or $-1$, thus it cannot be $x = -x$, thus contradiction. The latter means, we can always definitely fill the last element to make matrix all-rows-columns positive, QED.

Now return to the problem. First, we form arbitrary $(N-1) \times (N-1)$ submatrix (totally $2^{(N-1)^2}$ possibilities). Than we calculate last row and column to make it all-positive, that is always possible by lemma, thus $2^{(N-1)^2}$ all-positive grids possible. What to do next is well-described in the other answer, so I will not duplicate. As a final result you should get $N^2\,2^{(N-1)^2}$.