Kann eine solche Matrix existieren?

Während meiner Arbeit stieß ich auf folgendes Problem:

Ich versuche, eine $n \times n$ $(0,1)$ -Matrix $M$ für jedes $n > 3$ mit den folgenden Eigenschaften zu finden:

Die Determinante von $M$ ist gerade.
Für alle nicht leeren Teilmengen $I,J\subseteq\{1,2,3\}$ mit $|I| = |J|$ , Die Submatrix $M^I_J$ hat ungerade Determinante , wenn und nur wenn $I=J$ .

Hier bezeichnet $M^I_J$ die Submatrix von $M$ die durch Entfernen der Zeilen mit Indizes in $I$ und der Spalten mit Indizes in $J$ .

Bisher habe ich versucht, eine solche Matrix durch Zufallsstichprobe zu finden, aber ich kann nur eine Matrix finden, die alle Eigenschaften außer der ersten hat , dh die Matrix hat immer eine ungerade Determinante. Ich habe verschiedene Dimensionen und verschiedene Eingabe- / Ausgabesätze ohne Erfolg ausprobiert. Das bringt mich zum Nachdenken:

Gibt es eine Abhängigkeit zwischen den Anforderungen, die verhindert, dass sie gleichzeitig wahr sind?

oder

Ist es möglich, dass eine solche Matrix existiert und kann mir jemand ein Beispiel geben?

Danke, Etsch

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

Meinst du zufällige Teilmengen oder irgendwelche Teilmengen?

Suresh Venkat

Es scheint, dass und Konflikt stehen , weil es nichts gibt, was verhindern könnte, dass in einer zufälligen Teilmenge in einer anderen zufälligen Teilmenge ist. Oder möchten Sie nur, dass dies für ein einzelnes Paar von Teilmengen , ?

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

Ja, die beiden Teilmengen und sind fest. Beispielsweise für kann man einstellen , , und , , , und dann ist die Frage: Gibt es einen (7x7) Matrix derart , dass , , usw. gemäß den definierten 20 Eigenschaften.

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

Könnten Sie nicht einfach , , , , , , um die Frage zu vereinfachen und das Lesen zu erleichtern?

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

Aus Gründen der Übersichtlichkeit bearbeitet.

Jeffs

Antworten:

Eine solche Matrix existiert nicht.

Die Desnanot-Jacobi Identität sagt , dass für , so mit dies ergibt Ihre Anforderungen erzwingen jedoch, dass die linke Seite 0 (Mod 2) und die rechte Seite 1 (Mod 2) ist, was zeigt, dass sie nicht kompatibel sind. $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
quelle

Nett! Jetzt bin ich jedoch verwirrt, weil der Fragesteller sagte, dass die zweite Kugel in der Frage allein erfüllt werden kann, was in der Tat der von Ihnen zitierten Identität widerspricht.

Tsuyoshi Ito

@ Tsuyoshi: Wie widerspricht die zweite Kugel der Identität? Die Identitätsmatrix erfüllt die zweite Kugel, und es ist leicht zu überprüfen, ob die Desnanot-Jacobi-Identität erfülle. (Es sei denn, Sie nehmen , was eine Bedingung in der Identität verletzt, die ich gerade zu meiner Antwort hinzugefügt habe.)

I

$I$

I

$I$

i = j

$i = j$

Peter Shor

Entschuldigung, mein vorheriger Kommentar war falsch und es scheint, dass ich verwirrter bin als ich dachte. Warum zwingt die Anforderung in der Frage die linke Seite der zweiten Gleichung in Ihrer Antwort auf 0 mod 2?

Tsuyoshi Ito

Jetzt verstehe ich, was du gemeint hast. Sie mussten die erste Zeile und die erste Spalte nicht entfernen.

Tsuyoshi Ito

@Etsch: Ich dachte an als ich . Ich denke es ist jetzt richtig.

M

$M$

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

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

Peter Shor