The trace invariant and matrix inversion

Let A be a matrix whose entries are indeterminates over an infinite field. It is shown that, under the straight-line model with the nonscalar complexity measure, computing tr(A⁻¹) is at least as hard as matrix multiplication (up to a constant factor). Thus, subject to a standard assumption about matrix multiplication, it follows that computing tr(A⁻¹), A⁻¹ and matrix multiplication all have complexities of the same order. It is also shown that the complexity of computing tr(A⁻¹) is a nondecreasing function of the size of A. Parallel computations are also considered and for these it is shown that tr(A⁻¹) and A⁻¹ are of the same order of difficulty for all ground fields (this holds even if the number of processors is polynomially bounded).