Основы комбинаторной теории матриц

Преподаватель: Максаев Артём Максимович
Модуль: 3-4
Кредиты: 3
Формат проведения занятий: очно
Экзамен: в 4-м модуле

Аннотация:  

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

План занятий:
1.   Характеристический и минимальный многочлен матрицы, собственные векторы и значения. Совпадение характеристических многочленов матриц AB и BA. Теорема Гамильтона-Кэли.
2.   Локализация собственных значений матрицы, теорема о кругах Гершгорина.
3.   Псевдообратные матрицы, обратная Мура—Пенроуза. Приложения.
4.   Теоремы Кёнига и Холла в матричном виде. Теорема Биркгофа—фон Неймана.
5.   Неотрицательные матрицы. Неразложимые и примитивные матрицы. Теория Перрона-Фробениуса.
6.   Матрица смежности графа, примитивные графы, экспонента графа.
7.   Матрица инцидентности графа, тотально унимодулярные матрицы.
8.   Собственные значения графов. Оценка Хоффмана.
9.   Матрица Лапласа графа, формула Коши—Бине, подсчет числа остовных деревьев в графе. Алгебраическая связность графа, вектор Фидлера.

Формула оценивания: 0,5 О_сем + 0,5 О_экз (О_сем - работа на семинарах, О_экз - оценка за экзамен)

Пререквизиты:  Базовые знания линейной алгебры и теории графов (все необходимое будет напомнено).

Для кого:  Студенты ФКН.