Matrix multiplication could be useful to solve some problems. For example, what is the last digit of 1,000,000,000th 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 f0 and f1 (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 f1 and f0+f1 (= f2). If we multiply C with B, then we will get a matrix D which consist of f2 and f1+f2 (= f3). By doing this, we can obtain fn by multiplying A with B for n-1 times.

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

Here is an example code of computing the last digit of nth 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

### 3 Responses to “Matrix Multiplication”

1. 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)

😉