গাউস পদ্ধতিতে ম্যাট্রিক্সের নির্ণায়ক নির্ণয়#
সমস্যা: $N \times N$ আকারের একটি ম্যাট্রিক্স $A$ দেওয়া আছে। এর নির্ণায়ক নির্ণয় করতে হবে।
অ্যালগরিদম#
আমরা রৈখিক সমীকরণ ব্যবস্থা সমাধানের জন্য গাউস পদ্ধতি-এর ধারণা ব্যবহার করব।
আমরা রৈখিক সমীকরণ ব্যবস্থা সমাধানের মতোই একই ধাপগুলো অনুসরণ করব, শুধু বর্তমান সারিকে $a_{ij}$ দিয়ে ভাগ করা বাদ দিয়ে। এই অপারেশনগুলো ম্যাট্রিক্সের নির্ণায়কের পরম মান পরিবর্তন করবে না। তবে, যখন আমরা ম্যাট্রিক্সের দুটি সারি বিনিময় করি, তখন নির্ণায়কের চিহ্ন পরিবর্তন হতে পারে।
ম্যাট্রিক্সে গাউস পদ্ধতি প্রয়োগ করার পর, আমরা একটি কর্ণ ম্যাট্রিক্স পাই, যার নির্ণায়ক হলো কর্ণের উপাদানগুলোর গুণফল। পূর্বে উল্লেখিত চিহ্নটি সারি বিনিময়ের সংখ্যা দ্বারা নির্ধারিত হতে পারে (যদি বিজোড় হয়, তাহলে নির্ণায়কের চিহ্ন উল্টাতে হবে)। এভাবে, আমরা $O(N^3)$ কমপ্লেক্সিটিতে ম্যাট্রিক্সের নির্ণায়ক নির্ণয়ের জন্য গাউস অ্যালগরিদম ব্যবহার করতে পারি।
লক্ষণীয় যে, কোনো এক পর্যায়ে যদি বর্তমান কলামে অশূন্য ঘর খুঁজে না পাওয়া যায়, তাহলে অ্যালগরিদমটি থামবে এবং ০ রিটার্ন করবে।
ইমপ্লিমেন্টেশন#
const double EPS = 1E-9;
int n;
vector < vector<double> > a (n, vector<double> (n));
double det = 1;
for (int i=0; i<n; ++i) {
int k = i;
for (int j=i+1; j<n; ++j)
if (abs (a[j][i]) > abs (a[k][i]))
k = j;
if (abs (a[k][i]) < EPS) {
det = 0;
break;
}
swap (a[i], a[k]);
if (i != k)
det = -det;
det *= a[i][i];
for (int j=i+1; j<n; ++j)
a[i][j] /= a[i][i];
for (int j=0; j<n; ++j)
if (j != i && abs (a[j][i]) > EPS)
for (int k=i+1; k<n; ++k)
a[j][k] -= a[i][k] * a[j][i];
}
cout << det;