Suhendry’s Blog

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₀ and f₁ (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₁ and f₀+f₁ (= f₂). If we multiply C with B, then we will get a matrix D which consist of f₂ and f₁+f₂ (= f₃). 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ⁿ can be computed in O(lg n) and multiplying two matrixes needs O(s³) where s is the size of the matrix, hence the total time complexity would be O(s³ . 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