# Testing whether a determinant polynomial is identically zero

Suppose we are given matrices $A_1, \ldots, A_k$ which are $n \times n$ matrices with rational entries and are asked to determine whether the polynomial ${\rm det}(\alpha_1 A_1 + \alpha_2 A_2 + \cdots + \alpha_k A_k)$ is identically zero. How can we do this deterministically in polynomial time in $n$ and $k$?

I'm aware that black-box polynomial identity testing is a difficult problem, but then this is not quite a black box.

• – Yuval Filmus Dec 26 '13 at 8:27
• An issue here could be that equality in the reals is not decidable. So even in the case of $k=n=1$, you cannot do this. However, you can decide whether or not two numbers are $\epsilon$ close for any non-zero $\epsilon$, which is good enough if you are using something like floats. – Baby Dragon Dec 28 '13 at 20:35
• I meant to say that the matrices should have rational entries - have edited this into the question just now. – Jean Michelle Dec 29 '13 at 4:07
• suggest migrate to tcs.se. can you elaborate on how this is different than polynomial identity testing? there is a large amt of research on that – vzn Dec 29 '13 at 17:17
• @vzn - this is polynomial identity testing, but it might not be equivalent to "black box" identity testing since there might be hope that the specific structure of the polynomial here could be helpful. – Jean Michelle Dec 29 '13 at 18:27

Your polynomial is a multivariate polynomial of degree $n$ over the field $\mathbb{R}$. Pick a set $S$ of real numbers with cardinality $2n$, draw $k$ numbers uniformly at random from $S$, and evaluate the polynomial at those points (substituting the first for $\alpha_1$, the second for $\alpha_2$, and so on). Check whether the result is non-zero. By Schwartz-Zippel, either your polynomial is identically zero or else the result will be non-zero with probability $\ge 1/2$. Thus, we can repeat this test $m$ times. If we get zero every time, output "the polynomial is identically zero". Otherwise output "the polynomial is not identically zero". You'll be wrong with probability at most $1/2^m$.