Solvabilidade do enchimento da matriz

11

matriz tem dimensão . Queremos preencher usando inteiros entre e , inclusive.n × n ( n - 1 ) A 1 nAn×n(n1)A1n

Requisitos:

  1. Cada coluna de é uma permutação de .1 , , nA1,,n
  2. Qualquer submatriz formada por duas linhas de não pode ter colunas idênticas.A

Questão:

É possível preencher a matriz satisfazendo os requisitos?

Relação com criptografia:

Cada número de linha corresponde a um texto sem formatação. Cada coluna corresponde a uma chave. Como uma chave define uma injeção, cada coluna deve ser uma permutação. O segundo requisito é o segredo perfeito para duas mensagens.

Cyker
fonte
1
Dado que você marcou isso com cr.crypto-security, melhoraria a questão se você pudesse declarar como isso se relaciona com cripto / segurança.
Dave Clarke
1
Observações simples: Essa matriz existe para n≤4. Para n≤3, faça todas as permutações. Para n = 4, as únicas soluções são tomar todas as permutações pares ou todas as permutações ímpares.
Tsuyoshi Ito
Obrigado, Ito. Na verdade, eu vim com a resposta quando à mão. Mas as coisas se tornam muito mais difíceis quando . Explosão exponencial ocorre. n 5n4n5
Cyker
3
(1) Eu acho que o problema está relacionado à teoria da codificação e a adicionei como uma tag. (2) Outra observação: O problema pode ser afirmado também da seguinte forma. Encontre uma matriz B de tamanho n × (n ^ 2) tal que cada uma das primeiras n colunas de B seja n repetições do mesmo número e tal que B satisfaça a condição 2 da questão. Se esse B existir, cada uma das últimas n (n − 1) colunas de B deve ser uma permutação. Inversamente, qualquer matriz A que satisfaça as condições 1 e 2 pode ser convertida em uma matriz B anexando as n colunas indicadas à esquerda de A.
Tsuyoshi Ito

Respostas:

11

Tsuyoshi, ótima observação no seu comentário! Eu acho que isso quase resolve o problema.

Considere as duas perguntas a seguir

  1. Existem linhas de comprimento para que nenhum número apareça duas vezes em qualquer coluna e para cada par de linhas todos os pares ordenados dados pelas colunas sejam distintos?n ( n - 1 )kn(n1)
  2. Existem linhas de comprimento para que, para cada par de linhas, todos os pares ordenados dados pelas colunas sejam distintos?n 2kn2

A observação de Tsuyoshi em seu comentário mostra que se você pode obter algum valor para a pergunta (1), pode obter o mesmo valor para a pergunta (2). Agora mostramos que, se conseguirmos algum valor para a pergunta (2), podemos alcançar o valor para a pergunta (1). Portanto, a resposta para essas duas perguntas é quase a mesma.k k k - 1kkkk1

A construção continua da seguinte forma: Ignorar a primeira linha, excepto colocar todos os 's nos primeiros posições. Agora você pode aplicar uma permutação dos valores a cada uma das linhas restantes, para que, exceto na primeira entrada, cada uma das primeiras colunas contenha valores idênticos e pela observação de Tsuyoshi no comentário, isso fornece um conjunto de linhas que satisfazem sua condição.n { 1 , 2 , , n } k - 1 n k - 11n{1,2,,n}k1nk1

Agora, se você tiver um conjunto de linhas de comprimento com cada par de linhas contendo todos os pares ordenados em cada coluna, isso será equivalente a um conjunto de quadrados latinos ortogonais . Cada uma das linhas , , , fornece um quadrado latino. Para obter o quadrado latino associado à linha , coloque o valor na ésima coluna da linha na célula cujas coordenadas são dadas pelo par ordenado na ésima coluna nas duas primeiras linhas.n 2 k - 2 3 4 k j i j ikn2k2 34kjiji

Se não é uma potência primária, quantos quadrados latinos mutuamente ortogonais de ordem existem é um famoso problema em aberto, e não acredito que se saiba que existe um conjunto de quadrados latinos ortogonais para não uma potência primária; o consenso geral é que tais conjuntos não existem. O único resultado comprovado até agora é que esse conjunto não existe para . O que se sabe é que o número de linhas possíveis cresce pelo menos como para alguns . Acredito que ainda existam 8 quadrados latinos ortogonais da ordem 10. (Sabe-se que não existem 9, mas devido à possível diferença den n - 2 n n = 6 k k = Ω ( n c ) c 1nnn2nn=6kk=Ω(nc)c1 na resposta às duas perguntas, isso não nos diz nada sobre o problema original.)

Para , o máximo de você pode obter é 3, e você pode obter três linhas para o problema (1) olhando para qualquer quadrado latino com uma transversal, da qual existem muitas variáveis ​​não equivalentes exemplos. Para , existem construções conhecidas que dão dois quadrados latinos ortogonais. Se esses quadrados têm uma transversal comum, então você pode obter para o problema (1).k 6 × 6 n = 10 k = 4n=6k6×6n=10k=4

Peter Shor
fonte
n2nn1nnn1n=6
Esta é uma conexão muito agradável. Obrigado pela resposta! Um ponto secundário: de acordo com a Wikipedia, sabe-se que n-1 quadrados latinos ortogonais existem para n potência principal, não apenas para n-prime.
Tsuyoshi Ito
@Tsuyoshi - Opa. Eu sabia; Eu apenas disse errado. A construção vem de campos finitos. Obrigado pela correção. Corrigindo agora.
Peter Shor
Calculei que sim. :)
Tsuyoshi Ito
11

Esta é uma solução parcial. Essa matriz existe se n for uma potência primária.

Seja F o campo finito da ordem n . Construímos uma matriz n × n ( n -1) cujas linhas são rotuladas por F , cujas colunas são rotuladas por ( F ∖ {0}) × F e cujas entradas estão em F da seguinte maneira: a i -ésima linha da a coluna rotulada ( a , b ) é dada por ai + b . Em outras palavras, cada coluna corresponde a um grau polinomial-ona em F . Então cada coluna contém cada elemento de F exatamente uma vez e duas colunas não têm entradas iguais em mais de uma linha, porque os valores de dois polinômios distintos de grau um podem coincidir no máximo em um ponto.

(Se você deseja uma matriz cujas entradas estão em {1,…, n } em vez de em F , substitua os elementos de F por {1,…, n } arbitrariamente.)

Tsuyoshi Ito
fonte
n+1
@ Artigo: Pode haver, especialmente dada a resposta de Pedro, conectando essa questão a quadrados latinos ortogonais. (Disclaimer: na minha opinião não-especialista, quadrados ortogonais Latina, MUBS, desenhos combinatórios, projetos unitários e SIC-POVMs são quase indistinguíveis.)
Tsuyoshi Ito
Muito obrigado, Ito! Este design parece realmente bonito!
Cyker