Может ли такая матрица существовать?

Во время моей работы я столкнулся со следующей проблемой:

Я пытаюсь найти -матрицу , для любого , со следующими свойствами: $n \times n$ $(0,1)$ $M$ $n > 3$

Определитель четен. $M$
Для любых непустых подмножеств с, Подматрица имеет нечетный детерминанту тогда и только тогда , когда . $I,J\subseteq\{1,2,3\}$ $|I| = |J|$ $M^I_J$ $I=J$

Здесь обозначает подматрица создается путем удаления строк с индексами в и столбцами с номерами из . $M^I_J$ $M$ $I$ $J$

До сих пор я пытался найти такую матрицу с помощью случайной выборки, но я смог найти только матрицу, которая имеет все свойства, кроме первого , т. Е. Матрица всегда имеет нечетный определитель. Я пробовал разные размеры и разные наборы ввода / вывода без какого-либо успеха. Так что это заставляет меня думать:

Есть ли зависимость между требованиями, которая мешает им быть одновременно истинными?

или

Возможно ли, что такая матрица существует, и может ли кто-нибудь привести мне пример?

Спасибо, Etsch

graph-theory co.combinatorics linear-algebra matrices boolean-matrix Etsch
источник

Вы имеете в виду случайные подмножества или какие-либо подмножества?

Суреш Венкат

Похоже, что и конфликтуют друг с другом потому что ничто не может остановить в одном случайном подмножестве, являющееся в другом случайном подмножестве. Или вы просто хотите, чтобы это было верно для одной пары подмножеств , ?

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

Питер Шор

Да, два подмножества и являются фиксированными. Например, для можно установить , , и , , и тогда возникает вопрос: существует ли (7x7) матрица такая, что , , и т. Д. В соответствии с определенными 20 свойствами.

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

Не могли бы вы просто исправить , , , , , чтобы упростить вопрос и сделать его проще для чтения?

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$

Юкка Суомела

Отредактировано для наглядности.

Джефф

Ответы:

Такой матрицы не существует.

Идентичность Desnanot-Якоби говорит , что для , так , используя мы получаем Но ваши требования вынуждают левую сторону быть 0 (мод 2) и правую сторону равной 1 (мод 2), показывая, что они несовместимы. $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}$

Питер Шор
источник

Ницца! Тем не менее, теперь я запутался, потому что спрашивающий сказал, что вторая пуля в этом вопросе может быть удовлетворена, что действительно противоречит той личности, которую вы цитировали.

Tsuyoshi Ito

@ Tsuyoshi: как вторая пуля противоречит личности? Тождественная матрица удовлетворяет второму пункту, и легко проверить, что удовлетворяю тождеству Деснанота-Якоби. (Если вы не берете , что нарушает условие в идентичности, которое я только что добавил к своему ответу.)

I

$I$

I

$I$

i = j

$i = j$

Питер Шор

Извините, мой предыдущий комментарий был фальшивым, и мне кажется, что я запутался больше, чем думал. Почему требование в вопросе заставляет левую часть второго уравнения в вашем ответе быть 0 mod 2?

Tsuyoshi Ito

Теперь я понимаю, что вы имели в виду. Вам не нужно было удалять первую строку и первый столбец.

Tsuyoshi Ito

@Etsch: я думал о когда писал . Я думаю, что теперь это правильно.

M

$M$

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

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

Питер Шор