Let $M$ be an $n\times n$ matrix whose entries are $+$ and $-$. Call $M$ nice if it is possible to make it all $+$ by a set of operation, each consisting of changing the sign of one row or the sign of one column.
Design a simple and efficient algorithm for deciding whether the given M is nice.
For starts, I think that the the number of $+$ must be a multiple of $n$ (i.e: $ 0, n, 2n,...,n*n $). But i am not sure how to prove/continue, I would be happy for some help.
On
Here are some hints to get you started.
A particular element changes sign if and only if the number of times its row is flipped, plus the number of times its column is odd. The order of the flips doesn't matter. Also, we see that there is no point in flipping a line more than once; flipping it twice is the same as not flipping it. So, we can assume each line is flipped at most once.
If two elements in the same column of a nice matrix have the same sign, then in changing to a matrix of all plus signs, their rows must be flipped the same number of number of times.
On
Clearly, all (both) possible $1\times 1$ matrices are nice. For $2\times 2$ matices, we find that they are nice if and only if the number of entries that are $-$ is even. For larger matices, we see that if it is nice, then also every quadratic sub-matrix that can be obtained by removing rows and columns is (and must be) nice. If we want the check the niceness of a $n\times n$ matrix this way, we see that for $n>2$, we must only check the $(n-1)^2$ $2\times 2$ sub-matices in adjacent rows and columns. This might sound much, but the complexity is only $\mathcal{O}(n^2)$, so it's barely different than checking all entries of the matrix.
As @saulspatz already noted, there is no need to change a row or column more than once. To find a set of operations that turns a nice matrix into the "all $+$-matrix" (containing only $+$-entries), we can do the following: Find an initial $-$-entry and chose to "flip" its column as the initial element of our set of operations (we could also flip the row, which we will see later). Flipping this column, there might have been $+$-elements that are now $-$, so we must add the flippings of the corresponding rows to our set. After applying these operations, the initial column has turned to "all $+$". We won't change these entries again, because that would require an unneccessary operation to change it back. The row of the initial element (which we dont't flip) also might contain $-$-entries that need to be changed, so we must add the flippings of the corresponding columns to our set of operations. Now, after applying these operations, also the row of our initial element has become "all $+$". Any additional operation would affect either the row or the column of our initial element and thus would require an unneccessary operation to change it back, so our set of operations is complete and will turn the nice matrix into the "all $+$ matrix".
The order in that we apply the operations doesn't matter, each operation is inverse to itself and flipping all rows and all columns will change every entry of the matrix twice, so applying all possible flippings, the matrix will be returned to its original state. There are only $2n$ possible operations, and if we have a set of $k$ operations, the complementary set of $2n-k$ operations will have the same resulting matrix. This means, that we will need at most $n$ operations to make a nice $n\times n$ matrix the "all $+$-matrix" (and flipping the row of our initial element instead of ots column could be more efficient).
At last: How many of the $2^{n^2}$ possible $n\times n$ matices are nice? To count them, we can count the different resulting matrices when appling a possible set of flippings to the "all $+$-matrix". As we have seen, for each of the $2^{2n}$ possible sets of operations, the complementary set will have the same resulting matrix. Except for these duplicates, the results will all be different, so there are $2^{2n-1}$ nice $n\times n$ matrices.
Thanks for this nice question. :-)
Therefore, a simple algorithm is to check if each row is equal or opposite to the first row.
Proof: Suppose every row is either equal or opposite to the first row. Flip all rows which are opposite the first row, so now all rows are the same. Then, flip all negative columns.
Suppose $M$ is nice. Then there is a sequence of flips starting from the matrix $P$ whose entries are all $+$ and ending at $M$. Note $P$ has the property that every row is equal or opposite the first. Furthermore, flipping any row or column preserves this property. Therefore, $M$ has the property as well.