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

Задача 1 (ШАД). В ШАД поступили всего 10 студентов. Кураторы решили ограничить число доступных курсов и придумали набор простых правил:

  1. На каждый курс должно быть записано нечётное число студентов;

  2. Для любой пары курсов число студентов, записанных одновременно на оба, чётно.

Какое максимальное число курсов можно прочитать по новым правилам?

Переведём условие на язык множеств. Пусть A=\{1,\ldots,n\} (n=10)– множество студентов, A_1,\ldots,A_m\subseteq A – подмножества студентов, записанных на курсы 1,\ldots,m. Нужно найти максимальное число m подмножеств в A, мощности которых нечётны, а мощности попарных пересечений чётны.

Начнём с комбинаторных соображений. Несложно построить пример с n одноэлементными подмножествами. При чётном n подходит и система из n подмножеств из n-1 элементов. Можно построить и другие системы из n подмножеств. Но можно ли построить больше n подмн��жеств? Приведём набросок комбинаторного рассуждения. Будем выбирать подмножества последовательно. Подмножество A_1 может быть любым подмножеством из нечётного числа элементов. Всего таких

C_n^1+C_n^3+C_n^5+\ldots=2^{n-1}.

Пусть подмножество A_1 выбрано и состоит из n_1 элементов. Тогда A_2 будем строить по частям: A_2\cap A_1 и A_2\cap \overline{A_1} (чертой мы обозначаем дополнение до всего множества A). В качестве A_2\cap A_1 можно взять любое подмножество в A_1 чётной мощности – всего таких

C_{n_1}^0+C_{n_1}^2+C_{n_1}^4+\ldots=2^{n_1-1}.

Аналогично, множеством A_2\cap \overline{A_1} может быть любое подмножество в \overline{A_1} нечётной мощности – всего таких 2^{n-n_1-1}. Итого, множество A_2 можно выбрать

2^{n_1-1}\cdot 2^{n-n_1-1} =2^{n-2} \;\;\text{способами.}

Попробуем действовать дальше аналогично. Множество A_3 тоже будем строить "по кускам", выбирая подмножества в A_1\cap A_2, A_1\cap \overline{A_2}, \overline{A_1}\cap A_2, \overline{A_1}\cap \overline{A_2}.

Первое может быть любым из 2^{|A_1\cap A_2|} подмножеств, а для каждого из остальных уже есть ограничение на чётность мощности (в зависимости от чётности мощности выбранного подмножества в A_1\cap A_2). Казалось бы, надо вычитать 1 три раза и в итоге получим

2^{|A_1\cap A_2|} \cdot 2^{|A_1\cap \overline{A_2}|-1}\cdot 2^{|\overline{A_1}\cap A_2|-1}\cdot 2^{|\overline{A_1}\cap \overline{A_2}|-1}=2^{n-3}.

Вроде бы ясно, что для n-го подмножества будет 2^{n-n}=1 вариант. Однако аккуратно дожать эту идею не так просто. Ошибка возникает уже на третьем шаге. Дело в том, что если подмножества A_1 и A_2 взаимно дополняют друг друга, то есть A_2=\overline{A_1}, то подмножество A_3 выбрать нельзя вовсе: оно должно пересекаться по чётному числу элементов как с A_1, так и с A_2, а тогда его мощность чётна. Ошибка в рассуждении выше в том, что количество подмножеств из чётного числа элементов в k-элементном равна 2^{k-1}, кроме случая k=0.

На помощь приходят матрицы. Напрашивается рассматривать матрицы над полем \mathbb Z_2=\{0,1\} классов вычетов по модулю 2 (1+1=0 в \mathbb Z_2).
Рассмотрим матрицу

B=(b_{ij})\in \mathbb M_{m\times n}(\mathbb Z_2),;b_{ij}=1\iff j\in A_i.


Условие ,,Все множества A_i имеют нечётную мощность, а их попарные пересечения имеют чётную мощность'' равносильно условию B B^\top=E\in \mathbb M_m(\mathbb Z_2), откуда следует, что m\leq n, так как m=rk\; E=rk \;(BB^\top)\leq rk\; B\leq \min(m,n).

Итак, в случае n студентов ответ: n.

Задача 2 (фольклор). Квадратная таблица размера n\times n, где n – чётное число, заполнена буквами a и b так, что любые две строки отличаются ровно в половине позиций. Докажите, что столбцы таблицы обладают тем же свойством.

Начнём с примеров. При n=2 условию удовлетворяют в точности таблицы, в которых ровно одна буква a, либо ровно одна буква b. Например,

\begin{pmatrix} a & b \\ b & b \end{pmatrix}.

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

\begin{pmatrix} a & a & a & a \\ a & a & b & b \\ a & b & a & b \\ a & b & b & a \end{pmatrix}.

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

При больших n перебор уже становится невозможным. Более того, описать все n, при которых такая матрица существует, – открытая проблема!

Матрицы, о которых идёт речь, только с числами \pm 1 вместо букв a и b, называются матрицами Адамара. Не очень сложно показать, что порядок n такой матрицы кратен 4, Гипотеза Адамара состоит в том, что для любого n, кратного 4, матрица Адамара существует.
Для n\leq 2000 она подтверждена, кроме 12 значений n, для которых ответ неизвестен.
Существуют рекуррентные способы построения матриц Адамара для всех n=2^k.

Матрицы Адамара широко применяются в математике и технике, в частности, в теории кодирования, ЕСС-памяти, в рентгеновских телескопах.

Вернёмся к задаче и решим её в одну строчку. Условие задачи на строки матрицы A из \pm 1 равносильно попросту ортогональности строк относительно стандартного скалярного произведения в \mathbb R^n:

(X,Y)=X^\top Y=x_1y_1+\ldots x_ny_n,\;\;X=(x_1,\ldots,x_n)^\top\in \mathbb R^n,\, Y=(y_1,\ldots,y_n)^\top\in \mathbb R^n \text{ – столбцы}.

С учётом того, что все строки имеют скалярный квадрат n, получаем матричное равенство AA^\top =nE. Но хорошо известно, что для квадратных матриц

AB=E \implies BA=E. \;\;\;\;\; (1)

Применяя это к матрицам \dfrac{1}{\sqrt{n}}A и \dfrac{1}{\sqrt{n}}A^\top, заключаем, что A^\top A=nE, откуда столбцы матрицы A ортогональны, что и требовалось доказать. Итак, всё решение основано на известном факте (1) .

Модифицируя эту идею попробуйте решить следующую задачу.

Задача 3 (олимпиада кафедры алгебры мехмата МГУ, 2010). В таблице 2010\times 2010 расставлены элементы поля \mathbb Z_3. Известно, что разность любых двух столбцов есть столбец, содержащий поровну элементов 0, 1 и 2. Докажите, что разность любых двух строк является строкой, содержащей поровну элементов 0, 1 и 2.

Автор статьи: Андрей Канунников, к. ф.-м. н., преподаватель ШАД Хелпер.

Статья подготовлена при поддержке ШАД Хелпер.