67804

ПОДСТАНОВКИ И ЛИНЕЙНЫЕ ПРЕОБРАЗОВАНИЯ

Лабораторная работа

Математика и математический анализ

Цель работы – изучить основные свойства линейных преобразований и подстановочных матриц, необходимые для математического описания регистров сдвига с линейной обратной связью. Краткие теоретические сведения. Векторные пространства. Пусть – непустое множество элементов любой природы, которые будем обозначать...

Русский

2014-09-15

578.5 KB

3 чел.

PAGE   \* MERGEFORMAT 5

Лабораторная работа № 2

ТЕМА: ПОДСТАНОВКИ И ЛИНЕЙНЫЕ ПРЕОБРАЗОВАНИЯ

Цель работы – изучить основные свойства линейных преобразований и подстановочных матриц, необходимые для математического описания регистров сдвига с линейной обратной связью.

Краткие теоретические сведения.

Векторные пространства.

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

Множество  называется векторным (линейным) пространством, если в  определены алгебраическая операция сложения и операция умножения на числа из поля , причем выполнены следующие условия (аксиомы векторного пространства):

1.   – ассоциативность сложения;

2.   – коммутативность сложения;

3.  :  – существование нулевого элемента;

4.  : – существование противоположного элемента;

5.    – ассоциативность умножения на число;

6. .

7.    – дистрибутивность относительно сложения чисел;

8.    – дистрибутивность относительно сложения элементов;

Элементы векторного пространства называются векторами, элемент  называется нулевым вектором.

Линейной комбинацией векторов  векторного пространства  с коэффициентами  из поля  называется вектор .

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

Упорядоченная система векторов  векторного пространства  называется базисом векторного пространства , если

1) она линейно независимая;

2) каждый вектор  пространства  линейно выражается через векторы этой системы, то есть .

Следовательно, базис – это максимальная система линейно независимых векторов.

Векторное пространство называется конечномерным, если в нём существует базис, состоящий из конечного числа векторов.

Рассмотрим множество , элементами которого являются упорядоченные последовательности  элементов поля . Относительно покомпонентного сложения и покомпонентного умножения на элемент поля , построенное множество  является векторным пространством над  и обозначается . Очевидно, система , где , а единица находится на -ом месте, является базисом. Можно показать, что все принадлежащие  базисы состоят из одного и того же числа элементов.

Любое конечномерное линейное пространство  над полем  изоморфно  при некотором .

Число  векторов в базисе называется размерностью векторного пространства . Размерность пространства  обозначается . Если , то векторное пространство называется -мерным.

Линейные преобразования и матрицы над полем.

Пусть  – поле.

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

Если  матрица  называется квадратной порядка .

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

Множество квадратных матриц является некоммутативным кольцом.

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

Линейным оператором (линейным преобразованием) в векторном пространстве  называется отображение векторного пространства  в себя такое, что выполнены следующие условия (условия линейности):

1)  ;

1)  .

При фиксированном базисе  каждому линейному оператору  пространства  отвечает определенная матрица  -го порядка – матрица этого линейного оператора. Справедливое и обратное: каждая матрица -го порядка является матрицей определенного линейного оператора пространства  в базисе .

В координатном виде действие линейного оператора  на вектор  сводится к умножению матрицы линейного оператора на координатный столбец вектора :

.

Пусть  – обратимая матрица. Матрицей, обратной к , называется матрица , для которой выполняются условия .

Подстановочные матрицы. Определитель матрицы над .

Пусть  – конечное множество из  элементов.

Подстановкой порядка  на множестве  из  элементов называется взаимно однозначное отображение множества  на себя.

Пусть  упорядочено, тогда ему соответствует последовательность номеров . После применения подстановки порядок следования элементов изменится и примет вид .

Подстановку можно представить в виде двустрочной записи: . Очевидно, обратное преобразование имеет вид .

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

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

Пусть  и  - подстановка степени , причем I. Подстановка  называется k-членным циклом, если она не перемещает  элементов, а ее действие на оставшиеся k элементов  можно представить в виде циклической диаграммы переходов: . В этой диаграмме допускается только один переход от элемента с большим индексом к элементу с меньшим индексом, а именно: .

Например, трехчленный цикл пятой степени: . Здесь элементы 4 и 5 неподвижны, причем , , .

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

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

Запись подстановки в виде произведения независимых циклов называется циклической записью.

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

Подстановка называется регулярной, если ее циклическая запись состоит из циклов равной длины.

