Частичный определитель

[0101]

A - квадратная матрица NxN
$A=\left(\begin{array}{ccccccc} a_{000}& a_{013} &a_{022}&a_{031}\\ a_{101}& a_{110} &a_{123}&a_{132}\\ a_{202}& a_{211} &a_{220}&a_{233}\\ a_{303}& a_{312} &a_{321}&a_{330} \end{array}\right)$
В матрице А к каждому элементу добавлен третий дополнительный индекс. Столбец из третьих индексов получается путем циклического сдвига вниз столбца первых индексов на величину индекса столбца.
"Частичный" определитель detp(A) получается путем исключения из "классического" определителя det(A) произведений, содержащих одинаковые третьи индексы.
$ detp(A)=a_{303} \,detp \left(\begin{array}{ccccccc} 0 &a_{022}&a_{031}\\ a_{110} &0&a_{132}\\ a_{211} &a_{220}&0 \end{array}\right)+a_{312}\, detp \left(\begin{array}{ccccccc} a_{000}& 0&a_{031}\\ a_{101}& a_{123}&0\\ 0&a_{220}&a_{233} \end{array}\right)+a_{321}\, detp \left(\begin{array}{ccccccc} a_{000}& a_{013} &0\\ 0& a_{110} &a_{132}\\ a_{202}& 0&a_{233} \end{array}\right)+a_{330}\, detp \left(\begin{array}{ccccccc} 0& a_{013} &a_{022}\\ a_{101}& 0 &a_{123}\\ a_{202}& a_{211} &0 \end{array}\right)$ .
И т.д.
"Классический" определитель можно посчитать методом Гаусса с вычислительной сложностью $ О(N^3)$. Нужно оценить вычислительную сложность "частичного" определителя.
Есть подозрение, что вычислительная сложность не полиномиальная, идеи решения иссякли.

-- Ср апр 25, 2018 20:10:23 --

Цитата:

"Частичный" определитель detp(A) получается путем исключения из "классического" определителя det(A) произведений, содержащих одинаковые третьи индексы.

"Частичный" определитель detp(A) получается путем исключения из "классического" определителя det(A) произведений, содержащих элементы с одинаковыми третьими индексами.

[0101]

Если N четное, то "частичный" определитель равен 0.

[0101]

Несколько "грубоватое" решение может быть получено с использованием идеи циркулянта https://ru.wikipedia.org/wiki/%D0%A6%D0%B8%D1%80%D0%BA%D1%83%D0%BB%D1%8F%D0%BD%D1%82. Можно домножить элементы матрицы на соответствующие первообразные корни из единицы, и в полученном определителе отбросить произведения, все еще содержащие первообразные корни из единиц, тогда почти получим искомое.
$A=\left(\begin{array}{ccccccc} (-1)^\frac{1}{5}a_{000}&\; (-1)^\frac{2}{5}a_{014} &\;(-1)^\frac{3}{5}a_{023}&\;(-1)^\frac{4}{5}a_{032}&\;a_{041}\\ (-1)^\frac{2}{5}a_{101}&\; (-1)^\frac{4}{5}a_{110} &\;(-1)^\frac{1}{5}a_{123}&\;(-1)^\frac{3}{5}a_{133}&\;a_{142}\\ (-1)^\frac{3}{5}a_{202}&\; (-1)^\frac{1}{5}a_{211} &\;(-1)^\frac{4}{5}a_{220}&\;(-1)^\frac{2}{5}a_{234}&\;a_{243}\\ (-1)^\frac{4}{5}a_{303}&\; (-1)^\frac{3}{5}a_{312} &\;(-1)^\frac{2}{5}a_{321}&\;(-1)^\frac{1}{5}a_{330}&\;a_{344}\\ a_{404}&\; a_{413} &\;a_{422}&\;a_{431}&\;a_{440} \end{array}\right)$
Но, если элементы некоторые столбцов заменить единицами и не обнулять такие элементы в процессе вычисления (при этом станет больше произведений, не содержащих одинаковые третьи индексы),
например
$A=\left(\begin{array}{ccccccc} (-1)^\frac{1}{5}a_{000}&\; (-1)^\frac{2}{5}a_{014} &\;(-1)^\frac{3}{5}1&\;(-1)^\frac{4}{5}a_{032}&\;a_{041}\\ (-1)^\frac{2}{5}a_{101}&\; (-1)^\frac{4}{5}a_{110} &\;(-1)^\frac{1}{5}1&\;(-1)^\frac{3}{5}a_{133}&\;a_{142}\\ (-1)^\frac{3}{5}a_{202}&\; (-1)^\frac{1}{5}a_{211} &\;(-1)^\frac{4}{5}1&\;(-1)^\frac{2}{5}a_{234}&\;a_{243}\\ (-1)^\frac{4}{5}a_{303}&\; (-1)^\frac{3}{5}a_{312} &\;(-1)^\frac{2}{5}1&\;(-1)^\frac{1}{5}a_{330}&\;a_{344}\\ a_{404}&\; a_{413} &\;1&\;a_{431}&\;a_{440} \end{array}\right)$
то нужно что-то еще.

[0101]

Другая задача, родственная вышеупомянутым.
A - прямоугольная матрица M х N, $M\ne N$
Нужно оценить сложность вычисления выражения, содержащего все произведения из элементов различных строк и столбцов матрицы А. Знаки произведений произвольны, их можно выбрать из соображений уменьшения сложности вычисления.