Текст доклада

СТЕПЕНИ МАТРИЦ С НЕОТРИЦАТЕЛЬНЫМИ ЦЕЛЫМИ ЭЛЕМЕНТАМИ

На сайтах [1] и [2] проводился студенческий конкурс решения задач 2001-2002 года. Под №9 там была предложена следующая задача о матрицах:

Задача 9. Примитивные матрицы.  

Напомним, что GL(2,Z) - группа матриц второго порядка с целыми элементами и определителем ±1. Матрица M€GL(2,Z) называется примитивной, если не существует n≥2 и матрицы K€GL(2,Z) таких, что M=Kⁿ.

(А) Проверьте, будут ли следующие матрицы примитивными:

(Б) Найдите какие-либо достаточные и/или необходимые условия примитивности.

В этой своей работе я решаю другую, но очень близкую задачу: в качестве матриц M и K допускаются только матрицы с неотрицательными целыми элементами. Основное определение примет тогда следующий вид.
Обозначим через GL⁺(2,Z) полугруппу матриц второго порядка с целыми неотрицательными элементами и определителем ±1, а через GL⁺⁺(2,Z) ее подмножество (тоже полугруппу), состоящее из матриц второго порядка с целыми неотрицательными элементами и определителем +1. Назовем матрицу M€GL⁺(2,Z) положительно примитивной, если не существует n≥2 и матрицы K€GL⁺(2,Z) таких, что M=Kⁿ. Назовем матрицу M€GL⁺⁺(2,Z) строго положительно примитивной, если не существует n≥2 и матрицы K€GL⁺⁺(2,Z) таких, что M=Kⁿ.

 Среди простейших примеров выберем три матрицы:

Теорема 1. Для всякой матрицы M€GL⁺⁺(2,Z) существует и единственно ее представление в виде произведения матриц B и C (в нужном количестве и порядке).  

Доказательство базируется на сделанных выше наблюдениях и следующей лемме.

Лемма о мажорировании. Если M€GL⁺⁺(2,Z) и M≠E, то можно выбрать строку (или столбец) матрицы M, элементы которой не меньше соответствующих элементов другой строки.

Теорема 1 дает следующий алгоритм представления матрицы M€GL⁺⁺(2,Z) в виде степени матрицы K€GL⁺⁺(2,Z). Сначала нужно разложить M в произведение матриц B и C. Затем, обозначив через m число множителей в этом разложении, составить список всех делителей числа m. Наконец, для каждого делителя d нужно выписать первые d букв из записи разложения M в произведение матриц B и C, повторить этот фрагмент m/d раз и проверить, не получится ли в итоге сама эта запись. Положительный результат проверки даст нужное представление. Если проверка даст отрицательный результат при всех d<m , то матрица M строго положительно примитивна.

Из теоремы 1 также следует, что любую матрицу M€GL⁺(2,Z) можно представить в виде произведения матриц B, C и F. Однако здесь о единственности такого представления не может быть и речи. Тем не менее, удается так выбрать «канонический вид» разложения в произведение, что нужная единственность появляется.

Теорема 2. Для всякой матрицы M€GL⁺(2,Z) существует ее представление в виде произведения матриц F, B и C в нужном количестве и порядке. Дополнительное требование ставить множитель F не более одного раза и только на первое место обеспечивает  единственность такого представления.

Теорема 2 дает аналогичный алгоритм представления матрицы M€GL⁺(2,Z) в виде степени матрицы K€GL⁺(2,Z). Существенное отличие возникает лишь на последнем шаге. После того, как запись разложения M в произведение матриц B и C разбита на фрагменты по d букв, требуется дополнительная проверка. Надо проверить, не получается ли один фрагмент из другого домножением на F, и попытаться вставить в стык перед одним из таких фрагментов пару FF. Затем первый из двух множителей F оставить на месте, а второй «пронести» сквозь фрагмент (в результате чего все B заменятся на C, а C – на B). Учет знаков и соображения четности позволяют в некоторых случаях заметно сократить число проверяемых вариантов.

Проиллюстрируем теорему 2 на примерах со студенческого конкурса. Для второй матрицы получим  Q=FC³B³C³=(FC³)³ . Оставшиеся две матрицы положительно примитивны, что видно из анализа их разложений  P=FC²BC  и  R=FC²B²C⁵ .

Еще один пример:  BC=(BF)² .  Он показывает, что введенные в работе понятия положительно примитивной матрицы и строго положительно примитивной матрицы не совпадают друг с другом. Второе из этих условий необходимо (но не достаточно) для первого. Аналогично, положительная примитивность матрицы необходима (но не достаточна) для ее примитивности в обычном смысле.