Determinants from homomorphisms

04/22/2022
by   Radu Curticapean, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset