Addition Requirements for Matrix & Transposed Matrix Products

Let $M$ be an $s \times t$ matrix and let $M^{T}$ be the transpose of $M$. Let x and y be $t$- and $s$-dimensional indeterminate column vectors, respectively. We show that any linear algorithm $A$ that computes $M{\bf x}$ has associated with it a natural dual linear algorithm denoted $A^{T}$ that computes $M^{T}{\bf y}$. Furthermore, if $M$ has no zero rows or columns then the number of additions used by $A^{T}$ exceeds the number of additions used by $A$ by exactly $s-t$. In addition, a strong correspondence is established between linear algorithms that compute the product $M{\bf x}$ and bilinear algorithms that compute the bilinear form ${\bf y}^{T}M{\bf x}$.