Matrix multiplication could be useful to solve some problems. For example, what is the last digit of 1,000,000,000^{th} fibonacci? Calculating fibonacci number using dynamic programming will need O(n) time complexity, we need a faster one to solve this problem.

Let A be a 1 x 2 matrix which consist of f_{0} and f_{1} (ie. 0 and 1) and B be a 2 x 2 matrix which consist of {(0,1),(1,1)}. If we multiply A and B, we will get a 1 x 2 matrix C which consist of f_{1} and f_{0}+f_{1} (= f_{2}). If we multiply C with B, then we will get a matrix D which consist of f_{2} and f_{1}+f_{2} (= f_{3}). By doing this, we can obtain f_{n} by multiplying A with B for n-1 times.

Matrix multiplication is associative, so we can compute f_{n} by multiplying A with B to the power of n-1. We know that a^{n} can be computed in O(lg n) and multiplying two matrixes needs O(s^{3}) where s is the size of the matrix, hence the total time complexity would be O(s^{3} . lg n).

Here is an example code of computing the last digit of n^{th} fibonacci number.

typedef vector<vector<int> > vvi; const int mod = 10; vvi mul(const vvi &a, const vvi &b) { vvi ret(a.size(),b[0].size()); REP(i,a.size()) REP(j,b[i].size()) REP(k,a[i].size()) ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % mod; return ret; } vvi power(const vvi &a, int p) { if ( p == 1 ) return a; vvi x = power(a,p/2); if ( p % 2 == 1 ) return mul(a,mul(x,x)); return mul(x,x); } int main() { vvi a(1,2), b(2,2); a[0][1] = 0, a[0][1] = 1; b[0][0] = 0, b[0][1] = b[1][0] = b[1][1] = 1; int n; scanf( "%d", &n ); printf( "%d\n", n == 0 ? 0 : mul(a,power(b,n))[0][0] ); return 0; } |

Now let’s consider another problem. Given a graph G of k node, how many distinct path of length n are there that starts from node 1? This problem could also be solved by matrix multiplication.

Let A be a 1 x k matrix which consist of the number of path that end in each node, for the initial case of course it will be (1, 0, …, 0). Let B the adjacency matrix of graph G. If we multiply A with B, we will get a matrix C which consist of the number of path of length-1 that end in each node. If we multiply C with B again, we will get a matrix D which consist of the number of path of length-2 that end in each node, and so on.

There are 3 + 1 + 1 + 2 = 7 paths of length 2 in the graph above:

A – B – A

A – C – A

A – D – A

A – D – B

A – D – C

A – B – D

A – C – D

Exercises:

TJU 2169 – Number Sequence

TJU 2871 – Magic Bean

UVA 11149 – The Power of Matrix

SPOJ SEQ – Recursive Sequence

Live Archieve 4332 – Blocks for kids

For exercise:

let’s define F(i) = F(i-1) + F(i-2) + X where X is a constant.

Use the matrix way to calculate the last digit of F(1,000,000,000)

😉

-Kurniady

problem H?

nice tutorial, btw.

Have you tried Project Euler 237, … this is also another use of some matrix multiplication stuff, but tougher.