Подстановка называется полноцикловой, если ее цикловая запись состоит из одного цикла.

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

Пусть  – подстановка из ,   – любое её разложение в произведение транспозиций. Тогда число , которое называется знаком (или сигнатурой, или четностью ) полностью определяется подстановкой  и не зависит от способа разложение  в произведение транспозиций.

Существует изоморфное отображение , такое, что матрица , имеет детерминант .

Матрица вида , , называется матрицей подстановки, или подстановочной матрицей.

У подстановочной матрицы  порядка , элементы с индексами  равны единице, а прочие элементы равны нулю. Например, для подстановки , получим .

Очевидно, , т.е. матрица реализует заданную подстановку. Исходя из определения подстановки, подстановочные матрицы обратимы. Если матрица  - подстановочная, то .

Критерий обратимости матрицы формулируется с помощью понятия определителя (детерминанта). Детерминант матрицы  над полем  является элементом поля . Он является функцией всех элементов матрицы и обозначается через . Детерминант записывается также в виде .

Матрица  обратима тогда и только тогда, когда .

Рассмотрим случай, когда матрица  порядка  определена над полем .

Рассмотрим все  подстановочных матриц порядка . Представим себе, что каждая из них записана в виде таблицы на отдельном листе бумаги в клетку. Вырежем в каждой таблице окошки в тех клетках, где элементы соответствующей матрицы равны единице. Получим, таким образом, совокупность подстановок в виде трафаретов.

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

Найдем сумму над полем  всех  членов определителя. Результат назовем определителем матрицы над полем .

Аннулирующий и минимальный многочлен матрицы над полем.

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

Аннулирующим многочленом матрицы  называется многочлен , такой, что .

Минимальным многочленом матрицы  над полем  называется нормированный многочлен  наименьшей степени, для которого .

Минимальный многочлен матрицы делит любой аннулирующий многочлен той же матрицы.

Степень минимального многочлена матрицы не превосходит ее порядка.

Рассмотрим последовательность ,,, - мерных векторов.

На каждом шаге  будем проверять (например, с помощью схемы Гаусса решения систем линейных уравнений) является ли система полученных векторов зависимой, либо нет. На некотором шаге , вектори впервые окажутся линейно зависимыми, т.е. при соответствующих коэффициентах выполнится соотношение .

Многочлен  называется минимальным многочленом матрицы  относительно вектора . Минимальный многочлен единственен.

Минимальный многочлен суммы векторов является наименьшим общим кратным минимальных многочленов векторов - слагаемых.

Минимальный многочлен матрицы  относительно любого вектора  делит минимальный многочлен матрицы.

Пусть  - квадратная матрица над конечным полем  и . Последовательность ,, является периодической. Длина периода зависит от свойств минимального многочлена матрицы  относительно вектора .

Очевидно, наименьшее общее кратное минимальных многочленов базисных векторов относительно матрицы  является минимальным многочленом этой матрицы.

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

Многочлен  называется характеристическим многочленом матрицы .

Теорема Гамильтона-Кэли. Каждая матрица является корнем своего характеристического многочлена.

Следствие. Характеристический многочлен матрицы делится на ее минимальный многочлен.

Порядок выполнения работы

1. Изучите краткие теоретические сведения о линейных преобразования и подстановках.

2. Найдите произведение матриц вида  над полями Q, , , , .

a

b

c

d

e

a

b

c

d

e

a

b

c

d

e

1

1

5

3

2

0

6

3

4

0

5

2

11

1

4

3

4

3

2

3

5

4

7

2

7

2

0

5

3

5

12

2

3

5

3

1

3

2

3

1

5

4

8

3

6

0

1

2

13

4

2

1

6

4

4

1

4

6

0

2

9

3

5

4

3

0

14

3

6

1

1

3

5

6

3

9

8

2

10

7

1

1

4

2

15

5

1

8

2

5

a

b

c

d

e

a

b

c

d

e

16

3

0

6

3

2

21

1

6

2

0

5

17

2

1

3

5

2

22

3

2

5

1

4

18

3

2

7

4

3

23

4

7

0

2

1

19

3

1

5

1

3

24

5

0

3

1

2

20

0

2

7

3

1

25

1

8

3

2

0

2. Для подстановки

а) Найдите разложение в произведение циклов;

б) Запишите соответствующую подстановочную матрицу.

a

b

c

d

e

f

g

a

b

c

d

e

f

g

a

b

c

d

e

f

g

1

2

1

6

