Chapter 5: Matrices
Section 5.7 Matrices
Boolean Matrices
We will be interested in matrics with only 0s and 1s as entries, called
Boolean matrices
. We can define an operation of Boolean matrix multiplication \(A \times B\) on Boolean matrices using Boolean
multiplication and Boolean addition instead of regular multiplication and addition.
Boolean Multiplication
\( x ∧ y = \) min\((x,y)\)
| x |
y |
x ∧ y |
| 1 |
1 |
1 |
| 1 |
0 |
0 |
| 0 |
1 |
0 |
| 0 |
0 |
0 |
Boolean Addition
\( x ∨ y = \) max\((x,y)\)
| x |
y |
x ∨ y |
| 1 |
1 |
1 |
| 1 |
0 |
1 |
| 0 |
1 |
1 |
| 0 |
0 |
0 |
Boolean matrix multiplication
The operation of
Boolean matrix multiplication \(A \times B\)
is defined:
$$
c_{ij} = ∨_{k=1}^{m}(a_{ik} ∧ b_{kj})
$$
Example 1:
Let A and B be Boolean matrices.
$$
A =
\begin{pmatrix}
1 & 1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}
\quad
B =
\begin{pmatrix}
1 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{pmatrix}
$$
Then:
$$
A ∧ B=
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}
\quad
A ∨ B =
\begin{pmatrix}
1 & 1 & 0 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{pmatrix}
$$
and the Boolean product \(A \times B\) is:
$$
A \times B =
\begin{pmatrix}
1 & 1 & 1 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{pmatrix}
$$
Practice
1. In the above Example 1, does \(A \times B = A · B\) ?
2. In the above Example 1, please compute \(B \times A\).
Reference
saylor academy