Rozpuszczalność wypełnienia matrycy

Macierz ma wymiar . Chcemy wypełnić za pomocą liczb całkowitych od do włącznie. $A$ $n \times n(n-1)$ $A$ $1$ $n$

Wymagania:

Każda kolumna jest permutacją . $A$ $1, \dots, n$
Żadna submatrix utworzona z dwóch rzędów nie może mieć identycznych kolumn. $A$

Pytanie:

Czy możliwe jest wypełnienie matrycy spełniającej wymagania?

Związek z kryptografią:

Każdy numer wiersza odpowiada tekstowi jawnemu. Każda kolumna odpowiada kluczowi. Ponieważ klucz określa zastrzyk, każda kolumna musi być permutacją. Drugim wymogiem jest zachowanie idealnej tajemnicy dla dwóch wiadomości.

co.combinatorics cr.crypto-security coding-theory Cyker
źródło

Biorąc pod uwagę, że oznaczyłeś to tagiem cr.crypto-security, poprawiłoby to pytanie, gdybyś mógł określić, w jaki sposób odnosi się to do szyfrowania / bezpieczeństwa.

Dave Clarke

Proste obserwacje: taka macierz istnieje dla n≤4. Dla n≤3 weź wszystkie permutacje. Dla n = 4 jedynymi rozwiązaniami są wszystkie permutacje parzyste lub nieparzyste.

Tsuyoshi Ito

n \leq 4

$n \leq 4$

n \geq 5

$n \geq 5$

(1) Myślę, że problem związany jest z teorią kodowania i dodał ją jako tag. (2) Kolejne spostrzeżenie: problem można również określić w następujący sposób. Znajdź macierz B o rozmiarze n × (n ^ 2) tak, że każda z pierwszych n kolumn B jest n powtórzeniami o tej samej liczbie i taka, że B spełnia warunek 2 w pytaniu. Jeśli takie B istnieje, to każda z ostatnich n (n-1) kolumn B musi być permutacją. I odwrotnie, dowolną macierz A spełniającą warunki 1 i 2 można przekształcić w macierz B, dołączając n podanych kolumn po lewej stronie A.

Tsuyoshi Ito

Odpowiedzi:

Tsuyoshi, świetna obserwacja w twoim komentarzu! Myślę, że to prawie rozwiązuje problem.

Rozważ następujące dwa pytania

$k$ $n(n-1)$
$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
źródło

n - 2

$n - 2$

n

$n$

n - 1

$n - 1$

n

$n$

n

$n$

n - 1

$n - 1$

n = 6

$n = 6$

To bardzo miłe połączenie. Dziękuję za odpowiedź! Drobna uwaga: według Wikipedii wiadomo, że n-1 prostopadłe kwadraty łacińskie istnieją dla n-siły, nie tylko dla n-liczby.

Tsuyoshi Ito

@Tsuyoshi - Ups. Wiedziałem to; Po prostu powiedziałem to źle. Konstrukcja pochodzi z pól skończonych. Dziękuję za poprawienie mnie. Napraw to teraz.

Peter Shor

Zgadłem. :)

Tsuyoshi Ito

To jest częściowe rozwiązanie. Taka macierz istnieje, jeśli n jest siłą pierwszą.

Niech F będzie skończonym polem rzędu n . Konstruujemy macierz n × n ( n- 1), której wiersze są oznaczone przez F , której kolumny są oznaczone przez ( F ∖ {0}) × F , a których wpisy znajdują się w F w następujący sposób: i- ty rząd kolumna oznaczona ( a , b ) jest podana przez ai + b . W słowy, każda kolumna odpowiada stopniowi-jeden wielomian F . Następnie każda kolumna zawiera każdy element F. dokładnie raz, i żadna z dwóch kolumn nie ma równych wpisów w więcej niż jednym rzędzie, ponieważ wartości dwóch różnych wielomianów stopnia jeden mogą się pokrywać co najwyżej w jednym punkcie.

(Jeśli chcesz macierz, której wpisy znajdują się w {1,…, n } zamiast w F , zamień elementy F na {1,…, n } arbitralnie.)

Tsuyoshi Ito
źródło

n + 1

$n + 1$

@Artem: Być może, szczególnie biorąc pod uwagę odpowiedź Piotra łączącą to pytanie z prostopadłymi kwadratami łacińskimi. (Zastrzeżenie: według mojego nie-eksperckiego ortogonalne kwadraty łacińskie, MUB, kombinatoryczne, jednolite i SIC-POVM są prawie nierozróżnialne.)

Tsuyoshi Ito

Wielkie dzięki, Ito! Ten projekt wygląda naprawdę pięknie!

Cyker