Permanente de uma matriz

9

Seja uma matriz ou com entradas . Alguém pode me fornecer uma matriz para que ? Qual é o menor B explícito conhecido como \ nome do operador {por} (A) = \ det (B) ? Alguma referência nisso com exemplos explícitos?3 × 3 4 × 4 a i j B per ( A ) = det ( B ) B per ( A ) = det ( B )A3×34×4aijBper(A)=det(B)Bper(A)=det(B)

Algumas restrições podem ser os seguintes casos:

Capa Apenas linear funcionais são permitidos como entradas de .B(1)B

Caso (2) Funcionais não lineares são permitidos, desde que cada termo tenha no máximo O(log(n)) grau (grau é a soma do grau de variáveis) em que n é o tamanho da matriz envolvida. No nosso caso, até o grau 2 .

vs
fonte
2
@vs Quais são as restrições em ? Se não houver, então é uma matriz com , mas Estou supondo que não é isso que você tinha em mente. Tipicamente um permite que as entradas de ser lineares funções afins das variáveis em . B = ( por ( A ) ) 1 × 1 det ( B ) = por ( A ) B AB
B=(per(A))
1×1det(B)=per(A)BA
Tyson Williams

Respostas:

18

[EDITAR]

  1. Por consistência, troquei as notações de para .d c ( n )c(n)dc(n)
  2. Foi perguntado por vs nos comentários se minha resposta generaliza para dimensões mais altas. Ele cria e fornece um limite superior sobre qualquer campo: Veja meu rascunho sobre isso: um limite superior para o problema permanente versus determinante .
    dc(n)2n1.

[/EDITAR]

[Um comentário secundário: acho que você poderia editar sua pergunta anterior em vez de criar uma nova.]

Tenho a seguinte resposta para você:

per(abcdefghi)=det(0adg0000100if000100ci0001c0fe000100h000010b000001)

Observe que, procurando essas referências sobre exemplos explícitos, não consegui encontrar nenhum e, portanto, o exemplo que dou é um exemplo que eu criei.

Esta pergunta que você está fazendo é comumente chamada de "Problema permanente versus determinante". Suponha-se que tenham a da matriz , e que quer a menor matriz de tal modo que . Denotemos por as dimensões do menor tal . Aqui estão os resultados históricos:A B por A = det B(n×n)ABperA=detBdc(n)B

  • [Szegö 1913]dc(n)n+1
  • [von zur Gathen 1986]dc(n)n26n
  • [Cai 1990]dc(n)n2
  • [Mignon & Ressayre 2004] 2/2 na característicadc(n)n2/20
  • [Cai, Chen & Li 2008] na característica .dc(n)n2/22

Isso mostra que (o limite superior é a matriz dada acima).5dc(3)7

Como sou preguiçoso, apenas lhe dou uma referência onde você pode encontrar as outras. É o artigo mais recente que citei, por Cai, Chen e Li: Um limite inferior quadrático para o problema permanente e determinante sobre qualquer característica2 .

Se você lê francês, também pode dar uma olhada nos meus slides sobre este assunto: Permanente versus Déterminant .

Bruno
fonte
Muito obrigado. Esqueci de mencionar que estava familiarizado com os limites inferiores lineares e quadráticos. Seu exemplo é novo para mim e, é claro, examinarei seus slides franceses :)
vs
11
Para converter uma fórmula em um determinante, é um resultado (clássico?) De Valiant em 1979. Explicamos esse resultado em nosso artigo na Seção 2.1 (cf [ arxiv.org/abs/1007.3804] ).
1155 Bruno Bruno
2
Para , observe que há uma constante em O (n2 ^ n) para que 24 não seja o valor correto. No entanto, acho que meu exemplo é melhor do que simplesmente aplicar a fórmula de Ryser + a construção de Valiant. Isso é bastante normal, como se pode imaginar que ir da permanente para a fórmula e depois voltar para o determinante não é a melhor maneira de fazer. Eu não diria que meu exemplo é "melhor que o de Ryser", pois os objetivos não são os mesmos. Observe também que as fórmulas de Glynn's ou Ryser não são tão boas quanto a fórmula trivial para ; elas as vencem apenas assintoticamente. n=3n=3
de Bruno
2
Eu dei uma nova olhada no trabalho de JY Cai. O teorema 3 fornece um limite melhor: . c(n)O(2n)
Bruno
2
@ Bruno: excelente resposta!
Dai Le