3
$\begingroup$

I have to study systems of equations in a Boolean algebra, the matrix is $m\times n$ with $m\neq n$. The Boolean algebra is actually the simplest one, it contains only $0$ and $1$, let us denote it by $\mathbb{B}$. What I need to know is a necessary and sufficient condition for an application from $\mathbb{B}^n$ to $\mathbb{B}^m$ to be one-to-one. I read in the paper "Linear Boolean Equations and Generalized Minterms" by S. Rudeanu (Discrete Math 43 (1983) 241-248) that Löwenheim proved some theorems in a paper written in 1919. Hence my question :

Is there any more recent reference about this subject (systems of equations in Boolean algebra) ? And where can I find a proof of Löwenheim's theorem (that could help to understand) ?

All references I can found in some papers I can find (with difficulty) on the Web are unavailable online, and unavailable in my library.

EDIT: Here is Löwenheim's theorem I mention above: In a Boolean algebra $(\mathbb{B},\cup,.,',0,1)$ (I guess that $.$ is the intersection and $'$ the negation), to each $(b_1,\dots,b_m)\in \mathbb{B}^m$, we can associate the system of equations $$\bigcup_{j=1}^na_{ij}x_j=b_i \ \ \ (i=1,\dots,m).$$ Löwenheim proved in a 1919 paper that the system is consistent (I guess that that means that there is a solution) for a given $(b_1,\dots,b_m)\in \mathbb{B}^m$ if and only if $$b_i\leq \bigcup_{j=1}^n a_{ij} \prod_{h=1,h\neq i}^m (a'_{hj}\cup b_h)\ \ \ (i=1,\dots,m).$$ I guess that $\leq$ means the inclusion (it is not explained in the paper). In the same paper, the author calls $x+y=xy'\cup x'y$ the ring sum which is "xor".

$\endgroup$
  • $\begingroup$ I may be mistaken, but why do you insist on calling this a Boolean algebra? Why not to stick to and and xor and just do usual linear algebra over $\Bbb F_2$. $\endgroup$ – Alex Degtyarev Nov 20 '14 at 9:24
  • $\begingroup$ Probably because I am using the terminology in a wrong way: I don't know almost anything in Boolean algebra. I use "or", union and not "xor", for the addition. For me $1+1=1$, and not $0$. $\endgroup$ – Philippe Gaucher Nov 20 '14 at 9:46
  • $\begingroup$ That's exactly my question: on the one hand, all Boolean operations can be interpreted in terms of "and" and "xor"; on the other hand, the latter are merely the operations in the field $\Bbb F_2$, hence, one can apply college linear algebra to your problem. Then, if absolutely necessary, the obvious answer (the matrix has appropriate rank, or nullity is zero, or, in the square case, $\det\ne0$, etc.) can be translated back to "and" and "or". $\endgroup$ – Alex Degtyarev Nov 20 '14 at 10:16
  • $\begingroup$ Accidentally, I think your $x+y=xy'\cup x'y$ is "xor" (symmetric difference) for sets. But for just $0$, $1$ it's much simpler, as you can easily see from the truth tables. Anyway, this is just a suggestion, to use the kettle principle. $\endgroup$ – Alex Degtyarev Nov 20 '14 at 10:21
  • $\begingroup$ It is not a numerical system of equations (I cannot take a computer and ask it to solve it), but I understand what you mean. A round trip between the 2-element Boolean algebra and $\mathbb{F}_2$ could help. Anyway, any reference about the subject is welcome. $\endgroup$ – Philippe Gaucher Nov 20 '14 at 10:22
4
$\begingroup$

Let $A$ be an $m\times n$ Boolean matrix. Then the mapping $v\mapsto Av$ is 1:1 iff $n\leq m$ and some subset of $n$ rows of gives a permutation matrix.

The reason is duality of modules over the Boolean semiring shows that $A$ is 1:1 iff the transpose is onto. Since the standard basis vectors of a free $\mathbb B$-module are join irreducible a Boolean matrix gives an onto map iff each standard basis vector appears as a column.

Added per request for more detail.

A $\mathbb B$-module is the same thing as a join-semilattice $M$. The dual $M^*$ is the set of all join-semilattice homomorphisms $M\to \mathbb B$ with pointwise join. If $M$ is finite, then the dual consists of the mappings $f_m$ with $m\in M$ where $f_m(x)=0$ if $x\leq m$ and $1$ else. Indeed, choose $m$ to be the join of all elements mapping to $0$.

It follows if $N$ is a submodule of $M$ then the restriction $M^*\to N^*$ is surjective. Also the canonical map to the double dual is an ISO for $M$ finite. It now follows a map of finite $\mathbb B$-modules is injective iff the dual map is surjective. For a matrix map the dual is the transpose.

If we view $\mathbb B^n$ as a join semilattice, the basis consists of atoms. It follows a matrix transformation is onto iff each basis vector appears in some column. Dualizing gives the result.

$\endgroup$
  • $\begingroup$ Could you expand the proof please and/or give some references about e.g. duality of modules over Boolean semiring ? A basic course for a beginner I mean. $\endgroup$ – Philippe Gaucher Nov 20 '14 at 15:38
  • $\begingroup$ Some of this is discussed in Chapter 9 of my book with John Rhodes, The q-theory of finite semigroups. Either the result you want or its dual might even be there or in my paper with Izhakian and Rhodes on representations of monoids over semirings. I don't have references in front of me. I can try to write something more when I have a better computer than a smartphone $\endgroup$ – Benjamin Steinberg Nov 20 '14 at 17:45

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.