Программирование, 2023, № 1, стр. 38-47

1. ВВЕДЕНИЕ

Напомним, что матрица называется унимодулярной, если она квадратная, все ее элементы – целые числа и ее определитель равен ±1. Ее обратная матрица также унимодулярна.

Будем векторы обозначать как векторы-строки: $X = ({{x}_{1}}, \ldots ,{{x}_{n}})$. $\left[ x \right]$ – это целая часть вещественного числа x.

Задача 1. Пусть в n-мерном вещественном пространстве ${{\mathbb{R}}^{n}}$ задано m, $(m < n)$ целочисленных векторов ${{A}_{1}}, \ldots ,{{A}_{m}}$. Их линейная оболочка

образует линейное подпространство в ${{\mathbb{R}}^{n}}$. Требуется вычислить такую унимодулярную матрицу α, что преобразование переводит подпространство L в координатное подпространство где $l = {\text{dim}}L$.

Здесь указан алгоритм решения этой задачи, и составлена программа его реализующая. Это некоторое обобщение алгоритма цепной дроби [1], который напоминается в разделе 2. В разделе 3 описан алгоритм Эйлера [2], который обобщает алгоритм Евклида (т.е. цепной дроби) на n-мерный целочисленный вектор. В разделе 4 дается решение задачи 1, а в разделах 5, 6 – программы, соответствующие разделам 2, 3, 4. В разделе 7 рассмотрены степенные преобразования. Для вычисления их унимодулярных матриц развиты все эти алгоритмы и программы.

2. АЛГОРИТМ ЕВКЛИДА И ЦЕПНАЯ ДРОБЬ

Задача 2. Пусть заданы 2 целых положительных числа a₁ и a₂. Надо найти их наибольший общий делитель (НОД).

Для этого используется алгоритм Евклида. Пусть ${{a}_{1}} \geqslant {{a}_{2}}$; делим a₁ на a₂ с остатком:

где ${{b}_{1}} = [{{a}_{1}}{\text{/}}{{a}_{2}}]$ и ${{a}_{3}}$ – целые числа, $0 \leqslant {{a}_{3}} < {{a}_{2}}$. Если ${{a}_{3}} = 0$, то НОД равен ${{a}_{2}}$. Если ${{a}_{3}} \ne 0\;$, то делим с остатком ${{a}_{2}}$ на ${{a}_{3}}$: где ${{b}_{2}} = [{{a}_{2}}{\text{/}}{{a}_{3}}]$ и где $0 \leqslant {{a}_{4}} < {{a}_{3}}$. Если ${{a}_{4}} = 0$, то НОД равен a₃. Если ${{a}_{4}} \ne 0$, то продолжаем процедуру, пока не получим нулевой остаток ${{a}_{{k + 1}}} = 0$.

Тогда НОД – это a_k. Эту процедуру можно записать в виде цепной дроби

Она применима к любому вещественному числу β и дает, вообще говоря, бесконечное разложение. Только для рациональных чисел $\beta = {{a}_{1}}{\text{/}}{{a}_{2}}$ оно конечно. Для квадратичных иррациональностей β оно периодично [1]. Если в цепной дроби (2.3) отбросить окончание, начинающееся с ${{b}_{{l + 1}}}$, и свернуть полученную цепную дробь в рациональное число, то оно называется подходящей дробью.

Задача 3. Пусть заданы 2 целых положительных числа a₁ и a₂. Надо вычислить такую унимодулярную матрицу α, что $\left( {{{a}_{1}},{{a}_{2}}} \right)\alpha = ({{a}_{k}},0)$ или (0, a_k), где целое число ${{a}_{k}} > 0$.

