-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathmatrix-exponentiation.html
More file actions
137 lines (118 loc) · 37 KB
/
matrix-exponentiation.html
File metadata and controls
137 lines (118 loc) · 37 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - Matrix Exponentiation</title>
<meta name="generator" content="VuePress 1.8.2">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="description" content="Matrix Exponentiation to Solve Example Problems">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - Matrix Exponentiation">
<meta property="og:description" content="Matrix Exponentiation to Solve Example Problems">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/matrix-exponentiation.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - Matrix Exponentiation">
<meta name="twitter:description" content="Matrix Exponentiation to Solve Example Problems">
<meta name="twitter:url" content="/algorithm/matrix-exponentiation.html">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="/logo.png">
<meta name="theme-color" content="#ffffff">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="msapplication-TileImage" content="/mstile-150x150.png">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="google-site-verification" content="76_rKXgwMVIjd-axJC_1zPV9OS4mEjvtgjYOWVkAdnQ">
<link rel="preload" href="/assets/css/0.styles.60619e34.css" as="style"><link rel="preload" href="/assets/js/app.1779e102.js" as="script"><link rel="preload" href="/assets/js/3.2cfa8016.js" as="script"><link rel="preload" href="/assets/js/53.9ebacaa2.js" as="script">
<link rel="stylesheet" href="/assets/css/0.styles.60619e34.css">
</head>
<body>
<div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">DevTut</span></a> <div class="links"><form id="search-form" role="search" class="algolia-search-wrapper search-box"><input id="algolia-search-input" class="search-query"></form> <nav class="nav-links can-hide"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav> <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>Algorithm</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/algorithm/" aria-current="page" class="sidebar-link">Disclaimer</a></li><li><a href="/algorithm/getting-started-with-algorithm.html" class="sidebar-link">Getting started with algorithm</a></li><li><a href="/algorithm/algorithm-complexity.html" class="sidebar-link">Algorithm Complexity</a></li><li><a href="/algorithm/big-o-notation.html" class="sidebar-link">Big-O Notation</a></li><li><a href="/algorithm/trees.html" class="sidebar-link">Trees</a></li><li><a href="/algorithm/binary-search-trees.html" class="sidebar-link">Binary Search Trees</a></li><li><a href="/algorithm/check-if-a-tree-is-bst-or-not.html" class="sidebar-link">Check if a tree is BST or not</a></li><li><a href="/algorithm/binary-tree-traversals.html" class="sidebar-link">Binary Tree traversals</a></li><li><a href="/algorithm/lowest-common-ancestor-of-a-binary-tree.html" class="sidebar-link">Lowest common ancestor of a Binary Tree</a></li><li><a href="/algorithm/graph.html" class="sidebar-link">Graph</a></li><li><a href="/algorithm/graph-traversals.html" class="sidebar-link">Graph Traversals</a></li><li><a href="/algorithm/dijkstras-algorithm.html" class="sidebar-link">Dijkstra’s Algorithm</a></li><li><a href="/algorithm/a-pathfinding.html" class="sidebar-link">A* Pathfinding</a></li><li><a href="/algorithm/a-pathfinding-algorithm.html" class="sidebar-link">A* Pathfinding Algorithm</a></li><li><a href="/algorithm/dynamic-programming.html" class="sidebar-link">Dynamic Programming</a></li><li><a href="/algorithm/applications-of-dynamic-programming.html" class="sidebar-link">Applications of Dynamic Programming</a></li><li><a href="/algorithm/kruskal-s-algorithm.html" class="sidebar-link">Kruskal's Algorithm</a></li><li><a href="/algorithm/greedy-algorithms.html" class="sidebar-link">Greedy Algorithms</a></li><li><a href="/algorithm/applications-of-greedy-technique.html" class="sidebar-link">Applications of Greedy technique</a></li><li><a href="/algorithm/prim-s-algorithm.html" class="sidebar-link">Prim's Algorithm</a></li><li><a href="/algorithm/bellman-ford-algorithm.html" class="sidebar-link">Bellman–Ford Algorithm</a></li><li><a href="/algorithm/line-algorithm.html" class="sidebar-link">Line Algorithm</a></li><li><a href="/algorithm/floyd-warshall-algorithm.html" class="sidebar-link">Floyd-Warshall Algorithm</a></li><li><a href="/algorithm/catalan-number-algorithm.html" class="sidebar-link">Catalan Number Algorithm</a></li><li><a href="/algorithm/multithreaded-algorithms.html" class="sidebar-link">Multithreaded Algorithms</a></li><li><a href="/algorithm/knuth-morris-pratt-kmp-algorithm.html" class="sidebar-link">Knuth Morris Pratt (KMP) Algorithm</a></li><li><a href="/algorithm/edit-distance-dynamic-algorithm.html" class="sidebar-link">Edit Distance Dynamic Algorithm</a></li><li><a href="/algorithm/online-algorithms.html" class="sidebar-link">Online algorithms</a></li><li><a href="/algorithm/integer-partition-algorithm.html" class="sidebar-link">Integer Partition Algorithm</a></li><li><a href="/algorithm/maximum-path-sum-algorithm.html" class="sidebar-link">Maximum Path Sum Algorithm</a></li><li><a href="/algorithm/maximum-subarray-algorithm.html" class="sidebar-link">Maximum Subarray Algorithm</a></li><li><a href="/algorithm/sliding-window-algorithm.html" class="sidebar-link">Sliding Window Algorithm</a></li><li><a href="/algorithm/sorting.html" class="sidebar-link">Sorting</a></li><li><a href="/algorithm/bubble-sort.html" class="sidebar-link">Bubble Sort</a></li><li><a href="/algorithm/merge-sort.html" class="sidebar-link">Merge Sort</a></li><li><a href="/algorithm/insertion-sort.html" class="sidebar-link">Insertion Sort</a></li><li><a href="/algorithm/bucket-sort.html" class="sidebar-link">Bucket Sort</a></li><li><a href="/algorithm/quicksort.html" class="sidebar-link">Quicksort</a></li><li><a href="/algorithm/counting-sort.html" class="sidebar-link">Counting Sort</a></li><li><a href="/algorithm/heap-sort.html" class="sidebar-link">Heap Sort</a></li><li><a href="/algorithm/cycle-sort.html" class="sidebar-link">Cycle Sort</a></li><li><a href="/algorithm/odd-even-sort.html" class="sidebar-link">Odd-Even Sort</a></li><li><a href="/algorithm/selection-sort.html" class="sidebar-link">Selection Sort</a></li><li><a href="/algorithm/pigeonhole-sort.html" class="sidebar-link">Pigeonhole Sort</a></li><li><a href="/algorithm/radix-sort.html" class="sidebar-link">Radix Sort</a></li><li><a href="/algorithm/shell-sort.html" class="sidebar-link">Shell Sort</a></li><li><a href="/algorithm/pancake-sort.html" class="sidebar-link">Pancake Sort</a></li><li><a href="/algorithm/searching.html" class="sidebar-link">Searching</a></li><li><a href="/algorithm/substring-search.html" class="sidebar-link">Substring Search</a></li><li><a href="/algorithm/breadth-first-search.html" class="sidebar-link">Breadth-First Search</a></li><li><a href="/algorithm/depth-first-search.html" class="sidebar-link">Depth First Search</a></li><li><a href="/algorithm/hash-functions.html" class="sidebar-link">Hash Functions</a></li><li><a href="/algorithm/travelling-salesman.html" class="sidebar-link">Travelling Salesman</a></li><li><a href="/algorithm/shortest-common-supersequence-problem.html" class="sidebar-link">Shortest Common Supersequence Problem</a></li><li><a href="/algorithm/knapsack-problem.html" class="sidebar-link">Knapsack Problem</a></li><li><a href="/algorithm/equation-solving.html" class="sidebar-link">Equation Solving</a></li><li><a href="/algorithm/longest-common-subsequence.html" class="sidebar-link">Longest Common Subsequence</a></li><li><a href="/algorithm/longest-increasing-subsequence.html" class="sidebar-link">Longest Increasing Subsequence</a></li><li><a href="/algorithm/check-two-strings-are-anagrams.html" class="sidebar-link">Check two strings are anagrams</a></li><li><a href="/algorithm/pascal-s-triangle.html" class="sidebar-link">Pascal's Triangle</a></li><li><a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="sidebar-link">Algo:- Print a m*n matrix in square wise</a></li><li><a href="/algorithm/matrix-exponentiation.html" aria-current="page" class="active sidebar-link">Matrix Exponentiation</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/matrix-exponentiation.html#matrix-exponentiation-to-solve-example-problems" class="sidebar-link">Matrix Exponentiation to Solve Example Problems</a></li></ul></li><li><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html" class="sidebar-link">polynomial-time bounded algorithm for Minimum Vertex Cover</a></li><li><a href="/algorithm/dynamic-time-warping.html" class="sidebar-link">Dynamic Time Warping</a></li><li><a href="/algorithm/fast-fourier-transform.html" class="sidebar-link">Fast Fourier Transform</a></li><li><a href="/algorithm/pseudocode.html" class="sidebar-link">Pseudocode</a></li><li><a href="/algorithm/contributors.html" class="sidebar-link">The Contributors</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="matrix-exponentiation"><a href="#matrix-exponentiation" class="header-anchor">#</a> Matrix Exponentiation</h1> <h2 id="matrix-exponentiation-to-solve-example-problems"><a href="#matrix-exponentiation-to-solve-example-problems" class="header-anchor">#</a> Matrix Exponentiation to Solve Example Problems</h2> <p><strong>Find f(n): n<sup>th</sup> Fibonacci number.</strong> The problem is quite easy when <strong>n</strong> is relatively small. We can use simple recursion, <code>f(n) = f(n-1) + f(n-2)</code>, or we can use dynamic programming approach to avoid the calculation of same function over and over again. But what will you do if the problem says, <strong>Given 0 < n < 10⁹, find f(n) mod 999983?</strong> Dynamic programming will fail, so how do we tackle this problem?</p> <p>First let's see how matrix exponentiation can help to represent recursive relation.</p> <p><strong>Prerequisites:</strong></p> <ul><li>Given two matrices, know how to find their product. Further, given the product matrix of two matrices, and one of them, know how to find the other matrix.</li> <li>Given a matrix of size <strong>d X d</strong>, know how to find its n<sup>th</sup> power in <strong>O(d<sup>3</sup>log(n))</strong>.</li></ul> <p><strong>Patterns:</strong></p> <p>At first we need a recursive relation and we want to find a matrix <strong>M</strong> which can lead us to the desired state from a set of already known states. Let's assume that, we know the <strong>k</strong> states of a given recurrence relation and we want to find the <strong>(k+1)<sup>th</sup></strong> state. Let <strong>M</strong> be a <strong>k X k</strong> matrix, and we build a matrix <strong>A:[k X 1]</strong> from the known states of the recurrence relation, now we want to get a matrix <strong>B:[k X 1]</strong> which will represent the set of next states, i. e. <strong>M X A = B</strong> as shown below:</p> <div class="language- extra-class"><pre class="language-text"><code>
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
M X | f(n-2) | = | f(n-1) |
| ...... | | ...... |
| f(n-k) | |f(n-k+1)|
</code></pre></div><p>So, if we can design <strong>M</strong> accordingly, our job will be done! The matrix will then be used to represent the recurrence relation.</p> <p><strong>Type 1:</strong> <br>
Let's start with the simplest one, <code>f(n) = f(n-1) + f(n-2)</code> <br>
We get, <code>f(n+1) = f(n) + f(n-1)</code>. <br>
Let's assume, we know <code>f(n)</code> and <code>f(n-1)</code>; We want to find out <code>f(n+1)</code>. <br>
From the situation stated above, matrix <strong>A</strong> and matrix <strong>B</strong> can be formed as shown below:</p> <div class="language- extra-class"><pre class="language-text"><code>
Matrix A Matrix B
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
</code></pre></div><p>[Note: Matrix <strong>A</strong> will be always designed in such a way that, every state on which <code>f(n+1)</code> depends, will be present] <br>
Now, we need to design a <strong>2X2</strong> matrix <strong>M</strong> such that, it satisfies <strong>M X A = B</strong> as stated above. <br>
The first element of <strong>B</strong> is <code>f(n+1)</code> which is actually <code>f(n) + f(n-1)</code>. To get this, from matrix <strong>A</strong>, we need, <strong>1 X f(n)</strong> and <strong>1 X f(n-1)</strong>. So the first row of <strong>M</strong> will be <strong>[1 1]</strong>.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token operator">|</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token operator">|</span> X <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">=</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span> <span class="token operator">|</span>
</code></pre></div><p>[Note: ----- means we are not concerned about this value.] <br>
Similarly, 2nd item of <strong>B</strong> is <code>f(n)</code> which can be got by simply taking <strong>1 X f(n)</strong> from <strong>A</strong>, so the 2nd row of <strong>M</strong> is [1 0].</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token operator">|</span> <span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span> <span class="token operator">|</span> X <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">=</span> <span class="token operator">|</span> <span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token number">1</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">|</span>
</code></pre></div><p>Then we get our desired <strong>2 X 2</strong> matrix <strong>M</strong>.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token operator">|</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token operator">|</span> X <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">=</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token number">1</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">|</span>
</code></pre></div><p>These matrices are simply derived using matrix multiplication.</p> <p><strong>Type 2:</strong></p> <p>Let's make it a little complex: find <code>f(n) = a X f(n-1) + b X f(n-2)</code>, where <strong>a</strong> and <strong>b</strong> are constants.<br>
This tells us, <code>f(n+1) = a X f(n) + b X f(n-1)</code>. <br>
By this far, this should be clear that the dimension of the matrices will be equal to the number of dependencies, i.e. in this particular example, again 2. So for <strong>A</strong> and <strong>B</strong>, we can build two matrices of size <strong>2 X 1</strong>:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>Matrix A Matrix B
<span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">|</span>
</code></pre></div><p>Now for <code>f(n+1) = a X f(n) + b X f(n-1)</code>, we need [a, b] in the first row of objective matrix <strong>M</strong>. And for the 2nd item in <strong>B</strong>, i.e. <code>f(n)</code> we already have that in matrix <strong>A</strong>, so we just take that, which leads, the 2nd row of the matrix M to [1 0]. This time we get:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token operator">|</span> a b <span class="token operator">|</span> X <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">=</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token number">1</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">|</span>
</code></pre></div><p>Pretty simple, eh?</p> <p><strong>Type 3:</strong></p> <p>If you've survived through to this stage, you've grown much older, now let's face a bit complex relation: find <code>f(n) = a X f(n-1) + c X f(n-3)</code>?<br>
Ooops! A few minutes ago, all we saw were contiguous states, but here, the state <strong>f(n-2)</strong> is missing. Now?</p> <p>Actually this is not a problem anymore, we can convert the relation as follows: <code>f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3)</code>, deducing <code>f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2)</code>. Now, we see that, this is actually a form described in Type 2. So here the objective matrix <strong>M</strong> will be <strong>3 X 3</strong>, and the elements are:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token operator">|</span> a <span class="token number">0</span> c <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token number">1</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token operator">|</span> X <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">=</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token number">0</span> <span class="token number">1</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">|</span>
</code></pre></div><p>These are calculated in the same way as type 2, if you find it difficult, try it on pen and paper.</p> <p><strong>Type 4:</strong></p> <p>Life is getting complex as hell, and Mr, Problem now asks you to find <code>f(n) = f(n-1) + f(n-2) + c</code> where <strong>c</strong> is any constant. <br>
Now this is a new one and all we have seen in past, after the multiplication, each state in <strong>A</strong> transforms to its next state in <strong>B</strong>.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span> <span class="token operator">+</span> c
<span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> c
<span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">+</span><span class="token number">2</span><span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">+</span> c
<span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span> so on
</code></pre></div><p>So , normally we can't get it through previous fashion, but how about we add <strong>c</strong> as a state:</p> <div class="language- extra-class"><pre class="language-text"><code>
| f(n) | | f(n+1) |
M X | f(n-1) | = | f(n) |
| c | | c |
</code></pre></div><p>Now, its not much hard to design <strong>M</strong>. Here's how its done, but don't forget to verify:</p> <div class="language- extra-class"><pre class="language-text"><code>
| 1 1 1 | | f(n) | | f(n+1) |
| 1 0 0 | X | f(n-1) | = | f(n) |
| 0 0 1 | | c | | c |
</code></pre></div><p><strong>Type 5:</strong></p> <p>Let's put it altogether: find <code>f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e</code>.
Let's leave it as an exercise for you. First try to find out the states and matrix <strong>M</strong>. And check if it matches with your solution. Also find matrix <strong>A</strong> and <strong>B</strong>.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token operator">|</span> a <span class="token number">0</span> c d <span class="token number">1</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token number">1</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token number">0</span> <span class="token number">1</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">1</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">1</span> <span class="token operator">|</span>
</code></pre></div><p><strong>Type 6:</strong></p> <p>Sometimes the recurrence is given like this:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">-></span> <span class="token keyword">if</span> n is odd
<span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span> <span class="token operator">-></span> <span class="token keyword">if</span> n is even
</code></pre></div><p>In short:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token punctuation">(</span>n<span class="token operator">&</span><span class="token number">1</span><span class="token punctuation">)</span> X <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token punctuation">(</span><span class="token operator">!</span><span class="token punctuation">(</span>n<span class="token operator">&</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span> X <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span>
</code></pre></div><p>Here, we can split the functions in the basis of odd even and keep 2 different matrix for both of them and calculate them separately.</p> <p><strong>Type 7:</strong></p> <p>Feeling little too confident? Good for you. Sometimes we may need to maintain more than one recurrence, where they are interested. For example, let a recurrence re;atopm be:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">g</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token number">2</span>g<span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token number">2</span>g<span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span>
</code></pre></div><p>Here, recurrence <strong>g(n)</strong> is dependent upon <code>f(n)</code> and this can be calculated in the same matrix but of increased dimensions. From these let's at first design the matrices <strong>A</strong> and <strong>B</strong>.</p> <div class="language- extra-class"><pre class="language-text"><code>
Matrix A Matrix B
| g(n) | | g(n+1) |
| g(n-1) | | g(n) |
| f(n+1) | | f(n+2) |
| f(n) | | f(n+1) |
</code></pre></div><p>Here, <code>g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n)</code>.
Now, using the processes stated above, we can find the objective matrix <strong>M</strong> to be:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token operator">|</span> <span class="token number">2</span> <span class="token number">2</span> <span class="token number">1</span> <span class="token number">0</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token number">1</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">2</span> <span class="token number">2</span> <span class="token operator">|</span>
<span class="token operator">|</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">1</span> <span class="token number">0</span> <span class="token operator">|</span>
</code></pre></div><p>So, these are the basic categories of recurrence relations which are used to solveby this simple technique.</p></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/matrix-exponentiation.md" target="_blank" rel="noopener noreferrer">Edit this page on GitHub</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
←
<a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="prev">
Algo:- Print a m*n matrix in square wise
</a></span> <span class="next"><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html">
polynomial-time bounded algorithm for Minimum Vertex Cover
</a>
→
</span></p></div> </main></div><div class="global-ui"><!----></div></div>
<script src="/assets/js/app.1779e102.js" defer></script><script src="/assets/js/3.2cfa8016.js" defer></script><script src="/assets/js/53.9ebacaa2.js" defer></script>
</body>
</html>