یافتن رتبه یک ماتریس¶
رتبه یک ماتریس، بزرگترین تعداد سطرهای/ستون‌های مستقل خطی آن ماتریس است. رتبه تنها برای ماتریس‌های مربعی تعریف نمی‌شود.
رتبه یک ماتریس را می‌توان به عنوان بزرگترین مرتبه‌ی هر کهاد (minor) غیرصفر در ماتریس نیز تعریف کرد.
فرض کنید ماتریس مستطیلی و در ابعاد $N \times M$ باشد. توجه داشته باشید که اگر ماتریس مربعی باشد و دترمینان آن غیرصفر باشد، رتبه آن برابر با $N$ ($=M$) خواهد بود؛ در غیر این صورت، رتبه کمتر از آن است. به طور کلی، رتبه یک ماتریس از $\min (N, M)$ تجاوز نمی‌کند.
الگوریتم¶
می‌توانید رتبه را با استفاده از حذف گاوسی پیدا کنید. ما همان عملیاتی را انجام خواهیم داد که هنگام حل یک دستگاه معادلات یا یافتن دترمینان آن انجام می‌دهیم. اما اگر در هر مرحله، در ستون $i$-ام، در بین سطرهایی که هنوز انتخاب نکرده‌ایم، هیچ سطری با درایه غیرصفر وجود نداشته باشد، از این مرحله صرف نظر می‌کنیم. در غیر این صورت، اگر در مرحله $i$-ام، سطری با یک درایه غیرصفر در ستون $i$-ام پیدا کردیم، آن سطر را به عنوان انتخاب‌شده علامت‌گذاری می‌کنیم، رتبه را یکی افزایش می‌دهیم (در ابتدا رتبه برابر با $0$ است) و عملیات معمول کم کردن این سطر از سایر سطرها را انجام می‌دهیم.
پیچیدگی¶
این الگوریتم در زمان $\mathcal{O}(n^3)$ اجرا می‌شود.
پیاده‌سازی¶
const double EPS = 1E-9;
int compute_rank(vector<vector<double>> A) {
int n = A.size();
int m = A[0].size();
int rank = 0;
vector<bool> row_selected(n, false);
for (int i = 0; i < m; ++i) {
int j;
for (j = 0; j < n; ++j) {
if (!row_selected[j] && abs(A[j][i]) > EPS)
break;
}
if (j != n) {
++rank;
row_selected[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];
}
}
}
}
return rank;
}