# Matrix completion problem with determinant condition?

Given two $$\{0,1\}^{n\times n}$$ matrices $$L$$ and $$M$$ and an integer $$m$$ is there a polynomial in $$n$$ algorithm to find a $$\{-1,0,+1\}$$ matrix $$T$$ such that $$\mathsf{det}(L+T\odot M)=m$$ where $$\odot$$ refers to $$ij$$th entry of $$T\odot M$$ being $$T_{ij}M_{ij}$$?

1. Is there any canonical approach to this problem that can beat $$2^{O(n)}$$ time?

2. An evidence $$2^{O(n)}$$ could not be beaten would come if we show that 'Given two $$\{0,1\}^{n\times n}$$ matrices $$L$$ and $$M$$ and integers $$m,t$$ is there a $$\{-1,0,+1\}$$ matrix $$T$$ with $$\|T\|_F\leq t$$ such that $$\mathsf{det}(L+T\odot M)=m$$ holds?' is $$NP$$-complete (it is in $$NP$$ however there seems no canonical reduction from any $$NP$$ complete problem and I find every theoretical support for an $$NP$$ complete reduction seems to turn to absurdity here after the presented answer I think it should be $$NP$$ complete)?

It seems in all likelihood this problem is in $$P$$.

If $$T$$ is a planar bipartite signed biadjacency then the case could be special and might be handlable within $$P$$. This possibly yields difficulties in reductions.

• This does not look like a matrix completion problem to me. – Rodrigo de Azevedo Jun 22 '19 at 22:43
• Might as well write just "polynomial in $n$", because $\log |m| \ll n \log n$ for any achievable $m$: each entry of $L + T \odot M$ is between $-1$ and $2$, so $\left|\det(L + T \odot M)\right| \leq 2^n n!$. (Yes, Hadamard's inequality gives an even better bound, but this gives only a factor of $2$ improvement in $\log|m|$.) – Noam D. Elkies Jun 23 '19 at 4:14

I will prove it is NP-complete if $$T$$ is restricted to $$\pm 1$$.

Let $$k_1,\ldots,k_n$$ be an arbitrary list of integers.

Suppose the cofactors of $$L$$ along the top row are $$c_1,\ldots,c_n$$ and all not zero. Define $$M$$ to be $$k_1/c_1,\ldots,k_n/c_n$$ along the top row and 0 everywhere else. Define $$m=0$$.

Now the problem is to divide $$k_1,\ldots,k_n$$ into two parts of equal sum, which is the NP-complete problem PARTITION.

I doubt if allowing zeros in $$T$$ will suddenly make it polynomial, but I don't see the details. Maybe someone else does.

• So you think there is no sub exp algorithm? – T.... Jun 23 '19 at 9:08
• If the conjecture that NP-complete problems need exponential time is correct, yes. – Brendan McKay Jun 23 '19 at 9:10
• No not all NP complete problems need fully exponential time and that is known but many canonical reductions do need. – T.... Jun 23 '19 at 9:11
• The sum of absolute values of entries in your reduction is $\Omega(n)$ and so it seems highly likely some variant should handle $0$ case as well. – T.... Jun 23 '19 at 9:14
• I was taking "exponential" to mean $\Omega(e^{n^{\epsilon}})$ for some $\epsilon\gt 0$, which is one of the two common definitions. – Brendan McKay Jun 23 '19 at 9:16