title: How to reduce the number of matrix multiplications
body: <p>Let <code>A</code> be a given square matrix whose size is <code>nxn</code>. Let <code>A[i]</code> denote the <code>nxn</code> matrix formed by replacing the <code>i</code>-th column of <code>A</code> with the zero column vector.</p>
  
  <p>Now I want to calculate the following <code>(n^4+n^3+n^2)</code> matrix products:</p>
  
  <p><code>{A[x]*A[y]*A[z]*A[w] | for all x=1,...n , y=1,...,n , z=1,...n, and w=1,...,n}</code></p>
  
  <p><code>{A[y]*A[z]*A[w] | for all y=1,...,n , z=1,...n, and w=1,...,n}</code></p>
  
  <p><code>{A[z]*A[w] | for all z=1,...n, and w=1,...,n}</code></p>
  
  <p>If I calculate each product naively, it would take <code>O((n^4+n^3+n^2)*n^3)</code> time complexity (assuming that a matrix multiplication requires <code>O(n^3)</code> time). </p>
  
  <p>However, I noticed that there are many duplicate multiplications that can be memoized. Is there an efficient way (like DP) that can reduce the number of matrix multiplications as fewer as possible ? </p>