Матрицы Холла

Министерство образования и науки Республики Татарстан

ГАПОУ «Казанский политехнический колледж»

Исследовательская работа

на тему: «Матрицы Холла»

                                                            Выполнил: студент группы 42

                                                          Пулытаев Ринас Рустемович

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

                                                                  Михайлова Анастасия Олеговна

Казань

2017

Матрицы Холла.

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

         Задача работы: изучить основные теоремы о матрицах Холла по литературе, указанной ниже, и привести новое доказательство теорем и леммы.

Теорема о свадьбах.

        Одна из наиболее известных задач дискретной математики часто формулируется в шутливой форме: имеется множество юношей и множество девушек, и для любых юноши и девушки известно, знакомы ли они. ЗАДАЧА: можно ли женить каждого юношу на знакомой ему девушке? Пусть количество равно m, девушек – n.

      Теорема 1. (Ф.Холла) Задача о свадьбах разрешима тогда и только тогда, когда любые k юношей (k = 1, ..., m) знакомы в совокупности не менее, чем с k девушками.

     Доказательство. Необходимость почти очевидна: если некоторые k юношей знакомы в совокупности меньше, чем с k девушками, то им не хватит невест и задача в целом не разрешима. Достаточность доказывается индукцией по числу юношей. При m = 1 утверждение очевидно. Предположим, что оно верно для числа юношей, меньше, чем m, и докажем его для m юношей. Возможно два случая.

1. Условие теоремы выполнено с " с избытком": любые k юношей (k ≤ m−1) знакомы не меньше, чем с k + 1 девушками. Тогда женим какого-нибудь юношу на знакомой ему девушке. Для остальных m − 1 юношей и n − 1 девушек условие теоремы выполнено и по предположению индукции их можно женить на знакомых девушках.

2. Имеется k юношей (k ≤ m − 1), знакомых в совокупности ровно с k девушками. По предположению индукции этих юношей можно женить. Если мы теперь докажем, что любые p из остальных m − k юношей знакомы не меньше, чем с p из остальных n − k девушек, то и для них по предположению индукции задача будет разрешимой. Допустим противное: среди оставшихся есть p юношей, знакомых в совокупности лишь с q < p девушками из оставшихся. Но тогда во всём множестве юношей имеется k + p юношей, знакомых лишь с k + q девушками, причём k + q < k + p. Это противоречие завершает доказательство теоремы. В следующем параграфе показано, что задача о свадьбах и теорема Холла допускают формулировку и в других терминах. При этом их математическое содержание сохраняется. И каждая из этих формулировок используется в дискретной математике.

