Permanen dari

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

Beberapa batasan dapat berupa kasus-kasus berikut:

Kasus $(1)$ Hanya linear functionals diperbolehkan sebagai entri $B$ .

Kasus $(2)$ Fungsional non-linier diizinkan asalkan setiap istilah memiliki tingkat paling tinggi $O(log(n))$ (derajat adalah jumlah dari derajat variabel) di mana $n$ adalah ukuran dari matriks yang terlibat. Dalam kasus kami, hingga derajat $2$ .

cc.complexity-theory algebraic-complexity permanent vs.
sumber

@vs Apa batasan ? Jika tidak ada, maka adalah matriks

dengan

, tetapi Saya menduga itu bukan yang Anda pikirkan. Biasanya satu memungkinkan entri dari

menjadi fungsi linear affine dari variabel dalam

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

[EDIT]

Untuk konsistensi, saya mengalihkan notasi dari ke . $c(n)$ $dc(n)$
Itu ditanyakan oleh vs di komentar apakah jawaban saya menggeneralisasi ke dimensi yang lebih tinggi. Itu tidak dan memberikan batas atas bidang apa pun: Lihat draf saya tentang ini: Batas Atas untuk Masalah Permanen versus Penentu . $d c (n) \leq 2^{n} - 1.$ $dc(n)\le 2^n-1.$

[/ EDIT]

[Komentar sampingan: Saya pikir Anda dapat mengedit pertanyaan Anda sebelumnya alih-alih membuat yang baru.]

Saya punya jawaban berikut untuk Anda:

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}$

Perhatikan bahwa mencari referensi semacam itu tentang contoh eksplisit, saya tidak bisa menemukan apa pun dan dengan demikian contoh yang saya berikan adalah contoh yang saya buat.

Pertanyaan yang Anda ajukan ini biasa disebut "Masalah Permanen vs Penentu". Misalkan kita diberi matriks , dan kami ingin terkecil matriks seperti yang . Mari kita dilambangkan dengan dimensi terkecil seperti . Ini hasil sejarahnya: $(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] 2/2 dalam karakteristik $dc(n)\ge n^2/2$ $0$
[Cai, Chen & Li 2008] dalam karakteristik . $dc(n)\ge n^2/2$ $\neq 2$

Ini menunjukkan bahwa (batas atas adalah matriks yang diberikan di atas). $5\le dc(3)\le 7$

Karena saya malas, saya hanya memberi Anda satu referensi di mana Anda dapat menemukan yang lain. Ini adalah makalah terbaru yang saya kutip, oleh Cai, Chen dan Li: Batas bawah kuadratik untuk masalah permanen dan determinan atas setiap karakteristik $\neq 2$ .

Jika Anda membaca bahasa Prancis, Anda juga dapat melihat slide saya tentang subjek ini: Permanen versus Déterminant .

Bruno
sumber

Terima kasih banyak. Saya lupa menyebutkan bahwa saya akrab dengan batas bawah linier dan kuadratik. Contoh Anda baru bagi saya dan tentu saja saya akan melihat Slide Prancis Anda :)

Untuk mengubah rumus menjadi penentu, itu adalah hasil (klasik?) Oleh Valiant pada tahun 1979. Kami menjelaskan hasil ini dalam makalah kami di Bagian 2.1 (lih [ arxiv.org/abs/1007.3804] ).

Bruno

Untuk , perhatikan bahwa ada konstanta dalam O (n2 ^ n) sehingga 24 bukan nilai yang benar. Namun saya berpikir bahwa contoh saya lebih baik daripada hanya menerapkan formula Ryser + konstruksi Valiant. Ini cukup normal karena dapat dibayangkan bahwa beralih dari formula permanen ke formula dan kemudian kembali ke determinan bukan cara terbaik untuk melakukannya. Saya tidak akan mengatakan contoh saya "lebih baik daripada Ryser" karena tujuannya tidak sama. Perhatikan juga bahwa rumus Glynn's atau Ryser tidak sebagus rumus trivial untuk , mereka mengalahkannya hanya secara asimptotik.

n = 3

$n=3$

n = 3

$n=3$

Bruno

Saya melihat kertas JY Cai baru. Teorema 3 memberikan batas yang lebih baik: .

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

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

Bruno

@ Bruno: jawaban yang bagus!

Dai Le

Permanen dari

Jawaban: