?

Log in

No account? Create an account
теорема бонди - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

теорема бонди [окт. 21, 2015|06:52 pm]
Anatoly Vorobey
[Tags|]

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

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

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

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

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

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

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

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

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

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

Comments:
From: nighteagleowl
2015-10-21 04:15 pm
(1) число активных столбцов меньше или равно числу ребер в графе.

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

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

Что тогда такое не активные рёбра?
(Ответить) (Thread)
[User Picture]From: avva
2015-10-21 04:19 pm
Один и тот же столбец может соединять строки 1 и 2, и одновременно строки 3 и 4. В терминологии этого доказательства это означает, что есть два разных ребра: одно соединяет 1 и 2, другое 3 и 4. Но эти два ребра основаны на одном столбце (или являются одним и тем же столбцом - можно по-разному это сформулировать, но суть, я надеюсь, понятна).

Предположим, что есть такая ситуация, и больше вообще никаких ребер нет. Тогда есть 1 активный столбец и 2 ребра.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: alaev
2015-10-21 05:43 pm
- прямой чисто логический вывод ее из принципа Дирихле труден
Интересно, что такое прямой чисто логический вывод одной теоремы из другой?
(Ответить) (Thread)
From: (Anonymous)
2015-10-21 09:31 pm
На прологе )
(Ответить) (Parent) (Thread)
[User Picture]From: vanja_y
2015-10-21 05:44 pm
Матрицы должны иметь элементы из F2?
(Ответить) (Thread)
[User Picture]From: avva
2015-10-21 10:48 pm
Нет, необязательно, зачем? Док-во работает для матриц с любыми элементами, лишь бы между ними были отношения идентичности/неидентичности.
(Ответить) (Parent) (Thread)
[User Picture]From: brandt1
2015-10-21 06:12 pm
Красиво! По какому принципу вы отыскиваете такие теоремы (если таковой существует)? И ваше изложение, судя по поверхностному взгляду на указанный по ссылке текст, является его блестящей в методическом плане переработкой.
(Ответить) (Thread)
[User Picture]From: avva
2015-10-21 10:48 pm
Я читаю math.stackexchange.com время от времени и иногда отвечаю там. Увидел сегодня вопрос об этой теореме, почему она верна интуитивно. Я о ней не знал, пошел читать, понравилось.

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

Не упустите красивое геометрическое док-во в комменте прямо под вашим.
(Ответить) (Parent) (Thread)
[User Picture]From: hyperpov
2015-10-21 08:52 pm
Сложная теорема, целых 17 минут доказывал.

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

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

Edited at 2015-10-21 20:59 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2015-10-21 10:45 pm
Здорово, очень красиво! Спасибо!
(Ответить) (Parent) (Thread)
[User Picture]From: the_aaa13
2015-10-21 09:04 pm
Я не понял утверждения. В матрице
0 0 0
0 0 1
0 0 2
Все строки попарно отличаются друг от друга хотя бы в одном столбце?
(Ответить) (Thread)
[User Picture]From: francis_drake
2015-10-21 09:22 pm
Да, и найдётся такой столбец, который можно убрать, чтобы свойство сохранилось.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: avva
2015-10-22 11:09 am
Еще одно доказательство, на этот раз пользующееся свойствами порядка.

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

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

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

Edited at 2015-10-22 11:11 (UTC)
(Ответить) (Thread)
[User Picture]From: brandt1
2015-10-23 08:41 am
Т.е. это решение дает алгоритм, отличный от простого перебора, как найти столбец, после удаления которого все еще есть активные столбцы. Насколько он более эффективен?
(Ответить) (Parent) (Thread)
[User Picture]From: brandt1
2015-10-23 08:32 am
Идея геометрического доказательства, конечно, замечательная и, по-видимому, лучше вскрывает причины данного явления. Доказательство менее элементарно и несколько небрежно изложено. Позволю себе изложить, как я его понял. Строки матрицы - точки не в в n-мерном евклидовом, а в (n-1)-мерном аффинном пространстве. "Соединящее две точки ребро" - это не ребро-столбец, введенное avva, а вектор в n-мерном евклидовом пространстве, соответствующем данному аффинному, концами которого являются эти точки-строчки. Таким образом, если допустить, что для каждого i найдутся 2 строчки, совпадающие после удаления i-го столбца, то оказыватеся, что мы нашли n ортогональных векторов, лежащих в n-1-симплексе, что невозможно. Можно обойтись без понятия симплекса, сказав, что эти вектора лежат в n-1 -мерном пространстве, натянутом на пространство из n-1 векторов, полученном, если одну точку зафиксировать и соединить ее с остальными n-1 точками.
(Ответить) (Thread)