solving an XOR matrix
I'm working on a somewhat-unique linear algebra problem arising from XORing files together in order to encode them, and then figuring out how to subsequently recreate the original files from the encoded ones. For a trivial ($n=3$) example, files $f1-f3$ are combined to create the encoded files $c1-c3$ according to the following system:
$c1 = f1 \\ c2 = f1 \oplus f2 \oplus f3 \\ c3 = f1 \oplus f3$
It then follows that given the encoded files $c1-c3$, we can recreate files $f1-f3$ as follows:
$f1 = c1\\ f2 = c2 \oplus c3 \\ f3 = c1 \oplus c3$
So, given the above examples (which I just wrote/solved ad-hoc by looking at it), I'm trying to figure out how to go about solve a larger system (i.e. $n \geq 100$), mathematically and eventually programatically. Looking at the above example, I see how I could maybe represent it as matrix multiplication:
$ \begin{bmatrix}1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix} \begin{bmatrix}f1 \\ f2 \\ f3\end{bmatrix} = \begin{bmatrix}c1 \\ c2 \\ c3\end{bmatrix} $
except I'm not quite sure how to go about the math or if I'm allowed to just set up the matrices like this since I'm using $\oplus$ (which cancels itself out) instead of $+$. I'm also unsure how to go about solving the system, since I haven't done any linear algebra in almost a decade. For example, to find $f2$ in terms of $c1-c3$, should I just solve something like the matrix below?
$ \begin{bmatrix}1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix} \begin{bmatrix}0 \\ f2 \\ 0\end{bmatrix} = \begin{bmatrix}c1 \\ c2 \\ c3\end{bmatrix} $
Anyways, any tips or pointers, even just on math terminology, operations, or help in describing what I'm trying to do, would be much appreciated. Thanks!!!
$\endgroup$2 Answers
$\begingroup$What you're trying to do is solve a linear equation system with values in the finite field $\mathbb{F}_2$ instead of in $\mathbb{R}$. I have great news for you: it'll work just fine! Solve it like you would solve a real-valued system, using addition of rows and such, just make sure to use $\oplus$ when you would use $+$ or $-$.
Note: Solve $$\begin{bmatrix}1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix} \begin{bmatrix}f1 \\ f2 \\ f3\end{bmatrix} = \begin{bmatrix}c1 \\ c2 \\ c3\end{bmatrix}$$ as usual, using Gaussian elimination on $$\left[\begin{array}{ccc|c}1 & 0 & 0 & c1\\ 1 & 1 & 1 & c2 \\ 1 & 0 & 1 & c3\end{array}\right].$$
If you want to find a general scheme to calculate $f1, f2, f3$ from $c1, c2, c3$, why not simply invert your coefficient matrix?
$$\begin{bmatrix}1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix}^{-1} \begin{bmatrix}c1 \\ c2 \\ c3\end{bmatrix} = \begin{bmatrix}f1 \\ f2 \\ f3\end{bmatrix}$$
Inverting $\mathbb{F}_2$-matrices works just like with real-valued matrices, but again, use $\oplus$ when you would use $+$ or $-$. In this case, you'll get
$$\begin{bmatrix}1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix}^{-1} = \begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix}.$$
$\endgroup$ 1 $\begingroup$Why not take
$$ c1 = f1\\ c2 = f1 \oplus f2 \\ c3 = f1 \oplus f2 \oplus f3 $$
That way,
$$ f_2= c_2 \oplus c_1$ \\ f_3 = c_3 \oplus c_2 \oplus c_1 \\ \ldots \\ fn = c_n \oplus c_{n -1} \oplus \ldots \oplus c_1 $$
$\endgroup$ 1
