1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you. It's a very nice observation and shows my rusty Algebra. However, I am still confused about, "Use this observation to get a polynomial time algorithm to count a number of 2-colorings." I guess that the connection between a 2-colorability graph problem and the matrix is because of mod2 constriction? I know that the 2-coloring problem reduces to a decidable problem iff the graph is bi-partite or not; this takes polynomial time. ' $\endgroup$ – knowKnothing Dec 18 '13 at 11:49
  • $\begingroup$ What is the precise statement of "count a number of two coloring" problem? $\endgroup$ – hbm Dec 18 '13 at 12:59
  • $\begingroup$ Yes, I don't understand the statement either. I can only guess what the problem means, I could state some algorithm for decidability of a bi-partite graph. But, I am not fully sure what the "count a number of two coloring" statement means. $\endgroup$ – knowKnothing Dec 18 '13 at 13:23
  • $\begingroup$ I think that the statement refers to specific colorability and linear algebra differences. For Linear Algebra, vector [1 0 0] is different than vector [0 1 0], but for graph-colorability theory both vectors represent 3 colorability valid vectors. So, I think the question of counting a number of 2-colorings refer to find values of Y that are valid for colorability. $\endgroup$ – knowKnothing Dec 19 '13 at 20:35
  • $\begingroup$ 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. $\endgroup$ – hbm Dec 19 '13 at 20:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.