Unit 16: Grids of Numbers

Row times column, added up

Entry (i, j) of the answer is row i of the first grid paired off with column j of the second, multiplied and summed.

Three nested loops, and the middle one is the shared side. It only works when the first grid is as wide as the second is tall.

Python

def multiply(a, b):
    n = len(a)
    result = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                result[i][j] += a[i][k] * b[k][j]
    return result

a = [[1, 2], [3, 4]]
b = [[5, 6], [7, 8]]
for row in multiply(a, b):
    print(row)

It prints

[19, 22]
[43, 50]

Order matters

Swap the two grids and the answer changes — matrix multiplication is not like multiplying numbers.

It is associative, though: (a * b) * c equals a * (b * c). That single fact is what makes the next lesson possible.

Python

def multiply(a, b):
    n = len(a)
    result = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                result[i][j] += a[i][k] * b[k][j]
    return result

a = [[1, 2], [3, 4]]
b = [[5, 6], [7, 8]]
print(multiply(a, b))
print(multiply(b, a))

It prints

[[19, 22], [43, 50]]
[[23, 34], [31, 46]]

The one that changes nothing

Ones down the diagonal, zeroes everywhere else: the identity. Multiplying by it gives back what you started with, exactly as multiplying a number by 1 does.

It is what a power starts from, which is why every fast-power loop begins result = identity.

Python

def identity(n):
    return [[1 if i == j else 0 for j in range(n)] for i in range(n)]

for row in identity(3):
    print(row)

It prints

[1, 0, 0]
[0, 1, 0]
[0, 0, 1]

The pair of numbers, as a grid

Fibonacci says the next pair is (a + b, a). That is a multiplication by the grid [[1, 1], [1, 0]] — and doing it n times is that grid to the power n.

So the whole of Fibonacci is one matrix raised to a power.

Python

def multiply(a, b):
    return [[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
            [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]]

m = [[1, 1], [1, 0]]
power = [[1, 0], [0, 1]]
for step in range(1, 8):
    power = multiply(power, m)
    print(step, power[0][1])

It prints

1 1
2 1
3 2
4 3
5 5
6 8
7 13

And a power is doublings — unit 14 again

Square the matrix, square it again, and pick the squarings the bits of n ask for. Exactly the same loop as power(base, exponent, mod), with numbers replaced by grids.

Thirty squarings reach n = 1000000000. The one-at-a-time version would still be adding.

Python

MOD = 1000000007

def multiply(a, b):
    return [[(a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD, (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD],
            [(a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD, (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD]]

def fib(n):
    result = [[1, 0], [0, 1]]
    base = [[1, 1], [1, 0]]
    while n > 0:
        if n & 1:
            result = multiply(result, base)
        base = multiply(base, base)
        n >>= 1
    return result[0][1]

print(fib(10))
print(fib(90))
print(fib(1000000000000000000))

It prints

55
210345902
209783453

Checking the middle one by hand

The ninetieth Fibonacci number is 2880067194370816120. Its remainder after dividing by 1000000007 is 210345902 — which is what the matrix printed.

Always check a fast method against a slow one somewhere you can see both answers. The last line is not checkable by eye, and that is exactly why the first two matter.

Any recurrence with a fixed rule works

If the next term is a fixed combination of the last few — f(n) = 2f(n-1) + 3f(n-3), say — build a k by k grid whose top row is those multipliers and whose rest just shuffles the old terms down.

The cost is k * k * k * log n, which is nothing for the small k a problem will give you.

A graph as a grid of ones and zeroes

Put 1 where there is an arrow and 0 where there is not — the adjacency matrix from unit 8, which was too big for a real contest graph but is fine for a small one.

Square it, and entry (i, j) counts the routes from i to j of exactly two steps.

Python

a = [
    [0, 1, 1, 0],
    [0, 0, 1, 1],
    [0, 0, 0, 1],
    [0, 0, 0, 0],
]

def multiply(x, y):
    n = len(x)
    result = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                result[i][j] += x[i][k] * y[k][j]
    return result

square = multiply(a, a)
cube = multiply(square, a)
print(square[0])
print(cube[0])

It prints

[0, 0, 1, 2]
[0, 0, 0, 1]

Why multiplying counts routes

A two-step route from i to j is a first step to some k and then a step from k to j. The number of them is the sum over k of one times the other — which is exactly the multiplication rule.

So the same three loops that multiply grids also count routes, and the k being summed over is the node in the middle.

Two routes of length two, one of length three

From node 0 to node 3 in two steps: 0 → 1 → 3 and 0 → 2 → 3. The square says 2, and you can count them on the picture.

In three steps there is one: 0 → 1 → 2 → 3. The cube says 1.

Tiling a corridor

A corridor two squares wide and n long, tiled with 2 by 1 slabs. Lay one upright, and n - 1 is left. Lay two flat, and n - 2 is left.

So the count is t(n) = t(n-1) + t(n-2) — Fibonacci wearing a hat. Contests love this: the story is new, the recurrence never is.

Python

t = [0] * 11
t[0] = 1
t[1] = 1
for n in range(2, 11):
    t[n] = t[n - 1] + t[n - 2]

print(t)

It prints

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

A recurrence that is not Fibonacci

Now the slabs are 1, 3 or 4 long in a single-width corridor: t(n) = t(n-1) + t(n-3) + t(n-4).

The grid for it is 4 by 4: the top row holds the multipliers 1, 0, 1, 1, and the three rows below simply shuffle the older terms down one place.

Python

t = [0] * 12
t[0] = 1
for n in range(1, 12):
    total = t[n - 1]
    if n >= 3:
        total += t[n - 3]
    if n >= 4:
        total += t[n - 4]
    t[n] = total

print(t)

It prints

[1, 1, 1, 2, 4, 6, 9, 15, 25, 40, 64, 104]

The shuffling grid, written out

Multiply the column of the last four answers by this grid and you get the column of the next four. Then raise the grid to a power.

The two answers agree at n = 11, which is the check: the loop and the matrix are two different routes to 104.

Python

MOD = 1000000007
size = 4

def multiply(a, b):
    result = [[0] * size for i in range(size)]
    for i in range(size):
        for j in range(size):
            total = 0
            for k in range(size):
                total += a[i][k] * b[k][j]
            result[i][j] = total % MOD
    return result

base = [
    [1, 0, 1, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 1, 0],
]

result = [[1 if i == j else 0 for j in range(size)] for i in range(size)]
n = 11
steps = n - 3
while steps > 0:
    if steps & 1:
        result = multiply(result, base)
    base = multiply(base, base)
    steps >>= 1

start = [2, 1, 1, 1]
answer = 0
for k in range(size):
    answer += result[0][k] * start[k]

print(answer % MOD)

It prints

104

Reading the grid

The top row is the recurrence itself: one lot of the previous answer, none of the one before, one of the one before that, one more.

The rows underneath are all zeroes and a single 1 — they do no arithmetic, they only pass the old answers down so the column stays the last four. Every linear recurrence matrix looks like this.