The fantastic matrix

Question

Here's another question that I have been asked in an interview lately.

Let $M$ be an $n × n$ matrix whose values are $”+”$ and $”-”$. M is called fantastic if it is possible to make all it's values $”+”$ by a set of operations, when each only consisting of changing the sign of one column or the sign of one row.

I was asked to: Design a simple,efficient algorithm to decide whether a matrix $M$ is fantastic.

Answer 1

I think the following simple algorithm would work

A matrix is fantastic if and only if each row is either the same as the first row or the negative of the first row.

Equivalently

If we change "+" and "-" to $1$ and $-1$ then a matrix is fantastic if and only if it has rank $1$.

Proof

Consider the viewpoint where we have each "+" represented by $1$ and each "-" represented by $-1$. Each operation is now equivalent to multiplying a single row or a single column by $-1$. Each fantastic matrix can be obtained by applying a sequence of such operations to the matrix consisting entirely of $1$s.

Now, such an operation does not alter the rank of a matrix (if the changed row/column was a linear combination of the others then it still is) so any fantastic matrix necessarily has rank $1$. This proves the only if statement.

To prove the "if" statement, consider any matrix of rank $1$ with entries $\pm 1$. Identify all entries which are $-1$ in the top row, say they have indices $i_1, i_2, \ldots, i_m$.
Change all the entries in columns $i_1, i_2, \ldots, i_m$.
Then, the rows in the resulting matrix will either have all $1$s or all $-1$s. Select the rows which are all $-1$s and change these to get back to a matrix of all $1$s.

Answer 2

Each row and column can either be switched or un-switched. Assume $n\gt2$ (because otherwise the answer is trivial), and at least two rows/columns have been switched. Note that not all the R/C's have been switched, because again the answer is trivial. This results in a pattern such that if $(a,b)$ and $(c,d)$ are positive, then so are $(a,d)$ and $(c,b)$. so check that this is the case for all positive cells, and the matrix is fantastic! Note this also tells you which R/C's to switch to restore the pluses.