Matrix Exponentiation

Introduction:

The concept of matrix exponentiation in its most general form is very useful in solving questions that involve calculating the $$$n^{th}$$$ term of a linear recurrence relation in time of the order of log(n).

First of all we should know what a linear recurrence relation is like:

$$$f_n = \sum_{i=1}^{k} c_{i} * f_{n-i}$$$ and some other terms(I will talk about them later)

Here each $$$c_i$$$ can be zero also, which simply means that $$$f_n$$$ doesn't simply depend on $$$f_{n - i}$$$.

So, as the name suggests we will be making use of matrices to compute the $$$n^{th}$$$ term for us.

First, consider the simple case: $$$f_n = \sum_{n=1}^{k} c_{k} * f_{n-k}$$$

Consider the following $$${k*k}$$$ matrix T: \begin{pmatrix} 0 & 1 & 0 & 0 & . & . \\ 0 & 0 & 1 & 0 & . & . \\ 0 & 0 & 0 & 1 & . & . \\ . & . & . & . & . & . \\ c_k & c_{k-1} & c_{k — 2} & . & . & c_1 \end{pmatrix} And the $$${k*1}$$$ column vector F: \begin{pmatrix} f_0 \\ f_1 \\ f_2 \\ . \\ . \\ . \\ f_{k — 1} \end{pmatrix} Why does the F vector have a dimension of $$$k*1$$$? Simple, because a recurrence relation is complete only with the first $$$k$$$ values(just like the base cases in recursion) given together with the general equation of the same degree.

The matrix $$$T*F$$$ = \begin{pmatrix} f_1 \\ f_2 \\ f_3 \\ . \\ . \\ . \\ f_{k} \end{pmatrix} It is easy to see for the first $$$k - 1$$$ entries of vector $$$C = T*F$$$. The $$$k^{th}$$$ entry is just the calculation of recurrence relation using the past $$$k$$$ values of the sequence. Throughout our discussion so far it has been assumed that the $$$n^{th}$$$ term depends on the previous $$$k$$$ terms where $$$n \ge k$$$(zero based indexing assumed). So, when we obtain $$$C = T * F$$$, the first entry gives $$$f_1$$$. It is easy to see that $$$f_n$$$ is the first entry of the vector: $$$C_n = T^n * F$$$(Here $$$T^n$$$ is the matrix multiplication of T with itself $$$n$$$ times).

Let's construct the same $$$T$$$ matrix for our favourite fibonacci sequence. Turns out it is equal to \begin{pmatrix} 0&1 \\ 1&1 \\ \end{pmatrix}

So we see it all boils down to getting the T matrix right.

A practice problem: Calculate the T matrix for this recurrence: $$$f_n = 2 * f_{i - 1} + 3 * f_{i - 2} + 4 * f_{i - 3}$$$.

This much concept will help you solve this problem: https://www.spoj.com/problems/SEQ/

Little Variations:

Let's talk about the "some other terms" thing I mentioned. Consider the recurrence: $$$f_n = 2 * f_{i - 1} + 3 * f_{i - 2} + 5$$$. The T matrix for the recurrence will be \begin{pmatrix} 0&1&0 \\ 3&2&5 \\ 0&0&1 \\ \end{pmatrix} But there will be a slight variation to the F matrix also. It will now be \begin{pmatrix} f_0 \\ f_1 \\ 1 \\ \end{pmatrix} And the $$$n^{th}$$$ term will still be the first entry of the vector $$$C = T^n*F$$$. One last variation that I want to discuss is in this recurrence: $$$f_i = f_{i - 1} + 2 * i^2 + 5$$$ The T matrix and F vector will be(Try if you want to):

Practice problem: $$$f_i = f_{i - 1} + 2 * i^2 + 3 * i + 5$$$

Complexity Analysis

If you know the concept of binary exponentiation, then you can see that $$$T^n$$$ can be calculated in $$$O(log(n))$$$. But here we are dealing with matrices of the order of $$$k*k$$$. So, in the squaring step, we are multiplying the $$$k*k$$$ T matrix with itself. The matrix multiplication algorithm will have a complexity of $$$O(k^3)$$$. Hence, the overall complexity turns out be $$$O(k^3 * log(n))$$$.

Conclusion

Finally, I would like you to try this problem: https://codeforces.com/contest/1182/problem/E. This concept coupled with knowledge of Fermat's theorem and logarithms will make this problem super easy in terms of idea and doable in terms of implementation. I hope, I was clear enough while expressing myself and you gained something new from this tutorial. I hope to come up with useful ideas to help the community. Constructive suggestions are welcome.

I would like to explain the concept of derangement of a permutation.

Definition: Derangement of a permutation is another ordering where each and every element of the permutation is not in its original position.

