ম্যাট্রিক্সের র্যাঙ্ক নির্ণয়#
ম্যাট্রিক্সের র্যাঙ্ক (rank) হলো ম্যাট্রিক্সের সর্বাধিক সংখ্যক লিনিয়ারলি ইন্ডিপেন্ডেন্ট (linearly independent) রো (row)/কলাম। র্যাঙ্ক শুধুমাত্র বর্গ ম্যাট্রিক্সের জন্য ডিফাইন্ড নয়।
ম্যাট্রিক্সের র্যাঙ্ককে ম্যাট্রিক্সের যেকোনো অশূন্য মাইনরের সর্ববৃহৎ অর্ডার হিসেবেও ডিফাইন করা যায়।
ধরো ম্যাট্রিক্সটা আয়তাকার এবং এর আকার $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;
}