- ds.algorithms linear-algebra randomized-algorithms matrices sparse-matrix
- Updated Fri, 24 Jun 2022 07:27:58 GMT

Given a sparse matrix $A$ in $\mathbb{Z}^{n\times n}$, how easily could one check whether a coefficient $\alpha_k$ of the characteristic polynomial $P_A$ of $A$ is equal to $0$ (without the need to compute $P_A$)? Are there any known deterministic/randomized algorithms for this task?

The Faddeev-Leverrier algorithm seems to be a good start to answer your question, since it reduces the computation of $\alpha_k$ to matrix multiplications and traces. It runs in polynomial time (even in **NC**) and I guess any efficient treatment of sparse matrix operation carries to this algorithm.

Oddly enough the wikipedia page about that exists only in French and German:

https://fr.wikipedia.org/wiki/Algorithme_de_Faddeev-Leverrier

I found this article in english explaining the method:

http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1085-14.pdf

External links referenced by this document: