Editing Strassen algorithm (section)

=== Rank or bilinear complexity ===
The bilinear complexity or '''rank''' of a [[bilinear map]] is an important concept in the asymptotic complexity of matrix multiplication.  The rank of a bilinear map <math>\phi:\mathbf A \times \mathbf B \rightarrow \mathbf C</math> over a field '''F''' is defined as (somewhat of an [[abuse of notation]])
:<math>R(\phi/\mathbf F) = \min \left\{r\left|\exists f_i\in \mathbf A^*,g_i\in\mathbf B^*,w_i\in\mathbf C , \forall \mathbf a\in\mathbf A, \mathbf b\in\mathbf B, \phi(\mathbf a,\mathbf b) = \sum_{i=1}^r f_i(\mathbf a)g_i(\mathbf b)w_i \right.\right\}</math>
In other words, the rank of a bilinear map is the length of its shortest bilinear computation.<ref>{{cite book |last1=Burgisser |last2=Clausen |last3=Shokrollahi |title=Algebraic Complexity Theory |publisher=Springer-Verlag |year=1997 |isbn=3-540-60582-7 }}</ref>  The existence of Strassen's algorithm shows that the rank of <math>2 \times 2</math> matrix multiplication is no more than seven.  To see this, let us express this algorithm (alongside the standard algorithm) as such a bilinear computation.  In the case of matrices, the [[dual space]]s '''A'''* and '''B'''* consist of maps into the field '''F''' induced by a scalar '''[[Dyadics#Product of dyadic and dyadic|double-dot product]]''', (i.e. in this case the sum of all the entries of a [[Hadamard product (matrices)|Hadamard product]].)
{| class = "wikitable"
| || colspan="3" | Standard algorithm || ||colspan="3" | Strassen algorithm
|-
|| <math>i</math> || <math>f_i (\mathbf{a})</math> || <math>g_i (\mathbf{b})</math> || <math>w_i</math> || || <math>f_i (\mathbf{a})</math> || <math>g_i (\mathbf{b})</math> || <math>w_i</math>
|-
|| 1
||<math>\begin{bmatrix}1&0\\0&0\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}1&0\\0&0\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}1&0\\0&0\end{bmatrix}</math>
||
||<math>\begin{bmatrix}1&0\\0&1\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}1&0\\0&1\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}1&0\\0&1\end{bmatrix}</math>
|-
|| 2
||<math>\begin{bmatrix}0&1\\0&0\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}0&0\\1&0\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}1&0\\0&0\end{bmatrix}</math>
||
||<math>\begin{bmatrix}0&0\\1&1\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}1&0\\0&0\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}0&0\\1&-1\end{bmatrix}</math>
|-
|| 3
||<math>\begin{bmatrix}1&0\\0&0\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}0&1\\0&0\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}0&1\\0&0\end{bmatrix}</math>
||
||<math>\begin{bmatrix}1&0\\0&0\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}0&1\\0&-1\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}0&1\\0&1\end{bmatrix}</math>
|-
|| 4
||<math>\begin{bmatrix}0&1\\0&0\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}0&0\\0&1\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}0&1\\0&0\end{bmatrix}</math>
||
||<math>\begin{bmatrix}0&0\\0&1\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}-1&0\\1&0\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}1&0\\1&0\end{bmatrix}</math>
|-
|| 5
||<math>\begin{bmatrix}0&0\\1&0\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}1&0\\0&0\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}0&0\\1&0\end{bmatrix}</math>
||
||<math>\begin{bmatrix}1&1\\0&0\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}0&0\\0&1\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}-1&1\\0&0\end{bmatrix}</math>
|-
|| 6
||<math>\begin{bmatrix}0&0\\0&1\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}0&0\\1&0\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}0&0\\1&0\end{bmatrix}</math>
||
||<math>\begin{bmatrix}-1&0\\1&0\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}1&1\\0&0\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}0&0\\0&1\end{bmatrix}</math>
|-
|| 7
||<math>\begin{bmatrix}0&0\\1&0\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}0&1\\0&0\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}0&0\\0&1\end{bmatrix}</math>
||
||<math>\begin{bmatrix}0&1\\0&-1\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}0&0\\1&1\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}1&0\\0&0\end{bmatrix}</math>
|-
|| 8
||<math>\begin{bmatrix}0&0\\0&1\end{bmatrix}:\mathbf a</math>
||<math>\begin{bmatrix}0&0\\0&1\end{bmatrix}:\mathbf b</math>
||<math>\begin{bmatrix}0&0\\0&1\end{bmatrix}</math>
||
|colspan="3"|
|-
||
|colspan="3"|<math>\mathbf a\mathbf b = \sum_{i=1}^8 f_i(\mathbf a)g_i(\mathbf b)w_i</math>
||
|colspan="3"|<math>\mathbf a\mathbf b = \sum_{i=1}^7 f_i(\mathbf a)g_i(\mathbf b)w_i</math>
|}
It can be shown that the total number of elementary multiplications <math>L</math> required for matrix multiplication is tightly asymptotically bound to the rank <math>R</math>, i.e. <math>L = \Theta(R)</math>, or more specifically, since the constants are known, <math>R / 2 \le L \le R</math>. One useful property of the rank is that it is submultiplicative for [[tensor product]]s, and this enables one to show that <math>2^n \times 2^n \times 2^n</math> matrix multiplication can be accomplished with no more than <math>7n</math> elementary multiplications for any <math>n</math>.  (This <math>n</math>-fold tensor product of the <math>2 \times 2 \times 2</math> matrix multiplication map with itself &mdash; an <math>n</math>-th tensor power&mdash;is realized by the recursive step in the algorithm shown.)