Формула для подсчета обратимых матриц порядка 2.

Вятский государственный гуманитарный университет

 

Математический факультет

Кафедра алгебры и геометрии

 

 

Выпускная квалификационная работа

Обратимые матрицы над кольцом Z_n

 

Выполнила:

Студентка V курса

Математического факультета

Сычева О. Г.

Научный руководитель:

д.ф.-м.н., профессор

Вечтомов Е. М.

Рецензент:

к.ф.-м.н., доцент

Чермных В. В.

 

Допущена к защите в ГАК

Зав.кафедрой                                                             Вечтомов Е М.

« »

Декан факультета                                                       Варанкина В. И.

« »

Киров 2003

Содержание:

Введение………………………………………….…………………….2 стр.

§1 Основные понятия………………………………………………….3 стр.

§2 Обратимые матрицы над полем Z_p

п.1 формула для подсчета обратимых матриц порядка 2 ……….10 стр.

п.2 формула для подсчета обратимых матриц порядка 3 ……….11 стр.

п.3 общая формула подсчета обратимых матриц над полем Z_p ..16 стр.

§3 Обратимые матрицы над Z _n ………………………………………17 стр.

Литература …………………………………………………………….27 стр.

Введение

Теория матриц является одним из основных вопросов линейной алгебры.

Цель данной работы: подсчитать количество обратимых матриц над кольцом вычетов и по возможности получить формулу для их вычисления. Для вычисления количества обратимых матриц воспользовались теорией определителей и полным перебором всех возможных вариантов получения элементов в кольцах вычетов.

Вся работа разбита на два этапа:

В §2 показан метод построения обратимых матриц второго и третьего порядков над полем Z_p . В конце параграфа построена гипотеза формулы подсчета количества обратимых матриц n–го порядка над полем Z_p .

В §3 приведен алгоритм построения обратимых матриц второго порядка над некоторыми кольцами вычетов (приведены конкретные примеры). В конце параграфа построена гипотеза формулы подсчета количества обратимых матриц второго порядка над кольцом классов вычетов Z _n .

 

Основные определения.

Матрицей называется прямоугольная таблица, заполненная некоторыми математическими объектами. Чаще всего рассматриваются матрицы, заполненные элементами из некоторого поля P.

Элементы матрицы обозначаются одной буквой с двумя индексами, указывающими "адрес" элемента - первый индекс дает номер строки, содержащий элемент, второй - номер столбца. Если матрица имеет m строк и n столбцов, то говорят, что матрица имеет размерность  (или - размеров ). Мы будем обозначать матрицы заглавными латинскими буквами, а ее элементы - такими же буквами, но строчными. Таким образом, матрица (размеров ) записывается в форме:

.

Матрица, состоящая из одних нулей, называется нулевой.
Будем обозначать ее 0.

Матрица, имеющая одно и то же число n строк и столбцов, называется квадратной. Число n называется порядком квадратной матрицы.

Элементы матрицы, у которых оба индекса равны (i = j) называются диагональными, а воображаемая прямая, соединяющая все диагональные элементы матрицы называется главной диагональю.

Квадратная матрица, у которой все элементы, за исключением элементов главной диагонали, равны нулю, называется диагональной.

Диагональная матрица, у которой все диагональные элементы равны единице, называется единичной матрицей и обозначается Е.:

Две матрицы считаются равными, если они одного размера и у них совпадают соответствующие элементы.

Две матрицы A=(a_ij) и B=(b_ij) одного и того же размера можно складывать, их суммой будет матрица того же размера C=(c_{i j}), , т.е. чтобы получить сумму двух матрицы достаточно сложить соответственные элементы этих матриц.

Произведение элемента c из поля на матрицу A=(a_ij) определяется следующим образом: cA =(ca_ij).

Для любой матрицы A существует противоположная - A такая, что
A +(- A)=0.

Все перечисленные свойства непосредственно следуют из определений и свойств операций в поле.

Рассмотрим матрицу A=(a_ij) размером  и матрицу B=(b_ij) размером  (т.к. произведение матриц определено лишь в том случае, когда число столбцов в первой матрице равно числу строк во второй). Для таких матриц введем действие умножения матрицы на матрицу, в результате чего получается матрица C =(c_ij) размером , где .

Итак, матрицы можно складывать, умножать их на скаляр, а также умножать матрицу на матрицу. Эти действия обладают свойствами:

По сложению:

1. (A + B)+ C = A +(B + C) – ассоциативность;

2. A + B = B + A – коммутативность;

3. Существует нейтральный элемент – матрица 0: A + 0 = 0 + A = A;

4. Для матрицы A существует обратный элемент - A : A + (- A)=0;

По умножению матриц на скаляр:

5. ;

6. ;

7. ;

8. ;

По умножению матриц:

9. Произведение матриц в общем случае не коммутативно, т.е. AB ВА;

10. (AB)C = A(BC) – ассоциативность;

11. (cA)B = A(cB)= cAB;

12. Дистрибутивность умножения относительно сложения (правая и левая)(A ₁ + A ₂)B = A ₁ B + A ₂ B, A(B ₁ + B ₂)= AB ₁ + AB ₂;

13. Существует единственный нейтральный элемент E
(если A – квадратная): EA = AE = A . Если же A размером , то
E_mA = AE_n = A .

14. Произведение матрицы А на нулевую матрицу дает в результате так же нулевую матрицу (существуют случаи, когда нулевая матрица получается в результате перемножения ненулевых матриц).

