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.

  • 1
    $\begingroup$ Related: mathoverflow.net/questions/47362/subspaces-of-singular-matrices. $\endgroup$ – Yuval Filmus Dec 26 '13 at 8:27
  • $\begingroup$ 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. $\endgroup$ – Baby Dragon Dec 28 '13 at 20:35
  • 2
    $\begingroup$ I meant to say that the matrices should have rational entries - have edited this into the question just now. $\endgroup$ – Jean Michelle Dec 29 '13 at 4:07
  • $\begingroup$ 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 $\endgroup$ – vzn Dec 29 '13 at 17:17
  • $\begingroup$ @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. $\endgroup$ – Jean Michelle Dec 29 '13 at 18:27

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.

  • 1
    $\begingroup$ Thanks - but this is a theoretical problem. Mostly, I'm just curious whether "determinant structure" allows you to do identity testing. $\endgroup$ – Jean Michelle Dec 25 '13 at 20:10

This currently does not have any deterministic polynomial-time algorithm, not even "whitebox". Moreover, it is expected to be a very hard problem as due to a landmark paper by Kabanets-Impagliazzo Derandomizing Polynomial Identity Tests …, even showing that it is in NSUBEXP would imply strong circuit lower bounds like permanent has no polynomial-size circuit or that NEXP is not contained in P/poly.

There has been a lot of recent progress especially on a subcase called the "non-commutative" version of this in which we consider the $\alpha_i$ to be non-commuting variables. This was derandomized (whitebox) recently by GGOW (over C) and Ivanyos, Youming Qiao, and Subrahmanyam (over every characteristic fields).

Another recent work gave A Deterministic PTAS to approximate the maximum rank of such a linear combination


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.