Une telle matrice peut-elle exister?

10

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

J'essaie de trouver une -matrice , pour tout , avec les propriétés suivantes:( 0 , 1 ) M n > 3n×n (0,1)Mn>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 . | Je | = | J | M I J I = JI,J{1,2,3}|I|=|J|MJII=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 JMJIMIJ

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?

ou

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

Merci, Etsch

Etsch
la source
1
voulez-vous dire des sous-ensembles aléatoires ou des sous-ensembles?
Suresh Venkat
1
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 i 1 o 2 ) 0det(Mo1i1)1(mod2)o 1 o 2 { o 1 , o 2 , o 3 } { i 1 , i 2 , i 3 }det(Mo2i1)0(mod2)o1o2{o1,o2,o3}{i1,i2,i3}
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. O = { o 1 , o 2 , o 3 } n = 7 i 1 = 1 i 2 = 2 i 3 = 5 o 1 = 2 o 2 = 3 o 3 = 4 M det ( M ) 0I={i1,i2,i3}O={o1,o2,o3}n=7i1=1i2=2i3=5o1=2o2=3o3=4Mdet ( M 1 , 2 , 5 2 , 3 , 4 ) 1det(M)0(mod2)det ( M 1 , 2 2 , 3 ) 1det(M2,3,41,2,5)1(mod2)det(M2,31,2)1(mod2)
Etsch
2
Ne pourriez-vous pas simplement corriger , , , , , pour simplifier la question et la rendre plus facile à lire? i 2 = 2 i 3 = 3 o 1 = 1 o 2 = 2 o 3 = 3i1=1i2=2i3=3o1=1o2=2o3=3
Jukka Suomela
5
Modifié pour plus de clarté.
Jeffε

Réponses:

22

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.det M i j i j det M = det M i i det M j j - det M j i det M i j det M 12 12 det M = det M 1 1 det M 2 2 - det M 2 1 det M 1 2ij

detMijijdetM=detMiidetMjjdetMijdetMji
detM1212detM=detM11detM22detM12detM21
Peter Shor
la source
1
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
1
@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 = jIIi=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
1
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
1
@Etsch: Je pensais à quand j'ai écrit . Je pense que c'est correct maintenant. M 1 , 2 , 3 1 , 2 , 3MM1,2,31,2,3
Peter Shor