Essa matriz pode existir?

Durante o meu trabalho, eu vim com o seguinte problema:

Estou tentando encontrar uma matriz , para qualquer , com as seguintes propriedades: $n \times n$ $(0,1)$ $M$ $n > 3$

O determinante de é par. $M$
Para qualquer subconjunto não vazio com, A submatriz tem determinante estranho se e somente se . $I,J\subseteq\{1,2,3\}$ $|I| = |J|$ $M^I_J$ $I=J$

Aqui denota a submatriz de criado por remover as linhas com índices em e as colunas com índices em . $M^I_J$ $M$ $I$ $J$

Até agora, tentei encontrar essa matriz por amostragem aleatória, mas só consigo encontrar uma matriz que possua todas as propriedades, exceto a primeira , ou seja, a matriz sempre tem um determinante ímpar. Tentei várias dimensões e diferentes conjuntos de entrada / saída sem sucesso. Então isso me faz pensar:

Existe uma dependência entre os requisitos, o que os impede de serem simultaneamente verdadeiros?

É possível que essa matriz exista e alguém pode me dar um exemplo?

Obrigado, Etsch

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

você quer dizer subconjuntos aleatórios ou quaisquer subconjuntos?

Suresh Venkat

Parece que e conflitam entre si , porque não há nada para parar em um subconjunto aleatório sendo em outro subconjunto aleatório. Ou você só quer que isso seja verdade para um único par de subconjuntos , ?

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

Sim, os dois subconjuntos e foram corrigidos. Por exemplo, para pode-se definir , , e , , e, em seguida, a pergunta é: Existe uma matriz (7x7) tal que , , e assim por diante, de acordo com as 20 propriedades 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

Você não poderia simplesmente corrigir , , , , , para simplificar a pergunta e facilitar a leitura?

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 maior clareza.

Jeffε

Respostas:

Não existe essa matriz.

A identidade Desnanot-Jacobi diz que, para , usando isso, obtemos Mas seus requisitos forçam o lado esquerdo a ser 0 (mod 2) e o lado direito a ser 1 (mod 2), mostrando que eles são incompatíveis. $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
fonte

Agradável! No entanto, agora estou confuso porque o autor da pergunta disse que somente a segunda bala da pergunta pode ser satisfeita, o que de fato contradiz a identidade que você citou.

Tsuyoshi Ito

@ Tsuyoshi: como a segunda bala contradiz a identidade? A matriz de identidade que satisfaz a segunda bala, e é fácil verificar se satisfaz a identidade de Desnanot-Jacobi. (A menos que você está tomando , o que viola uma condição na identidade que eu adicionei para a minha resposta.)

I

$I$

I

$I$

i = j

$i = j$

Peter Shor

Desculpe, meu comentário anterior foi falso e parece que estou mais confuso do que pensei. Por que o requisito na pergunta força o lado esquerdo da segunda equação em sua resposta a ser 0 mod 2?

Tsuyoshi Ito

Agora eu entendo o que você quis dizer. Você não precisou remover a primeira linha e a primeira coluna.

Tsuyoshi Ito

@Etsch: Eu estava pensando em quando escrevi . Eu acho que está correto agora.

M

$M$

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

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

quer