Technical Reports

Let $M$ be an $s \times t$ matrix and let $M^{T}$ be the transpose of $M$. Let {\bf x} and {\bf 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}$.}