গাউস পদ্ধতিতে ম্যাট্রিক্সের ডিটারমিন্যান্ট (determinant) নির্ণয়#
সমস্যা: $N \times N$ আকারের একটি ম্যাট্রিক্স $A$ দেওয়া আছে। এর ডিটারমিন্যান্ট নির্ণয় করতে হবে।
অ্যালগরিদম#
আমরা রৈখিক ইকুয়েশন ব্যবস্থা সমাধানের জন্য গাউস পদ্ধতি-এর ধারণা ব্যবহার করব।
আমরা লিনিয়ার ইকুয়েশন সিস্টেম সমাধানের মতোই একই ধাপগুলো ফলো করব, শুধু বর্তমান রো-কে (row) $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;