Матрица Холла

        В этой главе А=(aij)-матрица размера m×n с элементами 0 и 1. Любой набор элементов a1j1, a2j2,..., amjm,, где вторые индексы попарно различны, называется диагональю матрицы. Если все элементы диагонали равны 1, то говорят, что диагональ положительна. Попросту говоря, положительная диагональ – это набор m единичных элементов матрицы, любые два из которых стоят в разных строках и столбцах.

       Лемма 1. Матрица А содержит положительную диагональ тогда и только тогда, когда любые k строк (k=1,2,…,m) матрицы А образует матрицу, имеющую не менее k ненулевых столбцов.

       Доказательство. Любая (0,1) – матрица А задает задачу о свадьбах, если считать, что юноши перенумерованы числами 1,…, m, девушки – числами 1,…, n. И равенство  aij=1 означает, что i-й юноша знаком с j-ой девушкой. Положительная диагональ a1j1, a2j2,..., amjm  определяет решение задачи: 1-го юношу женим на j-ой девушке и так далее. И наоборот, всякое решение задачи о свадьбах определяет положительную диагональ. Заметим, что j-ая вершина имеет знакомого в множестве {i1, i2,…,ik} юношей тогда и только тогда, когда j-й столбец матрицы, образованный строками  i1, i2,…,ik матрицы А, содержит единицу. Так что у этих k юношей в совокупности ровно столько знакомых девушек, сколько ненулевых столбцов в соответствующей матрице. Теперь уже ясно, что наша лемма – переформулировка теоремы Холла.

       Из доказательства леммы 1 видно, что (0,1) – матрица А содержит положительную диагональ, тогда и только тогда, когда эта матрица задает разрешимую задачу о свадьбах. То есть, задачу, имеющую решение.

       Определение. Пусть А=(aij)- m×n – матрица с элементами 0 или 1. Матрица А называется матрицей Холла, если она содержит положительную диагональ.

       Приведем доказательство леммы 1 в чисто математических (матричных) терминах, не используя «свадебную» терминологию.

       Доказательство. Любая (0,1) – матрица А удовлетворяет условиям Теоремы Холла, если считать, что столбцы перенумерованы числами 1,…m, а строки – числами 1,…,n. И равенство aij=1 означает, что на i-ой строке j-ом столбце стоит 1. Положительная диагональ a1j1, a2j2,..., amjm  определяет решение теоремы Холла. И наоборот, всякое решение теоремы Холла задает положительную диагональ. Пусть j-ый столбец матрицы, образованный строками i1, i2,…,ik матрицы А, содержит единицу. То есть в этих k строках столько единиц, сколько ненулевых столбцов в соответсвующей матрице.

       Теорема 2. Матрица А содержит положительную диагональ ( то есть является матрицей Холла) тогда и только тогда, когда любые k строк (k=1,2,…,n) матрицы А образуют матрицу, имеющую не менее k ненулевых столбцов.

       Доказательство. Пусть (0,1) – матрица А положительная диагональ –

a1j1, a2j2,..., amjm . Рассмотрим подматрицу В, составленную из строк с номерами  i1, i2,…,ik. Подматрица В содержит единицы в столбцах с попарно различными номерами ji1, ji2,…,jik. Следовательно, эти k столбцов подматрицы В – ненулевые.

      Теперь пусть любые k строк  (k=1,2,…,m) матрицы А образует матрицу, имеющую не менее k ненулевых столбцов. Докажем, что матрица А содержит положительную диагональ. Доказательство проведем методом математической индукции по числу m строк матрицы. При m=1 утверждение очевидно. Предположим, что оно верно для матриц, с числом строк  < m, и докажем, его для m×n –матриц.

       Возможны два случая.

1. Условие теоремы выполнено «с избытком»: любые k строк (k≤ m-1) образуют подматрицу, в которой ненулевых столбцов не менее, чем k+1. Тогда выберем какую-нибудь (например, - первую) строку и  какой-нибудь столбец, на пересечении с которым в этой строке стоит единица. Заштрихуем мысленно эту строку и этот столбец. Для  (m-1)×(n-1) матрицы, составленной из незаштрихованных элементов, условие теоремы по-прежнему выполнено и по предположению индукции в ней существует положительная диагональ. Дополнив эту диагональ заштрихованной единицей, получим положительную диагональ в исходной матрице.

2. Имеется k строк (k≤ m-1), образующих подматрицу В, в которой ровно k ненулевых столбцов. Можно считать, что матрица А имеет вид

A=.

       По предположению индукции подматрица В содержит положительную диагональ.

      Докажем, что в матрице D любые p из m-k строк образуют подматрицу, в которой не меньше, чем p ненулевых столбцов. Тогда по предположению индукции можно будет заключить, что D содержит положительную диагональ. Допустим противное: некоторые p строк матрицы D образуют подматрицу, в которой q ненулевых столбцов. Но тогда в матрице А имеется k+p строк, образующих подматрицу, в которой всего k+q ненулевых столбцов, причем k+q. Итак, доказали, что матрица D содержит положительную диагональ.

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

Библиография

1. Альпин Ю.А. Неотрицательные матрицы: учебное пособие для студентов ИММ КФУ.-Казань, Казан. Ун-т, 2015.-58с.
2. Альпин Ю.А. Дискретная математика: графы и автоматы. Учебное пособие