# Linear equations with Boolean variables

# Linear equations with Boolean variables

Solving a system of linear equations over a finite field is arguably one of the most fundamental operations in mathematics. This chapter considers a specific ensemble of random linear systems over Boolean variables, named XORSAT, and discusses the structure of its set of solutions. In large instances, the affine subspace of solutions can exhibit a remarkably rich geometrical structure. When the ratio of equations to variables is increased, the system first gets into an intermediate phase where solutions cluster in many well separated regions of the hypercube. Then it encounters a second phase transition and gets into an ‘UNSAT’ phase where the probability of existence of a solution vanishes. The study uses belief propagation equations, and a combinatorial analysis of the 2-core in the associated factor graph.

*Keywords:*
linear system, Boolean variables, XORSAT, belief propagation, cluster, 2-core

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .