2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This does not look like a matrix completion problem to me. $\endgroup$
    – Rodrigo de Azevedo
    Jun 22, 2019 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, 2019 at 4:14

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ So you think there is no sub exp algorithm? $\endgroup$
    – Turbo
    Jun 23, 2019 at 9:08
  • $\begingroup$ If the conjecture that NP-complete problems need exponential time is correct, yes. $\endgroup$
    – Brendan McKay
    Jun 23, 2019 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$
    – Turbo
    Jun 23, 2019 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$
    – Turbo
    Jun 23, 2019 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, 2019 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.