Символ Леви-Чивиты и Чётность перестановок (алгоритмическое определение)
Алгоритмическое определение Символа Леви-Чивиты и Чётности перестановок
Классические определения
Символ Леви-Чивиты (Тензор Леви-Чивиты, W)
может быть обобщён на любое количество измерений — $n > 1$,
если пользоваться определением через чётность перестановок (W) индексов.
В правом базисе такое обобщение примет вид:
${\varepsilon_{ijkl\dots} =
\begin{cases}
+\sqrt{g}, & \mbox{if }(i, j, k, l, \dots) \mbox{ is an even permutation of } (1, 2, 3, 4, \dots), \\
-\sqrt{g}, & \mbox{if }(i, j, k, l, \dots) \mbox{ is an odd permutation of } (1, 2, 3, 4, \dots), \\
0, & \mbox{otherwise}
\end{cases},}$
То есть,
в случае, когда индексы принимают значения, реализующие перестановку набора
$(1, 2, 3, \dots, n)$,
он равен знаку перестановки,
умноженному на корень из определителя метрики (W) —
$\ \sqrt{g} = \sqrt{det\{g_{ij}\}},$
а в остальных случаях ноль.
При единичном определении метрики отображение вырождается и принимет следующий вид:
${\varepsilon_{ijkl\dots} =
\begin{cases}
+1, & \mbox{if }(i, j, k, l, \dots) \mbox{ is an even permutation of } (1, 2, 3, 4, \dots), \\
-1, & \mbox{if }(i, j, k, l, \dots) \mbox{ is an odd permutation of } (1, 2, 3, 4, \dots), \\
0, & \mbox{otherwise}
\end{cases}}$
Другими словами, символ Леви-Чивиты в правом базисе с единичным определителем метрики равен 1, если перестановка чётна, -1, если перестановка нечётная и 0 в других случаях (индексы равны).
Например, для трёхмерного пространства, получим:
${\varepsilon_{ijk} =
\begin{cases}
+1 & \mbox{if } (i, j, k) \mbox{ is } (1, 2, 3) \mbox{ or } (3, 1, 2) \mbox{ or } (2, 3, 1), \\
-1 & \mbox{if } (i, j, k) \mbox{ is } (1, 3, 2) \mbox{ or } (3, 2, 1) \mbox{ or } (2, 1, 3), \\
0 & \mbox{if } i = j \mbox{ or } j = k \mbox{ or } k = i
\end{cases}}$
Знак перестановки вводится в комбинаторике формулой:
${sgn(\sigma)=(-1)^{N(\sigma)},}$
где $N(\sigma)$ — число инверсий в $\sigma$.
Алгебраические обобщения для символа Леви-Чивиты выглядят как:
где $n$ — размерность пространства, а $G(n)$ — G-функция Барнса
(W).
Проблемы классического определения
Комбинаторное определение символа Леви-Чивиты удобно для понимания, алгебраическое — для формализации и математического анализа.
Но ни то ни другое не подходит для прямой алгоритмической реализации при больших размерностях пространства.
Комбинаторное определение вводит символ Леви-Чивиты через решение задачи, с NP-классом вычислительной сложности
(W)
, так как число перестановок равняется $P_n=A_n^n=n!=1\cdot 2\cdot\dots\cdot n.$
Формальное алгебраическое определение предлагает произвести соизмеримое число произведений.
Другие существующие определения (например, через матрицы) также приводят, как минимум, к высокой вычисличесной сложности и заметному использованию памяти.
Алгоритмическое определение
Нетрудно заметить, что при единичном определении метрики вычисление произведений не требуется. Достаточно всего лишь следить за знаком при каждой инверсии.
С учётом данного факта, алгоритм функции, реализующей символ Леви-Чивиты для $n$-мерного пространства ($n > 1$) в правом базисе с единичным определителем метрики будет выглядеть так (C#):
Причём, данный алгоритм может быть применён для любого упорядоченного множества, на котором определён оператор сравнения.
В последнем случае он будет показывать знак перестановки вводимого множества относительно упорядоченного по возрастанию множества тех же элементов.
