{"id":113908,"date":"2026-06-06T00:03:40","date_gmt":"2026-06-05T18:33:40","guid":{"rendered":"https:\/\/www.guvi.in\/blog\/?p=113908"},"modified":"2026-06-06T00:03:42","modified_gmt":"2026-06-05T18:33:42","slug":"matrix-chain-multiplication-a-complete-guide","status":"publish","type":"post","link":"https:\/\/www.guvi.in\/blog\/matrix-chain-multiplication-a-complete-guide\/","title":{"rendered":"Matrix Chain Multiplication: A Complete Guide"},"content":{"rendered":"\n<p>Matrix multiplication is a fundamental operation in computer science, mathematics, and engineering. It underlies everything from computer graphics and machine learning to scientific simulation and signal processing.<\/p>\n\n\n\n<p>When a single pair of matrices must be multiplied, the computation is straightforward. But when a long chain of matrices must be multiplied together, the order in which the multiplications are performed, determined by how the expression is parenthesised, has a dramatic effect on the total number of arithmetic operations required.<\/p>\n\n\n\n<p>This is the matrix chain multiplication problem: given a sequence of matrices, determine the most efficient order to multiply them so that the total number of scalar multiplications is minimised.<\/p>\n\n\n\n<p>It is a classic problem in dynamic programming, taught in every algorithms course because it illustrates the core ideas of optimal substructure and overlapping subproblems with clarity and elegance. This guide explains the problem from first principles, walks through the dynamic programming solution in full, and covers the practical contexts in which matrix chain optimisation matters.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>TL;DR<\/strong><\/h3>\n\n\n\n<ul>\n<li>Matrix chain multiplication finds the optimal order to multiply a chain of matrices to minimise scalar multiplications.<\/li>\n\n\n\n<li>The result is the same for all parenthesizations (associativity), but the computational cost varies enormously.<\/li>\n\n\n\n<li>Naively trying all parenthesizations is exponential; dynamic programming solves it in O(n\u00b3) time and O(n\u00b2) space.<\/li>\n\n\n\n<li>The DP approach fills a table m[i][j] storing the minimum cost to multiply matrices from index i to j.<\/li>\n\n\n\n<li>A separate table s[i][j] records the optimal split point, enabling reconstruction of the optimal parenthesisation.<\/li>\n<\/ul>\n\n\n\n<div class=\"guvi-answer-card\" style=\"margin: 40px 0;\">\n\n  <div style=\"\n    position: relative;\n    background: linear-gradient(135deg, #f0fff4, #e6f7ee);\n    border: 1px solid #cfeedd;\n    padding: 26px 24px 22px 24px;\n    border-radius: 14px;\n    font-family: Arial, sans-serif;\n    box-shadow: 0 6px 16px rgba(0,0,0,0.05);\n  \">\n\n    <!-- Top accent -->\n    <div style=\"\n      position: absolute;\n      top: 0;\n      left: 0;\n      height: 6px;\n      width: 100%;\n      background: linear-gradient(to right, #099f4e, #6dd5a3);\n      border-radius: 14px 14px 0 0;\n    \"><\/div>\n\n    <!-- Title -->\n    <h3 style=\"\n      margin: 10px 0 12px 0;\n      color: #099f4e;\n      font-size: 20px;\n    \">\n      What Is Matrix Chain Multiplication?\n    <\/h3>\n\n    <!-- Content -->\n    <p style=\"\n      margin: 0;\n      color: #2f4f3f;\n      font-size: 16px;\n      line-height: 1.7;\n    \">\n      Matrix Chain Multiplication is a classic optimization problem in computer science that determines the most efficient order for multiplying a sequence of matrices. Although matrix multiplication is associative, meaning the final result remains the same regardless of how the matrices are grouped, different parenthesizations can require significantly different numbers of scalar multiplications. The objective is to find the multiplication order that minimizes computational cost rather than performing the actual matrix multiplication. This problem is commonly solved using dynamic programming, achieving a time complexity of O(n\u00b3) for a chain of n matrices.\n    <\/p>\n\n  <\/div>\n\n<\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Why Parenthesisation Order Matters<\/strong><\/h2>\n\n\n\n<p>To understand why the problem matters, consider what happens when two matrices are multiplied.<\/p>\n\n\n\n<p>Multiplying an (p x q) matrix by a (q x r) matrix requires exactly p x q x r scalar multiplications and produces a (p x r) result matrix. The dimensions must be compatible: the number of columns in the first matrix must equal the number of rows in the second.<\/p>\n\n\n\n<p>Now consider three matrices:<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; A1 : dimensions 10 x 30<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; A2 : dimensions 30 x 5<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; A3 : dimensions 5 x 60<\/p>\n\n\n\n<p>There are two ways to parenthesise this product: (A1 x A2) x A3&nbsp; or&nbsp; A1 x (A2 x A3).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Option 1: (A1 x A2) x A3<\/strong><\/h3>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; Multiply A1 x A2 : cost = 10 x 30 x 5 = 1,500 scalar multiplications. Result: 10 x 5.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; Multiply (10&#215;5) x A3 : cost = 10 x 5 x 60 = 3,000 scalar multiplications.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; <strong>Total: 4,500 scalar multiplications.<\/strong><\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Option 2: A1 x (A2 x A3)<\/strong><\/h3>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; Multiply A2 x A3 : cost = 30 x 5 x 60 = 9,000 scalar multiplications. Result: 30 x 60.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; Multiply A1 x (30&#215;60) : cost = 10 x 30 x 60 = 18,000 scalar multiplications.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; <strong>Total: 27,000 scalar multiplications.<\/strong><\/p>\n\n\n\n<p>The second parenthesisation requires six times more computation than the first, yet both produce identical results. For longer chains, the difference can be many orders of magnitude. With a chain of just 10 matrices, the number of possible parenthesizations exceeds 4,000. With 15 matrices, it exceeds 2 billion. An exhaustive search is completely impractical.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>The Recursive Structure of the Problem<\/strong><\/h2>\n\n\n\n<p>Before building the dynamic programming solution, it helps to understand the recursive structure of the problem, which reveals both why naive <a href=\"https:\/\/www.guvi.in\/blog\/guide-for-recursion-in-python\/\" target=\"_blank\" rel=\"noreferrer noopener\">recursion<\/a> is expensive and why dynamic programming is effective.<\/p>\n\n\n\n<p>Any parenthesisation of a chain A[i..j] (matrices from index i to j) must have a final multiplication at some split point k, where i &lt;= k &lt; j. The left side A[i..k] and the right side A[k+1..j] are each independently parenthesised optimally.<\/p>\n\n\n\n<p>This gives the recursive formulation:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>m[i][j] = 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if i == jm[i][j] = min over all k from i to j-1 of:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Where p[] is the dimensions array: matrix Ai has dimensions p[i-1] x p[i]. The term p[i-1] * p[k] * p[j] is the cost of the final multiplication that combines the two subchains.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Optimal Substructure<\/strong><\/h3>\n\n\n\n<p>The problem has optimal substructure: an optimal solution to the full problem contains optimal solutions to all its subproblems. If the optimal parenthesisation of A[1..n] splits at position k, then the parenthesisations of A[1..k] and A[k+1..n] within that solution must themselves be optimal. If either subchain were sub-optimally parenthesised, we could improve it and get a better overall solution, a contradiction.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Overlapping Subproblems<\/strong><\/h3>\n\n\n\n<p>The subproblems are not independent. A naive recursive implementation computes the same subproblem, the optimal cost of a given subchain, many times across different branches of the recursion tree. The number of unique subproblems is O(n\u00b2), but the naive recursion solves exponentially many total subproblem instances. Memoisation or bottom-up dynamic programming eliminates this redundancy.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>The Dynamic Programming Solution<\/strong><\/h2>\n\n\n\n<p>The dynamic programming solution builds a table bottom-up, starting with chains of length 1 and progressively solving longer chains using previously computed shorter-chain results.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Notation and Setup<\/strong><\/h3>\n\n\n\n<p>Given n matrices A1 through An, represent their dimensions as an array p[0..n] where matrix Ai has dimensions p[i-1] x p[i].<\/p>\n\n\n\n<p>Define two tables:<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; <strong>m[i][j]: <\/strong>The minimum number of scalar multiplications needed to compute the product of matrices Ai through Aj.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; <strong>s[i][j]: <\/strong>The index k of the optimal split point that achieves m[i][j] used later to reconstruct the optimal parenthesisation.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Algorithm: Bottom-Up DP<\/strong><\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>function MATRIX_CHAIN_ORDER(p[0..n]): n = length(p) &#8211; 1 \/\/ Base case: single matrices cost zero for i = 1 to n:&nbsp;&nbsp;&nbsp;&nbsp; m[i][i] = 0&nbsp; \/\/ Fill by increasing chain length L for L = 2 to n:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; \/\/ L = chain length&nbsp;&nbsp;&nbsp;&nbsp; for i = 1 to n &#8211; L + 1:&nbsp; &nbsp; \/\/ i = chain start&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; j = i + L &#8211; 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; \/\/ j = chain end&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; m[i][j] = INFINITY&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for k = i to j &#8211; 1:&nbsp; &nbsp; \/\/ try every split&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cost = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if cost &lt; m[i][j]:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; m[i][j] = cost&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s[i][j] = k&nbsp; return m, s<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>The final answer, the minimum cost to multiply all n matrices, is stored in m[1][n].<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Step-by-Step Worked Example<\/strong><\/h3>\n\n\n\n<p>Consider four matrices with dimension array p = [10, 30, 5, 60, 8]:<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; A1 : 10 x 30<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; A2 : 30 x 5<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; A3 : 5 x 60<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; A4 : 60 x 8<\/p>\n\n\n\n<p>Step 1 \u2014 Base case (chain length L=1): m[i][i] = 0 for all i.<\/p>\n\n\n\n<p>Step 2 \u2014 Chain length L=2: compute each adjacent pair.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>m[1][2] = p[0]*p[1]*p[2] = 10*30*5&nbsp; = 1500 &nbsp; s[1][2] = 1m[2][3] = p[1]*p[2]*p[3] = 30*5*60&nbsp; = 9000 &nbsp; s[2][3] = 2m[3][4] = p[2]*p[3]*p[4] = 5*60*8 &nbsp; = 2400 &nbsp; s[3][4] = 3<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Step 3 \u2014 Chain length L=3: try all splits for each triple.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>m[1][3]: k=1: m[1][1]+m[2][3]+10*30*60 = 0+9000+18000 = 27000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; k=2: m[1][2]+m[3][3]+10*5*60&nbsp; = 1500+0+3000&nbsp; = 4500&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; min = 4500 &nbsp; s[1][3] = 2&nbsp;m[2][4]: k=2: m[2][2]+m[3][4]+30*5*8&nbsp; = 0+2400+1200&nbsp; = 3600&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; k=3: m[2][3]+m[4][4]+30*60*8&nbsp; = 9000+0+14400 = 23400&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; min = 3600 &nbsp; s[2][4] = 2<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Step 4 \u2014 Chain length L=4: compute m[1][4].<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>m[1][4]: k=1: m[1][1]+m[2][4]+10*30*8&nbsp; = 0+3600+2400&nbsp; = 6000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; k=2: m[1][2]+m[3][4]+10*5*8 &nbsp; = 1500+2400+400 = 4300&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; k=3: m[1][3]+m[4][4]+10*60*8&nbsp; = 4500+0+4800 &nbsp; = 9300&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; min = 4300 &nbsp; s[1][4] = 2<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>The minimum cost to multiply all four matrices is 4,300 scalar multiplications, achieved by splitting at k=2: (A1 x A2) x (A3 x A4).<\/p>\n\n\n\n<div style=\"background-color: #099f4e; border: 3px solid #110053; border-radius: 12px; padding: 18px 22px; color: #FFFFFF; font-family: Montserrat, Helvetica, sans-serif; line-height: 1.6; box-shadow: 0 4px 12px rgba(0, 0, 0, 0.15); max-width: 800px;\">\n  <strong style=\"font-size: 22px; color: #FFFFFF;\">\ud83d\udca1 Did You Know?<\/strong>\n  <p style=\"margin-top: 14px;\">\n    The number of ways to fully parenthesize a chain of <strong>n matrices<\/strong> is given by the <strong>Catalan number<\/strong> C<sub>n-1<\/sub>, one of the most famous sequences in combinatorics. The count grows explosively: 2 matrices have only 1 valid parenthesization, 4 matrices have 5, 10 matrices have 4,862, and 20 matrices have more than <strong>1.7 billion<\/strong> possible parenthesizations. This rapid growth is why the <strong>Matrix Chain Multiplication<\/strong> problem cannot be solved efficiently by brute force. Instead, dynamic programming exploits overlapping subproblems to find the optimal multiplication order in polynomial time, turning a seemingly impossible search problem into a practical algorithm.\n  <\/p>\n<\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Reconstructing the Optimal Parenthesisation<\/strong><\/h2>\n\n\n\n<p>The m table tells us the minimum cost. The s table tells us how to achieve it. Reconstructing the optimal parenthesisation is done by recursively reading the split points stored in s.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>function PRINT_OPTIMAL_PARENS(s, i, j): if i == j:&nbsp;&nbsp;&nbsp;&nbsp; print &#8220;A&#8221; + i else:&nbsp;&nbsp;&nbsp;&nbsp; print &#8220;(&#8221;&nbsp;&nbsp;&nbsp;&nbsp; PRINT_OPTIMAL_PARENS(s, i, s[i][j])&nbsp;&nbsp;&nbsp;&nbsp; PRINT_OPTIMAL_PARENS(s, s[i][j] + 1, j)&nbsp;&nbsp;&nbsp;&nbsp; print &#8220;)&#8221;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>For our four-matrix example, calling PRINT_OPTIMAL_PARENS(s, 1, 4):<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; s[1][4] = 2 \u2192 split into A[1..2] and A[3..4].<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; s[1][2] = 1 \u2192 A[1..1] = A1, A[2..2] = A2. Left subchain: (A1 x A2).<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; s[3][4] = 3 \u2192 A[3..3] = A3, A[4..4] = A4. Right subchain: (A3 x A4).<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; <strong>Result: ((A1 x A2) x (A3 x A4))<\/strong><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Time and Space Complexity<\/strong><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/www.guvi.in\/blog\/complexity-analysis-in-data-structures\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>Time Complexity<\/strong><\/a><strong>: O(n\u00b3)<\/strong><\/h3>\n\n\n\n<p>The bottom-up DP algorithm uses three nested loops:<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; The outer loop iterates over chain lengths L from 2 to n: O(n) iterations.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; The middle loop iterates over start positions i: O(n) iterations.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; The inner loop iterates over split points k: O(n) iterations.<\/p>\n\n\n\n<p>Total: O(n) x O(n) x O(n) = O(n\u00b3). For n = 100 matrices, this is approximately 1,000,000 operations, trivially fast on modern hardware.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Space Complexity: O(n\u00b2)<\/strong><\/h3>\n\n\n\n<p>Both the m and s tables are (n+1) x (n+1) square tables. Each store has at most n\u00b2 values. Total space: O(n\u00b2). For n = 1,000 matrices, the tables require approximately 8 MB for 64-bit integers, well within the memory of any modern system.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Comparison with Naive Approaches<\/strong><\/h3>\n\n\n\n<ul>\n<li><strong>Exhaustive search: <\/strong>O(4^n \/ n^1.5)&nbsp; exponential. Completely impractical beyond ~20 matrices.<\/li>\n\n\n\n<li><strong>Naive recursion (no memoisation): <\/strong>O(2^n) exponential due to recomputation of overlapping subproblems.<\/li>\n\n\n\n<li><strong>Memoised recursion (top-down DP): <\/strong>O(n\u00b3) time, O(n\u00b2) space, equivalent to bottom-up but with function call overhead.<\/li>\n\n\n\n<li>&nbsp;<strong>Bottom-up DP: <\/strong>O(n\u00b3) time, O(n\u00b2) space optimal. No recursion overhead.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Implementation in Python<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>def matrix_chain_order(p): n = len(p) &#8211; 1&nbsp; &nbsp; &nbsp; # number of matrices # m[i][j] = min cost to multiply A[i..j] m = [[0] * (n + 1) for _ in range(n + 1)] # s[i][j] = optimal split point for A[i..j] s = [[0] * (n + 1) for _ in range(n + 1)]&nbsp; # Base case: single matrix, zero cost # (already 0 from initialisation)&nbsp; # Fill by increasing chain length for length in range(2, n + 1):&nbsp; &nbsp; &nbsp; # chain length&nbsp;&nbsp;&nbsp;&nbsp; for i in range(1, n &#8211; length + 2):&nbsp; # start index&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; j = i + length &#8211; 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # end index&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; m[i][j] = float(&#8216;inf&#8217;)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for k in range(i, j): &nbsp; &nbsp; &nbsp; # split point&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cost = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if cost &lt; m[i][j]:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; m[i][j] = cost&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s[i][j] = k return m, s&nbsp;def print_optimal_parens(s, i, j): if i == j:&nbsp;&nbsp;&nbsp;&nbsp; print(f&#8221;A{i}&#8221;, end=&#8221;&#8221;) else:&nbsp;&nbsp;&nbsp;&nbsp; print(&#8220;(&#8220;, end=&#8221;&#8221;)&nbsp;&nbsp;&nbsp;&nbsp; print_optimal_parens(s, i, s[i][j])&nbsp;&nbsp;&nbsp;&nbsp; print_optimal_parens(s, s[i][j] + 1, j)&nbsp;&nbsp;&nbsp;&nbsp; print(&#8220;)&#8221;, end=&#8221;&#8221;)&nbsp;# Example: p = [10, 30, 5, 60, 8]p = [10, 30, 5, 60, 8]m, s = matrix_chain_order(p)print(&#8220;Minimum cost:&#8221;, m[1][len(p)-1])&nbsp; # Output: 4300print(&#8220;Optimal order: &#8220;, end=&#8221;&#8221;)print_optimal_parens(s, 1, len(p)-1) &nbsp; # Output: ((A1A2)(A3A4))<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Applications of Matrix Chain Multiplication<\/strong><\/h2>\n\n\n\n<p>Matrix chain multiplication is not merely a textbook exercise. The problem of finding an optimal order for a sequence of matrix operations appears throughout applied computing.<\/p>\n\n\n\n<ul>\n<li><strong>Computer graphics and 3D rendering: <\/strong>Transformation pipelines apply sequences of matrices (translation, rotation, scaling, projection) to every vertex in a scene. Optimising the multiplication order reduces per-frame computation, directly improving frame rate.<\/li>\n\n\n\n<li><strong>Deep learning and neural networks: <\/strong>Forward and backward passes through <a href=\"https:\/\/www.guvi.in\/blog\/what-are-neural-networks-in-ai\/\">neural networks<\/a> involve multiplying sequences of weight matrices and activation Jacobians. Frameworks like TensorFlow and PyTorch use optimised einsum and contraction ordering to minimise computation.<\/li>\n\n\n\n<li><strong>Database query optimisation: <\/strong>Relational algebra operations, joins, projections, and selections can be modelled as matrix operations. Optimising their execution order is analogous to matrix chain optimisation and is a central task of query planners.<\/li>\n\n\n\n<li><strong>Scientific computing: <\/strong>Physics simulations, finite element analysis, and signal processing pipelines involve long chains of matrix operations. Libraries such as NumPy and MATLAB apply optimised ordering strategies automatically.<\/li>\n\n\n\n<li><strong>Compiler optimisation: <\/strong>Modern compilers optimise sequences of array operations and tensor contractions using techniques directly related to matrix chain ordering, reducing both instruction count and memory bandwidth.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Matrix Chain Multiplication vs. Related Problems<\/strong><\/h2>\n\n\n\n<p>Matrix chain multiplication belongs to a family of interval dynamic programming problems where the state is defined by a contiguous subrange [i, j] of a sequence, and the solution to [i, j] is built from solutions to shorter intervals.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; <strong>Optimal binary search tree: <\/strong>Finds the arrangement of keys in a BST that minimises the expected search cost given key access probabilities. Same O(n\u00b3) interval DP structure as matrix chain multiplication.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; <strong>Burst balloons: <\/strong>A LeetCode problem where coins are collected by bursting balloons in a sequence; the value depends on adjacent elements. Solved with interval DP using the same fill-by-chain-length pattern.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; <strong>Polygon triangulation: <\/strong>Finds the minimum-weight triangulation of a convex polygon by decomposing it into triangles structurally identical to matrix chain multiplication with a different cost function.<\/p>\n\n\n\n<p>Recognising the interval DP pattern, try all split points k in [i, j-1], combine subproblem results, and take the minimum is a transferable skill that applies across all of these problems.<\/p>\n\n\n\n<p>If you want practical experience working with activation functions, neural networks, and deep learning models, <strong>HCL GUVI\u2019s<\/strong> <a href=\"https:\/\/www.guvi.in\/courses\/machine-learning-and-ai\/mastering-ai-and-machine-learning\/?utm_source=blog&amp;utm_medium=hyperlink&amp;utm_campaign=Matrix+Chain+Multiplication%3A+A+Complete+Guide\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>AI and ML programs<\/strong><\/a> can help you understand how concepts like sigmoid, backpropagation, and gradient descent are implemented using frameworks such as TensorFlow and PyTorch through hands-on projects.\u00a0<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>Matrix chain multiplication is one of the most instructive problems in the study of dynamic programming. It demonstrates with exceptional clarity why the order of operations matters, how optimal substructure enables a recursive decomposition of a complex problem, and how memoisation or bottom-up table-filling transforms an exponential search into a polynomial-time algorithm.<\/p>\n\n\n\n<p>The O(n\u00b3) dynamic programming solution filling the m table by chain length and recording split points in the s table is both elegant and practical. It solves problems that would be computationally intractable with brute force, and the same algorithmic pattern reappears across a wide range of interval optimisation problems.<\/p>\n\n\n\n<p>Beyond the classroom, matrix chain optimisation has direct applications in computer graphics, deep learning, scientific computing, and database systems, anywhere that sequences of matrix operations must be performed efficiently at scale.<\/p>\n\n\n\n<p>Mastering matrix chain multiplication means mastering a way of thinking: decompose by interval, identify the optimal split, and build solutions bottom-up. That thinking is the foundation of dynamic programming itself.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>FAQs<\/strong><\/h2>\n\n\n<div id=\"rank-math-faq\" class=\"rank-math-block\">\n<div class=\"rank-math-list \">\n<div id=\"faq-question-1780467802349\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \"><strong>1. What is the matrix chain multiplication problem?<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>Matrix chain multiplication is an optimisation problem that finds the most efficient order to multiply a chain of matrices, minimising the total number of scalar multiplications. The final matrix product is the same regardless of order (associativity), but different parenthesizations have vastly different computational costs.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1780467807778\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \"><strong>2. Why can&#8217;t we just try all parenthesizations?<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>The number of distinct parenthesizations of n matrices is the Catalan number C(n-1), which grows exponentially. For n=15, it exceeds 2 billion. Exhaustive search is impractical beyond small chains, making the O(n\u00b3) dynamic programming solution essential.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1780467833643\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \"><strong>3. What is the time complexity of the DP solution?<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>The bottom-up dynamic programming algorithm runs in O(n\u00b3) time and uses O(n\u00b2) space for the m and s tables. It solves all O(n\u00b2) subproblems, each requiring O(n) work to find the optimal split point among all candidates.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1780467845519\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \"><strong>4. What do the m and s tables store?<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>The m[i][j] table stores the minimum number of scalar multiplications needed to compute the product of matrices Ai through Aj. The s[i][j] table stores the index k of the optimal split point, enabling reconstruction of the full optimal parenthesisation via traceback.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1780467854670\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \"><strong>5. Where is matrix chain multiplication used in practice?<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>It is used in computer graphics (transformation pipelines), deep learning frameworks (tensor contraction ordering), database query optimisers (join order planning), and scientific computing libraries, anywhere a sequence of matrix operations must be performed at minimum computational cost.<\/p>\n\n<\/div>\n<\/div>\n<\/div>\n<\/div>","protected":false},"excerpt":{"rendered":"<p>Matrix multiplication is a fundamental operation in computer science, mathematics, and engineering. It underlies everything from computer graphics and machine learning to scientific simulation and signal processing. When a single pair of matrices must be multiplied, the computation is straightforward. But when a long chain of matrices must be multiplied together, the order in which [&hellip;]<\/p>\n","protected":false},"author":63,"featured_media":114995,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[933],"tags":[],"views":"48","authorinfo":{"name":"Vishalini Devarajan","url":"https:\/\/www.guvi.in\/blog\/author\/vishalini\/"},"thumbnailURL":"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2026\/06\/matrix-chain-multiplication-a-complete-guide-300x150.webp","jetpack_featured_media_url":"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2026\/06\/matrix-chain-multiplication-a-complete-guide.webp","_links":{"self":[{"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/posts\/113908"}],"collection":[{"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/users\/63"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/comments?post=113908"}],"version-history":[{"count":5,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/posts\/113908\/revisions"}],"predecessor-version":[{"id":114996,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/posts\/113908\/revisions\/114996"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/media\/114995"}],"wp:attachment":[{"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/media?parent=113908"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/categories?post=113908"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/tags?post=113908"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}