A Note on the Complexity of the Transpose of a Matrix - Matthews, Philip; Sturtivant, Carl (DAIMI Report Series, 1988)
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.