Consider a square matrix defined over a finite field $M\in\mathbb{F}_p^{n\times n}$ having the following form $$M=\begin{bmatrix}a_{11}+b_{11}x_1&a_{12}+b_{12}x_1&\dots&a_{1n}+b_{1n}x_1\\a_{21}+b_{21}x_2&a_{22}+b_{22}x_2&\dots&a_{2n}+b_{2n}x_2\\\vdots&\vdots&\ddots&\vdots\\a_{n1}+b_{n1}x_n&a_{n2}+b_{n2}x_n&\dots&a_{nn}+b_{nn}x_n\end{bmatrix}$$ where all $a_{ij}$ and $b_{ij}$ are elements of $\mathbb{F}_p$, and all $x_i$ are binary variables: $x_i\in\left\{0,1\right\}$.
$p$ is assumed to be prime so $\mathbb{F}_p$ is actually the integers modulo $p$, and $a_{ij}$ and $b_{ij}$ is assumed to have a reasonably uniform distribution between $\left[0,p\right)$.
Our goal is to find a binary assignment of $\mathbb{x}=\left(x_1,x_2,\dots,x_n\right)\in\left\{0,1\right\}^n$ which makes $M$ singular (i.e. $\det M=0$). It can be assumed that $n\sim\log^2p$ so the probability that such an assignment indeed exists is high. Also, it is not required to solve the problem definitely or deterministically. We are satisfied as long as we can find at least one valid assignment with a non-trivial success rate.
The question is, what can we expect about an algorithm solving the above problem?
Certainly we can enumerate all possible assignment and test if $\det M=0$, which gives an algorithm with complexity $O^*(2^n)$. Can we do better?
Thanks to the comment of Kapil, Now we can reduce the original problem into another problem which seems more clear.
We have a matrix $M=A+DB=(A+B)-DB$ where $A$ and $B$ are two matrices assumed to be "randomly picked" and $D$ a diagonal matrix containing 0 and 1.
With high probability $B$ is invertible so $\det M=0\Leftrightarrow\det\left((A+B)B^{-1}-D\right)=0$.
Let $C=(A+B)B^{-1}$, the above condition can then be express as:
Finding a vector $\mathbf{v}=(v_1,v_2,...v_n)$ such that $C\mathbf{v}=\mathbb{v}'$ with $\mathbf{v}'=(v'_1,v'_2,...v'_n)$ and each $v'_i$ equals either $v_i$ or 0. That is, the vector $\mathbb{v}$ has some of its components "zeroed" by multiplication by matrix $C$.
The original problem then becomes:
- Giving a matrix $C$, with a non-trivial success rate finding a vector $\mathbb{v}$ such that $C\mathbb{v}=\mathbb{v}'$ where $\mathbb{v}'$ is $\mathbb{v}$ with some components zeroed out.
If $C$ has eigenvalue 0 or 1, the above problem is easily solved. What if $C$ doesn't have eigenvalue 0 or 1?
Any idea or reference of materials mentioning similar problems is appreciated.
Also, even though the problem is mainly defined over $\mathbb{F}_p$, any ideas about similar problems concerning matrices over $\mathbb{Q}$, $\mathbb{R}$ or $\mathbb{C}$ is also appreciated.