Bisakah matriks semacam itu ada?

10

Selama bekerja, saya menemukan masalah berikut:

Saya mencoba menemukan -matrix , untuk , dengan properti berikut:( 0 , 1 ) M n > 3n×n (0,1)Mn>3

  • Penentu adalah genap.M
  • Untuk setiap himpunan bagian non-kosong dengan, Submatriks memiliki penentu aneh jika dan hanya jika . | Saya | = | J | M I J I = JI,J{1,2,3}|I|=|J|MJII=J

Berikut menunjukkan submatriks dari diciptakan dengan menghapus baris dengan indeks di dan kolom dengan indeks di .MJII JMIJ

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

Etsch
sumber
1
maksud Anda himpunan bagian acak atau himpunan bagian apa pun?
Suresh Venkat
1
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 i 1 o 2 ) 0det(Mo1i1)1(mod2)det(Mo2i1)0(mod2)o 2 { o 1 , o 2 , o 3 } { i 1 , i 2 , i 3 }o1o2{o1,o2,o3}{i1,i2,i3}
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. O = { o 1 , o 2 , o 3 } n = 7 i 1 = 1 i 2 = 2 i 3 = 5 o 1 = 2 o 2 = 3 o 3 = 4 M det ( M ) 0I={i1,i2,i3}O={o1,o2,o3}n=7i1=1i2=2i3=5o1=2o2=3o3=4Mdet ( M 1 , 2 , 5 2 , 3 , 4 ) 1det(M)0(mod2)det ( M 1 , 2 2 , 3 ) 1det(M2,3,41,2,5)1(mod2)det(M2,31,2)1(mod2)
Etsch
2
Tidak bisakah Anda memperbaiki , , , , , untuk menyederhanakan pertanyaan dan membuatnya lebih mudah dibaca? i 2 = 2 i 3 = 3 o 1 = 1 o 2 = 2 o 3 = 3i1=1i2=2i3=3o1=1o2=2o3=3
Jukka Suomela
5
Diedit untuk kejelasan.
Jeff

Jawaban:

22

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.det M i j i j det M = det M i i det M j j - det M j i det M i j det M 12 12 det M = det M 1 1 det M 2 2 - det M 2 1 det M 1 2ij

detMijijdetM=detMiidetMjjdetMijdetMji
detM1212detM=detM11detM22detM12detM21
Peter Shor
sumber
1
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
1
@ 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 = jIIi=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
1
Sekarang saya mengerti maksud Anda. Anda tidak harus menghapus baris pertama dan kolom pertama.
Tsuyoshi Ito
1
@ Etsch: Saya berpikir ketika saya menulis . Saya pikir itu benar sekarang. M 1 , 2 , 3 1 , 2 , 3MM1,2,31,2,3
Peter Shor