The proof theoretic strength of the Steinitz exchange theorem
We show that the logical theory QLA QLA proves the CayleyHamilton theorem from the Steinitz exchange theorem together with a strengthening of the linear independence principle. Since QLA QLA is a fairly weak theory (in the sense that its quantifier-free fragment, LA LA , translates into tautologies with TC0 TC 0 -Frege proofswhen restricted to the field Q Q of the rationals), it follows that the proof complexity of matrix algebra can be distilled to the Steinitz exchange theorem.
proof complexity csanky's algorithm