# Testing for satisfiability of a system of linear equations over GF(2)

Consider a system linear equations in $x$, $Ax =b$, where A is an $n\times n$ matrix, and $b$ is a column vector, and all operations are over $GF(2)$.

Is it easier to check satisfiability of the system without finding a specific solution $x$, in terms of time complexity? (A solution can be found in matrix multiplication time.)

• I changed GL(2) to GF(2). I assumed you did not actually mean the general linear group of degree 2 – Sasho Nikolov Jun 28 '16 at 7:51
• By doing a binary search on x, it can be easier at most by a factor of 2n. – Joshua Grochow Jun 29 '16 at 4:45