Суровый канадский лесоруб

[xaxam]

Вдали от столичной суеты

Возьмём квадратную матрицу размера n x n и заполним её случайным образом плюс-минус единицами. Определитель такой матрицы - целое число между -n! и +n!. С какой вероятностью он окажется нулём? Ответ зависит от n: при n=1 ответ - нуль, при n=2 эта вероятность равна 1/2, если n=3, то посчитайте сами ;-)

Для произвольного n матрица будет вырожденной, если у неё есть две одинаковых строки или два одинаковых столбца. Это случается с вероятностью n(n-1) x 2^-n(1+...), - многоточие здесь и ниже означает выражение, стремящееся к нулю при больших n (в данном случае это вероятность одновременного наступления двух таких маловероятных событий). Верно ли, что это - правильная асимптотика, и ответ имеет вид (1/2+...)ⁿ? Казалось бы, с чего? помимо перечисленных причин для вырождения, есть масса более сложных линейных зависимостей, неужели они все вместе дают пренебрежимую поправку?

Задачу начали ковырять больше полувека назад, - первым (нетривиальным!) результатом было то, что вероятность убывает до нуля с ростом n. После этого почти тридцать лет было потрачено на то, чтобы понять, с какой скоростью она убывает: прорывной результат был получен в 1995-м и утверждал, что вероятность убывает быстрее, чем некоторая убывающая геометрическая прогрессия. Но какая прогрессия! Было доказано, что ответ стремится к нулю не медленнее, чем (0.999+...)ⁿ. Константу 0.999 удалось затем уменьшить, сначала до 0.75, потом до корня из двух пополам, 0.7071...

И только совсем недавно, в 2018-м, удалось-таки додавить жадину и доказать, что в самом деле там, где должна стоять не больше, чем половина, можно поставить ровно половину. Комментарии относительно того, с какими нетривиальными явлениями это связано, можно найти у Гиля Каллаи, чей пост я и попытался воспроизвести выше.

Для читателей "ХВ" будет небезынтересно узнать, кто же этот супермэн, которого спящая царевна-матрица ждала 50 лет.

Знакомьтесь: Константин Тихомиров, assistant professor (ассистент? скорее старший преподаватель по российским понятиям, короче, под-доцент) в Georgia Tech, Грузинский Политех. Примечательно, как Костя туда попал:

• Диплом - 2008, Самарский (б. Куйбышевский) университет, прикладная математика и информатика;
• к.ф.-м.н., 2011, Самарский ГУ (что означает, что он защищался в Воронеже, - я не понимаю, Воронеж - тоже заметное место на математической карте России).
• Ph. D., 2016, University of Alberta, Canada. Я затрудняюсь подобрать соответствующий российский эквивалент. Омский универ? Томский? Красноярский?
• Постдок в Принстоне (2016-2018), визитёр-постдок в Беркли (4 месяца).

Ни мехматов, ни вышек, ни гарвардов в анамнезе. Дерзайте, девушки и юноши!

Comments

[lxe]

При n=1 и единственном элементе, не равном 0, детерминант всегда ненулевой, нет?

[xaxam]

Да. См. испр.

Заинтересованно

[malobukov]

А каково практическое значение этого элегантного результата? Из него что-то важное следует, как из ЦПТ? Или где-то используются такие матрицы и надо знать, насколько часто они вырождаются?

Re: Заинтересованно

[xaxam]

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

Пост Каллаи (по ссылке) содержит некие комментарии, адресованные профессионалам, - в частности, Гиль пишет, что это проявление определённого явления, - guaranteed cancellation phenomenon (GCP), которое встречается в других трудных задачах. В частности, GCP ответственна за справедливость гипотезы Римана и теоремы о распределении простых чисел. Насколько это сходство внутреннее, а насколько внешнее - уж точно не мне судить.

[cjelli]

A^-n стремится вроде, к бесконечности, а не к нулю с ростом n и A < 1.

[xaxam]

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