hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Symbolic Computation, cs.SC
Abstract:
Despite its importance, all proofs of the correctness of Strassen's famous
1969 algorithm to multiply two 2x2 matrices with only seven multiplications
involve some more or less tedious calculations such as explicitly multiplying
specific 2x2 matrices, expanding expressions to cancel terms with opposing
signs, or expanding tensors over the standard basis. This is why the proof is
nontrivial to memorize and why many presentations of the proof avoid showing
all the details and leave a significant amount of verifications to the reader.
In this note we give a short, self-contained, easy to memorize, and elegant
proof of the existence of Strassen's algorithm that avoids these types of
calculations. We achieve this by focusing on symmetries and algebraic
properties.
Our proof combines the classical theory of M-pairs, which was initiated by
B\"uchi and Clausen in 1985, with recent work on the geometry of Strassen's
algorithm by Chiantini, Ikenmeyer, Landsberg, and Ottaviani from 2016.