Combinatorial Invariant Problem Solving Question Consider the following problem. Take an $nxn$ table $A$ with entries $\pm 1$. A permitted move is multiplying any row or column by -1. How many $nxn$ tables exist that can be transformed to a table containing only $1$s?
I've done questions like this where I'm given an initial table and prove that the operation can't be done. Those proofs often rely on invariants. For instance, the product of any row or column is invariant after applying one of the permitted moves. Also, the product of any 2x2 squares within the table remains invariant. Using those two facts I've been able to prove some tables can never be transformed to only contain $1$s. But not sure I can use invariants for this more general question.
Intuition tells me that the only permitted $nxn$ tables of this form are the initial table containing all 1s or permutations of tables containing an entire row or column of $-1$s which can be later transformed into a table of only $1$s. I'm not sure how to prove this, I'm not sure if I can use invariants since this is for a general $n$.
Would anyone have any suggestions as to how to move forward with this question and how can I count the number of $nxn$ matrices in question?
 A: Answer: The number of matrices that can reach the all-ones matrix is $2^{2n-1}$.

You mentioned that the product of every $2\times2$ square is an invariant. There are $(n-1)^2$ such $2\times 2$ squares. It turns out that the collection of such products is a complete set of invariants, meaning that a matrix is reachable from the all-ones matrix if and only if the product of each $2\times 2$ sub-square is $+1$.
How do we prove this? First, notice that if a $2\times 2$ sub-square has a product of $1$, then the top row is either equal to or opposite the bottom row. This can be checked case by case, since there are only $8$ ways to choose a $2\times2$ matrix whose product is $+1$.
Now, let us look at a matrix with $2$ rows and $n$ entries per row. Suppose that each $2\times 2$ square in this grid has a product of $+1$. This means that locally, each little $1\times 2$ pair of squares in the top row is equal or opposite the $1\times 2$ pair which is below it. Since the $2\times 2$ squares overlap each other, the choice of "equal" or "opposite" must be the same for every such little pair. We conclude that the entire top row is equal to or opposite the bottom row.
Finally, consider the $n\times n$ grid. From the previous paragraph, we know that each pair of rows is either equal or opposite to its neighboring rows. This means that calling the first row $r$, every row is equal to $r$ or opposite to $r$. Then, we can change the grid to all-ones as follows:

*

*Take all rows which are opposite $r$, and multiply by them by $-1$. Now, all rows are equal to $r$.


*Since all rows are equal, each column is either all ones or all $-1$'s. Finish up by flipping all negative columns.

Now that we have a complete set of invariants, how do we count all of the matrices which can reach the all ones matrix?

*

*First choose the entries in the top row. There are $2$ choices for each of these $n$ entries. There are therefore $2^n$ ways to do this.


*Next, choose the remaining entries in the left-most column. Again, these entries can be chosen freely, since we have not made any $2\times 2$ squares. There are $2^{n-1}$ ways to fill these $n-1$ entries.


*Now that we have filled in the top row and left-most column, the rest of the matrix is forced. Considering the undetermined entries in reading order (left to right, then top to bottom), we see that each one is forced since it is the lower right corner of a $2\times 2$ square where the remaining entries are filled. Here is a small example. On the left, we have the initial assignment for the top row and left column. On the right is the unique way to fill the matrix so every $2\times 2$ sub-square has a positive product, in the order they are filled.
$$
\begin{bmatrix}+&-&-\\-&&\\+&&\end{bmatrix}
\qquad
\begin{bmatrix}+&-&-\\-&+_1&+_2\\+&-_3&-_4\end{bmatrix}
$$
Therefore, the number of matrices is $2^n\times 2^{n-1}=2^{2n-1}$.
