Consider the following problem: you are given a matrix (say, with rational entries) some of whose entries are actually left blank; can these blanks be filled in with real numbers so that the resulting matrix is singular?

It seems like deciding this should be NP-hard. Is this so and has this problem ever been studied before?

  • $\begingroup$ (Here's an upper bound.) $\:$ By proposition 4.2 on page 291 of the book, which is about $\hspace{.71 in}$ 5/6 of the way through the pdf (just before the references), that problem is in PSPACE. $\hspace{.78 in}$ $\endgroup$ – user6973 Jul 4 '15 at 20:45
  • 1
    $\begingroup$ If you only want to decide if it can be filled with complex numbers, then that can be decided in $\mathsf{RP}$ by a very slight variant of the usual randomized PIT algorithm (Schwarz--Zippel--DeMillo--Lipton). Namely, let $A(X)$ denote the obvious matrix such that solutions to $\det(A(X)) = 0$ are fillings of the blanks that make the matrix singular. Then there are no complex solutions iff $\det(A(X))$ is a constant, which can be tested w.h.p. by evaluating at several random points. $\endgroup$ – Joshua Grochow Jul 12 '15 at 3:34
  • 1
    $\begingroup$ I do not see why you'd need complex numbers here. The Schwartz–Zippel lemma applies to any field: en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma $\endgroup$ – Marc Jul 12 '15 at 22:45

Your Answer

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

Browse other questions tagged or ask your own question.