A Note on the Complexity of the Transpose of a Matrix

Abstract

Let x be a column vector of indeterminates. We show that the complexity of computing the linear forms Ax for a fixed matrix A is essentially the same as that of computing the linear forms A'x where the prime denotes transpose. Our result also holds for non-square matrices, under a simple restriction.