矩阵的行列式通过高斯消去C++

Question

我试图找到一个求平方矩阵行列式的代码，我遇到了这个代码。

    int det(vector<vector<int> > mat) {
        int n = mat.size();

        for(int col = 0; col < n; ++col) {
            bool found = false;
            for(int row = col; row < n; ++row) {
                if(mat[row][col]) {
                    mat[row].swap(mat[col]);
                    found = true;
                    break;
                }
            }
            if(!found) {
                return 0;
            }
            for(int row = col + 1; row < n; ++row) {
                while(true) {
                    int del = mat[row][col] / mat[col][col];
                    for (int j = col; j < n; ++j) {
                        mat[row][j] -= del * mat[col][j];
                    }
                    if (mat[row][col] == 0)
                        break;
                    else
                        mat[row].swap(mat[col]);
                }
            }
        }
        li res = 1;
        for(int i = 0; i < n; ++i) {
            res *= mat[i][i];
        }
        return abs(res);
    }

但我很难理解第20-29行，即从另一行的倍数中减去行的位置。我的意思是为什么这里需要while循环？就像我一样减去商*被除数，它应该总是0，对吧？所以我认为它应该只是一次迭代。那么，为什么我们需要执行这个mat[row].swap(mat[col]);操作呢？提前谢谢。

Answer 1

您的代码中有一些奇怪的逻辑来解释您使用整数算术执行计算的事实。

假设你有一个3x3矩阵，其中前两行是：

4 6 5
1 2 3

当你为col=0和row=1计算del时，你会得到：

del = 1/4 = 0

这样，当你计算时：

mat[row][j] -= del * mat[col][j];

mat[row][j]根本没有改变。

为此，您交换了行。现在前两行是：

1 2 3
4 6 5

通过这样交换行，del的值就是4/1 = 4。现在的线路：

mat[row][j] -= del * mat[col][j];

确实会有所不同。mat[1][0]的值最终为零，这正是您所需要的。所以你打破了while循环。

这里有一个插入指令的函数版本，它会产生大量调试输出，其中有一个用于打印矩阵的辅助函数和一个用于测试代码的主函数。

#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
void printMatrix(vector<vector<int> > const& mat)
{
   int n = mat.size();
   for(int row = 0; row < n; ++row) {
      for(int col = 0; col < n; ++col) {
         cout << mat[row][col] << " ";
      }
      cout << "n";
   }
   cout << "n";
}
int det(vector<vector<int> > mat) {
   int n = mat.size();
   for(int col = 0; col < n; ++col) {
      cout << "Column: " << col << "n";
      printMatrix(mat);
      bool found = false;
      for(int row = col; row < n; ++row) {
         if(mat[row][col]) {
            cout << "Got non-zero value for row " << row << " and col " << col << "n";
            if ( row != col )
            {
               cout << "(1) Swapping rows " << col << " and " << row << "n";
               mat[row].swap(mat[col]);
               printMatrix(mat);
            }
            else
            {
               cout << "Not swapping rowsn";
            }
            found = true;
            break;
         }
      }
      if(!found) {
         cout << "Did not find a non-zero row. Column: " << col << "n";
         return 0;
      }
      for(int row = col + 1; row < n; ++row) {
         while(true) {
            int del = mat[row][col] / mat[col][col];
            cout << "del: " << del << "n";
            for (int j = col; j < n; ++j) {
               mat[row][j] -= del * mat[col][j];
            }
            if (mat[row][col] == 0)
            {
               break;
            }
            else
            {
               cout << "(2) Swapping rows " << col << " and " << row << "n";
               mat[row].swap(mat[col]);
               printMatrix(mat);
            }
         }
      }
   }
   printMatrix(mat);
   long res = 1;
   for(int i = 0; i < n; ++i) {
      res *= mat[i][i];
   }
   return abs(res);
}
int main()
{
   vector<vector<int> > mat = { {4, 6, 5}, {1, 2, 3}, {8, 10, 9} };
   int r = det(mat);
   cout << "Determinant: " << r << endl;
   return 0;
}