论文标题
同构的决定因素
Determinants from homomorphisms
论文作者
论文摘要
我们为矩阵能力的决定因素和痕迹之间的众所周知关系提供了新的组合解释。这种关系可用于获得决定因素的多项式时间和多同源空间算法。我们的新解释避免了线性的代数参数，而是利用了子图和同态数量之间的经典联系。
We give a new combinatorial explanation for well-known relations between determinants and traces of matrix powers. Such relations can be used to obtain polynomial-time and poly-logarithmic space algorithms for the determinant. Our new explanation avoids linear-algebraic arguments and instead exploits a classical connection between subgraph and homomorphism counts.
