# Solving a Linear Equation over $2^X$

I was reading Vinberg's "A Course in Algebra" and in the opening line of chapter 2 he says, "Fix a field $\mathbb K$. We are going to abuse the language slightly and call elements of $\mathbb K$ numbers."

Anyway, linear algebra and solving systems of equations is present (it seems) in tons of abstract books for various reasons (analysis, algebra, geometry, ...) but the most "abstract" I've seen the discussion become is the use of the field $\mathbb Q$ or $\mathbb C$. I'm really wanting to make solving systems of equations a more abstract thing, where we don't even deal with equations of "numbers".

For example, if $X$ is a set and $2^X$ is the set of all its subsets, it can be shown that $2^X$ is a ring with respect to the operations of symmetric difference: $M \Delta N = (M - N) \cup (N- M)$ and intersection, taken for addition and multiplication, respectively. (The ring is commutative and associative).

Well, what does solving a system of equations of this sort look like? Are there other "abstract" systems of equations that you can think of, which are interesting.

Further, are there any connections of this idea with other things we are familiar with? Positive definiteness? Eigenvalue problem? Uniqueness and Existence of solution, etc...

-
I've added some details that show the mechanics of exactly what you're asking to my answer. – Arkamis Aug 25 '12 at 16:35
This construction is the same as considering the direct product of $\mathbb{F}_2$ over $X$ as the indexing set, as Ed's answer tries to argue. However, this does not make it into a field. Solving linear equations can still be done using matrices, only checking that the determinant is invertible is more complicated. – ronno Aug 25 '12 at 17:59

If $\Bbb K$ is a field, then it is equipped with operators $+$ and $\cdot$, and those operators are well-defined and the field axioms are satisfied.

Numbers in $\Bbb Q$ are just elements of $\Bbb Q$ where we have a familiar interpretation for the operators $+$ and $\cdot$. But there's nothing preventing us from making a field of letters, and defining $A+B = C$, $A+C = D$, and so on...

The solution of a linear system of $n$ equations in $\Bbb Q$ yields some tuple in $\Bbb Q^n$ such that each element of the tuple can be written in terms of combinations of elements in $\Bbb Q$ operated on in some order by $+$ and $\cdot$.

So solutions in a linear system in $\mathbf{2^X}$ would look like a combination of elements of $\mathbf{2^X}$ with the operations $\Delta$ and $\cap$ respectively. Since $\mathbf{2^X}$ is a ring, it is closed under these operations, and the resulting element will just be another element in $\mathbf{2^X}$.

In other words, it looks exactly like a solution in $\Bbb Q$, but with different operations and different elements.

As far as what we can define in this system, we need to define a vector space over $\mathbf{2^X}$. Once this vector space is defined, we can define matrix-vector multiplication in all the same ways, and so we could have things like eigenvalues, etc. Things get a little unfamiliar when $\mathbf{X}$ is finite; however, to find an analog, you could look how linear systems work in a field of prime characteristic, such as $\Bbb Z_p.$

Let's first consider a simple case, say $\Bbb Z_5$. Define a 2-dimensional vector space, $\Bbb Z_5^2$. Let's set $x = 3$ and $y = 2$ (but pretend that we don't know that!).

Then, we can write the following two equations \begin{align*} 2x + 3y & = & 2 \\ 4x + 2y & = & 1 \end{align*}

The matrix representation is exactly what we expect: $$\begin{pmatrix} 2 & 3 \\ 4 & 2 \end{pmatrix}\begin{pmatrix} x \\ y\end{pmatrix} = \begin{pmatrix} 2 \\ 1 \end{pmatrix}.$$

We can perform Gaussian elimination on this matrix, where we must simply remember that we're working in a field of characteristic 5. $$\begin{pmatrix}2 & 3 \\ 0 & 2-3\cdot 2\end{pmatrix}\begin{pmatrix}x \\ y\end{pmatrix} = \begin{pmatrix}2 & 3 \\ 0 & 1\end{pmatrix}\begin{pmatrix}x \\ y\end{pmatrix} = \begin{pmatrix}2 \\ 1-2\cdot 2\end{pmatrix} = \begin{pmatrix} 2 \\ 2\end{pmatrix}.$$

This gives us $y = 2$ and $2x+1=2$, the latter of which is solved as $2x = 1 \Longrightarrow x = 3$.

-
I'm not really sure what Z_p would look like here, but I do like the response. I was really hoping to get some more "nifty" examples. I mean of course we can abstractly say such a computation exists but I was hoping to get an intuition of what it would be like. – Squirtle Aug 24 '12 at 22:25
I can provide an example later... Its not as much an abstraction as you might think. – Arkamis Aug 24 '12 at 23:52
@dustanalysis I have added some details that work out some examples. – Arkamis Aug 25 '12 at 16:35
Your argument for why $\mathbb{F}$ is a field does not work. In fact it is not, with the multiplication you defined. What is the product of (1,0,0) with (0,1,0)? – ronno Aug 25 '12 at 17:57
@ronno Shoot, you are quite right! I need to re-visit my notes to see how I wanted to define things to avoid this very problem! – Arkamis Aug 25 '12 at 21:28