Examples: A derangement of 1 2 3 can be 3 1 2, but 3 2 1 is not a derangement of 1 2 3 because 2 is still in its correct position.

Sometimes for an array, a derangement is not possible. Let us take an example.

Consider the array of numbers 1 2 1. Try writing the remaining permutations of this array, at least 1 element will retain its position.

Statement: If an element occurs more than 'half the size' number of times in an array then the derangement of that array is not possible.

Proof: Consider, an array of n elements. If there exists an element with a frequency that is greater than n / 2(take it as real division). Then the given array cannot be deranged because if we pick that particular element and try filling the remaining numbers into its original position, we will run out of numbers. For example, in the case of 1, 2, 2, 2, 3 In order for 2 to not be in its original set of positions, we need 1 and 3, which are the remaining distinct elements in the array, to fill in for 2. But there are 3 positions and only 2 numbers to occupy, hence every position will not be occupied, hence no derangement is possible. That concludes our proof.

When a derangement is possible, how do we construct it? Consider the case when elements are sorted. If we calculate the maximum frequency that a number has in an array, we can rotate the array by that amount and get the derangement of the given sorted array.

How is that possible?

Consider the n elements of a sorted array, a1, a2, ....., an. If we rotate the array by the maximum frequency, we are sure that the elements with the maximum frequency are not going to retain their original position as the series of similar numbers will be shifted ahead. For example, if we have, 1, 1, 2, 2, maximum frequency here is 2 and rotating by 2 yields 2, 2, 1, 1. In the forward direction, the ones are all ahead of the last one in the original permutation. So, in the forward direction, the array has kind of shifted right. No element will retain its position. You can try rotating 1, 1, 2, 2, 2, 3 by 3 to get a better feel or try out as many examples you want. As long as derangement is possible, and you rotate the array by maximum frequency, the new permutation of that sorted array is deranged.

Now how does this help in deranging an unsorted array? Simple, when you sort the array, keep the positions of each occurrence of the number with it. For example, for the array 1, 1, 6, 7, 8, 9, 1, 2, 2 the sorting would be (1, 1), (1, 2), (1, 7), (2, 8), (2, 9), (6, 3), (7, 4), (8, 5), (9, 6). Now when you rotate the sorted array by the maximum frequency, you will get the derangement of the sorted array, not of the actual one. So, keep an auxiliary array of the same size and go through the sorted array that stored the indices, sequentially from beginning and fill that index of the auxiliary array with the value of the rotated array that is equal to that retained index alongside the value(in the sorted array that is not rotated, look at the example). In a way, you are using the derangement of the sorted array to fill in the position of the numbers in the unsorted array. Let us consider an example. The array is 2, 1, 1, 2, 1, 3, 4, 5. If we sort the array and retain the indices, we have (1, 2), (1, 3), (1, 5), (2, 1), (2, 4), (3, 6), (4, 7), (5, 8). Now since the maximum frequency is 3(1 occurs thrice), we rotate this sorted array by 3, based on the first element. We now get, 3, 4, 5, 1, 1, 1, 2, 2.

3 goes to position 2 as in the corresponding array, the element is (1, 2)

4 goes to position 3 as in the corresponding array, the element is (1, 3)

5 goes to position 5 as in the corresponding array, the element is (1, 5)

1 goes to position 1 as in the corresponding array, the element is (2, 1) and, so on.

We get the following output, 1, 3, 4, 1, 5, 1, 2, 2 which is a derangement. If you observe carefully, the sorted version is just being modified, if a number x comes in position of y in case of sorted array, it just replaces y in its position in case of an unsorted array.

I would like to acknowledge this problem https://www.codechef.com/problems/MARCAPS for motivating me to write a blog on the topic. Hope the idea was clear enough and please point out errors, I will be happy to correct them. This is my first educational blog and I would like to contribute more if I find cool concepts like this in future.

I was stuck in a question from https://icpc.baylor.edu/regionals/finder/mid-central-usa-2018. The problem gives you 4 values a, b, c and d where a <= b and c <= d and b, d <= 10^7. We are supposed to find all ordered pairs (x, y) where a <= x <= b and c <= y <= d. I cannot understand how inclusion-exclusion principle / any other combinatorics can be efficiently used here.

int knapsack(int* weights, int* values, int n, int maxWeight){ int i, j;

int dp[maxWeight + 1];

memset(dp, 0, sizeof dp);

int flag = 1;

for(i = 1; i <= n; i++) {

for(j = maxWeight; j >= weights[i - 1]; j--)

    dp[j] = max(dp[j], values[i - 1] + dp[j] + weights[i - 1]]);

}

int ans = dp[maxWeight];

return ans; }