Деление с остатком (2.1) можно записать в виде умножения на матрицу $\left( {{{a}_{1}},{{a}_{2}}} \right)\left( {\begin{array}{*{20}{c}} 1&0 \\ { - {{b}_{1}}}&1 \end{array}} \right) = ({{a}_{3}},{{a}_{2}})$ или $\left( {{{a}_{1}},{{a}_{2}}} \right){{\beta }_{1}} = \left( {{{a}_{3}},{{a}_{2}}} \right)$, где ${{\beta }_{1}} = \left( {\begin{array}{*{20}{c}} 1&0 \\ { - {{b}_{1}}}&1 \end{array}} \right)$, а деление с остатком (2.2) есть $\left( {{{a}_{3}},{{a}_{2}}} \right)\left( {\begin{array}{*{20}{c}} 1&{ - {{b}_{2}}} \\ 0&1 \end{array}} \right) = ({{a}_{3}},{{a}_{4}})$ или $\left( {{{a}_{3}},{{a}_{2}}} \right){{\beta }_{2}} = \left( {{{a}_{3}},{{a}_{4}}} \right)$, где ${{\beta }_{2}} = \left( {\begin{array}{*{20}{c}} 1&{ - {{b}_{2}}} \\ 0&1 \end{array}} \right)$. Последний шаг алгоритма Евклида есть либо

либо

Поэтому искомая матрица

где если  j нечетно, если  j четно.

Поскольку все матрицы ${{\beta }_{j}}$ унимодулярны, то их произведение α также унимодулярная матрица. Она дает решение задачи 3.

Отметим, что

и согласно (2.4) и (2.5) $\beta _{j}^{{ - 1}} = \left( {\begin{array}{*{20}{c}} 1&0 \\ {{{b}_{j}}}&1 \end{array}} \right)$ или $\left( {\begin{array}{*{20}{c}} 1&{{{b}_{j}}} \\ 0&1 \end{array}} \right)$, т.е. содержит неотрицательные элементы. Поэтому в матрице α^–1 все элементы неотрицательны.

Пример 1. Пусть ${{a}_{1}}$ = 17, ${{a}_{2}}$ = 5. Тогда ${{b}_{1}} = [17{\text{/}}5]$ = 3, ${{a}_{3}} = 2$, ${{\alpha }_{1}} = \left( {\begin{array}{*{20}{c}} 1&0 \\ { - 3}&1 \end{array}} \right)$,

Матрица $\alpha = {{\alpha }_{1}}{{\alpha }_{2}}{{\alpha }_{3}}$ = $\left( {\begin{array}{*{20}{c}} 1&0 \\ { - 3}&1 \end{array}} \right)\left( {\begin{array}{*{20}{c}} 1&{ - 2} \\ 0&1 \end{array}} \right)\left( {\begin{array}{*{20}{c}} 1&0 \\ { - 2}&1 \end{array}} \right)$ = = $\left( {\begin{array}{*{20}{c}} 5&{ - 2} \\ { - 17}&7 \end{array}} \right)$.

Раскладывая в цепную дробь

получим, что последняя подходящая дробь – это $3 + 1{\text{/}}2 = 7{\text{/}}2$. Поэтому в матрице α второй столбец состоит из –2, 7.

Здесь было предложено решение задачи 3 для ${{a}_{1}}$, ${{a}_{2}} > 0$. Если ${{a}_{1}}$, ${{a}_{2}} < 0$, то надо взять матрицу α для вектора $\left( { - {{a}_{1}}, - {{a}_{2}}} \right).$ Если ${{a}_{1}} \cdot {{a}_{2}} < 0$, то надо взять матрицу $\alpha = \left( {\begin{array}{*{20}{c}} {{{\alpha }_{{11}}}}&{{{\alpha }_{{12}}}} \\ {{{\alpha }_{{21}}}}&{{{\alpha }_{{22}}}} \end{array}} \right)$ для вектора $\left( {\left| {{{a}_{1}}} \right|,\left| {{{a}_{2}}} \right|} \right)$. Тогда матрица

является унимодулярной и аннулирует одну из координат вектора $\left( {{{a}_{1}},{{a}_{2}}} \right)$.

