4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I don't quite understand your reformulation: if $C$ is diagonal without 0s and 1s on the diagonal, there will be no $v$ and $v'$ satisfying $Cv=v'$. $\endgroup$ May 8, 2021 at 8:58
  • $\begingroup$ Yes, if $C$ is diagonal without 0s and 1s, then clearly there isn’t a solution. However, usually $C$ is not diagonal and the existence of such $v$ is not invariant under general linear transformation of $C$, so merely testing for eigenvalues is not sufficient. $\endgroup$
    – Tippisum
    May 8, 2021 at 13:03

1 Answer 1

2
$\begingroup$

This is more of a long comment than a proper answer.

The question appears to be related to generalised eigenvalue problems. Specfically, let $X=diag(x_1,...,x_n)$, with $x_k\in\{0,1\}$. Then you want to solve $Cv=Xv$, with $v\neq 0$, which is a kind of "inverse" gen. eigenvalue problem, the gen. eigenvalue is 1, but you don't know $X$.

It's solvable iff $\det (C-X)=0$, which, together with $x_k^2=x_k$, $1\leq k\leq n$, gives one $n+1$ equations for $n$ variables, a system that typically has no solutions in a sufficiently large field.

$\endgroup$

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.