A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications

A noncommutative algorithm, as opposed to a commutative algorithm, performs matrix multiplication without requiring the matrix elements to be commutative under the operation of multiplication.Such an algorithm is most desirable since it can be employed to multiply two matrices whose elements are themselves matrices.The standard definition for the multiplication of two n x n matrices yields a noncommutative algorithm using n 3 multiplications.Strassen [7] produced a noncommutative algorithm which multiplies two 2x2 matrices using seven multiplications.In that paper Strassen proved that two n x n matrices could be multiplied asymptotically in 0(n 0%2 ) ~ 0(n 2S1 ) multiplications and likewise 0(n ° 82 ) total arithmetic operations.He accomplished this by embedding n x n matrices into larger matrices (m2 k x m2 k ) and then employing recursively his 2x2 algorithm.In that procedure the noncommutativity of the algorithm was essential.Since 0(n 2 ) arithmetic operations is the best asymptotic lower bound for multiplying two n x n matrices and many problems are related to matrix multiplication (see Strassen [7] and Munro [6] ) much interest has developed in finding better algorithms.Winograd [9] proved that seven multiplications are required by any algorithm for the product of two 2x2 matrices.In multiplying 3x3 matrices, since log 2 7 ~ log 3 21.8, a noncommutative algorithm requiring 21 or fewer multiplications is needed to improve on Strassen's asymptotic result.In [3] Gastinel produced a noncommutative algorithm using 25 multiplications.Hopcroft and Kerr [4] described the construction of a noncommutative algorithm with 24 multiplications and Hopcroft and Musinski [5] explicitly state several such algorithms.Following is a noncommutative algorithm using 23 multiplications for obtaining C = AB where A and B are 3 x 3 matrices.Obviously the number of additions in this algorithm could be greatly reduced, but it is being given in its more basic form.Let