Paper: The Proof Complexity of Linear Algebra (at LICS 2002)

Authors: Michael Soltys Stephen A. Cook

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.

BibTeX

  @InProceedings{SoltysCook-TheProofComplexityo,
    author = 	 {Michael Soltys and Stephen A. Cook},
    title = 	 {The Proof Complexity of Linear Algebra},
    booktitle =  {Proceedings of the Seventeenth Annual IEEE Symposium on Logic in Computer Science (LICS 2002)},
    year =	 {2002},
    month =	 {July}, 
    pages =      {335--344},
    location =   {Copenhagen, Denmark}, 
    publisher =	 {IEEE Computer Society Press}
  }