Успешное подключения к БД.

-------------------
Вы знаете, как устроен наш мир?



---Load files---
Совет: если изображения отображаются неправильно, попробуйте очистить кеш браузера!
Поиск на странице - нажмите "Ctrl+F", Поиск на сайте - поле ввода "Яндекс-Найти" на "шапке",
Поиск в интернете - 1) выделите текст, 2) нажмите правую клавишу мыши и 3) выберите поисковик.

С О Д Е Р Ж А Н И Е

------- Тимин В.А. (mail: timinva@yandex.ru) Дата последней загрузки: October 31 2017. -------
Ссылка на этот материал: konechnyye_gruppy_tablica_umnozheniya.htm)
Таблица умножения групп

1      Таблица умножения групп

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

1

a

b

c

a

aa

ab=c

ac

b

ba

bb

bc

c

ca

cb

cc

Для примера стрелками обозначен результат операции ab = c: a, b – начало операции, c – конец (результат) операции. Определение группы  с помощью таблицы умножения не ограничивает эти отношения чем-либо, кроме удовлетворения своим аксиомам. Единственное требование к этой таблице – ее биективность, полнота всех строк и столбцов, существование обратного для каждого элемента группы и ее ассоциативность.

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

Какой-либо простой схемы определения ассоциативности по таблице умножения не имеется. Для ассоциативности таблицы умножения необходимо, чтобы вся таблица состояла из ячеек вида:

ab

a

b

I

Для таблицы проверка ассоциативности заключается в проверке всех произведений вида abc на это свойство.

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

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

1.1      Свойства таблицы умножения.

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

1)      Количество строк и столбцов совпадает с количеством элементов (символов) группы.

2)      В каждой строке и столбце имеется не более одного одинакового символа.  Следовательно, в каждой строке и столбце  обязательно должен встретиться символ единицы I.

3)      Инвариантом таблицы является количество единиц на главной диагонали. Если они различны, то таблицы отличаются друг от друга.

4)      Инвариантом является также числа цикличности группы и их степень.

5)      Если на пересечении строки и столбца стоит единица, то на главных строке и столбце стоят взаимно обратные элементы.

6)      Для коммутативной группы таблица умножения симметрична относительно главной диагонали.

Можно поставить вопрос: сколько групп можно построить из n элементов? Но для начала надо решить вопрос: возможно ли определить все группы определенного порядка? Ответ на этот вопрос в принципе положительный: каждую таблицу умножения можно проверить на соответствие аксиомам группы. Но вопрос осложняется еще одним обстоятельством – две (или больше) таблиц умножения могут определять эквивалентные группы с точностью до перенумерации элементов. К счастью, ответ и на этот вопрос положительный. Во первых, можно опять же сравнить все таблицы умножения перенумерацией элементов, объединить в классы все эквивалентные таблицы. Одну из них определить как представителя класса. Этого представителя можно выделить по некоторому признаку: например, упорядочить все таблицы, и в каждом классе выбрать наименьший.

1.2      Минимальный алгоритм построения таблицы умножения

Но количество возможных таблиц умножения из конечного набора элементов даже для небольших чисел огромно. Из n элементов в общем случае можно построить  таблиц умножения. Даже для n = 3 это число равно 19 683, а для n = 4 оно огромно и равно 4 294 967 296. Поэтому простой перебор возможностей практически неосуществим. При практическом решении этой задачи с помощью таблиц умножения необходимо пользоваться методами перебора с эффективным фильтрованием решений. Для этого для начала надо упорядочить все таблицы умножения, и при построении таблицы умножения периодически проверять частичные решения на принадлежность, во первых, группе, во вторых, проверять текущую таблицу (или ее частичное решение) на принадлежность классу представителей групп. Для этого можно придерживаться некоторых конструктивных правил, которые несут и определенную классифицирующую нагрузку.

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

2)      Таблицу умножения составим в форме латинского квадрата, где первая строка и первый столбец состоят из упорядоченных чисел:

1

2

n

2

r22

r2n

n

rn2

rnn

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

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

4)      Построим наименьшую таблицу, являющуюся группой. Для этого воспользуемся алгоритмом (см. блок-схему):

1.      Обходим таблицу слева направо – сверху вниз;