Здесь предполагалось, что $\left| {{{a}_{1}}} \right| \geqslant \left| {{{a}_{2}}} \right|$. Если это не так, то надо предварительно сделать перестановку координат

Похожее изложение см. в п. 1.9, § 1, гл. І [3].

3. АЛГОРИТМ ЭЙЛЕРА И ОБОБЩЕНИЕ ЦЕПНОЙ ДРОБИ

Задача 4. Пусть задан n-мерный целочисленный вектор $A = ({{a}_{1}},{{a}_{2}}, \ldots ,{{a}_{n}})$. Надо найти такую n‑мерную унимодулярную матрицу $\alpha $, что вектор Aα = C = $({{c}_{1}}, \ldots ,{{c}_{n}})$ содержит только одну координату ${{c}_{n}}$, отличную от нуля.

Для ее решения Эйлер [2] предложил следующий алгоритм. Пусть для начала все координаты вектора A неотрицательны. С помощью перестановки $A{{\alpha }_{0}} = \left( {{{{\tilde {a}}}_{1}},{{{\tilde {a}}}_{2}}, \ldots ,{{{\tilde {a}}}_{n}}} \right)$ упорядочим координаты

Здесь ${{\alpha }_{0}}$ – унимодулярная матрица перестановки. Пусть ${{\tilde {a}}_{k}}$ – наименьшее из чисел ${{\tilde {a}}_{j}}$, отличное от нуля.

Пусть

При этом ${{b}_{1}} = \cdots = {{b}_{{k - 1}}} = 0$, ${{b}_{k}} = 1$. Делаем преобразование

Ему соответствует унимодулярная матрица ${{\alpha }_{1}}$, у которой на диагонали стоят единицы, в k-й строке стоят

т.е.

Теперь упорядочиваем компоненты вектора D с помощью унимодулярной матрицы-перестановки ${{\beta }_{0}}$ так, что $D{{\beta }_{0}} = \tilde {D}$ = $(0, \ldots ,0,{{\widetilde d}_{k}}, \ldots ,{{\widetilde d}_{n}})$, где ${{\widetilde d}_{j}} \leqslant {{\widetilde d}_{{j + 1}}}$.

Пусть ${{\widetilde d}_{l}}$ – наименьшее из ${{\widetilde d}_{j}}$, отличное от нуля, и ${{e}_{j}} = [{{\widetilde d}_{j}}{\text{/}}{{\widetilde d}_{l}}]$, $\;j = 1, \ldots ,l$. Делаем преобразование

и так далее. На каждом шаге максимум координат вектора убывает и является n-й координатой. Поэтому через конечное число шагов получаем вектор с одной ненулевой координатой – последней. Ее величина – это НОД всех исходных координат ${{a}_{1}}, \ldots ,{{a}_{n}}$. Каждый шаг состоит из матрицы-перестановки и треугольной матрицы с единичной диагональю:

Матрица

является решением задачи 4.

Если не все координаты a_j исходного вектора A одного знака, то сначала упорядочиваем их по модулю

и полагаем

Замечание 1. Умножая справа матрицу α на унимодулярную матрицу-перестановку, можно из вектора C получить вектор, у которого все координаты кроме одной равны нулю, а единственная ненулевая координата расположена на любом месте.

Пример 2. Пусть n = 4 и $A = \left( {5,2,4,3} \right)$. Упорядочиваем координаты вектора A: A · $\left( {\begin{array}{*{20}{c}} 0&0&0&1 \\ 1&0&0&0 \\ 0&0&1&0 \\ 0&1&0&0 \end{array}} \right) = \tilde {A}$ = = (2, 3, 4, 5), где $\left( {\begin{array}{*{20}{c}} 0&0&0&1 \\ 1&0&0&0 \\ 0&0&1&0 \\ 0&1&0&0 \end{array}} \right) = {{\alpha }_{0}}$, имеем k = 1. Получаем

Поэтому

Упорядочиваем координаты вектора D:

