Return to Question

$\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$ 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$).

$\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$ 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$).

$\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$ 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. (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$).

$\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$ 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$).

$\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$ with the no-intersection condition removed.

Added after Domotorp's comment: It seems that finding a perfect matching in an arbitrary graph is NP-complete. (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$).

$\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$ 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. (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$).