Scholarly Works

The Proof Complexity of Linear Algebra

The Proof Complexity of Linear Algebra

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.

Authors

Soltys M; Cook S

Pagination

pp. 335-344

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Publication Date

January 1, 2002

DOI

10.1109/lics.2002.1029841

Name of conference

Proceedings 17th Annual IEEE Symposium on Logic in Computer Science

Associated Experts

Michael Soltys

Adjunct Professor, Faculty of Engineering

Labels

Fields of Research (FoR)

5003 Philosophy 4904 Pure Mathematics 49 Mathematical Sciences 50 Philosophy and Religious Studies

View published work (Non-McMaster Users)

Contact the Experts team

Get technical help

or

Provide website feedback