$D\left( {\begin{array}{*{20}{c}} 0&0&0&1 \\ 0&1&0&0 \\ 1&0&0&0 \\ 0&0&1&0 \end{array}} \right)\, = \,\left( {0,1,1,2} \right)\, = \,\tilde {D}$, где $\left( {\begin{array}{*{20}{c}} 0&0&0&1 \\ 0&1&0&0 \\ 1&0&0&0 \\ 0&0&1&0 \end{array}} \right)$ = β₀. Здесь l = 2. Получаем ${{e}_{1}} = 0$, ${{e}_{2}} = 1$, ${{e}_{3}} = 1$, ${{e}_{4}} = 2$ и ${{\beta }_{1}} = \left( {\begin{array}{*{20}{c}} 1&0&0&0 \\ 0&1&{ - 1}&{ - 2} \\ 0&0&1&0 \\ 0&0&0&1 \end{array}} \right)$.

$\tilde {D}{{\beta }_{1}} = \left( {0,1,0,0} \right)$. Наконец, ${{\gamma }_{0}} = \left( {\begin{array}{*{20}{c}} 1&0&0&0 \\ 0&0&0&1 \\ 0&1&0&0 \\ 0&0&1&0 \end{array}} \right)$ и $\tilde {D}{{\beta }_{1}}{{\gamma }_{0}} = \left( {0,0,0,1} \right)$ = C.

Здесь

Пусть заданный вектор A является нормалью к некоторому линейному многообразию. Тогда после преобразования с помощью матрицы α получим, что этот вектор содержит первые n – 1 нулевые координаты. Следовательно, все векторы исходного многообразия после преобразования будут иметь последней координатой ноль.

Алгоритм Эйлера обобщает алгоритм цепной дроби только для целочисленных векторов. Для произвольных вещественных векторов это обобщение искали все крупные математики XIX века. Но безуспешно. В [4] предложено такое обобщение цепной дроби для n-мерного вектора, которое дает последовательность наилучших приближений и периодично, если все координаты исходного вектора являются корнями многочлена степени n с целыми коэффициентами.

4. РЕШЕНИЕ ЗАДАЧИ 1

Пусть заданы целочисленные векторы

$(m < n)$ и линейное пространство (1.1).

Первым делом проверяем, что среди них нет одинаковых. Если есть, то оставляем из них только один, а остальные отбрасываем. Поэтому будем считать, что все векторы (4.1) разные. Теперь применяем алгоритм Эйлера к вектору ${{A}_{1}}$, т.е. вычисляем матрицу ${{\alpha }_{0}}$, такую, что ${{A}_{1}}{{\alpha }_{0}} = {{C}_{1}} = {{c}_{n}}{{E}_{n}}$, где c_n – целое число и ${{E}_{k}}$ – это k-й единичный вектор.

Пусть ${{A}_{j}}{{\alpha }_{0}} = {{C}_{j}} = ({{c}_{{j1}}}, \ldots ,{{c}_{{jn}}})$, $j = 2, \ldots ,m$. Полагаем $A_{j}^{1} = ({{c}_{{j1}}}, \ldots ,{{c}_{{jn - 1}}})$, $j = 2, \ldots ,m$. Применяем алгоритм Эйлера к (n – 1)-мерному вектору $A_{2}^{1}$. Получаем $A_{2}^{1}{{\alpha }_{1}} = C_{2}^{1} = (0,0, \ldots ,c_{{n - 1}}^{1})$, где ${{\alpha }_{1}}$ – это (n – 1)-мерная квадратная матрица. Пусть $A_{j}^{1}{{\alpha }_{1}}$ = = $C_{j}^{1} = (c_{{j1}}^{1}, \ldots ,c_{{jn - 1}}^{1})$, $j = 3, \ldots ,m$. Применяем алгоритм Эйлера к (n – 2)-мерному вектору $C_{3}^{1}$ и т. д. В итоге получаем последовательность матриц ${{\alpha }_{0}},{{\alpha }_{1}}, \ldots ,{{\alpha }_{{m - 1}}}$ убывающих размерностей n, n – 1, ..., $n - m + 1$. Образуем блочные квадратные матрицы ${{\beta }_{j}} = \left( {\begin{array}{*{20}{c}} {{{\alpha }_{j}}}&0 \\ 0&{{{I}_{{j + 1}}}} \end{array}} \right)$, $j = 0, \ldots ,n - m$, размерности n, где ${{I}_{{j + 1}}}$ – это единичные матрицы размерности j + 1. Положим

