Instruction Grids

Understanding Matrices

---

The Simple Story

Imagine you have a bingo card - a grid of boxes with numbers or arrows in each one.

Instead of one arrow telling you where to go, you have a whole table of arrows!

Each box in the table tells you: "If you follow THIS rule, go HERE."

That table = that's a matrix!

Matrices let you do many vector operations at once!

---

Mental Model

Hold this picture in your head:

Matrix = Bingo card of instructions

Instructions for how to transform one vector into another:

          Input: v₀ v₁ v₂ v₃ (4 input values)
          
  Output:
  w₀ =  [ a↦b  a↦c  a↦e  a↦g ] ← First output
  w₁ =  [ b↦c  b↔d  b↦e  b↦h ] ← Second output
  w₂ =  [ c↦e  c↔d  c↔f  c↦e ] ← Third output

Each position in matrix = "How much input vⱼ contributes to output wᵢ"

Think of it like this:

• Bingo card: Each square = instruction
• Recipe book: Each page = combining different ingredients
• Playlist: Each song = different mood

Matrix = Table combining all inputs to create all outputs

---

See It Happen

Let's see how a matrix transforms vectors:

---

Try It Yourself

Question 1: Given matrix M and vector v, what's the result?

Matrix M:

Row 1: [1, 2, 3]
Row 2: [0, 1, 4]

Vector v: (5, 2, 1)

Show Answer

Compute each output:

Output w₀ (first row): 1·5 + 2·2 + 3·1 = 5 + 4 + 3 = 12

Output w₁ (second row): 0·5 + 1·2 + 4·1 = 0 + 2 + 4 = 6

Result vector: (12, 6)

---

Question 2: If matrix A = [[2, 0], [1, 3]] and vector x = (4, 5), what's Ax?

Show Answer

Matrix A:

• Row 1: [2, 0]
• Row 2: [1, 3]

Compute:

Output y₀ = 2·4 + 0·5 = 8 + 0 = 8 Output y₁ = 1·4 + 3·5 = 4 + 15 = 19

Result: (8, 19)

---

Question 3: What's the matrix that sends (1, 0) → (2, 3) and (0, 1) → (5, 1)?

Show Answer

Matrix = [first column, second column]

Column 1 = image of (1, 0) = (2, 3) Column 2 = image of (0, 1) = (5, 1)

Matrix M:

[ 2  5 ]
[ 3  1 ]

Check:

• M·(1, 0) = (2, 3)
• M·(0, 1) = (5, 1)

---

The Math

Matrix Notation

Mathematicians write matrices with rows and columns:

$\mathbf{A} = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix}$

Where:

• $a_{ij}$ = Entry at position (row i, column j)
• Row i = Horizontal (left → right)
• Column j = Vertical (top → bottom)

Example 2×2 matrix: $\mathbf{A} = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$

Matrix-Vector Multiplication

To multiply matrix $\mathbf{A}$ by vector $\mathbf{v}$:

$\mathbf{A}\mathbf{v} = \begin{bmatrix} a_{11} & a_{12} & \dots \\ a_{21} & a_{22} & \dots \\ \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix} v_0 \\ v_1 \\ v_2 \\ \vdots \end{bmatrix} = \begin{bmatrix} a_{11}v_0 + a_{12}v_1 + \dots \\ a_{21}v_0 + a_{22}v_1 + \dots \\ \vdots \end{bmatrix}$

In words: Each output = sum of (row entries) × (vector entries)

Simplified:

• Output position 0 = dot product of row 0 and vector
• Output position 1 = dot product of row 1 and vector
• Output position i = dot product of row i and vector

Matrix Dimensions

If matrix $\mathbf{A}$ has $r$ rows and $c$ columns, and vector $\mathbf{v}$ has $c$ entries, then:

$\mathbf{A}\mathbf{v}$ = vector with $r$ entries

Example:

• 3×4 matrix × 4-entry vector = 3-entry output
• 2×2 matrix × 2-entry vector = 2-entry output

ML-KEM uses 3×3 matrix = 3-entry output

---

Why We Care

Problem: ML-KEM Has Many Parallel Operations

During key generation, ML-KEM computes:

$\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}$

Where:

• $\mathbf{A}$ = 3×3 matrix (9 entries)
• $\mathbf{s}$ = entry vector (3 entries)
• $\mathbf{e}$ = error vector (3 entries)

Without matrices, you'd write:

t₀ = A₀₀·s₀ + A₀₁·s₁ + A₀₂·s₂ + e₀
t₁ = A₁₀·s₀ + A₁₁·s₁ + A₁₂·s₂ + e₁
t₂ = A₂₀·s₀ + A₂₁·s₁ + A₂₂·s₂ + e₂

That's 3 equations with 9 matrix entries!

With matrix notation: $\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}$

One equation! Much simpler!

Matrix = Compacted Parallel Operations

Matrix-vector multiplication = computing MANY dot products in parallel:

Output entry 0 = dot(row 0, vector)
Output entry 1 = dot(row 1, vector)
Output entry 2 = dot(row 2, vector)

All done at once when you write: 𝐀𝐯

This is powerful for:

• Cryptography (ML-KEM, etc.)
• Machine learning (neural networks)
• Graphics (3D transformations)
• Linear algebra (solving equations)

ML-KEM's Matrix Format

In ML-KEM:

$\mathbf{A} \in R_q^{k \times k}$

Where:

• $k = 3$ for ML-KEM768
• $R_q$ = Polynomial ring (polynomials with coefficients modulo 3329)
• Each entry $A_{ij}$ = A polynomial

So actually: Matrix of polynomials!

$\mathbf{A} = \begin{bmatrix} P_{11} & P_{12} & P_{13} \\ P_{21} & P_{22} & P_{23} \\ P_{31} & P_{32} & P_{33} \end{bmatrix}$

Where each $P_{ij}$ = Polynomial with 256 coefficients!

But we'll learn about polynomial matrices soon. For now, just know:

ML-KEM matrix = 3×3 = 9 polynomials × 256 coefficients = 2304 entries!

---

Quick Check

Can you explain matrices to a 5-year-old?

Try saying this out loud:

"A matrix is like a bingo card - a table where each box has a job. When you give the matrix some numbers, it looks at each row, multiplies the boxes by the numbers, and gives you back answers for each row. It's like doing many different math problems at once!"

Can you multiply a 2×2 matrix by a 2D vector?

Try this examples:

Matrix A = [[2, 1], [0, 3]] Vector v = (4, 2)

Compute A·v:

Output position 0 = 2·4 + 1·2 = 8 + 2 = 10 Output position 1 = 0·4 + 3·2 = 0 + 6 = 6

Result: (10, 6)

---

Key Takeaways

Matrix = Table of instructions (bingo card metaphor) Matrix-vector multiplication = Compute dot products for each row Output size = Number of rows in matrix Compacts many operations = Write one equation instead of many ML-KEM = Uses 3×3 polynomial matrices Polynomial matrices = 9 polynomials × 256 coefficients = 2304 entries

---