patternMinor
Testing whether a determinant polynomial is identically zero
Viewed 0 times
polynomialidenticallytestingdeterminantzerowhether
Problem
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.
I'm aware that black-box polynomial identity testing is a difficult problem, but then this is not quite a black box.
Solution
Is this a practical problem or a theoretical problem?
If it a practical problem, it looks to me like standard randomized algorithms for black-box polynomial identity testing should suffice to solve this.
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$.
If you want to have a small seed, use a cryptographically secure pseudorandom number generator to generator the random numbers needed for this procedure. Under a suitable cryptographic assumption, this will allow you to use only 128 bits of true randomness (or so).
This should be good enough for all practical applications. Of course, it doesn't answer the theoretical question of whether this problem has a deterministic polytime algorithm.
If it a practical problem, it looks to me like standard randomized algorithms for black-box polynomial identity testing should suffice to solve this.
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$.
If you want to have a small seed, use a cryptographically secure pseudorandom number generator to generator the random numbers needed for this procedure. Under a suitable cryptographic assumption, this will allow you to use only 128 bits of true randomness (or so).
This should be good enough for all practical applications. Of course, it doesn't answer the theoretical question of whether this problem has a deterministic polytime algorithm.
Context
StackExchange Computer Science Q#19278, answer score: 3
Revisions (0)
No revisions yet.