$\def\p{\phantom-}$Call a $\lbrace 0,-1,1\rbrace$-matrix $M$ an even sign configuration if every row of $M$ contains an even number of 1's and every column of $M$ contains an even number of $-1$'s. The matrix
$$\begin{bmatrix} \p1 & -1 & 1 & 0 \\\\ -1 & \p1 & 0 & 1 \\\\ \p0 & -1 & 1 & 1 \\\\ -1 & \p0 & 0 & 0 \end{bmatrix}$$
is an example of an even sign configuration. The support of such a matrix $M$ is the matrix obtained from $M$ by taking absolute values.


Given a $\lbrace 0,1\rbrace$-matrix $A$ of square size $d\times d$, is it possible to decide in polynomial time (with respect to $d$) if $A$ is the support of an even sign configuration?


More or less equivalently, if a $\lbrace 0,1\rbrace$-matrix $A$ is the support of an even sign configuration, does there exist a polynomial time algorithm which finds an even sign configuration $M$ with support $A$? 


This question is essentially question [Complexity of a matching problem on the grid $\mathbb Z^2$](https://mathoverflow.net/questions/116592/complexity-of-a-matching-problem-on-the-grid-mathbb-z2) with the no-intersection condition removed.


Algebraic reformulation: An even sign configuration $M$ corresponds to two 
$\lbrace 0,1\rbrace$ matrices $A\_+,A\_-$ such that $M=A\_+ -A\_-$ such that 
$A\_+ (A\_-)^t$ has only zeros on the diagonal and the support of $M$ is given by $A\_+ +A\_-$.


Added after Domotorp's comment: It seems that finding a perfect matching in an arbitrary graph is NP-complete (Added afterwards: WRONG, see Tony Huynh's answer). (This would solve the problem: Consider the graph with vertices corresponding to all non-zero entries, put an edge between two vertices if they are either on a common row or column. Find a complete matching in this graph if it exists.
Put a $-1$ at every vertex matched to a vertex of the same column and a $+1$ otherwise.)
The graph associated as above is however special. The question makes thus still sense
and is essentially a question on the existence of an efficient algorithm finding a complete
matching in the class of graphs defined by supports of matrices (or equivalently by finite
subsets of $\mathbb Z^2$).



Even sign configurations with prescribed support
The answer to both of your questions is **yes**. 


As suggested by the edit, consider the graph $G(A)$ whose vertex set is the set of non-zero entries of $A$, and where two entries are adjacent if they are in the same row or column. Now, as mentioned in the latest edit, if $G(A)$ contains a perfect matching then $A$ is the support of an even sign configuration. On the other hand, if $A$ is the support of an even sign configuration, then it is easy to construct a perfect matching in $G(A)$. 


Thus $A$ is the support of an even sign configuration if and only if $G(A)$ has a perfect matching.


Now, by [Edmond's Blossom Algorithm](http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm), the problem of finding a perfect matching in an arbitrary graph (not just maximum degree 4) is in P. So both of your problems can be solved in polynomial-time. 


