A parity check matrix for a binary linear code is a matrix $H$ (with linearly independent rows) such that the (right) kernel of $H$ is the codespace. Clearly we can replace any row $r_i$ by $r_i + \sum_{j \in J} r_j$ if $i \not \in J$ to produce a matrix with the same kernel. It is a natural question to ask if there is some matrix $H'$ with the same kernel as $H$ such that all rows of $H'$ have weight at most $k$, where the weight of a row is just the number of nonzero entries in the row. Is there a way to produce such an $H'$ (or even to tell if one exists) without checking all matrices with the same nullspace?
Follow up: is there a way to solve the same problem given a parity check matrix over $GF(4)$?
