<p>No such matrix exists.</p>

<p>The <a href="http://en.wikipedia.org/wiki/Dodgson_condensation#The_Desnanot-Jacobi_identity_and_proof_of_correctness_of_the_condensation_algorithm">Desnanot-Jacobi identity</a> says that for $i \neq j$, 
$$
\det M_{ij}^{ij} \det M = \det M_i^i \det M_j^j -\det M_i^j \det M_j^i
$$
so using this, we get
$$
\det M_{12}^{12} \det M = \det M_{1}^{1} \det M_{2}^{2} - \det M_{1}^{2} \det M_{2}^{1}
$$
But your requirements force the left-hand-side to be 0 (mod 2) and the right-hand-side to be 1 (mod 2), showing they are incompatible. </p>

CC BY-SA 3.0
2011-11-10T17:53:12.687Z
Nice!  However, now I am confused because the asker said that the second bullet in the question alone can be satisfied, which indeed contradicts the identity which you quoted.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-10T19:45:52.033Z
@Tsuyoshi: how does the second bullet contradict the identity? The identity matrix $I$ satisfies the second bullet, and it's easy to check that $I$ satisfies the Desnanot-Jacobi identity. (Unless you're taking $i = j$, which violates a condition in the identity that I just added to my answer.)
Peter Shor 
CC BY-SA 3.0
2011-11-10T19:50:15.613Z
Sorry, my previous comment was bogus, and it seems that I am more confused than I thought.  Why does the requirement in the question force the left-hand side of the second equation in your answer to be 0 mod 2?
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-10T19:52:39.747Z
@Tsuyoshi: I totally goofed up the notation. Let me rewrite my answer.
Peter Shor 
CC BY-SA 3.0
2011-11-10T19:53:15.857Z
Now I see what you meant.  You did not have to remove the first row and the first column.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-10T19:58:19.397Z
Hi Peter,

thanks for response, but according to the requirements $\det(M)^{1,2,3}_{1,2,3}$ 
as well as $\det(M)^1_1$ must be odd, which makes the left-hand-side odd.
The same holds for $\det(M)^{1,2}_{1,2}$ and $\det(M)^{1,3}_{1,3}$, both must be odd.
Only $\det(M)^{1,3}_{1,2}\det(M)^{1,2}_{1,3}$ are even, which makes the right-hand-side also even.
Etsch
CC BY-SA 3.0
2011-11-10T20:01:16.070Z
@Etsch: I was thinking $M$ when I wrote $M^{1,2,3}_{1,2,3}$.  I think it's correct now.
Peter Shor 
CC BY-SA 3.0
2011-11-10T20:06:59.463Z
Perfect, now it makes sense, $\det(M)$ indeed must be odd. Thanks very much for your help.
Etsch
CC BY-SA 3.0
2011-11-10T17:08:20.280Z
2011-11-10T19:54:45.983Z
2011-11-10T19:54:45.983Z
Peter Shor 
<p>During my work i came up with the following problem:</p>

<p>I am trying to find an $n \times n$ $(0,1)$-matrix $M$, for any $n &gt; 3$, with the following properties:</p>

<ul>
<li>The determinant of $M$ is even.</li>
<li>For any non-empty subsets $I,J\subseteq\{1,2,3\}$ with $|I| = |J|$, the submatrix $M^I_J$ has odd determinant if and only if $I=J$.  </li>
</ul>

<p>Here $M^I_J$ denotes the submatrix of $M$ created by removing the rows with indices in $I$ and the columns with indices in $J$.</p>

<p>So far, I tried to find such a matrix via random sampling but I am only able to find a matrix that has all properties <strong>except the first one</strong>, i.e., the matrix always has an odd determinant. I tried various dimensions and different input/output sets without any success. So this makes me think: </p>

<p>Is that there is a dependency among the requirements, which prevents them from being simultaneously true?</p>

<p>or</p>

<p>Is it possible that such a matrix exists and can someone give me an example?</p>

