2
$\begingroup$

Given a family of matrices $M$ with entries in $\mathbb{F}_2$ find the subset $N \subseteq M $ such that the rank of the matrix $$A = \sum_{m \in N}m $$ is minimal.

I am wondering if anyone have seen this kind of problem or anything related before. It could of course also be viewed as some kind of graph problem so it might have be studied in that contexts as well.

$\endgroup$
1
  • $\begingroup$ $N = \emptyset$? $\endgroup$
    – Neal Young
    Commented Jun 4 at 21:01

1 Answer 1

2
$\begingroup$

This is a homogeneous variant of the minrank problem over $\mathbb{F}_2$. We looked at it in the following paper: M. Bläser et al, "On the Orbit Closure Containment Problem and Slice Rank of Tensors", SODA 2021, 2565—2584. It is NP-hard to decide if the minimal rank is 1, and it is also NP-hard to decide for $n$ matrices of size $(2n+1)\times (2n+1)$ if the rank is less than half of the size.

Similar problems are also used in cryptography (see for example Faugère et al, "Cryptanalysis of MinRank", CRYPTO 2008), but they are usually nonhomogeneous (there is one matrix you must take).

$\endgroup$
1
  • $\begingroup$ thats perfect. just what i was looking for. $\endgroup$
    – Sander
    Commented Jun 3 at 19:56

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.