# Is this minimization problem NP-Complete ?

We are given an nx(n+k) matrix A, with entries in GF(2), of the form A=(In|B) where In is a nxn identity matrix where the matrix B has no "zero" rows or columns.

The problem is to partition the columns of A into atmost m subsets each of size atmost 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 not able to understand from which problem we should try to reduce.

The elaborate problem definition/relevant discussion can be found at http://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code. I am defining here in some abstract way. Also, I wanted to post it under NP-Complete tag.

-
Are you sure you want B to have "no non-zero rows or columns"? – François G. Dorais Aug 28 '11 at 14:03
This question was also posted here: math.stackexchange.com/questions/60322/… – Martin Sleziak Aug 28 '11 at 14:07
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. – Thierry Zell Aug 28 '11 at 14:46
@Martin and Thierry: Sorry for posting it twice. I will keep in mind what you have said next time I post. – aaaaaa Aug 28 '11 at 17:08
@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. – Andreas Blass Aug 28 '11 at 21:59