3
$\begingroup$

Let $\mathbb{Z}_2 = \{0,1\}$ be the integers mod $2$. Let $A \in \mathbb{Z}_2^{m \times n}$ and $u,v \in \mathbb{Z}_2^m$. Consider the problem of determining whether there is a vector $x \in \mathbb{Z}_2^n$ such that $Ax = u \vee Ax = v.$ One can reduce this problem to the problem of determining whether there is a solution to this system: \begin{pmatrix} 0 & \ldots & 0 & 1 & 1 \\ A_{1,1} & \ldots & A_{1,n} & u_1 & v_1 \\ \vdots & \ddots & \vdots & \vdots & \vdots \\ A_{m,1} & \ldots & A_{m,n} & u_m & v_m \\ ­\end{pmatrix} \begin{pmatrix} x_1 \\ \vdots \\ x_n \\ y_1 \\ y_2\end{pmatrix} = \begin{pmatrix}1 \\ 0 \\ \vdots \\ 0\end{pmatrix} since each line gives $A_i \cdot x = y_1 u_i + y_2 v_i$ and $(y_1, y_2) \in \{(0,1), (1,0)\}$.

I wonder if there is such a strategy to reduce $Ax = u \vee Ax = v$ to $By = w$ over $\mathbb{Z}_3$.

  • 0
    Shawn, keep in mind there is something very special about $\mathbb{Z}_2$. Let 1 = True and 0 = False. Then multiplication is the same as conjunction: $1 \wedge 0 = 1 \cdot 0 =0$ etc. and addition is the same as exclusive or (XOR): $0+0=0$, $0+1=1$, $1+0=1$, $1+1=0$. This may help explain why such a trick involving ``Either system A is consistent OR system B is consistent'' works just for $\mathbb{Z}_2$.2011-09-25

1 Answers 1

0

There is not. The solutions to a system of linear equations form an affine subspace, whose intersection with another affine subspace is again an affine subspace, and over a finite field $\mathbb F$ the cardinality of an affine subspace is a power of $|\mathbb F|$. If $Ax=u$ and $Ax=v$ both have solutions, they both have the same number of solutions, and if $u\neq v$, the solutions are all distinct, so the total number of solutions for the disjunction is twice the number for the individual equations. In the case of $\mathbb Z_2$, that's OK, since you can write a system with twice as many solutions. You can't do this in the case of $\mathbb Z_3$, at least not with a vector consisting of the $x_i$ and some auxiliary variables, since the resulting set of solutions for the $x_i$ is the intersection of an affine subspace with the affine subspace of solutions for the entire vector, whose cardinality is a power of $3$, whereas the cardinality of the desired solution set is twice a power of $3$.

  • 0
    Could there be a way to have $Ax = u \vee Ax = v$ has a solution iff $By = w$ has a solution, for some $B,w$?2011-09-24