2.      В позиции r22 ставим число 1 – инициализируем алгоритм. Переходим в следующую позицию и тоже ставим число 1.

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

4.      Если такое число есть, то переходим на предыдущую ячейку.

5.      Увеличиваем текущее число на единицу. Переходим на пункт 3.

6.      Если такого числа нет, то пишем это число в текущую ячейку и переходим на п.4.

7.      Выполняем эти процедуры, пока не дойдем до правого нижнего угла и не запишем туда число.

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

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

8.      не пора ли остановить процесс? Признаком конца перебора всех возможностей является выход на определенном шаге на конец второй строки таблицы умножения.

9.      Если нет, то процесс получения следующей таблицы продолжается с конца таблицы умножения прибавлением единицы к последней ячейке таблицы с переходом к продолжению предыдущего алгоритма с п.4.

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

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

1.3      Построение второй и последующих строк таблицы умножения

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

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

Возьмем первый элемент – единицу, и посмотрим, во что он превращается при последовательном умножении числа 2 на нее. В результате мы получим, например, для последовательность элементов 1-2-5-4-6-1, циклическую перестановку

1

2

4

5

6

2

5

6

4

1

Что можно сделать с этой последовательностью? А мы перенумеруем ее элементы в соответствии с таблицей

1

2

5

4

6

1

2

3

4

5

В результате получим перестановку

1

2

4

3

5

2

3

5

4

1

Переставим столбцы 3 и 4:

1

2

3

4

5

2

3

4

5

1

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

6

7

8

9

10

7

8

9

10

6

причем вся эта пара строк будет состоять из таких циклических участков. Если количество элементов в цикле n1, а таких циклов n2, то общее количество элементов в строке равно их произведению, что соответствует порядку группы, представленной этой таблицей. Каждый из циклов будет представлять некоторый смежный класс подгруппы, состоящей из элементов 1…n. Это говорит о том, что любую перестановку двух первых строк таблицы умножения можно превратить в некоторую стандартную. Как можно применить это свойство таблицы умножения для оптимизации поиска таблиц? А так:

Вывод: первая строка состоит из последовательных чисел 1…n,  а вторая строка состоит из последовательности смежных классов подгруппы порядка n1.

Для n = 12 с количеством циклических элементов в смежном классе 3 эти две строки будут следующими:

1

2

3

4

5

6

7

8

9

10

11

12

2

3

1

5

6

4

8

9

6

11

12

9

В алгоритме это может быть определено следующим образом:

1) Разница в числах между второй и первой строкой не может быть более 1;

2) Если разница меньше 0, то на этом месте кончается текущий цикл. Если это первый цикл, то номер столбца равен порядку цикла подгруппы.

3) Порядки циклов всех смежных классов  равны этому числу и это число должно быть делителем порядка группы.

Если при анализе второй строки получим противоречие с этими условиями, то можно вернуться назад для поиска другой таблицы, не продолжая эту. При n1 > 2 значения элементов строк с 3-го по n однозначно определяются второй строкой. Перестановка, соответствующая двум соседним строкам, должна быть той же, что и у первых двух строк. Для таблицы с одним циклом, соответствующей простому числу, мы получим однозначную таблицу умножения:

1

2

3

n

2

3

4

1

3

4

5

2

n

1

2

n-1

Для таблицы  умножения группы порядка 12 при цикличности n1 = 3 первые три строки определятся однозначно:

1

2

3

4

5

6

7

8

9

10

11

12

2

3

1

5

6

4

8

9

6

11

12

9

3

1

2

6

4

5

9

6

8

12

9

11

Если n1 – не простое число, то насчет 3-й и остальных строк пока ничего определенного сказать нельзя, точнее, конкретное решения остальных строк будут не однозначны.

Вывод: внутри простого кластера цикличность каждой строки равна размерности кластера.

