Stała macierzy i z wyznaczników

Niech będzie macierzą lub z wpisami . Czy ktoś może mi dostarczyć macierz , aby ? Jaki jest najmniejszy znany jawny , taki że ? Wszelkie odniesienia do tego z wyraźnymi przykładami? $A$ $3 \times 3$ $4 \times 4$ $a_{ij}$ $B$ $\operatorname{per}(A) = \det(B)$ $B$ $\operatorname{per}(A) = \det(B)$

Niektóre ograniczenia mogą być następujące przypadki:

Przypadek $(1)$ Tylko liniowy Funkcjonały są dopuszczone jako wpisów $B$ .

Przypadek $(2)$ Funkcjonały nieliniowe są dozwolone pod warunkiem, że każdy termin ma stopień $O(log(n))$ stopień (stopień jest sumą stopnia zmiennych), gdzie $n$ jest rozmiarem stosowanej macierzy. W naszym przypadku do stopnia $2$ .

cc.complexity-theory algebraic-complexity permanent

— vs
źródło

@vs Jakie są ograniczenia dotyczące ? Jeśli nie ma, to nazwa to macierz z nazwa , ale Zgaduję, że nie o to ci chodziło. Typowo umożliwia wpisy być afiniczne funkcje liniowe zmiennych .

B

$B$

b = (\begin{matrix} za (ZA) \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

[EDYTOWAĆ]

Dla spójności zmieniłem notacje z na . $c(n)$ $dc(n)$
W komentarzach pytano vs, czy moja odpowiedź uogólnia na wyższe wymiary. Robi i daje górną granicę nad dowolnym polem: Zobacz mój projekt na ten temat: Górna granica dla problemu trwałego kontra determinującego . $d c (n) \leq 2^{n} - 1.$ $dc(n)\le 2^n-1.$

[/EDYTOWAĆ]

[Dodatkowy komentarz: Myślę, że możesz edytować poprzednie pytanie zamiast tworzyć nowe.]

Mam dla ciebie następującą odpowiedź:

za (\begin{matrix} za & b & do \\ re & mi & fa \\ sol & h & ja \end{matrix}) = det (\begin{matrix} 0 & za & re & sol & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & ja & fa & 0 \\ 0 & 0 & 1 & 0 & 0 & do & ja \\ 0 & 0 & 0 & 1 & do & 0 & fa \\ mi & 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}$

Zauważ, że szukając takich odniesień do wyraźnych przykładów, nie mogłem znaleźć żadnego, dlatego przykład, który ci daję, jest przykładem, który zbudowałem.

To pytanie, które zadajesz, jest powszechnie nazywane „problemem stałym a determinującym”. Niech dana e matrycy i chcemy najmniejszą macierzy tak, że . Oznaczmy przez do wymiarów najmniejszych taki . Oto historyczne wyniki: $(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 i Ressayre 2004] 2/2 w charakterystyce $dc(n)\ge n^2/2$ $0$
[Cai, Chen i Li 2008] w charakterystycznym . $dc(n)\ge n^2/2$ $\neq 2$

To pokazuje, że (górna granica to matryca podana powyżej). $5\le dc(3)\le 7$

Ponieważ jestem leniwy, podaję tylko jedno odniesienie, w którym możesz znaleźć inne. Jest to najnowszy cytowany przeze mnie artykuł Cai, Chena i Li: Kwadratowa dolna granica trwałego i determinującego problemu w stosunku do dowolnej cechy $\neq 2$ .

Jeśli czytasz francuski, możesz także zapoznać się z moimi slajdami na ten temat: Permanent kontra Déterminant .

— Bruno
źródło

Dziękuję Ci bardzo. Zapomniałem wspomnieć, że znałem liniowe i kwadratowe dolne granice. Twój przykład jest dla mnie nowy i oczywiście spojrzę na twoje Francuskie Slajdy :)

— kontra

Aby przekonwertować formułę na wyznacznik, jest to (klasyczny?) Wynik Valiant w 1979 r. Wyjaśniamy ten wynik w naszym artykule w Rozdziale 2.1 (por. [ Arxiv.org/abs/1007.3804] ).

— Bruno,

Dla

n = 3

$n=3$ , zwróć uwagę, że w O (n2 ^ n) jest stała, więc 24 nie jest prawidłową wartością. Myślę jednak, że mój przykład jest lepszy niż zwykłe zastosowanie wzoru Rysera + konstrukcji Valianta. Jest to całkiem normalne, jak można sobie wyobrazić, że przejście od stałego do formuły, a następnie powrót do wyznacznika, nie jest najlepszym sposobem. Nie powiedziałbym, że mój przykład jest „lepszy niż Rysera”, ponieważ cele nie są takie same. Zauważ też, że formuły Glynn'sor Ryser nie są tak dobre, jak banalna formuła

n = 3

$n=3$ pobili go tylko asymptotycznie.

— Bruno,

Miałem nowe spojrzenie na artykuł JY Cai. Twierdzenie 3 daje lepszą granicę:

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

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

— Bruno

@Bruno: doskonała odpowiedź!

— Dai Le