<p>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? </p>

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

CC BY-SA 3.0
2015-07-12T03:34:41.410Z
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.
Joshua Grochow
CC BY-SA 3.0
2015-07-12T22:45:32.723Z
I do not see why you'd need complex numbers here. The Schwartz–Zippel lemma applies to any field: https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma
Marc
<np-hardness><optimization><linear-algebra>
Completing a matrix (over the reals) to be singular
P.T.
# Completing a matrix (over the reals) to be singular

(Asked by: username_0 on 2015-07-04)

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?

**Tags:** np-hardness, optimization, linear-algebra

> **Comments:**
> **username_1**: 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.  
> **username_2**: I do not see why you'd need complex numbers here. The Schwartz–Zippel lemma applies to any field: https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma  

---

## 0 answers