Учет этих свойств таблицы умножения может значительно уменьшить время поиска всех таблиц. Для таблицы, внутренний цикл которой равен общему порядку, это уменьшение равно факториалу этого порядка, а уже факториал 6! = 720 раз. Для таблицы, общий порядок которой равен n1·n2, это уменьшение равно . Это уже очень большой выигрыш. Но этот выигрыш гораздо выше, потому что каждая следующая строка тоже состоит из этих же циклических блоков, в некотором другом, но вполне определенном порядке.  По этим n1 строкам мы определим возможную группу как группу порядка n = n1 · n2, но оно не обязано быть группой, полученной как прямое произведение двух групп Gn1 и Gn2 порядка n1 и n2, и даже не обязано быть группой. Но несмотря на такой большой выигрыш, этот метод практически пригоден только до порядка группы 6, дальше время поиска значительно увеличивается и представителей одного класса оказывается очень много.

1.4      Структура соседних кластеров первого ряда таблицы

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

Knij = K1ij + NKn2 - 1,

где Knij – элемент рассматриваемого кластера Kn2,

K1ij – элементы первого кластера таблицы,

NKn2 – минимальное число, или параметр, кластера.

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

Вывод: первый ряд кластеров подобен первому кластеру со смещением на число кластера. Все они циклические с одним направлением.

2      Таблица умножения групп Gn´Gm

2.1      Кластеры и их ряды

Построение первых строк таблицы вышеописанным способом приводит к тому, что вся таблица умножения будет состоять из квадратных кластеров размером n1·n2, и наша дальнейшая задача – построить дальнейшие ряды кластеров. Для дальнейших построений мы каждому кластеру присвоим число, классифицирующее ее. В каждом кластере есть минимальное число, и это число всегда принадлежит множеству {1, n1+1, 2n1+1, … n2n1+1}. Проанализировав этот ряд, можно прийти к двум решениям: это число можно принять равным или минимальному числу кластера (из этого ряда), или множителю n2 этого ряда. Примем второй способ нумерации кластеров и будем писать K1, K2, … при этом надо иметь в виду, что равенство K1 = K2 не означает, что эти кластеры тождественны, а только то, что они принадлежат одному классу. Тогда вся таблица будет соответствовать следующей таблице:

K1

K2

Kn2

K2

Kn2

Замечание: это построение верно для групп Gnm = Gn´Gm. Для других групп может быть и не верно. Например, для диэдров D2n это не верно: кластеры не могут иметь порядок 2, но они могут иметь порядок n.

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

K1

K2

Kn2

K2

K3

K1

Kn2

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

K1

K2

Kn2

K2

K3

K1

K3

K4

K2

Kn2

K1

Kn2-1

Если число n2 – не простое, то насчет 3-го и остальных рядов пока ничего нельзя сказать, точнее, конкретное решения остальных строк будут не однозначны.

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

2.2      Кластерные группы и их ряды

Если число n2 – не простое, то в результате построения этой таблицы мы, возможно, получим еще одно значение для цикла группы: n2 = n21·n22. Общий порядок группы будет равен n = nn21·n22. Все, что мы говорили выше относительно кластерных рядов, можно повторить и на этом уровне, с поправкой на то, что элементарными объектами таблицы будут кластеры, а кластерами – кластерные группы порядка n21. Если n21 будет больше двух, то это, как и в предыдущем случае для цикла n1, будет означать, что групповые кластерные ряды с 3-го по n21 будут определены однозначно. При этом таблица с учетом этого примет вид:

K1

K2

Kn21

Kn2

K2

K3

K1

Kn2-1

Kn21

K1

Kn21-1

Kn2

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

Таким образом можно пойти дальше и ввести понятие кластерных рядов большего уровня, равное номеру числа цикла k в разложении первых двух строк и последующих уровней кластерных групп текущей таблицы умножения группы порядка n на множители n = n1·n2·…·nk·… Эти отношения можно применить для оптимизации построения таблиц умножения группы.

2.3      Построение второго и остальных рядов кластерного ряда

Структура второго кластерного ряда подобна второму ряду таблицы умножения, т.е. она представляет циклическую перестановку первого ряда с точностью до класса кластера. Но внутри кластера таблица умножения свободна. Нам необходимо определить некий порядок, который поможет выбрать из них представителя. Этот порядок определяется опять же эквивалентными перестановками строк и столбцов, и эти условия прежние – первая и вторая строка таблицы (а не кластера!) инвариантны. Но структура первой и второй строки кластера не обязана быть инвариантной. Но первое условие приводит к тому, что кластер будет инвариантен с точностью до циклических перестановок элементов кластера с перенумерацией. Рассмотрим последовательно первый, второй, и т.д. кластеры второго ряда.

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

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

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

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

