The Proof Complexity of Linear Algebra

Michael Soltys and Stephen Cook

To appear at Symposium on Logic in Computer Science (LICS'2002), Copenhagen, Denmark, July 22nd - 25th, 2002

Abstract

We introduce three formal theories of increasing strength for linear algebra in order to study the complexity of the concepts needed to prove the basic theorems of the subject. We give what is apparently the first feasible proofs of the Cayley-Hamilton theorem and other properties of the determinant, and study the propositional proof complexity of matrix identities.

Server START Conference Manager
Update Time 15 Mar 2002 at 15:30:29
Maintainer lics02@dcs.ed.ac.uk.
Start Conference Manager
Conference Systems