Циркулянты квадратных матриц и способы их формирования

Циркулянты квадратных матриц и способы их формирования

УДК 519.6

ЦИРКУЛЯНТЫ КВАДРАТНЫХ МАТРИЦ И СПОСОБЫ ИХ ФОРМИРОВАНИЯ И.П. Кадиев, П.А. Кадиев

Дагестанский государственный технический университет

Аннотация

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

Ключевые слова

циклические сдвиги, п-множества, циркулянт, пхп -матрица, комбинаторная конфигурация, системы представительства История статьи:

Дата поступления в редакцию: 22 февраля 2017

Дата принятия к печати: 26 февраля 2017

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

Известны комбинаторные конфигурации в виде квадратных матриц, полученные перестановками элементов конечного множества, называемые «циркулянтные матрицы» или просто «циркулянты». Они представляют собой пхп - матрицы, строки и столбцы которых представляют собой подмножества, образованные из элементов некоторого п-множества. Эти подмножества образованы перестановками элементов исходного п-множества путем циклических его сдвигов по формуле: первая строка матрицы является п-множеством, каждая следующая строка образована путем циклических сдвигов на один шаг в одну и ту же сторону по отношению к вышестоящей строке, при которых элементы строки, находящиеся на первых позициях в строке, перемешаются в конец строки при сдвигах влево, а находящиеся на последних позициях, перемещаются на первые позиции при циклических сдвигах вправо. Ниже, приведен циркулянт п-множества С= (С1,С2,С3,С4,С5).

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

С С С С С

1 2 3 4 5

С С С С С

2 3 4 5 1

С = С С С С С

Ц 3 4 5 1 2

С С С С С

4 5 12 3

С С С С С

5 12 3 4

Рис. 1

Необходимо отметить, что одним из первых известных циркулянтов являются предложенные Л. Эйлером конфигурации, известные как «латинские квадраты». Название конфигурации было предопределено тем, что в качестве исходного п-множества Эйлером было использовано множество символов латинского алфавита. В каждой строке и в каждом столбце латинских квадратных конфигураций находятся все символы латинского алфавита.

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

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

Общий алгоритм циклических сдвигов строк исследуемых матриц при перестановке их элементов, подобный сдвигам при формировании циркулянтов, может быть сформулирован как циклические сдвиги 1 -ой строки на (1 - 1) позицию в одну и ту же сторону, где 1 принимает значения от 1 до п. Образованная при этом конфигурация В1 для матрицы В5х5 приведена ниже на рис. 2.

В

5Х5

В11В12В13В14В15 В21В22В23В24В25 В31В32В33В34В35 В41В42В43В44В45 В51В52В53В54В55

Вт =

В11В12В13В14В15 В22В23В24В25В21 В33В34В35В31В32 В44В45В41В42В43 В55В51В52В53В54

Рис. 2

Циркулянтыквадратных матриц испособыихформирования

Из рис. 2 видно, что при циклических сдвигах сток пхп - матрицы, по указанному выше алгоритму, форм ируютсяконфикурациа,лкоторых:

- первый столбец образуютэлементы главной диагонали исходной матрицы;

- вторые индексы элементов каждого из столбцов принимают значения от 1 до п;

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

Обш,иаакгоритмцакличесаихсдвигов столбцов матрицы сохраняется таким же, как и для строк: каждыквоош сгилОецциооическичдвогалнхяик ()-1бпозицию воикуа туже сторону, при этом ) принимает значения от 1 до п. Полученная при этом конфигурация В2 приведена на рис. 3.

Во

В11В22В33В44В55

В21В32В43В54В15

В31В42В53В14В25

В41В52В13В24В35

В51В12В23В34В45 Рис. 3

Из рис. 3следует,что циклические сдвигистолбцов,поприведенномуалгоритму, формируют конфигурации, в которых:

- первую строку образуют элементы главнойдиагонали исходной матрицы;

- первыеиндексыэлементовстрокиэтойконфигурации принимаютзначенияот 1до п;

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

Циклические сдвиги строк и столбцов в пхп - матрице могут быть выполнены в последовательности «строки - столбцы» или «столбцы-строки». Результат выполнения циклических сдвигов в последовательности «строки - столбцы» В12 приведен на рис.4.

В11В23В35В42В54

В12 -

В22В34В41В53В15 В33В45В52В14В21 В44В51В13В25В34 В55В15В24В31В45

