Доказательство теоремы.

Необходимость. Система совместна. Докажем, что .

Система совместна — существуют такие числа ,что

т.е. вектор-столбец правой части линейно выражается через столбцы матрицы A. Это означает, что при добавлении столбца число линейно независимых столбцов не увеличивается, т.е. . Необходимость доказана.

Достаточность. . Докажем, что система совместна.

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

Положим ,

тогда

т.е. вектор — решение системы ,

т.е. система совместна. Теорема доказана.