Following Multiple Paths

How Vectors Add Together

---

The Simple Story

Imagine you're walking through town to get to school.

Your mom gives you directions:

1. Start at home
2. Walk 3 blocks east
3. Walk 1 block north
4. Walk 2 blocks east

Question: Where do you end up?

Trick: What if you just walked 5 blocks east and 1 block north and got to the same place?

That's vector addition - adding multiple arrows into one!

---

Mental Model

Think of it like this:

Following multiple arrows:

Home →→→→ |↑  →→ School
         |↑

Becomes one straight arrow:

Home →→→→→→ School
         |↑

Visual:

  School
     ↑
     │ 1 block
     │ (result)
     ├────────── 5 blocks (result)
     │
     │ 2 blocks
     ├────────── (part 2)
     │
     │ 1 block
     ├────────── (part 1)
     │
  Home

Same result, just combined!

---

See It Happen

Let's add vectors step by step:

---

Try It Yourself

Question 1: You start at home. Follow these vectors:

• Vector A: "4 steps East"
• Vector B: "2 steps North"
• Vector C: "3 steps West"

Where do you end up?

Show Answer

Write each vector:

• A = (4, 0)
• B = (0, 2)
• C = (-3, 0)

Add them together:

A + B + C = (4 + 0 + (-3), 0 + 2 + 0)
           = (1, 2)

Final position: 1 block East, 2 blocks North from home!

---

Question 2: You're at position (5, 3). You walk 2 steps South and 1 step West. Where are you now?

Show Answer

Starting position: (5, 3)

Vector you follow: "1 West, 2 South" = (-1, -2)

Add the vector to your position:

(5, 3) + (-1, -2) = (5 + (-1), 3 + (-2))
                     = (4, 1)

Final position: 4 blocks East, 1 block North from origin.

---

Question 3: You walk "3 East" then "2 North" then "5 East" then "1 South." What's the result?

Show Answer

Write all vectors:

• Step 1: (3, 0)
• Step 2: (0, 2)
• Step 3: (5, 0)
• Step 4: (0, -1)

Add them:

Sum = (3 + 0 + 5 + 0, 0 + 2 + 0 + (-1))
     = (8, 1)

Result: 8 blocks East, 1 block North

Think of it this way: 3 + 5 = 8 (all the east steps), 2 - 1 = 1 (all the north/south steps)

---

The Math

Vector Addition

Mathematicians write vector addition like this:

$\mathbf{v} + \mathbf{w} = (v_x + w_x, v_y + w_y)$

Example: $\mathbf{v} = (3, 4)$
$\mathbf{w} = (1, 2)$ $\mathbf{v} + \mathbf{w} = (3 + 1, 4 + 2) = (4, 6)$

Adding multiple vectors: $\mathbf{v}_1 + \mathbf{v}_2 + \mathbf{v}_3 = (v_{1x} + v_{2x} + v_{3x}, v_{1y} + v_{2y} + v_{3y})$

Properties That Always Work

Order doesn't matter: $\mathbf{v} + \mathbf{w} = \mathbf{w} + \mathbf{v}$

Grouping doesn't matter: $(\mathbf{v} + \mathbf{w}) + \mathbf{u} = \mathbf{v} + (\mathbf{w} + \mathbf{u})$

Zero vector does nothing: $\mathbf{v} + \mathbf{0} = \mathbf{v}$

These properties also work in 256 dimensions!

---

Why We Care

Problem: ML-KEM Uses Lots of Vectors

During key generation and encapsulation, ML-KEM does:

Result = Vector_1 + Vector_2 + Vector_3 + ... + Vector_k

Without vector addition, you'd have to write everything individually!

Solution: Add them all at once:

Start with nothing (zero vector)
Add first vector → current position
Add second vector → new position
Keep going...

Simplified as:
Total = sum(all vectors)

Example: ML-KEM Key Generation

When ML-KEM generates a key, it computes:

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

Where:

• $\mathbf{A}\mathbf{s}$ = multiplying matrix by vector (we'll learn this!)
• $\mathbf{e}$ = small error vector

Multiplying a matrix by a vector = adding MANY vectors together!

$\mathbf{A}\mathbf{s} = \mathbf{A}_1 s_1 + \mathbf{A}_2 s_2 + \mathbf{A}_3 s_3 + \dots + \mathbf{A}_{k} s_{k}$

Vector addition is how we combine all these parts into one result!

Without vector addition, you'd write 256 separate equations. With it, you write: $\mathbf{A}\mathbf{s}$ (one line!)

---

Quick Check

Can you explain vector addition to a 5-year-old?

Try saying this out loud:

"When you have multiple treasure map arrows, you can combine them all into one bigger arrow. You just add up all the 'left-right' steps together, and all the 'up-down' steps together. It's like measuring how far you went east-west and north-south in total!"

Can you work out an example?

Compute this:

Add these vectors: (2, 1) + (3, -2) + (0, 4)

First numbers: 2 + 3 + 0 = 5
Second numbers: 1 + (-2) + 4 = 3

Result: (5, 3) = "5 steps East, 3 steps North"

---

Key Takeaways

Vector addition = Combine multiple arrows into one Formula = (x₁+x₂+..., y₁+y₂+...) - add each coordinate separately Order doesn't matter = Can add in any order, same result Works in 256D = Same rules for ML-KEM's big vectors ML-KEM uses this = Combines 256 vectors into one result

---