Рис. 4

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

2. Индексы элементов в строках и столбцах принимают значения от 1 до n;

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

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

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

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

ЛИТЕРАТУРА

1. Андерсон Джеймс. Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: «Вильямс», 2006. — С. 960. — ISBN 0-13-086998-8.

2. Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975.

3. Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 с.

3. Липский В. Комбинаторика для программиста. — М.: Мир, 1988. — 213 с.

4. Раизер Г. Дж. Комбинаторная математика. — пер. с англ. — М., 1966.

5. Райгородский А. М. Линейно-алгебраические и вероятностные методы в комбинаторике. — Летняя школа «Современная математика». — Дубна, 2006.

6. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980. — 476 с.

7. Риордан Дж. Введение в комбинаторный анализ. — пер. с англ. — М., 1963.

8. Р. Стенли. Перечислительная комбинаторика = Enumerative Combinatorics. — М.: «Мир», 1990. — С. 440. — ISBN 5-03-001348-2.

9. Р. Стенли. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции = Enumerative Combinatorics. Volume 2. — М.: «Мир», 2009. — С. 767. — ISBN 978-503-003476-8.

10. Кемени Дж. и др. Введение в конечную математику. - М: Изд.ИЛ. 1963, 346с.

11. Тараканов В.Е. Комбинаторные задачи и (0,1) - матрицы. - М.: Наука, 1985, 193 с.

12. Кадиев И.П., Кадиев П.А. Циклические методы индексной сортировки элементов массивов данных. Вестник ДГТУ. Технические науки, №36, 2015, с.79-84

13. Нефедова И.В. Тестирование кода при переносе базы данных// Системные технологии, - 2016, -№3(20), - С. 96-100

Индексные методы формирования таблиц c магическими свойствами

Просьба ссылаться на эту статью следующим образом:

И.П. Кадиев, П.А. Кадиев. Циркулянты квадратных матриц и способы их формирования // Системные технологии. — 2017. — № 22. — С. 57—61

THE SKEW-CIRCULANTS ARE OBTAINED SQUARE MATRICES AND METHODS FOR THEIR FORMATION I.P. Kadiev, P.A. Kadiev

Abstract

The paper proposed a combinatorial configurations defined by the authors as «skew-circulants are obtained square matrices», in contrast to existing configurations, known as «skew-circulants are obtained» or circulante matrix. Skew-circulants are obtained, the configuration obtained by cyclic shifts of the individual elements of the finite set, with pre-picture obtained by shifts of the subsets in the form of configuration lines - the circus Lantau matrix. The skew-circulants are obtained the matrix, in contrast to the «circulant», is a configuration obtained by cyclic shifts of the elements in the rows and columns of square matrices by a certain, in the proposed method.

Key words

cyclic shifts, n -sets, circulant, n x n -

matrix, com-biatora configuration of the

system representation

Date of receipt in edition:

22 February 2017

Date of acceptance for printing:

26 February 2017

УДК 519.6

ИНДЕКСНЫЕ МЕТОДЫ ФОРМИРОВАНИЯ ТАБЛИЦ С МАГИЧЕСКИМИ СВОЙСТВАМИ И.П. Кадиев, П.А. Кадиев

Дагестанский государственный технический университет

Аннотация

В статье предложены индексные алгоритмы формирования класса комбинаторных конфигураций, известных как числовые магические квадраты, у которых суммы чисел в стоках и столбцах равны магическому числу. В основе алгоритмов циклические сдвиги строк и столбцов исходных конфигураций - квадратов, заполненных числами от1 до п,по приведенному в работе алгоритму: каждая 1-я строка сдвигается циклически в одну и ту же сторону на ( 1-1)- позицию, после чего в образовавшейся конфигурации каждый л'-ый столбец сдвигается циклически в одну и ту же сторону на ( '-1) -позицию

Ключевые слова

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

Дата поступления в редакцию: 15 февраля 2017

Дата принятия к печати: 20 февраля 2017

Введение. Издревле известны математические конфигурации, известные как магические или волшебные квадраты. Они представляют собой пхп - таблицы, ячейки которых заполнены числами, расположенными таким образом, что сумма чисел в каждой строке, в каждом столбце и диагоналях равны числу, называемому магической константой. Для магических квадратов это число определяется по известной формуле [1]:

М(п) = п(п2+1)/2