теорема бонди

[avva]

Неожиданно красивая теорема Бонди (Bondy, 1972). Пусть есть квадратная матрица, в которой все строки попарно отличаются друг от друга хотя бы в одном столбце. Тогда из нее можно удалить один столбец, так что в оставшейся матрице все еще все строки попарно отличаются. Можно попробовать придумать контрпример для матрицы 3x3, чтобы убедиться наглядно на уровне интуиции, почему контрпримеры не работают и как это получается.

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

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

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

(1) число активных столбцов меньше или равно числу ребер в графе.

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

(2) число ребер меньше числа вершин n.

Соединяя (1) и (2), получаем то, что мы хотели доказать.

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

Update: красивое геометрическое доказательство hyperpov в комментариях, не пропустите!

Comments

[nighteagleowl.livejournal.com]

(1) число активных столбцов меньше или равно числу ребер в графе.

А как оно может быть строго меньше?!

Это бы значило что есть рёбра, т.е. (по определению ребра) что есть соединяющий столбец т.е. (по определению соединяющего столбца) что есть две строки, в которых при удалении столбца i все оставшиеся элементы одинаковы. Но ведь раз есть ребро. то оно соединяет какую-то пару вершин-строк, а значит (по определению активности) оно активно.

Что тогда такое не активные рёбра?

[avva.livejournal.com]

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

Предположим, что есть такая ситуация, и больше вообще никаких ребер нет. Тогда есть 1 активный столбец и 2 ребра.

[nighteagleowl.livejournal.com]

Спасибо! Второй уточняющий вопрос - правильно ли я умозаключаю из определения "соединены ребром" => между парой вершин не может быть более одного ребра (иначе про него мы бы не могли сказать 'соединяет'; если в строках 2 и более различных столбца, то на графе они вообще соединены не будут). Следовательно в компонентах связности с циклами - минимум 3 вершины.

[avva.livejournal.com]

Да, совершенно верно.

[alaev.livejournal.com]

- прямой чисто логический вывод ее из принципа Дирихле труден
Интересно, что такое прямой чисто логический вывод одной теоремы из другой?

[(Anonymous)]

На прологе )

[avva.livejournal.com]

Если мы обозначим через a_ij элемент матрицы на месте i,j, то утверждения типа "строки попарно отличаются" можно записать в виде длинной булевой формулы, использующей только стандартные логические операторы (NOT AND OR) и отношения типа a_ij=a_kl, a_ij!=a_kl. Все утверждение теоремы тоже можно записать в виде еще более длинной формулы, и тогда эта очень длинная формула будет тавтологией.

Поскольку это тавтология, у нее есть доказательство из аксиом логики высказываний. Это доказательство "чисто логическое" в том смысле, что кроме свойств равенства и неравенства объектов, в нем не используется никакая математика, никакие свойства элементров матриц, и даже не используются кванторы существования/всеобщности, а только простая манипуляция булевых предикатов. Но это доказательство очень длинное. Если же принять принцип Дирихле (тоже формулируемый как определенная булева формула) за аксиому, т.е. позволить им пользоваться "бесплатно", то док-во теоремы Бонди становится сильно короче. Но все еще остается довольно длинным. Этот факт, говоря очень упрощенно и туманно, соответствует нашей интуиции в том смысле, что мы не видим "очевидного" док-ва теоремы Бонди в том смысле, в каком принцип Дирихле для нас "очевиден".

[alaev.livejournal.com]

Понятно, спасибо.

- говоря очень упрощенно и туманно

Да, сама идея измерять сложность доказательства длиной его вывода в ИВ кажется весьма туманной. Как следует из сказанного, вывод принципа Дирихле тоже довольно длинный, особенно при больших n, хотя его очевидность кажется очевидной (и не зависящей от n).

Если при этом мы перейдём к ИП и позволим себе использовать аксиомы теории множеств, или хотя бы индукцию и некоторые свойства натуральных чисел, доказательство действительно станет коротким, и вдобавок не зависящим от n (если навесить квантор по n).

[mirdin.livejournal.com]

Кстати, обратите внимание, что доказательство через геометрическое представление от hyperpov, по сути сводит теорему к принципу Дирихле.

[avva.livejournal.com]

Разве? Честно говоря, не понимаю почему, можете объяснить подробнее? Ведь то, что 10 ортогональных векторов не умещаются в 9-мерном пространстве нетривиально использует алгебру, свойства поля...

[mirdin.livejournal.com]

Эм. Мне, честно говоря, казалось это достаточно очевидно, когда я это писал... Хотя при здравом размышленни становится понятно, что все не так тривиально.

[(Anonymous)]

то, что 10 ортогональных векторов не умещаются в 9-мерном пространстве нетривиально использует алгебру, свойства поля...

I have the impression that all this complexity (properties of fields, algebra etc.) may be compartmentalized into the definition of "one cage contains one rabbit" in terms of the number of orthogonal vectors in n dimensions.

[avva.livejournal.com]

Хмм, я не очень понимаю, как это может выглядить.

[janatem.livejournal.com]

А как тогда с квантором по размеру матрицы? Его придется вынести за рамки доказательства, то есть для каждого размера строить свое доказательство. Это как-то неэстетично, да и нельзя уж будет сказать, что существует чисто логическое доказательство исходного утверждения.

[vanja-y.livejournal.com]

Матрицы должны иметь элементы из F₂?

[avva.livejournal.com]

Нет, необязательно, зачем? Док-во работает для матриц с любыми элементами, лишь бы между ними были отношения идентичности/неидентичности.

