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