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

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

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

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

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

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

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

На прологе )

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

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

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

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

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

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

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

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

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

Edited at 2015-10-21 20:59 (UTC)

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

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

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

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

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

Теперь для каждой строки, начиная со второй, отметим самый левый столбец, в котором она отличается от предыдущей. Всего мы так отметим не более 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)

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

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