The fantastic matrix

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.

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.

• Yea, I was thinking on the lines of determinants, but this is essentially equivalent. – Don Thousand Mar 30 at 14:44

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.