- Practice
- About 19 min
- 5 practice questions
Boolean matrices and modular arithmetic
Find the join and meet of Boolean matrices and state their properties, work with congruence modulo n and the residue classes ℤₙ, and use operation tables for +ₙ and ×ₙ to find identities and inverses.
If something looks wrong, please tell us.
By the end of this lesson you can
- Compute the join A ∨ B and the meet A ∧ B of two Boolean matrices.
- State which properties join and meet satisfy, with their identities.
- Use congruence a ≡ b (mod n) and list the residue classes of ℤₙ.
- Build tables for addition and multiplication modulo n and read identities and inverses from them.
Binary operations are not only about numbers. Two important discrete examples are operations on matrices whose entries are only 0 and 1 (used for switches that are on or off, and for networks), and arithmetic with remainders (used in clocks, calendars and check digits).
Boolean matrices: join and meet
A Boolean matrix is a matrix whose entries are each 0 or 1. For Boolean matrices A = [aᵢⱼ] and B = [bᵢⱼ] of the same order:
- The join A ∨ B = [aᵢⱼ ∨ bᵢⱼ], where aᵢⱼ ∨ bᵢⱼ = 1 if either entry is 1 and 0 if both are 0. In other words a ∨ b = max(a, b).
- The meet A ∧ B = [aᵢⱼ ∧ bᵢⱼ], where aᵢⱼ ∧ bᵢⱼ = 1 if both entries are 1 and 0 otherwise. In other words a ∧ b = min(a, b).
Worked example 1: join and meet
Let A have rows (1, 0, 1) and (0, 1, 1), and B have rows (0, 0, 1) and (1, 1, 0). Entry by entry, A ∨ B has rows (1∨0, 0∨0, 1∨1) = (1, 0, 1) and (0∨1, 1∨1, 1∨0) = (1, 1, 1). A ∧ B has rows (1∧0, 0∧0, 1∧1) = (0, 0, 1) and (0∧1, 1∧1, 1∧0) = (0, 1, 0).
On the set 𝔹 of all Boolean matrices of one order, join is closed, commutative and associative; its identity is the null matrix O (A ∨ O = A), but there are no inverses, since A ∨ B = O is impossible when A has a 1. Meet is also closed, commutative and associative; its identity is the matrix U with every entry 1 (A ∧ U = A), and again inverses do not exist in general.
Congruence modulo n
Fix an integer n > 1, the modulus. We write a ≡ b (mod n), read "a is congruent to b modulo n", when a − b = nk for some integer k; b is usually taken as the least non-negative remainder, 0 ≤ b ≤ n − 1, when a is divided by n. For example 23 ≡ 2 (mod 7) because 23 − 2 = 21 = 7 × 3, and −13 ≡ 2 (mod 5) because −13 − 2 = −15 = 5 × (−3).
Dividing integers by n leaves remainders 0, 1, …, n − 1, which split ℤ into residue classes. For n = 4: [0] = {…, −8, −4, 0, 4, 8, …}, [1] = {…, −7, −3, 1, 5, 9, …}, [2] = {…, −6, −2, 2, 6, 10, …}, [3] = {…, −5, −1, 3, 7, 11, …}. We write ℤ₄ = {[0], [1], [2], [3]} and usually use the remainders 0, 1, 2, 3 as names. According to the textbook, modular arithmetic is used in book numbering: the old 10-digit ISBN ends in a check digit worked out modulo 11, and the 13-digit ISBN in one worked out modulo 10.
On ℤₙ define addition modulo n: a +ₙ b = the remainder of a + b on division by n, and multiplication modulo n: a ×ₙ b = the remainder of a × b on division by n.
Worked example 2: addition modulo 4
| +₄ | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 2 | 3 | 0 |
| 2 | 2 | 3 | 0 | 1 |
| 3 | 3 | 0 | 1 | 2 |
- Closure: every box holds exactly one element of ℤ₄.
- Commutative: the table is symmetric about the main diagonal.
- Associative: a table cannot show this at a glance; check triples, e.g. (2 +₄ 3) +₄ 3 = 1 +₄ 3 = 0 and 2 +₄ (3 +₄ 3) = 2 +₄ 2 = 0. It holds for all triples because ordinary + is associative.
- Identity: the row and column headed 0 repeat the headings, so 0 is the identity.
- Inverse: 0 appears in every row and column. Find 0 in the row of a; the column heading above it is a⁻¹. So 0⁻¹ = 0, 1⁻¹ = 3, 2⁻¹ = 2, 3⁻¹ = 1.
Worked example 3: multiplication modulo 7 on {1, 2, 3, 4, 5, 6}
| ×₇ | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 2 | 4 | 6 | 1 | 3 | 5 |
| 3 | 3 | 6 | 2 | 5 | 1 | 4 |
| 4 | 4 | 1 | 5 | 2 | 6 | 3 |
| 5 | 5 | 3 | 1 | 6 | 4 | 2 |
| 6 | 6 | 5 | 4 | 3 | 2 | 1 |
Every entry lies in the set, so ×₇ is binary on it. The table is symmetric (commutative); associativity is inherited from ordinary multiplication. The row headed 1 repeats the headings, so 1 is the identity. The identity 1 appears in every row, giving the inverses 1⁻¹ = 1, 2⁻¹ = 4, 3⁻¹ = 5, 4⁻¹ = 2, 5⁻¹ = 3, 6⁻¹ = 6. Compare {1, 2, 3, 4, 5} under ×₆: 2 ×₆ 3 = 0, which is not in the set, so ×₆ is not even binary there.
Join and meet; +ₙ and ×ₙ
-
Join ∨
Entry-wise max
- Identity: null matrix O
- No inverses
-
Meet ∧
Entry-wise min
- Identity: all-ones matrix U
- No inverses
-
+ₙ on ℤₙ
Remainder of a + b
- Identity 0
- Inverse of a is n − a (0 for 0)
-
×ₙ
Remainder of a × b
- Identity 1
- Inverses only where 1 appears in the row
Key takeaways: join and meet work entry by entry with max and min; their identities are the null matrix and the all-ones matrix, and neither has inverses. a ≡ b (mod n) means n divides a − b. In an operation table, the identity's row and column copy the headings, and an element has an inverse exactly when the identity appears in its row.
Check your understanding
-
1. What is the least non-negative r with 47 ≡ r (mod 6)?
- 1
- 3
- 5
- 11
Show answer
Answer: C. 47 = 6 × 7 + 5, so 47 − 5 = 42 is a multiple of 6 and r = 5.
-
2. Under multiplication modulo 7 on {1, 2, 3, 4, 5, 6}, what is the inverse of 3?
- 5
- 4
- 2
- 6
Show answer
Answer: A. 3 × 5 = 15 = 2 × 7 + 1, so 3 ×₇ 5 = 1, the identity. Hence the inverse of 3 is 5.
-
3. To which residue class in ℤ₅ does −13 belong?
- [3]
- [2]
- [1]
- [4]
Show answer
Answer: B. −13 = 5 × (−3) + 2, with remainder 2 in the range 0 to 4. So −13 ≡ 2 (mod 5) and −13 ∈ [2].
-
4. A has rows (1, 0) and (0, 1); B has rows (0, 0) and (1, 1). What is A ∨ B?
- Rows (0, 0) and (0, 1)
- Rows (1, 0) and (1, 1)
- Rows (1, 1) and (1, 1)
- Rows (1, 0) and (0, 1)
Show answer
Answer: B. Join takes the larger entry in each place: first row (1∨0, 0∨0) = (1, 0); second row (0∨1, 1∨1) = (1, 1).
-
5. What is the identity element for the meet ∧ on 2 × 2 Boolean matrices?
- The null matrix
- The unit matrix with rows (1, 0) and (0, 1)
- There is none
- The matrix with every entry 1
Show answer
Answer: D. a ∧ 1 = min(a, 1) = a for a = 0 or 1, so A ∧ U = A when U has every entry 1. The null matrix is the identity for join instead.
Sign in to keep track of the lessons you finish.