5

7

3

4

6

2

5

1

6

4

7

3

11

7

3

4

5

2

6

1

2

5

7

4

2

3

1

6

7

1

7

6

2

5

4

3

12

1

6

7

4

3

2

5

3

1

6

7

3

4

5

2

8

1

4

3

7

5

6

2

13

2

5

6

7

1

4

3

4

5

2

1

6

7

3

4

9

4

1

7

2

6

5

3

14

5

2

7

3

4

1

6

5

6

5

7

4

2

3

1

10

5

7

4

1

2

6

3

15

3

2

1

7

5

6

4

a

b

c

d

e

f

g

a

b

c

d

e

f

g

16

2

1

3

7

5

6

4

21

7

1

5

4

2

3

6

17

7

6

5

4

3

2

1

22

5

2

4

7

6

1

3

18

1

2

6

4

3

7

5

23

3

5

1

6

4

7

2

19

3

5

4

1

2

6

7

24

1

5

3

2

7

6

4

20

5

7

3

2

1

6

4

25

2

4

7

1

3

6

5

3. Вычислите характеристический многочлен для матрицы  над полями Q, , . (a,b,c,d,e,fиз п. 2)

4. Постройте минимальный многочлен матрицы  относительно вектора  над полем .

1) , .   2) , .

a

b

c

d

e

f

g

h

i

a

b

c

d

e

f

g

h

i

1

1

1

3

2

0

3

4

0

3

6

1

4

3

4

3

3

0

6

3

2

3

5

4

7

2

2

2

5

0

7

2

3

3

3

2

2

1

3

5

3

2

3

1

5

4

3

1

0

1

8

4

2

1

6

4

3

1

7

4

4

1

1

2

0

1

3

5

3

3

9

3

6

1

1

3

3

1

2

1

5

6

3

9

8

2

1

0

1

0

10

5

1

8

2

5

0

2

2

0

a

b

c

d

e

f

g

h

i

a

b

c

d

e

f

g

h

i

11

3

1

1

1

9

8

2

9

2

16

7

2

1

1

3

0

1

0

5

12

3

0

0

1

2

3

1

5

4

17

1

6

4

3

7

2

2

2

5

13

0

4

1

1

3

5

6

0

1

18

2

1

1

0

3

3

4

4

0

14

3

3

3

2

2

1

1

0

4

19

1

3

4

1

2

0

0

4

1

15

1

0

1

0

3

4

2

2

1

20

3

5

1

8

9

1

1

0

2

a

b

c

d

e

f

g

h

i

21

1

2

2

1

6

3

1

5

4

22

2

5

0

3

2

2

4

7

1

23

6

4

3

1

7

5

0

3

1

24

1

2

7

3

0

1

2

8

0

25

1

5

4

0

3

2

4

1

2

5. Составьте отчёт, приобщив полученные результаты.

Требования к отчету.

В отчете должны быть приведены:

  1.  Исходные данные (варианты заданий);
  2.  Результаты и промежуточные данные преобразований.
  3.  Ответы на контрольные вопросы и их обоснование.

Контрольные вопросы

  1.  Что называется векторным пространством?
  2.  Какая система векторов называется линейно независимой?
  3.  В каком случае система векторов образует базис пространства?
  4.  Что называется линейным преобразованием пространства?
  5.  Что представляет собой действие линейного оператора на вектор?
  6.  Что такое подстановка?
  7.  Какая матрица называется подстановочной?
  8.  Какой многочлен называется характеристическим многочленом матрицы ; минимальным многочленом матрицы ; минимальным многочленом матрицы  относительно вектора ?


 

А также другие работы, которые могут Вас заинтересовать

78045. VPN (Virtual Private Networks) 56 KB
  Преимущества технологии VPN в том что организация удалённого доступа делается через Интернет что очень удобно. Для организации удалённого доступа к частной сети с помощью технологии VPN понадобится Интернет и реальный IP адрес.
78046. Антидепрессанты и их применение при соматической патологии 22 KB
  На этом основан механизм действия антидепрессантов за счет улучшения проведения по синапсам которое достигается либо инактивацией моноаминооксидазы МАО либо блокированием обратного нейронального захвата.
78047. Правовые основы налогообложения 77.69 KB
  Следующий вид нормативных документов - это подзаконные акты, регулирующие детальный порядок налогообложения конкретных видов налогов. В соответствии с определением Закона о налогах и сборах налоги представляют собой денежные платежи, которые не являются ответными услугой...