Discrete Mathematics - Lattices and boolean Algebra

Question

Let $A$ be the set of all $2\times2$ boolean matrices and $R$ be a relation defined on $A$ as $M \mathrel{R} N$ if and only if $m_{ij} \leqslant n_{ij}$, where $1 \leqslant i, j \leqslant 2$. Is $(A,R)$ a lattice? Justify.

I am unable to solve the above question. I already know the following: There are 16 elements in set $A$. Now when i try to calculate relation $R$ according to the given conditions i am getting 81 pairs in relation $R$. Drawing a hasse diagram and calculating least upper bound and greatest lower bound for each point in the hasse diagram will go too lengthy. Is there a better method to do this?? Please help.

Answer 1

It looks like your structure is simply ${\Bbb B}^4$, the product of four copies of the Boolean lattice ${\Bbb B} = \{0, 1\}$, ordered by $0 \leqslant 1$. Thus, yes, $(A, R)$ is a lattice.

Answer 2

If you have two matrices $A=\{a_{ij}:0\leq i,j\leq1\}$ and $B=\{b_{ij}:0\leq i,j\leq1\}$, then $$A \wedge B = C = \{c_{ij}:0\leq i,j\leq1\}$$ and $$A\vee B = D =\{d_{ij}:0\leq i,j\leq1\},$$ where $$c_{ij}=\min\{a_{ij},b_{ij}\}$$ and $$d_{ij}=\max\{a_{ij},b_{ij}\}.$$ This also forms a Boolean algebra, with $$A' =\{1- a_{ij}:0\leq i,j\leq1\}.$$

Answer 3

In general, if $\{ L_\alpha \}$ is a family of lattices, then the Cartesian product $\prod_{\alpha} L_{\alpha}$ also has the structure of a lattice given by $\mathbf{x} \wedge \mathbf{y} = (x_\alpha \wedge y_\alpha)_{\alpha}$, $\mathbf{x} \vee \mathbf{y} = (x_\alpha \vee y_\alpha)_{\alpha}$ for $\mathbf{x}, \mathbf{y}$ in the product. This fact, although obvious, is actually very convenient as it allows you to point out complicated lattices as the product of less-complicated ones, or as sublattices of the product of less-complicated lattices. (If you are interested, Google "Dilworth's Embedding Theorem.")

Sometimes is is useful to indentify matrices with elements in blank as a product of blank the number of entries in such matrices times. You see this in many areas of mathematics. Lie group theory comes to mind. If you want to think about $GL_n(\mathbb{R})$ as a space, then you can think about how it sits inside $\mathbb{R}^{n \times n}$.