Permanent d'une matrice

$A$ $3 \times 3$ $4 \times 4$ $a_{ij}$ $B$ $\operatorname{per}(A) = \det(B)$ $B$ $\operatorname{per}(A) = \det(B)$

Certaines restrictions pourraient être les cas suivants:

Cas Seuls sont autorisés linéaire Fonctionnelles sous forme d' entrées de . $(1)$ $B$

Cas Les fonctions fonctionnelles non linéaires sont autorisées à condition que chaque terme ait au moins degré (degré est la somme du degré des variables) où est la taille de la matrice impliquée. Dans notre cas, jusqu'à degré . $(2)$ $O(log(n))$ $n$ $2$

cc.complexity-theory algebraic-complexity permanent contre
la source

@vs Quelles sont les restrictions sur ? S'il n'y en a pas, alors est une matrice avec , mais Je suppose que ce n'est pas ce que vous aviez en tête. Typiquement , on permet les entrées de soient des fonctions linéaires affines des variables dans .

B

$B$

B = (\begin{matrix} per (A) \end{matrix})

$B = \begin{pmatrix} \operatorname{per}(A)\end{pmatrix}$

1 \times 1

$1 \times 1$

det (B) = per (A)

$\det(B) = \operatorname{per}(A)$

B

$B$

A

$A$

Tyson Williams

[ÉDITER]

Par souci de cohérence, j'ai changé les notations de à . $c(n)$ $dc(n)$
Il a été demandé par vs dans les commentaires si ma réponse à généralisent dimensions supérieures. Il fait et donne une limite supérieure sur n'importe quel champ: Voir mon brouillon à ce sujet: une limite supérieure pour le problème permanent versus déterminant . $d c (n) \leq 2^{n} - 1.$ $dc(n)\le 2^n-1.$

[/ÉDITER]

[Un commentaire secondaire: je pense que vous pouvez modifier votre question précédente au lieu d'en créer une nouvelle.]

J'ai la réponse suivante pour vous:

per (\begin{matrix} a & b & c \\ d & e & f \\ g & h & i \end{matrix}) = det (\begin{matrix} 0 & a & d & g & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & i & f & 0 \\ 0 & 0 & 1 & 0 & 0 & c & i \\ 0 & 0 & 0 & 1 & c & 0 & f \\ e & 0 & 0 & 0 & 1 & 0 & 0 \\ h & 0 & 0 & 0 & 0 & 1 & 0 \\ b & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix})

$\operatorname{per}\begin{pmatrix} a&b&c\\d&e&f\\g&h&i\end{pmatrix}= \det\begin{pmatrix} 0 & a & d & g & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & i & f & 0 \\ 0 & 0 & 1 & 0 & 0 & c & i \\ 0 & 0 & 0 & 1 & c & 0 & f \\ e & 0 & 0 & 0 & 1 & 0 & 0 \\ h & 0 & 0 & 0 & 0 & 1 & 0 \\ b & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$

Notez que la recherche de telles références sur des exemples explicites, je n'ai pas pu en trouver et donc l'exemple que je vous donne est un exemple que j'ai construit.

Cette question que vous posez est communément appelée le "problème permanent vs déterminant". Supposons que nous sommes donné un matrice , et nous voulons la plus petite matrice telle que . Appelons les dimensions du plus petit comme . Voici les résultats historiques: $(n\times n)$ $A$ $B$ $\operatorname{per} A=\det B$ $dc(n)$ $B$

[Szegö 1913] $dc(n)\ge n+1$
[von zur Gathen 1986] $dc(n)\ge n\sqrt 2-6\sqrt n$
[Cai 1990] $dc(n)\ge n\sqrt 2$
[Mignon & Ressayre 2004] dans la caractéristique $dc(n)\ge n^2/2$ $0$
[Cai, Chen & Li 2008] dans la caractéristique . $dc(n)\ge n^2/2$ $\neq 2$

Cela montre que (la borne supérieure est la matrice donnée ci-dessus). $5\le dc(3)\le 7$

Comme je suis paresseux, je vous donne juste une référence où vous pouvez trouver les autres. C'est le document le plus récent que j'ai cité, par Cai, Chen et Li: Une borne inférieure quadratique pour le problème permanent et déterminant sur toute caractéristique $\neq 2$ .

Si vous lisez le français, vous pouvez également consulter mes diapositives sur ce sujet: Permanent versus Déterminant .

Bruno
la source

Merci beaucoup. J'ai oublié de mentionner que je connaissais les bornes inférieures linéaires et quadratiques. Votre exemple est nouveau pour moi et bien sûr je vais regarder vos diapositives en français :)

Pour convertir une formule en déterminant, c'est un résultat (classique?) De Valiant en 1979. Nous expliquons ce résultat dans notre article à la section 2.1 (cf. [ arxiv.org/abs/1007.3804] ).

Bruno

Pour , notez qu'il existe une constante dans O (n2 ^ n) de sorte que 24 n'est pas la bonne valeur. Pourtant, je pense que mon exemple est meilleur que d'appliquer simplement la formule de Ryser + la construction de Valiant. C'est tout à fait normal car on peut imaginer que passer du permanent à une formule puis revenir à un déterminant n'est pas la meilleure façon de le faire. Je ne dirais pas que mon exemple est "meilleur que celui de Ryser" car les objectifs ne sont pas les mêmes. Notez également que les formules de Glynn ou de Ryser ne sont pas aussi bonnes que la formule triviale pour , elles la battent asymptotiquement uniquement.

n = 3

$n=3$

n = 3

$n=3$

Bruno

J'ai revu le papier de JY Cai. Le théorème 3 donne une meilleure borne: .

c (n) \leq O (2^{n})

$c(n)\le O(2^n)$

Bruno

@Bruno: excellente réponse!

Dai Le

Permanent d'une matrice

Réponses: