The trace invariant and matrix inversion

AbstractLet 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−1) 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−1), A−1 and matrix multiplication all have complexities of the same order. It is also shown that the complexity of computing tr(A−1) is a nondecreasing function of the size of A.Parallel computations are also considered and for these it is shown that tr(A−1) and A−1 are of the same order of difficulty for all ground fields (this holds even if the number of processors is polynomially bounded)