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

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ do you mean random subsets or any subsets ? $\endgroup$
    – Suresh Venkat
    Nov 9, 2011 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, 2011 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, 2011 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, 2011 at 0:54
  • 5
    $\begingroup$ Edited for clarity. $\endgroup$
    – Jeffε
    Nov 10, 2011 at 14:24

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
8
  • 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, 2011 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, 2011 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, 2011 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, 2011 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, 2011 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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