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.



Matrix completion problem with determinant condition?
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.


