On Fri, Jul 16, 2010 at 7:17 PM, Nathann Cohen <[email protected]> wrote: > Hello everybody !!!! > > I have a small Linear Algebra question for you... I am pretty sure it > has a well-known answer, but this is where I feel how far my linear > algebra is... :-) > > Actually, it is a simple one. I have one matrix M defined over Z^n, > whose kernel K is of interest to me. I would then like to find the > intersection of K with (Z/2Z)^n, and a basis of it.
[snip] If I am understanding your problem correctly, the decision of the existence of such a set of solutions (doesn't really make sense to have a basis does it? 0,1 vectors in the kernel?) NP-Complete by Karp, The Binary Integer Programming problem. http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems The hardness of this problem is the main difficulty underlying of much of combinatorics. -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
