Разрешимость заполнения матрицы

Матрица имеет размерность . Мы хотим заполнить используя целые числа от до включительно. $A$ $n \times n(n-1)$ $A$ $1$ $n$

Требования:

Каждый столбец является перестановкой . $A$ $1, \dots, n$
Любая подматрица, образованная двумя строками не может иметь одинаковые столбцы. $A$

Вопрос:

Можно ли заполнить матрицу, удовлетворяющую требованиям?

Отношение к криптографии:

Каждый номер строки соответствует открытому тексту. Каждый столбец соответствует ключу. Поскольку ключ определяет инъекцию, каждый столбец должен быть перестановкой. Второе требование - полная секретность двух сообщений.

co.combinatorics cr.crypto-security coding-theory Cyker
источник

Учитывая, что вы пометили это с помощью cr.crypto-security, это улучшило бы вопрос, если бы вы могли заявить, как это относится к крипто / безопасности.

Дейв Кларк,

Простые наблюдения: такая матрица существует для n≤4. Для n≤3 возьмите все перестановки. При n = 4 единственными решениями являются все четные перестановки или все нечетные перестановки.

Цуёси Ито

Спасибо, Ито. На самом деле я придумал ответ, когда

от руки. Но все становится намного сложнее, когда

. Происходит экспоненциальный взрыв.

n \leq 4

$n \leq 4$

n \geq 5

$n \geq 5$

Cyker

(1) Я думаю, что проблема связана с теорией кодирования и добавил ее в качестве тега. (2) Еще одно наблюдение: проблему можно сформулировать также следующим образом. Найдите матрицу B размера n × (n ^ 2), такую, что каждый из первых n столбцов B является n повторениями одного и того же числа и такой, что B удовлетворяет условию 2 в вопросе. Если такой B существует, то каждый из последних n (n − 1) столбцов B должен быть перестановкой. И наоборот, любая матрица A, удовлетворяющая условиям 1 и 2, может быть преобразована в матрицу B путем присоединения n указанных столбцов слева от A.

Tsuyoshi Ito

Ответы:

Tsuyoshi, большое замечание в вашем комментарии! Я думаю, что это почти решает проблему.

Рассмотрим следующие два вопроса

Существует ли строк длины чтобы ни в одном столбце число не встречалось дважды, а для каждой пары строк все упорядоченные пары, заданные столбцами, различны? $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$

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

n - 2

$n - 2$

n

$n$

n - 1

$n - 1$

n

$n$

n

$n$

n - 1

$n - 1$

n = 6

$n = 6$

Это очень хорошая связь. Спасибо за ответ! Незначительный момент: согласно Википедии известно, что n − 1 ортогональных латинских квадратов существуют для n простых степеней, а не только для n простых.

Цуёси Ито

@ Tsuyoshi - Упс. Я знал это; Я просто сказал, что это неправильно. Конструкция происходит из конечных полей. Спасибо за исправление. Исправляем это сейчас.

Питер Шор

Я так и предположил. :)

Tsuyoshi Ito

Это частичное решение. Такая матрица существует, если n - простая степень.

Пусть F - конечное поле порядка n . Мы строим матрицу n × n ( n − 1), строки которой помечены буквой F , столбцы которой помечены ( F ∖ {0}) × F , а записи которой находятся в F следующим образом: i-я строка столбец с меткой ( a , b ) задается как ai + b . На словах, каждый столбец соответствует степени полинома-один в F . Тогда каждый столбец содержит каждый элемент F ровно один раз, и никакие два столбца не имеют одинаковых записей в более чем одной строке, потому что значения двух различных многочленов степени один могут совпадать не более чем в одной точке.

(Если вам нужна матрица, элементы которой находятся в {1,…, n } вместо F , замените элементы F на {1,…, n } произвольно.)

Цуёси Ито
источник

n + 1

$n + 1$

@ Артем: Может быть, особенно учитывая ответ Петра, связывающий этот вопрос с ортогональными латинскими квадратами. (Отказ от ответственности: на мой неэкспертный взгляд, ортогональные латинские квадраты, MUB, комбинаторные конструкции, унитарные конструкции и SIC-POVM почти неразличимы.)

Tsuyoshi Ito

Большое спасибо, Ито! Этот дизайн выглядит действительно красиво!

Cyker