Выражение определителя как постоянного

Одной из основных проблем в TCS является проблема выражения перманента в качестве детерминанта. Я читал статью Агравала « Детерминант против перманента», и в одном абзаце он утверждает, что обратная проблема проста.

Легко видеть , что определитель матрицы может быть выражен как перманент соответствующей матрицы элементы s и который имеет размер (настройки записи Х такое , что Det Det и продукт , соответствующий каждой перестановки , которая имеет четное цикл равен нулю). $X$ $Xˆ$ $x_{i,j}$ $O(n)$ $Xˆ$ $X$

Прежде всего, я не думаю, что 0, 1 и переменных достаточно, потому что мы пропустили бы отрицательные члены. Но даже если бы мы допустили переменные -1 и , я не понимаю, почему увеличение размера можно сделать линейным. Может ли кто-нибудь объяснить мне конструкцию? $x_{i,j}$ $-x_{i,j}$

cc.complexity-theory algebraic-complexity permanent determinant Farnak
источник

x_{i j} s

$x_{ij} s$

x_{i j}

$x_{ij}$

s = \pm 1

$s = \pm 1$

@ GeoffreyIrving, эта интерпретация мне не кажется правильной ... насколько я могу судить, "s" набирается в текстовом режиме, а не в математическом режиме; «s» никогда не определяется как переменная; и "s" не индексируется ничем. Я думаю, что это просто указывает на множественное число.

усуль

x_{i j}

$x_{ij}$

Я должен указать, что отрицательные члены, связанные со знаком перестановки, рассматриваются в его комментарии, в котором говорится, что вы настроили матрицу так, чтобы члены, связанные с четными циклами, сводились к нулю.

Суреш Венкат

@SureshVenkat: Это звучит легче сказать, чем сделать (по крайней мере, для меня). Не могли бы вы продемонстрировать это, скажем, на матрице 4х4?

Фарнак

Выражение определителя как постоянного

Ответы: