Solvabilitas pengisian matriks

Matriks memiliki dimensi . Kami ingin mengisi menggunakan bilangan bulat antara dan , inklusif. $A$ $n \times n(n-1)$ $A$ $1$ $n$

Persyaratan:

Setiap kolom adalah permutasi . $A$ $1, \dots, n$
Setiap submatrix yang dibentuk oleh dua baris tidak dapat memiliki kolom yang identik. $A$

Pertanyaan:

Apakah mungkin untuk mengisi matriks yang memenuhi persyaratan?

Hubungan dengan kriptografi:

Setiap nomor baris sesuai dengan plaintext. Setiap kolom berhubungan dengan kunci. Karena kunci mendefinisikan injeksi, setiap kolom harus permutasi. Persyaratan kedua adalah kerahasiaan sempurna untuk dua pesan.

co.combinatorics cr.crypto-security coding-theory Cyker
sumber

Mengingat Anda telah menandai ini dengan cr.crypto-security, itu akan meningkatkan pertanyaan jika Anda bisa menyatakan bagaimana kaitannya dengan crypto / security.

Dave Clarke

Pengamatan sederhana: Matriks seperti itu ada untuk n≤4. Untuk n≤3, ambil semua permutasi. Untuk n = 4, satu-satunya solusi adalah mengambil semua permutasi genap atau semua permutasi ganjil.

Tsuyoshi Ito

Terima kasih, Ito. Sebenarnya saya datang dengan jawaban ketika

dengan tangan. Tetapi hal-hal menjadi jauh lebih sulit ketika

. Ledakan eksponensial terjadi.

n \leq 4

$n \leq 4$

n \geq 5

$n \geq 5$

Cyker

(1) Saya pikir masalahnya terkait dengan teori pengkodean dan menambahkannya sebagai tag. (2) Pengamatan lain: Masalahnya dapat dinyatakan juga sebagai berikut. Temukan matriks B ukuran n × (n ^ 2) sedemikian rupa sehingga masing-masing kolom n pertama dari B adalah n pengulangan dari nomor yang sama dan sedemikian rupa sehingga B memenuhi syarat 2 dalam pertanyaan. Jika B seperti itu ada, maka masing-masing dari n (n − 1) kolom B terakhir harus permutasi. Sebaliknya, setiap matriks A yang memenuhi kondisi 1 dan 2 dapat dikonversi ke matriks B dengan melampirkan kolom yang dinyatakan di sebelah kiri A.

Tsuyoshi Ito

Jawaban:

Tsuyoshi, pengamatan hebat dalam komentar Anda! Saya pikir ini hampir menyelesaikan masalah.

Pertimbangkan dua pertanyaan berikut

Apakah ada baris dengan panjang sehingga tidak ada angka yang muncul dua kali dalam kolom apa pun, dan untuk setiap pasangan baris, semua pasangan berurutan yang diberikan oleh kolom berbeda? $k$ $n(n-1)$
Apakah ada baris dengan panjang sehingga untuk setiap pasangan baris, semua pasangan berurutan yang diberikan oleh kolom berbeda? $k$ $n^2$

$k$ $k$ $k$ $k-1$

$1$ $n$ $\lbrace 1, 2, \ldots, n \rbrace$ $k-1$ $n$ $k-1$

$k$ $n^2$ $k-2$ $3$ $4$ $\ldots$ $k$ $j$ $i$ $j$ $i$

$n$ $n$ $n-2$ $n$ $n=6$ $k$ $k=\Omega(n^c)$ $c$ $1$

$n=6$ $k$ $6\times 6$ $n=10$ $k=4$

Peter Shor
sumber

n - 2

$n - 2$

n

$n$

n - 1

$n - 1$

n

$n$

n

$n$

n - 1

$n - 1$

n = 6

$n = 6$

Ini koneksi yang sangat bagus. Terima kasih atas jawabannya! Poin minor: Menurut Wikipedia, diketahui bahwa n − 1 kotak Latin ortogonal ada untuk n kekuatan utama, tidak hanya untuk n prime.

Tsuyoshi Ito

@ Tsuyoshi - Ups. Saya tahu itu; Saya hanya mengatakan itu salah. Konstruksi berasal dari bidang yang terbatas. Terima kasih atas koreksinya. Perbaiki sekarang.

Peter Shor

Saya rasa begitu. :)

Tsuyoshi Ito

Ini adalah solusi parsial. Matriks seperti itu ada jika n adalah kekuatan utama.

Biarkan F menjadi bidang urutan terbatas n . Kami membangun sebuah matriks n × n ( n −1) yang barisnya diberi label oleh F , yang kolomnya dilabeli oleh ( F ∖ {0}) × F , dan yang entri-entrinya dalam F sebagai berikut: baris ke- i dari kolom berlabel ( a , b ) diberikan oleh ai + b . Dengan kata, setiap kolom berkorespondensi untuk tingkat-satu polinomial di F . Kemudian setiap kolom berisi setiap elemen F tepat sekali, dan tidak ada dua kolom memiliki entri yang sama di lebih dari satu baris karena nilai dua polinomial derajat-satu yang berbeda dapat bertepatan paling banyak satu titik.

(Jika Anda ingin sebuah matriks yang entri-entrinya ada dalam {1, ..., n } alih-alih dalam F , ganti elemen F dengan {1, ..., n } secara sewenang-wenang.)

Tsuyoshi Ito
sumber

n + 1

$n + 1$

@ Artem: Mungkin ada, terutama mengingat jawaban Peter yang menghubungkan pertanyaan ini dengan kotak Latin ortogonal. (Penafian: dalam pandangan non-ahli saya, kotak Latin ortogonal, MUB, desain kombinatorial, desain kesatuan dan SIC-POVM hampir tidak bisa dibedakan.)

Tsuyoshi Ito

Terima kasih banyak, Ito! Desain ini terlihat sangat indah!

Cyker