[brandt1.livejournal.com]

Красиво! По какому принципу вы отыскиваете такие теоремы (если таковой существует)? И ваше изложение, судя по поверхностному взгляду на указанный по ссылке текст, является его блестящей в методическом плане переработкой.

[avva.livejournal.com]

Я читаю math.stackexchange.com время от времени и иногда отвечаю там. Увидел сегодня вопрос об этой теореме, почему она верна интуитивно. Я о ней не знал, пошел читать, понравилось.

Да, в статье Бонди теорема сформулирована в терминах подмножеств, что то же самое, что 0-1 матрицы. Но поскольку в оригинальном вопросе речь шла о любых матрицах, я решил переформулировать док-во для этого случая и постараться написать его как можно понятнее.

Не упустите красивое геометрическое док-во в комменте прямо под вашим.

[hyperpov.livejournal.com]

Сложная теорема, целых 17 минут доказывал.

Переведем утверждение на геометрический язык. Строки матрицы - точки в n-мерном евклидовом пространстве. По условию они попарно различны. Две строки совпадают после вычеркивания i-го столбца = проекции соответствующих точек вдоль i-го координатного направления совпадают. Иначе гворя, соединяющее их ребро имеет направление i-го базисного вектора.

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

[avva.livejournal.com]

Здорово, очень красиво! Спасибо!

[janatem.livejournal.com]

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

[avva.livejournal.com]

Согласен, но есть простая "жульническая" поправка: мы заменяем все элементы матрицы числами от 1 до n^2, сколько понадобится (естественно, сохраняя равные элементы равными). На истинность утверждения теоремы это не влияет.

[hyperpov.livejournal.com]

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

[edd-l.livejournal.com]

То есть, для n=3 теорема Бонди это теорема о трёх мухах: "Через согнанных с поверхности стола мух по прежнему в любой момент можно провести плоскость" с замечанием, что это плоскость-поверхность, через них проведённая, или по прежнему "не имеет протяжённости" по высоте, или теперь уже по длине, или по ширине (или по нескольким координатам сразу), и, соответственно, эту лишнюю координату можно убрать без опасности мухослипания.

[the-aaa13.livejournal.com]

Я не понял утверждения. В матрице
0 0 0
0 0 1
0 0 2
Все строки попарно отличаются друг от друга хотя бы в одном столбце?

[francis-drake.livejournal.com]

Да, и найдётся такой столбец, который можно убрать, чтобы свойство сохранилось.

[(Anonymous)]

Ваше утверждение звучит более математично, чем у автора блога. Можно Машку за ляшку.

[francis-drake.livejournal.com]

Набежали,

напоминает

[(Anonymous)]

Из Литтлвудовской Матсмеси:

- Но, учитель, предпополижим что X _не_ есть число овец.

Re: напоминает

[francis-drake.livejournal.com]

набежали.

[fbpa.livejournal.com]

Поддержу товарища с матрицей

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

[francis-drake.livejournal.com]

Мне кажется, это вопрос привычки к жаргону. Если слово "любой" не написано, то вчитывать его в текст в сообществе не принято.

[fbpa.livejournal.com]

Странно, на этой неделе с математиком общалась из МГУ, все было ровно наоборот.

[(Anonymous)]

А где написано, что количество строк должно быть больше двух?
0 0
0 1

[avva.livejournal.com]

Да, и если удалить первый столбец, то они все еще будут попарно различаться, как и требуется.

[avva.livejournal.com]

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

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

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

Это утверждение очевидно для соседних строк, потому что для каждой пары соседей мы выбрали различающий столбец. Теперь представим себе любые две строки, например i < j, и посмотрим на все различающие столбцы, которые мы выбрали между ними - столбец, который отличает i+1 от i, i+2 от i+1 итд. до j от j-1. Из всех этих столбцов посмотрим на самый левый. Я утверждаю, что в нем i-я строка отличается от j-й. Почему? Во всех столбцах еще левее его эти строки совпадают (иначе мы бы выбрали один из них по дороге, мы всегда стремились выбрать самый левый). В самом этом столбце обязаны были быть какие-то изменения от i к j, потому что он один из различающих. Но эти изменения могли идти только "вверх" по порядку, а не вниз, из-за того, как отсортированы строки - чтобы измениться вниз, должен был измениться также один из столбцов левее. Значит, эти изменения не могли вернуться обратно к значению в i.

[brandt1.livejournal.com]

Т.е. это решение дает алгоритм, отличный от простого перебора, как найти столбец, после удаления которого все еще есть активные столбцы. Насколько он более эффективен?

[brandt1.livejournal.com]

Идея геометрического доказательства, конечно, замечательная и, по-видимому, лучше вскрывает причины данного явления. Доказательство менее элементарно и несколько небрежно изложено. Позволю себе изложить, как я его понял. Строки матрицы - точки не в в n-мерном евклидовом, а в (n-1)-мерном аффинном пространстве. "Соединящее две точки ребро" - это не ребро-столбец, введенное avva, а вектор в n-мерном евклидовом пространстве, соответствующем данному аффинному, концами которого являются эти точки-строчки. Таким образом, если допустить, что для каждого i найдутся 2 строчки, совпадающие после удаления i-го столбца, то оказыватеся, что мы нашли n ортогональных векторов, лежащих в n-1-симплексе, что невозможно. Можно обойтись без понятия симплекса, сказав, что эти вектора лежат в n-1 -мерном пространстве, натянутом на пространство из n-1 векторов, полученном, если одну точку зафиксировать и соединить ее с остальными n-1 точками.