<p>Thanks,
Etsch</p>

CC BY-SA 3.0
2011-11-09T10:39:37.953Z
do you mean random subsets or any subsets ?
Suresh Venkat
CC BY-SA 3.0
2011-11-09T16:51:46.820Z
It seems that $\det(M^{i_1}_{o_1}) \equiv 1 \pmod{2}$ and $\det(M^{i_1}_{o_2}) \equiv 0 \pmod{2}$ conflict with each other, because there's nothing to stop $o_1$ in one random subset being $o_2$ in another random subset. Or do you just want this to be true for a single pair of subsets $\{o_1,o_2,o_3\}$, $\{i_1,i_2,i_3\}$?
Peter Shor 
CC BY-SA 3.0
2011-11-09T18:19:38.063Z
Yes, the two subsets $\mathcal{I} = \{i_1,i_2,i_3\}$ and $\mathcal{O} = \{o_1,o_2,o_3\}$ are fixed. E.g. for $n=7$ one can set $i_1 = 1$, $i_2 = 2$, $i_3 = 5$ and $o_1 = 2$, $o_2 = 3$, $o_3 = 4$ and then the question is: Is there a (7x7) matrix $M$ such that $\det(M) \equiv 0\pmod{2}$, $\det(M^{1,2,5}_{2,3,4}) \equiv 1 \pmod{2}$, $\det(M^{1,2}_{2,3})  \equiv 1\pmod{2}$ and so on, according to the defined 20 properties.
Etsch
CC BY-SA 3.0
2011-11-10T00:54:38.663Z
Couldn't you just fix $i_1 = 1$, $i_2 = 2$, $i_3 = 3$, $o_1 = 1$, $o_2 = 2$, $o_3 = 3$ to simplify the question and to make it easier to read?
Jukka Suomela
CC BY-SA 3.0
2011-11-10T06:15:53.597Z
Sure, $i_1 = 1, i_2 = 2, i_3 = 3, o_1 = 1, o_2 = 2, o_3 = 3$ is a valid choice.
Etsch
CC BY-SA 3.0
2011-11-10T14:24:37.050Z
Edited for clarity.
Jeffε
CC BY-SA 3.0
2011-11-10T15:18:33.647Z
PS. I added the graph-theory tag, as we are looking for a bipartite graph with certain properties (the number of perfect matchings is odd/even in certain subgraphs).
Jukka Suomela
<graph-theory><co.combinatorics><linear-algebra><matrices><boolean-matrix>
Can such a matrix exist?
Etsch
# Can such a matrix exist?

(Asked by: username_0 on 2011-11-09)

During my work i came up with the following problem:

I am trying to find an $n \times n$ $(0,1)$-matrix $M$, for any $n > 3$, with the following properties:

* The determinant of $M$ is even.
* For any non-empty subsets $I,J\subseteq\{1,2,3\}$ with $|I| = |J|$, the submatrix $M^I\_J$ has odd determinant if and only if $I=J$.

Here $M^I\_J$ denotes the submatrix of $M$ created by removing the rows with indices in $I$ and the columns with indices in $J$.

So far, I tried to find such a matrix via random sampling but I am only able to find a matrix that has all properties **except the first one**, i.e., the matrix always has an odd determinant. I tried various dimensions and different input/output sets without any success. So this makes me think:

Is that there is a dependency among the requirements, which prevents them from being simultaneously true?

or

Is it possible that such a matrix exists and can someone give me an example?

Thanks,
Etsch

