SEM 6 › Discrete Mathematics › Week 05
Discrete Mathematics · Week 05

Matrices

Matrices to represent data, size, square and equal matrices, rows, columns and entries, addition, multiplication and its algorithm, non-commutativity, identity, powers, transpose, symmetric matrices, and zero–one matrices (join and meet).

ITE38221 video · 30 min📄 Lesson 5.pdf

1Matrices represent data

Matrices are used throughout discrete maths to express relationships between elements of sets. For example, they're used to model communication networks and transportation systems. Later they represent relations (Week 9) and graphs (Week 11).

Definition 1
  • A matrix is a rectangular array of numbers.
  • A matrix with m rows and n columns is an m × n matrix (rows first).
  • A matrix with the same number of rows and columns is a square matrix.
  • Two matrices are equal if they have the same size and equal entries in every position.
Example 5.1.1

101123 is a 2 × 3 matrix: 2 rows, 3 columns.

Rows, columns, entries (Definition 2)

  • A = [aᵢⱼ] is the general notation.
  • The i-th row is the 1 × n matrix [aᵢ₁ aᵢ₂ … aᵢₙ].
  • The j-th column is an n × 1 matrix (a₁ⱼ, a₂ⱼ, …, aₙⱼ written vertically).
  • The (i, j)-th entry is aᵢⱼ: row i, column j.

2Matrix addition

If A = [aᵢⱼ] and B = [bᵢⱼ] are both m × n, then A + B = [aᵢⱼ + bᵢⱼ]. Add entries in the same position.

Example 5.2.1

A = 104−1220−2−3 B = −1352−2−32−30

A + B = 03910−12−5−3

Common mistake

You can only add matrices of the same size.

3Matrix multiplication

Let A be m × k and B be k × n. The product AB is m × n, and its (i, j) entry is the sum of products of row i of A with column j of B:

cij = ai1b1j + ai2b2j + … + aikbkj
Size rule

(m × k) · (k × n) = m × n. The inner sizes must match; the outer sizes give the result's size.

Example 5.2.2

A = 314−123 (2 × 3), B = 13−34−12241 (3 × 3), so AB is 2 × 3.

Entry Row of A · column of B Value
c₁₁ (3)(1) + (1)(4) + (4)(2) 15
c₁₂ (3)(3) + (1)(−1) + (4)(4) 24
c₁₃ (3)(−3) + (1)(2) + (4)(1) −3
c₂₁ (−1)(1) + (2)(4) + (3)(2) 13
c₂₂ (−1)(3) + (2)(−1) + (3)(4) 7
c₂₃ (−1)(−3) + (2)(2) + (3)(1) 10

AB = 1524−313710

Matrix multiplication is NOT commutative (Example 5.2.3)

A = 1121, B = 2111

AB = 3253 but BA = 4332

So AB ≠ BA. Also, AB may exist while BA doesn't (when the sizes don't match).

Algorithm 1: matrix multiplication

procedure matrix multiplication (A: m×k, B: k×n)
for i := 1 to m
    for j := 1 to n
    begin
        c[i][j] := 0
        for q := 1 to k
            c[i][j] := c[i][j] + a[i][q] * b[q][j]
    end
{C = [c[i][j]] is the product of A and B}
Example 5.2.4 — cost of multiplying two n × n matrices
  • The product has n² entries.
  • Each entry needs n multiplications and n − 1 additions.

Total: n³ multiplications and n²(n − 1) additions. That's O(n³).

🧪 Try it — Matrix calculator (click a cell of AB to see its working)

4Identity, powers, transpose & symmetric

Identity matrix (Definition 3)

Iₙ is the n × n matrix with 1s on the main diagonal and 0s everywhere else. E.g. I₃ = 100010001

If A is n × n: IₙA = AIₙ = A

Powers of matrices

For a square n × n matrix A:

A⁰ = Iₙ, Aʳ = A·A·…·A (r times)

Transpose (Definition 3)

The transpose Aᵗ of an m × n matrix is the n × m matrix you get by swapping rows and columns.

Example: A = 123456, so Aᵗ = 142536

Symmetric matrix (Definition 3)

A square matrix A is symmetric if A = Aᵗ. It is a mirror image across the main diagonal: aᵢⱼ = aⱼᵢ.

Example: 11−1120−105 is symmetric.

Useful transpose facts

(A + B)ᵗ = Aᵗ + Bᵗ · (AB)ᵗ = Bᵗ Aᵗ (the order reverses) · (Aᵗ)ᵗ = A

5Zero–one matrices: join and meet

A zero–one matrix has entries that are only 0 or 1. Its arithmetic uses the Boolean operations ∧ and ∨:

b₁ ∧ b₂ = 1 if b₁ = b₂ = 1, otherwise 0
b₁ ∨ b₂ = 1 if b₁ = 1 or b₂ = 1, otherwise 0

For m × n zero–one matrices A = [aᵢⱼ] and B = [bᵢⱼ]:

Operation Notation (i, j) entry
Join A ∨ B aᵢⱼ ∨ bᵢⱼ (OR)
Meet A ∧ B aᵢⱼ ∧ bᵢⱼ (AND)
Example 5.2.4 (join and meet)

A = 101010, B = 010110

A ∨ B = 1∨00∨11∨00∨11∨10∨0 = 111110

A ∧ B = 1∧00∧11∧00∧11∧10∧0 = 000010

Exam focus

Expect:

  • Matrix sizes
  • Addition
  • Multiplication with all working (cij sums)
  • Checking which products are defined and their sizes (e.g. A 3×4, B 4×5, C 4×4: AB is 3×5; BA is undefined; AC is 3×4; CA is undefined; BC is undefined; CB is 4×5)
  • Showing AB ≠ BA
  • Transpose / symmetric
  • Join and meet
  • Powers Aʳ
  • Counting operations in Algorithm 1

6Quick revision sheet

Concept Remember it as
m × n Rows × columns; square if m = n
aᵢⱼ Row i, column j
Equal Same size + same entries
A + B Same size; add entrywise
AB (m×k)(k×n) = m×n; cij = row i · column j
Commutative? No: AB ≠ BA in general
Algorithm 1 Three nested loops; n³ multiplications, n²(n−1) additions
Identity IₙA = AIₙ = A
Powers A⁰ = Iₙ; Aʳ = A·…·A
Transpose Swap rows and columns; (AB)ᵗ = BᵗAᵗ
Symmetric A = Aᵗ
Join / meet Entrywise OR / AND for 0–1 matrices

?Self-check quiz

12 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.

← PreviousSequences & SummationsNext →Number Theory & Cryptography