3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.