# Can such a matrix exist?

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

• do you mean random subsets or any subsets ? – Suresh Venkat Nov 9 '11 at 10:39
• 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 Nov 9 '11 at 16:51
• 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 Nov 9 '11 at 18:19
• 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 Nov 10 '11 at 0:54
• Edited for clarity. – Jeffε Nov 10 '11 at 14:24

The Desnanot-Jacobi identity 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.
• @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 Nov 10 '11 at 19:45
• @Etsch: I was thinking $M$ when I wrote $M^{1,2,3}_{1,2,3}$. I think it's correct now. – Peter Shor Nov 10 '11 at 20:01