2.4      Построение третьей и последующих строк таблицы

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

2.5      Общий алгоритм

Таким образом, имеем алгоритм построения группы, полученной прямым произведением групп меньшего порядков:

1.      Строим латинский квадрат.

2.      Выбираем цикличность второй строки, второго кластерного ряда и т.д.

3.      Автозаполняем первый кластер.

4.      Автозаполняем первый кластерный ряд.

5.      Заполненяем остальные кластерные ряды и группы кластеров.

6.      Проверяем на выполнение аксиомам группы.

7.      Анализируем другие свойства группы.

3      Таблица умножения "эксклюзивных" групп Gn

Показанный выше алгоритм позволяет построить все группы, получаемые как прямое произведение групп меньших порядков. Но не все группы можно получить этим способом. Кластеризовать можно только группы, которые можно разделить на классы смежности. Первый такой пример – диэдры. Диэдры Dn при n > 2 не могут быть получены как прямое произведение двух групп, но можно разделить на 2 класса смежности. Таблица умножения для диэдров состоит из 4-х кластеров размеренности n:

K1

K2

K2*

K1*

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

1

2

3

4

5

6

2

3

1

5

6

4

3

1

2

6

4

5

4

6

5

1

3

2

5

4

6

2

1

3

6

5

4

3

2

1

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

1

2

3

4

5

6

7

8

2

3

4

1

6

7

8

5

3

4

1

2

7

8

5

6

4

1

2

3

8

5

6

7

5

6

7

8

3

2

1

4

6

7

8

5

2

3

4

1

7

8

5

6

1

4

3

2

8

5

6

7

4

1

2

3

Из таблицы видно, что она состоит тоже из кластеров порядка 4. Несмотря на то, что 8 = 2´2´2, мы не можем использовать кластеры порядка для создания таблицы умножения.

Таблицу умножения тетраэдра уже нельзя разделить нам кластеры, потому что тетраэдр не имеет классов смежности несмотря на то, что 12 = 2´2´3. Для нее имеем следующую таблицу умножения:

1

2

3

4

5

6

7

8

9

10

11

12

2

3

1

5

6

4

8

9

6

11

12

9

3

1

2

6

4

5

9

6

8

12

9

11

4

7

10

12

8

2

6

11

3

9

5

1

5

8

11

10

9

3

4

12

1

7

6

2

6

9

12

11

7

1

5

10

2

8

4

3

7

10

4

8

2

12

11

3

6

5

1

9

8

11

5

9

3

10

12

1

4

6

2

7

9

12

6

7

1

11

10

2

5

4

3

8

10

4

7

2

12

8

3

6

11

1

9

5

11

5

8

3

10

9

1

4

12

2

7

6

12

6

9

1

11

7

2

5

10

3

8

4

Только верхний ряд кластеризован, остальные устроены довольно сложным образом. Верхний ряд может быть выстроен кластерами порядка 2 и 3.

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

 

 

 

Ссылка на этот материал: konechnyye_gruppy_tablica_umnozheniya.htm)

- - - ВЫ МОЖЕТЕ ОСТАВИТЬ ПЕРВЫЙ КОММЕНТАРИЙ! - - -


Введите логин:      Введите эл.адрес:

Введите пароль:    Ваш телефон:        

Введите Ваш комментарий:
Формулы:

(возможно использование BB-кодов для оформления комментария и кодов LaTeX для ввода формул)

Решите пример: 70 to divide on 14 equally:

---Load files---
Сегодня - 18_08_2019
Время переоткрытия сайта 17 ч 59 м по Гр.
Календарь
на АВГУСТ месяц 2018 г.
Пн Вт Ср Чт Пт Сб Вс
      1; 2; 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31 1
(8 431)

---Load files---

---Load files---

© Все права защищены 2017-2019 При использовании материалов сайта ссылка на http://lowsofphisics.ru обязательна.

В НАЧАЛО
КОММЕНТ
В КОНЕЦ
U:14 V:25
Уникальных посетителей: 14 Просмотров: 25