1
$\begingroup$

We are given an $n\times (n+k)$ matrix $A,$ with entries in $\mathrm{GF}(2),$ of the form $A=(I_n|B)$ where $I_n$ is a $n\times n$ identity matrix where the matrix $B$ has no "zero" rows or columns.

The problem is to partition the columns of $A$ into at most $m$ subsets each of size at most $b$ such that the number of "critical subset's" is minimized, where a critical subset is a subset of the set of columns such that if we remove it from $A$ the reduced matrix has rank less than $n.$

The problem seems to be NP-Complete to me but I am not able to understand from which problem we should try to reduce.

The elaborate problem definition/relevant discussion can be found at:

https://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code.

I am defining it here in some abstract way. Also, I wanted to post it under the NP-Complete tag.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Are you sure you want B to have "no non-zero rows or columns"? $\endgroup$
    – François G. Dorais
    Commented Aug 28, 2011 at 14:03
  • 3
    $\begingroup$ This question was also posted here: math.stackexchange.com/questions/60322/… $\endgroup$
    – Martin Sleziak
    Commented Aug 28, 2011 at 14:07
  • 5
    $\begingroup$ Prasenjit: to expand on Martin's remark, it is considered extremely poor form to post identical questions on MO and SE at the same time. The recommended course of action is to post it on SE, and then only repost on MO after about a week, if it looks like the SE question is going nowhere. $\endgroup$
    – Thierry Zell
    Commented Aug 28, 2011 at 14:46
  • 1
    $\begingroup$ @Martin and Thierry: Sorry for posting it twice. I will keep in mind what you have said next time I post. $\endgroup$
    – aaaaaa
    Commented Aug 28, 2011 at 17:08
  • 3
    $\begingroup$ @Prasenjit: I assume that Francois interpreted "no non-zero rows or columns" the same way I did, which would mean that B is the zero matrix. (A row or column (or any other sort of vector) is non-zero if at least one entry is non-zero.) I also assume that you meant something else. Please tell us what you meant. $\endgroup$
    – Andreas Blass
    Commented Aug 28, 2011 at 21:59

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .