Нахождение ранга матрицы

Ранг матрицы - это наибольшее число линейно независимых строк/столбцов матрицы. Ранг определён не только для квадратных матриц; пусть матрица прямоугольна и имеет размер NxM.

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

Заметим, что если матрица квадратная и её определитель отличен от нуля, то ранг равен N(=M), иначе он будет меньше. В общем случае, ранг матрицы не превосходит min(N,M).

Алгоритм

Искать ранг можно с помощью модифицированного метода Гаусса. Будем выполнять абсолютно те же самые операции, что и при решении системы или нахождении её определителя, но если на каком-либо шаге в i-ом столбце среди невыбранных до этого строк нет ненулевых, то мы этот шаг пропускаем, а ранг уменьшаем на единицу (изначально ранг полагаем равным max(N,M)). Иначе, если мы нашли на i-ом шаге строку с ненулевым элементом в i-ом столбце, то помечаем эту строку как выбранную, и выполняем обычные операции отнимания этой строки от остальных.

Реализация

const double EPS = 1E-9;

int rank = max(n,m);
vector<char> line_used (n);
for (int i=0; i<m; ++i) {
	int j;
	for (j=0; j<n; ++j)
		if (!line_used[j] && abs(a[j][i]) > EPS)
			break;
	if (j == n)
		--rank;
	else {
		line_used[j] = true;
		for (int p=i+1; p<m; ++p)
			a[j][p] /= a[j][i];
		for (int k=0; k<n; ++k)
			if (k != j && abs (a[k][i]) > EPS)
				for (int p=i+1; p<m; ++p)
					a[k][p] -= a[j][p] * a[k][i];
	}
}