행렬의 곱셈을 생각해보자 행렬의 크기가 m*r인 행렬과 r*n행렬의 곱은 총 몇번 연산할까? 간단한 예로 1*3행렬인A=(1,2,3)을 생각해보자 이 행렬의 전치행렬과의 곱은 다음과 같이 된다 1*3과 3*1 이므로 결과는 1*1 행렬이 나온다. 1*1+2*2+3*3 여기서 사칙연산이 몇번 수행 되었는지 보면 5번 수행되었다. 이것을 일반화 해보자 m*r인 행렬과 r*n인 행렬 곱의 총 연산횟수는 일단 m*r과 r*n 행렬의 곱의 크기는 m*n이다. 즉 m*n개의 성분이 생기므로 기본적으로 각 성분이 몇번 연산되는지만 알아내어 m*n을 곱하면 두 행렬의 곱을 하기 위해서 총 몇번 연산해야하는지 횟수가 나오는 것이다. 여기서 m*r행렬에서 곱셈을 할때 1행에서의 성분의 갯수는 r개이다. 똑같이 r*n행렬에서는 1열이 선택이 되므로 1열의 성분의 갯수는 r개이다. 그렇다면 r개의 성분이 몇번 연산되는지만 알아내면 되는 것이다. 기본적으로 r개의 성분이 각각 곱해지므로 r번 곱셈 연산이 일어나고 r-1번 덧셈이 일어나므로 최종적으로는 2r-1번 연산이 일어나는 것이다. 따라서 m*r 행렬과 r*n 행렬의 곱은 연산을 (m*n)*(2r-1)번 연산을 해야하는 것이다. 그런데 이 행렬의 곱셈이 여러개일 때 그 행렬들의 곱셈에 대한 결합법칙에 의하여 먼저 연산하는 행렬이 달라도 그 연산 횟수는 똑같을까?

위의 정답은 딱 잘라 말하자면 No이다. 예를 들어보자 다음과 같은 4개의 행렬을 생각해보자 각 행렬의 크기는 다음과 같다. A=10*1 B=1*10 C=10*50 D=50*20이다. 여기서 ABCD 행렬을 구한다고 할때 

1.((AB)C)D

2.(AB)(CD) 

이 두 계산의 연산 횟수를 비교해보자

1.은 위의 (m*n)*(2r-1)에 따라서 100*1+500*19+200*49가 나와 총 19400번 연산을 해야한다.

2.는 AB=100*1 크기는 10*10행렬 CD=200*49 크기는 10*20행렬 마지막으로 두 행렬의 곱은 200*19 따라서 총합은 13700번으로 2.번이 훨씬 더 적게 연산을 하고도 같은 결과를 낸다. 그렇다면 어떻게 편하게 각 다른 곱셈에 따른 결합법칙 행렬의 연산횟수를 비교할 수 있을까?
이 문제에서는 두가지가 증명이 필요하다. 첫번째는 곱셈할려는 행렬의 갯수가 x개라고 할 때 곱셈에 따른 결합법칙으로 나타날 수 있는 모든 경우의 수는 몇개인가? 두번째는 그에 따른 연산 횟수를 어떻게 쉽게 비교할 수 있는가이다.

3. 구현