Une telle matrice peut-elle exister?

Pendant mon travail, j'ai rencontré le problème suivant:

J'essaie de trouver une -matrice , pour tout , avec les propriétés suivantes: $n \times n$ $(0,1)$ $M$ $n > 3$

Le déterminant de est pair. $M$
Pour tout sous-ensemble non vide avec, La sous - matrice a déterminant impair si et seulement si . $I,J\subseteq\{1,2,3\}$ $|I| = |J|$ $M^I_J$ $I=J$

Ici désigne le sous - matrice de créé en supprimant les lignes avec des indices dans et les colonnes avec des indices dans . $M^I_J$ $M$ $I$ $J$

Jusqu'à présent, j'ai essayé de trouver une telle matrice via un échantillonnage aléatoire, mais je ne peux trouver qu'une matrice qui a toutes les propriétés sauf la première , c'est-à-dire que la matrice a toujours un déterminant impair. J'ai essayé différentes dimensions et différents ensembles d'entrée / sortie sans succès. Cela me fait donc penser:

Est-ce qu'il y a une dépendance entre les exigences, ce qui les empêche d'être simultanément vraies?

Est-il possible qu'une telle matrice existe et quelqu'un peut-il me donner un exemple?

Merci, Etsch

graph-theory co.combinatorics linear-algebra matrices boolean-matrix Etsch
la source

voulez-vous dire des sous-ensembles aléatoires ou des sous-ensembles?

Suresh Venkat

Il semble que et entrent en conflit les uns avec les autres , car rien n'empêche dans un sous-ensemble aléatoire d'être dans un autre sous-ensemble aléatoire. Ou voulez-vous simplement que cela soit vrai pour une seule paire de sous-ensembles , ?

det (M_{o_{1}}^{i_{1}}) \equiv 1 (\mod 2)

$\det(M^{i_1}_{o_1}) \equiv 1 \pmod{2}$

det (M_{o_{2}}^{i_{1}}) \equiv 0 (\mod 2)

$\det(M^{i_1}_{o_2}) \equiv 0 \pmod{2}$

o_{1}

$o_1$

o_{2}

$o_2$

{o_{1}, o_{2}, o_{3}}

$\{o_1,o_2,o_3\}$

{i_{1}, i_{2}, i_{3}}

$\{i_1,i_2,i_3\}$

Peter Shor

Oui, les deux sous-ensembles et sont fixes. Par exemple, pour on peut définir , , et , , , puis la question est la suivante: existe-t-il une matrice (7x7) telle que , , et ainsi de suite, selon les 20 propriétés définies.

I = {i_{1}, i_{2}, i_{3}}

$\mathcal{I} = \{i_1,i_2,i_3\}$

O = {o_{1}, o_{2}, o_{3}}

$\mathcal{O} = \{o_1,o_2,o_3\}$

n = 7

$n=7$

i_{1} = 1

$i_1 = 1$

i_{2} = 2

$i_2 = 2$

i_{3} = 5

$i_3 = 5$

o_{1} = 2

$o_1 = 2$

o_{2} = 3

$o_2 = 3$

o_{3} = 4

$o_3 = 4$

M

$M$

det (M) \equiv 0 (\mod 2)

$\det(M) \equiv 0\pmod{2}$

det (M_{2, 3, 4}^{1, 2, 5}) \equiv 1 (\mod 2)

$\det(M^{1,2,5}_{2,3,4}) \equiv 1 \pmod{2}$

det (M_{2, 3}^{1, 2}) \equiv 1 (\mod 2)

$\det(M^{1,2}_{2,3}) \equiv 1\pmod{2}$

Etsch

Ne pourriez-vous pas simplement corriger , , , , , pour simplifier la question et la rendre plus facile à lire?

i_{1} = 1

$i_1 = 1$

i_{2} = 2

$i_2 = 2$

i_{3} = 3

$i_3 = 3$

o_{1} = 1

$o_1 = 1$

o_{2} = 2

$o_2 = 2$

o_{3} = 3

$o_3 = 3$

Jukka Suomela

Modifié pour plus de clarté.

Jeffε

Réponses:

Aucune matrice de ce type n'existe.

L' identité Desnanot-Jacobi dit que pour , donc en utilisant cela nous donne Mais vos exigences forcent le côté gauche à 0 (mod 2) et le côté droit à 1 (mod 2), montrant qu'ils sont incompatibles. $i \neq j$

det M_{i j}^{i j} det M = det M_{i}^{i} det M_{j}^{j} - det M_{i}^{j} det M_{j}^{i}

$\det M_{ij}^{ij} \det M = \det M_i^i \det M_j^j -\det M_i^j \det M_j^i$

det M_{12}^{12} det M = det M_{1}^{1} det M_{2}^{2} - det M_{1}^{2} det M_{2}^{1}

$\det M_{12}^{12} \det M = \det M_{1}^{1} \det M_{2}^{2} - \det M_{1}^{2} \det M_{2}^{1}$

Peter Shor
la source

Agréable! Cependant, maintenant je suis confus parce que le demandeur a dit que la deuxième puce de la question seule peut être satisfaite, ce qui contredit en effet l'identité que vous avez citée.

Tsuyoshi Ito

@Tsuyoshi: comment la deuxième puce contredit-elle l'identité? La matrice d'identité satisfait la deuxième puce, et il est facile de vérifier que satisfait l'identité de Desnanot-Jacobi. (Sauf si vous prenez , ce qui viole une condition de l'identité que je viens d'ajouter à ma réponse.)

I

$I$

I

$I$

i = j

$i = j$

Peter Shor

Désolé, mon commentaire précédent était faux, et il semble que je suis plus confus que je ne le pensais. Pourquoi l'exigence de la question force-t-elle le côté gauche de la deuxième équation de votre réponse à 0 mod 2?

Tsuyoshi Ito

Maintenant je vois ce que tu voulais dire. Vous n'avez pas eu à supprimer la première ligne et la première colonne.

Tsuyoshi Ito

@Etsch: Je pensais à quand j'ai écrit . Je pense que c'est correct maintenant.

M

$M$

M_{1, 2, 3}^{1, 2, 3}

$M^{1,2,3}_{1,2,3}$

Peter Shor