• 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

Every entry is in ℤ₄, so +₄ is a binary operation
+₄0123
00123
11230
22301
33012
  • 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}

For example 3 × 5 = 15 = 2 × 7 + 1, so 3 ×₇ 5 = 1
×₇123456
1123456
2246135
3362514
4415263
5531642
6654321

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. 1. What is the least non-negative r with 47 ≡ r (mod 6)?

    1. 1
    2. 3
    3. 5
    4. 11
    Show answer

    Answer: C. 47 = 6 × 7 + 5, so 47 − 5 = 42 is a multiple of 6 and r = 5.

  2. 2. Under multiplication modulo 7 on {1, 2, 3, 4, 5, 6}, what is the inverse of 3?

    1. 5
    2. 4
    3. 2
    4. 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. 3. To which residue class in ℤ₅ does −13 belong?

    1. [3]
    2. [2]
    3. [1]
    4. [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. 4. A has rows (1, 0) and (0, 1); B has rows (0, 0) and (1, 1). What is A ∨ B?

    1. Rows (0, 0) and (0, 1)
    2. Rows (1, 0) and (1, 1)
    3. Rows (1, 1) and (1, 1)
    4. 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. 5. What is the identity element for the meet ∧ on 2 × 2 Boolean matrices?

    1. The null matrix
    2. The unit matrix with rows (1, 0) and (0, 1)
    3. There is none
    4. 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.

Privacy · Terms · Refunds · Delivery