Determinante als permanent ausdrücken

Ein Hauptproblem bei TCS ist das Problem, eine bleibende Karte als Determinante auszudrücken. Ich habe Agrawals Artikel Determinant Versus Permanent gelesen und in einem Absatz behauptet er, das umgekehrte Problem sei einfach.

Es ist leicht zu erkennen, dass die Determinante einer Matrix als die bleibende Zahl einer verwandten Matrix ausgedrückt werden kann, deren Einträge 0, 1 oder s sind und die die Größe (aufgebaut) hat Einträge von Xˆ, so dass det = det und das Produkt, das jeder Permutation mit einem geraden Zyklus entspricht, Null ist). $X$ $Xˆ$ $x_{i,j}$ $O(n)$ $Xˆ$ $X$

Erstens glaube ich nicht, dass die Variablen 0, 1 und ausreichen, da uns negative Ausdrücke fehlen würden. Aber selbst wenn wir die Variablen -1 und , verstehe ich nicht, warum das Größenwachstum linear gemacht werden kann. Könnte mir bitte jemand den Aufbau erklären? $x_{i,j}$ $-x_{i,j}$

cc.complexity-theory algebraic-complexity permanent determinant Farnak
quelle

Beachten Sie, dass er

sagt , nicht

liefert die notwendigen Vorzeichen.

x_{i j} s

$x_{ij} s$

x_{i j}

$x_{ij}$

s = \pm 1

$s = \pm 1$

Geoffrey Irving

@GeoffreyIrving, diese Interpretation scheint mir nicht richtig zu sein ... Soweit ich das beurteilen kann, ist "s" im Textmodus und nicht im Mathematikmodus gesetzt. "s" wird niemals als Variable definiert; und "s" wird von nichts indiziert. Ich denke, es gibt nur den Plural an.

usul

Ich denke, @usul ist richtig. er benutzt das 's' als Plural (dh viele

x_{i j}

$x_{ij}$

Suresh Venkat

Ich möchte darauf hinweisen, dass die negativen Terme, die mit dem Vorzeichen der Permutation verbunden sind, in seinem Kommentar behandelt werden, der besagt, dass Sie die Matrix so einrichten, dass die Terme, die mit geraden Zyklen verbunden sind, auf Null reduziert werden.

Suresh Venkat

@SureshVenkat: Das klingt leichter gesagt als getan (zumindest für mich). Könnten Sie dies bitte an einer 4x4-Matrix demonstrieren?

Farnak

Determinante als permanent ausdrücken

Antworten: