Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A fact about complexity of algorithms for computing the product of matrices was brought up to me that was very interesting I was not aware of. I still am not sure what the optimal bound is on the minimum number of scalar multiplications to compute a product of $n \times n$ matrices (maybe it is a simple result in the $2 \times 2$ case?) but I was told there is at least a basic proof for the following case. After playing around for a while I was not sure what the best route to take was so I thought I would just ask what is the easiest way to show the following result:

How do you prove that if $A,B$ are two $2 \times 2$ matrices then the product $AB$ can be computed using only 7 scalar multiplications?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

This is the Strassen algorithm. You only use 7 scalar multiplications, and use 18 scalar additions (the standard method uses 8 scalar multiplications and 4 scalar additions).

Since addition is $O(n)$ (where $n$ is the number of bits of the two numbers) and multiplication is $O(n^2)$ (in the naive way; but there are better methods that are $O(n\log n 2^{\log_*n})$), for large enough numbers it is more efficient.

You can also iterate Strassen's algorithm to compue products of matrices by using the same formulas but with blocks instead of entries.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.