# Gauss Elimination for Colorability Problem

Consider the following system of linear equations modulo 2:

$A.X + B.Y = Z,$

where $A$ is a non-singular(modulo 2) $n$ x $n$ boolean matrix, $B$ is $n$ x $m$ boolean matrix, $X$ is n-dimensional boolean(unknown) vector, $Y$ is $m$-dimensional boolean(unknown) vector and $Z$ is $n$-dimensional boolean unknown vector.

So, solutions of the equation above are pairs of boolean vectors $(X,Y)$.

Prove that the number of solutions is equal $2^{m}$. Use this observation to get a polynomial time algorithm to count a number of 2-colorings.

I see that the products are defined. We would end up with $Z$ as a (nx1) vector that I assume is mod2 as well. All possible combinations of this boolean solution is $2^{n}$. I don't know why the question state it as $m$. Apparently, I need to use the Gauss elimination algorithm for 2-colorability in order to solve this problem.

Any ideas? Thank you.

Since $A$ is non-singular the equation is equivalent to $X = A^{-1}(Z-BY)$. So, for any choice of $Y$ you get a solution to the system. So, the number of solutions is the same as the number of possible $Y$. That is $2^m$.
• What kind of 2-coloring are you considering? If you are considering proper vertex 2-coloring, then any connected bipartite graph has exactly 2 proper colorings. However, if you are considering any 2-coloring, them the number is $2^k$ where $k$ is the number of vertices of the graph. – hbm Dec 19 '13 at 20:41