Пересечение векторных пространств

[Oddler]

Здравствуйте.

Сразу хочу извиниться, если будут какие-то неточности в терминах, т.к. я не математик.
Перейду к делу.

1. Задача в общем виде.
Имеется несколько матриц $m\times n$, причем $m$ не превосходит $n$. Количество матриц тоже не превосходит $n$.
Строки этих матриц - элементы векторного пространства $R^n$. Соответственно, каждая матрица порождает некоторое подпространство $R^m$ (если все m строк матрицы линейно независимы, конечно).
Задача максимум: найти пересечение (базис) векторных пространств, порождаемых матрицами.
Задача минимум: найти размерность этого пересечения. Еще точнее, проверить равна ли она нулю.

2. Частный случай
Есть три матрицы $2\times 3$, причем на самом деле они все получаются через элементарные преобразования матриц $5\times 3$ и три строки оказываются нулевыми. Кстати тут дополнительный вопрос. Верно ли, что если хотя бы одна матрица будет окажется $3\times 3$, а не $2\times 3$, то пресечение трех подпространств гарантированно будет ненулевым (при условии что оставшиеся две матрицы $2\times 3$ не вырождены)?
Итак, есть эти три матрицы. Задачи такие же как в п.1.
Суть заключается в том, что надо найти какое-то элегантное и понятное решение.

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

[lena7]

Oddler в сообщении #731777 писал(а):

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

Короче, вы хотите найти ранг матрицы $m\times n$?

Если делать это, например, методом Гаусса, то вы автоматически получите ответ на задачу максимум.

[Oddler]

lena7, не совсем так.

Для исходных своих матриц я всегда знаю ранг. А вот для их пересечения - нет. Причем, если матриц было бы две, то можно было просто использовать формулу $dim(A \cap B) = dim(A) + dim(B) - dim (A+B) $, где размерность определяется как раз рангом. Для трех я, к сожалению, таких формул не видел.
Т.е. для частного случая каждая матрица содержит 2 вектора и порождает плоскость. Меня, как минимум, интересует возможность показать, что не существует у трех таких плоскостей общих точек (кроме начала координат, естественно) не прибегая к решению систем $A_i\cdot x=0, i=1,2,3 $. Т.е. какое-то условие, например, которое гарантирует что пересечения (как минимум размерности 1) векторных пространств нет. И, соответственно, если условие нарушается, то пересечение есть. Ну или наоборот.

Хотя, возможно, я просто не понял о чем вы.

[lena7]

Опечаталась. Я имела в виду ранг матрицы $mk\times n$, склеенную из ваших $k$ матриц. По методу Гаусса вы обнулите часть строк, а то, что останется, будет базисом пересечения. Размерность -- это ранг той матрицы.

Это равносильно решению СЛАУ и, в общем случае, от этого никуда не деться. Метод Гаусса легко программируется, а размер матриц у вас, как я поняла, достаточно мал, чтобы беспокоится о скорости.

[ewert]

lena7 в сообщении #731896 писал(а):

Я имела в виду ранг матрицы $mk\times n$, склеенную из ваших $k$ матриц. По методу Гаусса вы обнулите часть строк, а то, что останется, будет базисом пересечения.

Увы, наоборот -- это будет базисом объединения образующих (или, что то же, суммы подпространств). С пересечением так дёшево не отделаешься.

lena7 в сообщении #731896 писал(а):

Метод Гаусса легко программируется

Это в теории. А на практике при работе с вырожденными системами придётся повозиться и понастраивать.

[Oddler]

Все как говорит ewert

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

Я позволю себе немного написать о том, почему я не хочу связываться с ядром (помимо физического смысла)
Допустим есть три матрицы $2\times 3$. И одна из них представляет собой что-то вроде $\left( \begin{matrix}\cos(\alpha) & 0 & \sin(\alpha)\\ 0 & \cos(\beta) & \sin(\beta)\end{matrix} \right)$. При маленьких $\alpha$ и $\beta$ получается что пространство представляет собой плоскость, почти совпадающую с $OXY$ (если в матрице компоненты $x,y,z$). Ядро значит будем вектором, почти совпадающим с осью $z$, но все же имеющим ненулевые компоненты по остальным двум осям. И вот тогда если я неудачно выберу свободную переменную. Допустим компонента $x=1$, тогда я рискую просто вылететь в огромнейшие степени для компоненты $z$.
В данном примере, конечно, все это очевидно и легко обходится, но когда компоненты матриц рассчитываются по здоровенным формулам, сложно предугадать такое поведение. А т.к. мне нужно в итоге написать программку, которая будет перебирать параметры вроде $\alpha$ и $\beta$ и для каждого их сочетания находить ядро, то это действительно доставляет неудобства.

Как я уже сказал, найти просто размерность пересечения подпространств (проверить равна ли она нулю) уже будет достаточно хорошим результатом для дальнейшей работы.

[bot]

ewert в сообщении #731897 писал(а):

С пересечением так дёшево не отделаешься

Для случая двух матриц смотрите здесь. Общий случай аналогичен.

[provincialka]

Так ведь ТС хотел как раз избежать такого утомительного метода, ему нужна только размерность подпространства.

[Oddler]

bot , спасибо за совет, но данный подход был среди первых, который я рассматривал.
Как и говорит provincialka, в большей степени меня интересует именно размерность пересечения. Точнее возможность найти размерность, даже просто доказать что она равна/не равна нулю, не прибегая к решению уравнений, в которых число неизвестных будет больше числа самих уравнений.

[bot]

Эта частность потребует усилий не намного меньше.

[Oddler]

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

[bot]

Oddler в сообщении #732636 писал(а):

Вероятно, так и есть.

Если найти базис каждого из ортогональных дополнений, составить из них матрицу, то вычисляя её ранг приведением к трапецевидной форме, если он не полный, мы оказываемся в полшаге от нахождения базиса пересечения - останется лишь обратная прогонка.

[Oddler]

bot
А разве это не то же самое, что я в первом посте написал?
Типа найти ядро $\ker(A_i)$ каждой матрицы, затем найти их объединение $K=\ker(A_1)\cup\ker(A_2)\cup\dots$\cup\ker(A_n), и, если ранг $K$ будет неполный, то искомое пересечение будет равно $\ker(K)$.

[bot]

Типа того, только не объединение, а сумма, и не ранг, а размерность и не если, а в любом случае и не $\ker$, а ортогональное дополнение.

[ewert]

bot в сообщении #733851 писал(а):

и не $\ker$, а ортогональное дополнение.

Это практически одно и то же (с точностью до разгильдяйства в формулировках). Но, строго говоря, $\ker$ лучше, т.к. выглядит, вообще говоря, проще ортогонального дополнения.