Для квадратных матриц фиксированного порядка n действия сложения и умножения определены всегда, и их результатами являются квадратные матрицы того же порядка. Таким образом, квадратные матрицы фиксированного порядка образуют кольцо.

Определителем n-го порядка квадратной матрицы А, называется алгебраическая сумма n ! членов, которыми являются всевозможные произведения по n элементов, взятых по одному и только по одному из каждой строки и каждого столбца, причем член берется со знаком плюс, если его индексы составляют четную перестановку, и со знаком минус – если нечетную перестановку.

,

где (a ₁ , a ₂ , ..., a _n) пробегает все перестановки чисел 1, 2, ..., n; множитель  равен +1, если (a ₁ , a ₂ , ..., a _n) - четная перестановка, и равен –1, если нечетная.

Минором элемента a_ij называется определитель (n-1) – порядка, полученный из данного определителя n-го порядка, путем вычеркивания i -й строки и j -го столбца.

Минор a_ij элемента обозначается М _ij .

Алгебраическим дополнением элемента a_ij называется минор этого элемента, взятый со знаком (-1)^{i + j} .

Алгебраическое дополнение элемента обозначается А _ij =(-1)^{i + j} × М _ij.

Матрица B называется обратной для матрицы A, если AB = BA = E,
где E - единичная матрица. Равенство AB = BA показывает (нетрудно видеть, используя правило умножения матриц), что число строк и столбцов матрицы A должно быть одинаково.

Таким образом, обратная матрица имеет смысл только для квадратных матриц. Далее мы будем рассматривать только квадратные матрицы.

Если матрица А имеет обратную, то она единственна.

Покажем это. Пусть АВ=СА=Е и С В, тогда заметим: С=СЕ=С(АВ)=(СА)В=ЕВ=В. Что противоречить условию.

Определитель произведения любых двух матриц n -го порядка равен произведению их определителей.

Докажем. Рассмотрим единичные столбцы n -го порядка:

, , …,

Возьмем произведение матрицы АВ на столбец единичных столбцов (т.е. столбец из n n-мерных столбцов)

Тогда = ×1= × = =

= = = = .
 Что требовалось доказать.

Заключение данной теоремы также выполняется и для случая, когда элементы матриц взяты из кольца вычетов Z_n.

Квадратная матрица называется вырожденной, если ее определитель равен нулю и не вырожденной в противном случае.

Для всякой невырожденной матрицы существует обратная матрица.

Покажем это. Пусть A=(a_ij) –невырожденная квадратная матрица ( ). Рассмотрим матрицу А^*= , где А_ij – алгебраическое дополнение элементов определителя , причем алгебраические дополнения i-й сроки стоят в i-ом столбце.

Найдем произведение С=АА^*, где С=(с _ij)

 и т.д.

Найдя все элементы матрицы С по описанному выше алгоритму,
в итоге, получим следующее: , т.е. . Значит матрица А^* - обратная к невырожденной матрице А.

Для вырожденной матрицы обратной матрицы не существует. Иначе если вырожденная матрица А ( ) имеет обратную А^*, тогда верными будут следующие равенства: А·А^*=Е, , , .
 Что в принципе не верно.

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

§2 . Обратимые матрицы над полем Z _p

В данном параграфе попытаемся вывести формулу для подсчета количества обратимых матриц в поле Z_p, где p – простое.

Формула для подсчета обратимых матриц порядка 2.

Будем рассматривать матрицы .

Алгебраическое дополнение к элементу  есть определитель матрицы  порядка 1, т.е. . Алгебраическое дополнение к элементу  есть определитель матрицы  порядка 1, т.е. .

Нужно найти количество всех невырожденных матриц
(когда ). При этом

     (1.1)

Формулу выведем в 2 этапа.

1) Пусть  (р-1 штук),  (р-1 штук),

 (по р штук) (1.2).

Тогда количество матриц, удовлетворяющих данным условиям, вычисляется по формуле

(р-1)²р²    (1.3)

Мы утверждаем, что по этой же формуле вычисляется количество матриц, определитель которых не обращается в нуль, при условии, что , .

В условии (1.2) не учитываются матрицы вида  с неравным нулю определителем, количество которых нужно прибавить.
Но сосчитали матрицы вида  с определителем обращающимся в нуль, количество которых нужно вычесть.

 Докажем, что количество матриц в обоих случаях одинаково.

а)  (р-1 штук),  и . Из (1.1) получаем равенство . Значит . При заданном  (где =1,2…р-1) элемент  однозначно выражается через  и  (количество невырожденных матриц  – р-1). Поэтому количество матриц удовлетворяющих этим условиям (р-1)³ штук.

б) ,  и . Значит . Отсюда . Элемент  однозначно выражается через , , , которые принимаю не нулевые значения. Поэтому количество матриц удовлетворяющих этим условиям (р-1)³ штук

Значит формула (1.3) при условии (1.2) верна.

2) Пусть . Тогда , а из (1.1) получаем что  и  (как в первом этапе, случае а). Тогда количество таких матриц вычисляется по формуле

(р-1)²×р (1.4)

Этими этапами мы перебрали все случаи невырожденных матриц.

Складывая формулы (1.3) и (1.4) полученные в этапах 1) и 2) получаем формулу для нахождения количества обратимых матриц порядка 2 над полем Z_p

(р-1)²×р×(р+1) (1.5)