Сайт Марии Федотовой, ученицы ФМЛ №239 СПб

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

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

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

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

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

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

P=(

5

3

)

2

1

,

Q=(

33

10

)

10

3

,

R=(

27

5

)

11

2

.

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

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

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

B=(

1

1

)

0

1

,

C=(

1

0

)

1

1

,

F=(

0

1

)

1

0

.

Прежде всего, заметим, что BF=FC , CF=FB и F2=E, где E – единичная матрица (в частности, отсюда следует F3=F , то есть F – не примитивна, а также B=FCF и C=FBF ).

Несложно проверить, что произойдет с произвольной матрицей M€GL(2,Z) после ее умножения слева или справа на одну из этих матриц. При умножении на F слева строки матрицы M поменяются местами, а при умножении на F справа местами поменяются столбцы матрицы M. При умножении на B слева строки матрицы M складываются, а их сумма пишется в первой строке произведения BM, тогда как вторая строка произведения BM совпадает со второй строкой B. При умножении слева на C сумма строк матрицы M пишется в первой строке СM, а первая строка СM совпадает с первой строкой С. При умножении справа происходит сложение столбцов матрицы M, причем их сумма пишется во втором столбце MB и в первом столбце MC, а оставшиеся столбцы этих произведений совпадают с соответствующим столбцом матрицы M.

Теорема 1. Для всякой матрицы MGL++(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. Для всякой матрицы MGL+(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=FC3B3C3=(FC3)3 . Оставшиеся две матрицы положительно примитивны, что видно из анализа их разложений  P=FC2BC  и  R=FC2B2C5 .

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

Цитируемые источники

1.         http://logic.pdmi.ras.ru/~vsemir/konkurs2001 – студенческий конкурс решения задач 2001-2002 года (на сайте Петербургского отделения математического института Российской академии наук).

2.         http://www.mathsoc.spb.ru/  – сайт Санкт-Петербургского математического общества.

Сайт управляется системой uCoz