I have a $12 \times 12$ (so not really large) system of linear equations in $\mathbb{F}_2$ which I got to RREF through the usual row reduction. Suppose the system has multiple solutions, and call the unknowns $x_i$. What is the least expensive way to find a solution that minimizes the amount of $x_i$'s such that $x_i = 1$, or equivalently, a solution of minimal norm? Is this solution unique?

  • $\begingroup$ Well if it is homogenous the 0 is your answer. But if you want to ignore that then no it wont be unique, a null space with basis $\langle (1,0,1),(1,1,0)\rangle$ exists and has no nonzero vector of hamming weight 1. $\endgroup$ – Algeboy Aug 5 '19 at 4:11
  • $\begingroup$ No, it is not homogenous. $\endgroup$ – Fabian Levican S. Aug 5 '19 at 5:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.