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.

  • 2
    $\begingroup$ This does not look like a matrix completion problem to me. $\endgroup$ – Rodrigo de Azevedo Jun 22 '19 at 22:43
  • $\begingroup$ 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|$.) $\endgroup$ – 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.

  • $\begingroup$ So you think there is no sub exp algorithm? $\endgroup$ – T.... Jun 23 '19 at 9:08
  • $\begingroup$ If the conjecture that NP-complete problems need exponential time is correct, yes. $\endgroup$ – Brendan McKay Jun 23 '19 at 9:10
  • $\begingroup$ No not all NP complete problems need fully exponential time and that is known but many canonical reductions do need. $\endgroup$ – T.... Jun 23 '19 at 9:11
  • $\begingroup$ 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. $\endgroup$ – T.... Jun 23 '19 at 9:14
  • $\begingroup$ I was taking "exponential" to mean $\Omega(e^{n^{\epsilon}})$ for some $\epsilon\gt 0$, which is one of the two common definitions. $\endgroup$ – Brendan McKay Jun 23 '19 at 9:16

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.