The trace invariant and matrix inversion

K. Kalorkoti

Research output: Contribution to journalArticlepeer-review

Abstract

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−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).
Original languageEnglish
Pages (from-to)277-286
Number of pages10
JournalTheoretical Computer Science
Volume59
Issue number3
DOIs
Publication statusPublished - Aug 1988

Fingerprint

Dive into the research topics of 'The trace invariant and matrix inversion'. Together they form a unique fingerprint.

Cite this