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?
1 Answer
$\begingroup$
$\endgroup$
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
