Bisakah matriks semacam itu ada?

Selama bekerja, saya menemukan masalah berikut:

Saya mencoba menemukan -matrix , untuk , dengan properti berikut: $n \times n$ $(0,1)$ $M$ $n > 3$

Penentu adalah genap. $M$
Untuk setiap himpunan bagian non-kosong dengan, Submatriks memiliki penentu aneh jika dan hanya jika . $I,J\subseteq\{1,2,3\}$ $|I| = |J|$ $M^I_J$ $I=J$

Berikut menunjukkan submatriks dari diciptakan dengan menghapus baris dengan indeks di dan kolom dengan indeks di . $M^I_J$ $M$ $I$ $J$

Sejauh ini, saya mencoba untuk menemukan matriks seperti itu melalui pengambilan sampel acak tetapi saya hanya dapat menemukan matriks yang memiliki semua properti kecuali yang pertama , yaitu, matriks selalu memiliki penentu aneh. Saya mencoba berbagai dimensi dan set input / output yang berbeda tanpa hasil. Jadi ini membuat saya berpikir:

Apakah ada ketergantungan di antara persyaratan, yang mencegah mereka secara bersamaan benar?

atau

Mungkinkah matriks semacam itu ada dan dapatkah seseorang memberi saya contoh?

Terima kasih, Etsch

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

maksud Anda himpunan bagian acak atau himpunan bagian apa pun?

Suresh Venkat

Tampaknya dan saling bertentangan , karena tidak ada yang menghentikan dalam satu subset acak menjadi dalam subset acak lain. Atau Anda hanya ingin ini benar untuk sepasang himpunan bagian , ?

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

Ya, dua himpunan bagian dan sudah diperbaiki. Misalnya untuk orang dapat mengatur , , dan , , dan kemudian pertanyaannya adalah: Apakah ada (7x7) matriks sedemikian sehingga , , dan seterusnya, sesuai dengan 20 properti yang ditentukan.

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

Tidak bisakah Anda memperbaiki , , , , , untuk menyederhanakan pertanyaan dan membuatnya lebih mudah dibaca?

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

Diedit untuk kejelasan.

Jeff

Jawaban:

Tidak ada matriks seperti itu.

The Desnanot-Jacobi identitas mengatakan bahwa untuk , sehingga menggunakan ini, kita dapatkan Tetapi persyaratan Anda memaksa sisi kiri menjadi 0 (mod 2) dan sisi kanan menjadi 1 (mod 2), menunjukkan mereka tidak kompatibel. $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
sumber

Bagus! Namun, sekarang saya bingung karena penanya mengatakan bahwa peluru kedua dalam pertanyaan itu saja dapat dipenuhi, yang memang bertentangan dengan identitas yang Anda kutip.

Tsuyoshi Ito

@ Tsuyoshi: bagaimana peluru kedua bertentangan dengan identitas? Matriks identitas memuaskan peluru kedua, dan mudah untuk memeriksa apakah memenuhi identitas Desnanot-Jacobi. (Kecuali jika Anda menggunakan , yang melanggar suatu kondisi dalam identitas yang baru saja saya tambahkan pada jawaban saya.)

I

$I$

I

$I$

i = j

$i = j$

Peter Shor

Maaf, komentar saya sebelumnya palsu, dan sepertinya saya lebih bingung daripada yang saya kira. Mengapa persyaratan dalam pertanyaan memaksa sisi kiri persamaan kedua dalam jawaban Anda menjadi 0 mod 2?

Tsuyoshi Ito

Sekarang saya mengerti maksud Anda. Anda tidak harus menghapus baris pertama dan kolom pertama.

Tsuyoshi Ito

@ Etsch: Saya berpikir ketika saya menulis . Saya pikir itu benar sekarang.

M

$M$

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

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

Peter Shor