Тогда ${{A}_{j}}\gamma = (0,0, \ldots ,0,{{w}_{{j,n - j + 1}}}, \ldots ,{{w}_{{j,n}}}) = {{W}_{j}}$, j = = $1, \ldots ,m$. Матрица γ дает решение задачи 1.

Замечание 2. Умножая справа матрицу γ на матрицу-перестановку $\left( {\begin{array}{*{20}{c}} 0&{}&1 \\ {}& {\mathinner{\mkern2mu\raise1pt\hbox{.}\mkern2mu \raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}} &{} \\ 1&{}&0 \end{array}} \right)$, можно из набора векторов ${{W}_{1}}, \ldots ,{{W}_{m}}$ получить треугольную матрицу $U\, = \,({{u}_{{jk}}})$, $j = 1, \ldots ,m$, $k = 1, \ldots ,n$, у которой ${{u}_{{jk}}}$ = 0, если $k > j$.

Пример 3 (продолжение примера 2). Пусть $n = 4$, $m = 2$, заданы векторы ${{A}_{1}} = \left( {5,2,4,3} \right)$, A₂ = = $(7,8,9,3)$. Согласно примеру 2 матрица $\alpha $ из (3.3) приводит вектор ${{A}_{1}}$ к виду (0, 0, 0, 1). Имеем

образуем вектор $A_{2}^{1} = ( - 7, - 4,18)$. К этому трехмерному вектору применяем алгоритм Эйлера. Упорядочиваем его координаты по модулю

Имеем

Получаем

Упорядочиваем координаты по модулю

Имеем

Получаем

Упорядочиваем

Имеем

получаем

Упорядочиваем

Теперь

Полагаем

Теперь

Проверяем ${{A}_{1}}\gamma = (0,0,0,1)$, ${{A}_{2}}\gamma = (0,0, - 1, - 5)$. Итак,

5. ПРОГРАММЫ ВЫЧИСЛЕНИЯ ЦЕПНОЙ ДРОБИ

Алгоритмы вычисления цепных дробей реализованы в различных системах. Здесь опишем основные процедуры в двух системах компьютерной алгебры (СКА): в проприетарной Maple и в открытой sympy. Пакет NumberTheory в СКА Maple [5] позволяет получать разложение в цепную дробь рациональных, алгебраических и трансцендентных чисел, а также полиномов или элементарных функций от одной переменной. В пакете sympy [7] такой функционал реализован только для рациональных чисел или квадратичных иррациональностей. Если требуется работа с цепными дробями для других иррациональностей или трансцендентных чисел, то следует использовать открытую СКА Sage [6].

Для работы с рациональным числом в виде цепной дроби достаточно трех основных процедур: [1)]

1) преобразование в цепную дробь;

2) получение элементов цепной дроби;

3) получение рациональных приближений.

В СКА Maple соответствующие действия обеспечивают процедуры ContinuedFraction, Term и Convergent, а в sympy функционал пунктов 1 и 2 обеспечивает процедура continued_fraction, а пункта 3 – процедура continued_fraction_convergents.

Ниже приведем примеры реализации вычисления унимодулярных 2 × 2 матриц в соответствии с алгоритмами п. 1.9 книги [3]. Эти алгоритмы используют цепные дроби.

Первый алгоритм (см. [3], стр. 28–30) использует слагаемые разложения рационального числа p/q, а итоговая унимодулярная матрица получается путем последовательного умножения верхне- или нижнетреугольных матриц, которые составляются на основе элементов разложения цепной дроби. Его реализация для Maple и для sympy приведена на листингах 1 и 2 соответственно.

Листинг 1

Листинг 2

Пример работы процедуры UniMod1 для пары чисел 5, 17 примера 1 приведен на листинге 3.

Листинг 3

Второй алгоритм (см. [3], стр. 30–31) использует только само рациональное число  p/q и его последнюю подходящую дробь ${{p}_{{n - 1}}}{\text{/}}{{q}_{{n - 1}}}$. Его реализация приведена на листингах 4 и 5 соответственно.

Листинг 4

Листинг 5

6. РЕАЛИЗАЦИЯ АЛГОРИТМА ЭЙЛЕРА И РЕШЕНИЯ ЗАДАЧИ 1

Для имплементации алгоритма Эйлера, описанного в разделе 3, был реализован набор процедур в СКА Maple, листинги которых представлены ниже вместе с кратким их описанием. Отметим, что целочисленный вектор в СКА Maple может быть представлен в двух различных формах: в виде списка (перечня чисел в квадратных скобках) или в виде вектора-строки (вектора-столбца) пакета LinearAlgebra (Vector[row] или Vector[column] соответственно). Если имя процедуры содержит цифру 2, то это означает, что входной целочисленный вектор может быть задан в одном из двух указанных видов.

Процедура MakePermute2 представлена на листинге 6. Она строит перестановочную матрицу по заданному вектору $A$. Результат работы процедуры – упорядоченный вектор и перестановочная матрица ${{\alpha }_{0}}$. Порядок сортировки элементов вектора задается параметром sorting, но по умолчанию элементы упорядочиваются по возрастанию. В начале работы процедура проверяет, что вектор $A$ не является нульмерным (строка 4 листинга 6).

Листинг 6

Вторая процедура MakeUnimod2 (листинг 7) для упорядоченного по возрастанию вектора A строит унимодулярную матрицу α₁, реализующую один шаг (3.1) алгоритма Эйлера.

Листинг 7

Рекурсивная процедура Unimodr2 (листинг 8) вычисляет по исходному вектору A унимодулярную матрицу α, которая преобразует A в вектор C с единственной последней ненулевой координатой. При первом ее вызове второй параметр Uni не указывается. В этом случае он полагается равным единичной матрице (строка 7 листинга). При последующих вызовах в процедуру передается унимодулярная матрица, вычисленная на предыдущих вызовах. Для своей работы процедура Unimod2 использует описанные выше процедуры MakePermute2 и MakeUnimod2. Условие окончания рекурсии – это получение вектора, у которого все элементы, кроме одного, равны нулю (строка 16 листинга).

Листинг 8

Ниже приведен листинг 9 решения примера 2 для вектора $A = (5,2,4,3)$.

Листинг 9

Решение задачи 1 в соответствии с алгоритмом раздела 4 реализовано в рекурсивной процедуре UniSys, приведенной на листинге 10. Процедура получает исходный набор целочисленных векторов A_j, $j = 1, \ldots ,m$ в виде списка Vlst. Если исходный список пуст (строка 5), либо число векторов превышает их размерность (строка 8), либо векторы являются линейно зависимыми (строки 9–15), либо векторы из набора имеют разный тип (строки 16–24) или разную размерность (строки 25–28), то процедура UniSys завершает свою работу. Если список состоит из одного вектора, то вызывается процедура Unimodr2, вычисляется матрица α – и на этом работа процедуры окончена. В противном случае осуществляется повторный вызов процедуры UniSys для набора векторов $A_{j}^{1}$, $j = 2, \ldots ,m$, из которого исключен первый вектор, к оставшимся векторам применена унимодулярная матрица α. При этом размерность векторов $A_{j}^{1}$ уменьшена на единицу, а матрица α передается в виде параметра Uni для повторного вызова процедуры. При успешном окончании работы процедура UniSys возвращает итоговую матрицу $\gamma $, решающую задачу 1.

Листинг 10

Ниже приведен листинг 11 решения примера 3 для векторов $A = (5,2,4,3)$ и $B = (7,8,9,3)$.

Листинг 11

7. СТЕПЕННЫЕ ПРЕОБРАЗОВАНИЯ

Пусть задан многочлен

где $X = ({{x}_{1}}, \ldots ,{{x}_{n}}) \in {{\mathbb{R}}^{n}}$ или ${{\mathbb{C}}^{n}}$, $Q = ({{q}_{1}}, \ldots ,{{q}_{n}}) \in {{\mathbb{Z}}^{n}},$ $Q \geqslant 0,$ f_Q – постоянные коэффициенты из $\mathbb{R}$ или $\mathbb{C}$, ${\mathbf{S}} = {\mathbf{S}}(f)$ – носитель многочлена f. Пусть $\mathcal{F}$ – алгебраическое многообразие $f(X) = 0$ и точка $X = {{X}^{0}} \in \mathcal{F}$.

Если X⁰ – простая точка, т.е. хотя бы одна из производных $\partial f{\text{/}}\partial {{x}_{j}}$ в этой точке X⁰ отлична от нуля, то, по теореме о неявной функции, вблизи точки X⁰ многообразие $\mathcal{F}$ описывается уравнением

где $\Delta {{x}_{k}} = {{x}_{k}} - x_{k}^{0}$, $\varphi $ – сходящийся степенной ряд от своих аргументов.

Если точка X⁰ – не простая, то согласно [8, 9] можно искать ветви многообразия $\mathcal{F}$, проходящие через точку X⁰, в виде параметрических разложений

где ${{\xi }_{k}}$ – малые параметры, а ${{\varphi }_{j}}$ – сходящиеся степенные ряды. Для этого строится выпуклая оболочка Γ носителя S в пространстве ${{\mathbb{R}}^{n}}$. Тогда Γ – это многогранник, граница которого $\partial \Gamma $ состоит из (обобщенных) граней $\Gamma _{j}^{{(d)}}$ размерностей $d$, $0 \leqslant d < n$. Здесь  j – это номер грани. Поскольку все вершины $\Gamma _{j}^{{(0)}}$ многогранника $\Gamma $ целочисленны, то каждая грань $\Gamma _{j}^{{(d)}}$ имеет n – d целочисленных линейно независимых нормалей $N_{{j1}}^{{(d)}}, \ldots ,N_{{jn - d}}^{{(d)}} \in \mathbb{R}_{*}^{n}$, т.е. лежащих в пространстве $\mathbb{R}_{*}^{n}$, двойственном (сопряженном) пространству ${{\mathbb{R}}^{n}}$.

Кроме того, каждой грани $\Gamma _{j}^{{(d)}}$ соответствуют граничное множество

и укороченная сумма

Теорема ([8, следствие § 3, гл. II] и теорема 3.1 [9]). Для грани $\Gamma _{j}^{{(d)}}$ существует степенное преобразование

где $\ln Y = (\ln {{y}_{1}}, \ldots ,\ln {{y}_{n}})$, $\ln X = (\ln {{x}_{1}}, \ldots ,\ln {{x}_{n}})$ с унимодулярной матрицей α, которое переводит укороченную сумму (7.4) в многочлен g от d координат, т.е.где $T = ({{t}_{1}}, \ldots ,{{t}_{n}}) \in {{\mathbb{Z}}^{n}}$.

Но в [8, 9] не было указано, как вычислять унимодулярную матрицу $\alpha $. Это сделано в настоящей работе. А именно: если n = 2, то с помощью цепной дроби раздела 2, если $d = n - 1$, то с помощью алгоритма Эйлера, если n > 2 и $d < n - 1$, то с помощью алгоритма раздела 4, решающего задачу 1.