**Tags:** graph-theory, co.combinatorics, linear-algebra, matrices, boolean-matrix
> **Comments:**
> **username_1**: do you mean random subsets or any subsets ?  
> **username_2**: It seems that $\det(M^{i_1}_{o_1}) \equiv 1 \pmod{2}$ and $\det(M^{i_1}_{o_2}) \equiv 0 \pmod{2}$ conflict with each other, because there's nothing to stop $o_1$ in one random subset being $o_2$ in another random subset. Or do you just want this to be true for a single pair of subsets $\{o_1,o_2,o_3\}$, $\{i_1,i_2,i_3\}$?  
> **username_0**: Yes, the two subsets $\mathcal{I} = \{i_1,i_2,i_3\}$ and $\mathcal{O} = \{o_1,o_2,o_3\}$ are fixed. E.g. for $n=7$ one can set $i_1 = 1$, $i_2 = 2$, $i_3 = 5$ and $o_1 = 2$, $o_2 = 3$, $o_3 = 4$ and then the question is: Is there a (7x7) matrix $M$ such that $\det(M) \equiv 0\pmod{2}$, $\det(M^{1,2,5}_{2,3,4}) \equiv 1 \pmod{2}$, $\det(M^{1,2}_{2,3})  \equiv 1\pmod{2}$ and so on, according to the defined 20 properties.  
> **username_3**: Couldn't you just fix $i_1 = 1$, $i_2 = 2$, $i_3 = 3$, $o_1 = 1$, $o_2 = 2$, $o_3 = 3$ to simplify the question and to make it easier to read?  
> **username_0**: Sure, $i_1 = 1, i_2 = 2, i_3 = 3, o_1 = 1, o_2 = 2, o_3 = 3$ is a valid choice.  
> **username_4**: Edited for clarity.  
> **username_3**: PS. I added the graph-theory tag, as we are looking for a bipartite graph with certain properties (the number of perfect matchings is odd/even in certain subgraphs).  

---

## 1 answers

### Answer by username_2 on 2011-11-10. Score: 22 | Accepted answer

No such matrix exists.

The [Desnanot-Jacobi identity](http://en.wikipedia.org/wiki/Dodgson_condensation#The_Desnanot-Jacobi_identity_and_proof_of_correctness_of_the_condensation_algorithm) says that for $i \neq j$,
$$
\det M\_{ij}^{ij} \det M = \det M\_i^i \det M\_j^j -\det M\_i^j \det M\_j^i
$$
so using this, we get
$$
\det M\_{12}^{12} \det M = \det M\_{1}^{1} \det M\_{2}^{2} - \det M\_{1}^{2} \det M\_{2}^{1}
$$
But your requirements force the left-hand-side to be 0 (mod 2) and the right-hand-side to be 1 (mod 2), showing they are incompatible.

> **Comments:**
> **username_5**: Nice!  However, now I am confused because the asker said that the second bullet in the question alone can be satisfied, which indeed contradicts the identity which you quoted.  
> **username_2**: @Tsuyoshi: how does the second bullet contradict the identity? The identity matrix $I$ satisfies the second bullet, and it's easy to check that $I$ satisfies the Desnanot-Jacobi identity. (Unless you're taking $i = j$, which violates a condition in the identity that I just added to my answer.)  
> **username_5**: Sorry, my previous comment was bogus, and it seems that I am more confused than I thought.  Why does the requirement in the question force the left-hand side of the second equation in your answer to be 0 mod 2?  
> **username_2**: @Tsuyoshi: I totally goofed up the notation. Let me rewrite my answer.  
> **username_5**: Now I see what you meant.  You did not have to remove the first row and the first column.  
> **username_0**: Hi Peter,  thanks for response, but according to the requirements $\det(M)^{1,2,3}_{1,2,3}$  as well as $\det(M)^1_1$ must be odd, which makes the left-hand-side odd. The same holds for $\det(M)^{1,2}_{1,2}$ and $\det(M)^{1,3}_{1,3}$, both must be odd. Only $\det(M)^{1,3}_{1,2}\det(M)^{1,2}_{1,3}$ are even, which makes the right-hand-side also even.  
> **username_2**: @Etsch: I was thinking $M$ when I wrote $M^{1,2,3}_{1,2,3}$.  I think it's correct now.  
> **username_0**: Perfect, now it makes sense, $\det(M)$ indeed must be odd. Thanks very much for your help.  

---

