algorithm - 是否有一种快速算法来确定充满变量的矩阵的行列式？

Question

我正在拼命寻找一种多项式时间算法，它可以计算符号 (n x n) 矩阵的行列式。

问题是，矩阵上三角的每个条目都包含一个不同的变量(例如 x_1、x_2、...)。

在对角线上，每个条目都是一个多项式，由最多 (n-1) 个这些变量的负和组成(例如(- x_1 - x_2 - x_3)，(- x_3 - x_2)，... ).

然而，它始终是一个对称矩阵，因此如果沿对角线镜像，则条目是相同的。也许此属性有助于运行时？

我已经考虑过 LU 分解算法，但恐怕它只适用于纯数值矩阵，还是我错了？

有人可以帮帮我吗？

Answer 1

@MattTimmermans 评论回答了这个问题:

“LU(不是 LUP)分解在符号上工作得很好。每个单元格都包含一个有理函数，并且有理函数集在所有必需的操作(*、/、+、-)上是封闭的”

这似乎意味着我可以按原样使用 LU 分解算法，但只要 LU 分解算法使用这些运算符之一，就必须将此运算符作为子函数用于多项式。

非常感谢!