к теореме Кенига
Пусть А - матрица n×m над каким-то полем F. Предположим, что все ненулевые элементы матрицы А можно покрыть r линиями (линия это строка или столбец). Тогда матрица есть сумма r матриц ранга не больше 1 (сосредоточенных каждая в одной линии), так что ранг A не больше r. Обратное неравенство состояло бы в том, что если ранг матрицы A равен r, то все ее ненулевые элементы покрываются r линиями, но это, конечно, не верно. Однако если между ненулевыми элементами нет алгебраических зависимостей (не над исходным полем F, конечно, а над его подполем, порожденным единицей), то утверждение становится верным. Можно, например, считать, что ненулевые элементы матрицы A суть различные буквы, а поле F есть поле рациональных функций (над неким меньшим полем, неважно каким) от этих букв.
В этом случае ранг приобретает ясный комбинаторный смысл: это просто наибольшее число не бьющих друг друга ладей, которых можно поставить на ненулевые элементы матрицы А (из-за отсутствия зависимостей соответствующий минор будет ненулевым).
Таким образом, наше утверждение есть просто известная комбинаторная теорема Кенига, по сути равносильная еще более известной лемме о девушках: если в некоторых клетках матрицы стоят ладьи, то наибольшее число не бьющих друг друга ладей равно наименьшему числу линий, покрывающих все ладьи.
Конечно, теорему Кенига несложно доказать, но наша цель установить, не проливает ли некоторый свет на нее алгебраическая формулировка.
В приводимом ниже доказательстве линейная алгебра используется, как мне представляется, по существу.
Итак, доказываем, что все ненулевые элементы матрицы А покрываются r линиями, где r=rank(A). Индукция по числу n строк матрицы, база для одной строки очевидна. Если r=n, в качестве линий можно взять просто строки, так что пусть r < n. Не умаляя общности, верхний левый минор матрицы A не равен 0. Обозначим матрицу, образуемую верхнюю r строками матрицы A через B, оставшимися n-r строками через C. Столбцы матриц B,C будем обозначать b1,b2,...;c1,c2... слева направо. Во-первых ясно, что при k > r столбец c[k] нулевой, иначе мы можем расширить ненулевой минор в левом верхнем углу до ненулевого минора порядка r+1.
Не умаляя общности, можно считать, что столбцы c1,c2,...,c[s] ненулевые, а остальные столбцы матрицы C нулевые. При этом s не больше r. Рассмотрим для произаольного k > r разложение столбца b[k] по b1,...,b[r]. Предположим, что коэффициент при некотором b[j] не равен 0, где j от 1 до s. Заменим в наборе b1,...,b[r] столбец b[i] на b[k]. Набор останется линейно независимым, и соответствующий минор порядка r можно будет расширить до минора порядка r+1, используя ненулевой элемент столбца c[j]. Противоречие. Итак, b[k] выражается линейно через b[s+1],...,b[r]. Это значит, что после выкидывания из матрицы B (а значит, и A) первых s столбцов ранг оставшегося будет равен r-s. Осталось применить к этому оставшемуся индукционное предположение и добавить первые s столбцов.
В этой связи возникает несколько вопросов.
Во-первых, нельзя ли привести какое-то тождество с минорами, которое само по себе доказывает теорему Кенига?
Во-вторых, алгебраически можно переформулировать вопрос и паросочетаниях в недвудольных графах. Если мы по обычному графу на n вершинах построим кососимметричную n×n матрицу, в которой каждому ребру e будет соответствовать пара элементов x[e], -x[e], где буквы снова разные и независимые, то наличие совершенного паросочетания будет равносильно тому, что пфаффиан этой матрицы не равен нулю. Нельзя ли так понять критерий существования паросочетания типа Татта?
Запись сделана с помощью m.livejournal.com.
В этом случае ранг приобретает ясный комбинаторный смысл: это просто наибольшее число не бьющих друг друга ладей, которых можно поставить на ненулевые элементы матрицы А (из-за отсутствия зависимостей соответствующий минор будет ненулевым).
Таким образом, наше утверждение есть просто известная комбинаторная теорема Кенига, по сути равносильная еще более известной лемме о девушках: если в некоторых клетках матрицы стоят ладьи, то наибольшее число не бьющих друг друга ладей равно наименьшему числу линий, покрывающих все ладьи.
Конечно, теорему Кенига несложно доказать, но наша цель установить, не проливает ли некоторый свет на нее алгебраическая формулировка.
В приводимом ниже доказательстве линейная алгебра используется, как мне представляется, по существу.
Итак, доказываем, что все ненулевые элементы матрицы А покрываются r линиями, где r=rank(A). Индукция по числу n строк матрицы, база для одной строки очевидна. Если r=n, в качестве линий можно взять просто строки, так что пусть r < n. Не умаляя общности, верхний левый минор матрицы A не равен 0. Обозначим матрицу, образуемую верхнюю r строками матрицы A через B, оставшимися n-r строками через C. Столбцы матриц B,C будем обозначать b1,b2,...;c1,c2... слева направо. Во-первых ясно, что при k > r столбец c[k] нулевой, иначе мы можем расширить ненулевой минор в левом верхнем углу до ненулевого минора порядка r+1.
Не умаляя общности, можно считать, что столбцы c1,c2,...,c[s] ненулевые, а остальные столбцы матрицы C нулевые. При этом s не больше r. Рассмотрим для произаольного k > r разложение столбца b[k] по b1,...,b[r]. Предположим, что коэффициент при некотором b[j] не равен 0, где j от 1 до s. Заменим в наборе b1,...,b[r] столбец b[i] на b[k]. Набор останется линейно независимым, и соответствующий минор порядка r можно будет расширить до минора порядка r+1, используя ненулевой элемент столбца c[j]. Противоречие. Итак, b[k] выражается линейно через b[s+1],...,b[r]. Это значит, что после выкидывания из матрицы B (а значит, и A) первых s столбцов ранг оставшегося будет равен r-s. Осталось применить к этому оставшемуся индукционное предположение и добавить первые s столбцов.
В этой связи возникает несколько вопросов.
Во-первых, нельзя ли привести какое-то тождество с минорами, которое само по себе доказывает теорему Кенига?
Во-вторых, алгебраически можно переформулировать вопрос и паросочетаниях в недвудольных графах. Если мы по обычному графу на n вершинах построим кососимметричную n×n матрицу, в которой каждому ребру e будет соответствовать пара элементов x[e], -x[e], где буквы снова разные и независимые, то наличие совершенного паросочетания будет равносильно тому, что пфаффиан этой матрицы не равен нулю. Нельзя ли так понять критерий существования паросочетания типа Татта?
Запись сделана с помощью m.livejournal.com.