Теорема. Элементарные преобразования не изменяют ранга матрицы.
Доказательство. Пусть столбцы линейно зависимы, т.е. существуют , не все из которых равны нулю, такие, что
Пусть мы прибавили ко второй строке первую, умноженную на :
Тогда
т.е. и столбцы матрицы, полученной после преобразования, линейно зависимы.
Значит, наше преобразование не увеличивает ранг. Пусть оно ранг уменьшает. Чтобы из преобразованной матрицы получить исходную, нужно из ее второй строки вычесть первую, умноженную на . Тогда ранг после преобразования еще уменьшится. Получим, что , что невозможно.