Using an inductive argument, and splitting (2n) × (2n) matrices into four n × n matrices,...

Using an inductive argument, and splitting (2n) × (2n) matrices into four n × n matrices, use Exercise to show that it is possible to multiply two 2k × 2k matrices using only 7k multiplications, and less than 7k + 1 additions.

Exercise

Show that it is possible to multiply two 2 × 2 matrices using only seven multiplications of integers, by using the identity

where x = a11b11 − (a11 − a21 −a22)(b11 − b12 + b22).