solving an XOR matrix

Question

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!!!

Answer 1

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

Answer 2

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