國立清華大學 數學系

Abstract: We are interested in the Computational Complexity of multiplication of matrices. For 2x2 size matrix, by definition you do 8 multiplications together with additions of corresponding entry numbers, to accomplish a multiplication of two matrices. In 1969, Srassen found a simple algorithm so that you can always do 7 instead of 8 multiplications. Last 50 years, this leads to active mathematical researches, people want to minimize the number of multiplications needed in multiplying matrices. Tools used starting from Linear Algebra to Elementary Algebraic Geometry, and even more and deeper mathematics. Still today we do not know whether it is possible to find an algorithm doing only 18 multiplications (besides additions and subtractions), for any two given 3x3 matrices to get their product 3x3 matrix.