LIPIcs.ESA.2022.38.pdf
- Filesize: 0.59 MB
- 7 pages
Document
Determinants from Homomorphisms
Author
Radu Curticapean 
-
Part of:
Volume:
30th Annual European Symposium on Algorithms (ESA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-09-01
File
Document Identifiers
Author Details
Cite As Get BibTex
Radu Curticapean. Determinants from Homomorphisms. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 38:1-38:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.38
Abstract
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.
Subject Classification
ACM Subject Classification
- Computing methodologies → Linear algebra algorithms
- Mathematics of computing → Combinatorics
- Mathematics of computing → Graph theory
- Theory of computation → Parallel algorithms
Keywords
- determinant
- homomorphisms
- matrix trace
- Newton identities
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Stuart J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inf. Process. Lett., 18(3):147-150, 1984. URL: https://doi.org/10.1016/0020-0190(84)90018-8.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
- Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017., pages 210-223. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055502.
- Dexter C. Kozen. Csanky’s Algorithm, pages 166-170. Springer New York, New York, NY, 1992. URL: https://doi.org/10.1007/978-1-4612-4400-4_31.
- László Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications. American Mathematical Society, 2012. URL: http://www.ams.org/bookstore-getitem/item=COLL-60.
- Meena Mahajan and V. Vinay. A combinatorial algorithm for the determinant. In Michael E. Saks, editor, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana, USA, pages 730-738. ACM/SIAM, 1997. URL: http://dl.acm.org/citation.cfm?id=314161.314429.
- P. A. Samuelson. A method of determining explicitly the coefficients of the characteristic equation. The Annals of Mathematical Statistics, 13(4):424-429, 1942. URL: http://www.jstor.org/stable/2235845.
- Leslie G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189-201, 1979. URL: https://doi.org/10.1016/0304-3975(79)90044-6.