6
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.