<p>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 <strong>NC</strong>) and I guess any efficient treatment of sparse matrix operation carries to this algorithm.</p>

<p>Oddly enough the wikipedia page about that exists only in French and German:</p>

<p><a href="https://fr.wikipedia.org/wiki/Algorithme_de_Faddeev-Leverrier">https://fr.wikipedia.org/wiki/Algorithme_de_Faddeev-Leverrier</a></p>

<p>I found this article in english explaining the method:</p>

<p><a href="http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1085-14.pdf">http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1085-14.pdf</a></p>

CC BY-SA 3.0
2016-01-31T02:17:07.260Z
2016-01-31T02:17:07.260Z
Marc
<p>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? </p>

<ds.algorithms><linear-algebra><randomized-algorithms><matrices><sparse-matrix>
Checking properties of matrices
Nado
# Checking properties of matrices

(Asked by: username_0 on 2016-01-29)

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?

**Tags:** ds.algorithms, linear-algebra, randomized-algorithms, matrices, sparse-matrix

---

## 1 answers

### Answer by username_1 on 2016-01-31. Score: 4 | Accepted answer

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>


---

