¿Puede existir tal matriz?

Durante mi trabajo se me ocurrió el siguiente problema:

Estoy tratando de encontrar una matriz , para cualquier , con las siguientes propiedades: $n \times n$ $(0,1)$ $M$ $n > 3$

El determinante de es par. $M$
Para cualquier subconjunto no vacío con , La submatriz tiene determinante extraño si y sólo si . $I,J\subseteq\{1,2,3\}$ $|I| = |J|$ $M^I_J$ $I=J$

Aquí indica la submatriz de creado por la eliminación de las filas con índices en y las columnas con índices en . $M^I_J$ $M$ $I$ $J$

Hasta ahora, intenté encontrar una matriz de este tipo mediante un muestreo aleatorio, pero solo puedo encontrar una matriz que tenga todas las propiedades excepto la primera , es decir, la matriz siempre tiene un determinante impar. Probé varias dimensiones y diferentes conjuntos de entrada / salida sin ningún éxito. Entonces esto me hace pensar:

¿Es que existe una dependencia entre los requisitos, que les impide ser simultáneamente verdaderos?

¿Es posible que tal matriz exista y alguien puede darme un ejemplo?

Gracias Etsch

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

¿te refieres a subconjuntos aleatorios o cualquier subconjunto?

Suresh Venkat

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\}$

Sí, los dos subconjuntos y son fijos. Por ejemplo, para se puede establecer , , y , , y la pregunta es: ¿Hay una matriz (7x7) tal que , , y así sucesivamente, de acuerdo con las 20 propiedades definidas.

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

¿No podría simplemente arreglar , , , , , para simplificar la pregunta y facilitar su lectura?

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

Editado para mayor claridad.

Jeff el

Respuestas:

No existe tal matriz.

La identidad de Desnanot-Jacobi dice que para , usando esto, obtenemos Pero sus requisitos obligan al lado izquierdo a ser 0 (mod 2) y al lado derecho a ser 1 (mod 2), lo que demuestra que son 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
fuente

¡Agradable! Sin embargo, ahora estoy confundido porque el autor de la pregunta dijo que solo se puede satisfacer la segunda viñeta en la pregunta, lo que de hecho contradice la identidad que citó.

Tsuyoshi Ito

@ Tsuyoshi: ¿cómo la segunda bala contradice la identidad? La matriz identidad satisface la segunda bala, y que es fácil comprobar que satisface la identidad Desnanot-Jacobi. (A menos que esté tomando , lo que viola una condición en la identidad que acabo de agregar a mi respuesta.)

I

$I$

I

$I$

i = j

$i = j$

Peter Shor

Lo siento, mi comentario anterior fue falso, y parece que estoy más confundido de lo que pensaba. ¿Por qué el requisito en la pregunta obliga al lado izquierdo de la segunda ecuación en su respuesta a ser 0 mod 2?

Tsuyoshi Ito

Ahora veo a qué te referías. No tuvo que eliminar la primera fila y la primera columna.

Tsuyoshi Ito

@Etsch: Estaba pensando en cuando escribí . Creo que es correcto ahora.

M

$M$

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

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

Peter Shor