10
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ do you mean random subsets or any subsets ? $\endgroup$ – Suresh Venkat Nov 9 '11 at 10:39
  • 1
    $\begingroup$ 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\}$? $\endgroup$ – Peter Shor Nov 9 '11 at 16:51
  • $\begingroup$ 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. $\endgroup$ – Etsch Nov 9 '11 at 18:19
  • 2
    $\begingroup$ 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? $\endgroup$ – Jukka Suomela Nov 10 '11 at 0:54
  • 5
    $\begingroup$ Edited for clarity. $\endgroup$ – Jeffε Nov 10 '11 at 14:24
22
$\begingroup$

No such matrix exists.

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Nov 10 '11 at 17:53
  • 1
    $\begingroup$ @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.) $\endgroup$ – Peter Shor Nov 10 '11 at 19:45
  • $\begingroup$ 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? $\endgroup$ – Tsuyoshi Ito Nov 10 '11 at 19:50
  • 1
    $\begingroup$ Now I see what you meant. You did not have to remove the first row and the first column. $\endgroup$ – Tsuyoshi Ito Nov 10 '11 at 19:53
  • 1
    $\begingroup$ @Etsch: I was thinking $M$ when I wrote $M^{1,2,3}_{1,2,3}$. I think it's correct now. $\endgroup$ – Peter Shor Nov 10 '11 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.