does checking if a matrix can have at least one positive number at each row by negation of columns a NP-complete problem? Given a NxN matrix of numbers {-1, 0, 1} we want to check if it's possible to reach a state where each row contains at least one one only by changing the sign of columns (1 = -1, -1 = 1).
Is this a NP-complete problem?
I can easily show it's a NP problem by using a verifier that takes a number between 0 and 2^N where the i'th bit of the number represent whether or not we changed the sign of the i'th column.
But I don't know how to prove it's a NP-hard problem. I tried to use a reduction to 3-SAT but I didn't thought of any way to do it.
 A: It is indeed possible to reduce 3-SAT to this problem.
For each variable $x_i$, add two columns (name them $a_i$ and $b_i$) and two rows to the matrix, with one of this rows having two $1$ in this columns, the other having two $-1$, and all other elements of this row be $0$. We will need to invert exactly one of this columns (if we invert none, the second added row will have no ones, and if we invert both, the first will have no ones). Inverting $a_i$ will correspond to taking $x_i = 0$, and inverting $b_i$ will correspond to taking $x_i = 1$.
Now, add a row for each clause. If the clause includes $x_i$, place $-1$ in column $b_i$ in the corresponding row; if the clause includes $\neg x_i$, place $-1$ in column $a_i$. So each new row will have three $-1$.
Now, if we have some interpretation $x_i = y_i$ that satisfies all clauses, invert $a_i$ if $y_i = 0$ and $b_i$ if $y_i = 1$ - each row will have at least one $1$ with such inversion. The other way, each inversion with at least one $1$ in each row inverts exactly one of $a_i$ and $b_i$ - if it inverts $a_i$, take $x_i = 0$, otherwise take $x_i = 1$.
