Find the number of magical grids.

Question

Question-

Consider an N ×N grid in which very cell has either +1 or −1. We call such a grid a Binary grid. The Row-Product of any row is defined to be the product of all elements in that single row. Similarly, the Column Product of a column is defined to be the product of all elements in that single column. An N ×N Binary grid is called a Magical Grid if exactly one of the N Row-Products is −1, and exactly one of the N Column-Products is −1. That is, the other N−1 Row-Products should all be +1, and the other N−1 Column-Products should all be +1. Find the number of Magical Grids of size N × N.(I am only interested in the case N=3,4,5).

My attempt- I really haven't figured out a way of attacking the problem but here are a few deductions that I have made:

1. The number of $-1$s in only one row will be odd. Same goes for columns.

2. I could potentially break down the problem into sub-cases, finding the number of magical grids for only one $-1$, then two $-1$s but that will take a very long time, and very inelegant.

Could anyone give any leads?

Answer 1

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}$

Answer 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.

Answer 3

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}$.