Feasible Proofs of Matrix Properties with Csanky's Algorithm

Details Feasible Proofs of Matrix Properties with Csanky's Algorithm Feasible Proofs of Matrix Properties with Csanky's Algorithm

2005-05-31

arxiv.org/abs/cs/0505087v1

Computer Science

Logic in Computer Science

Scientific paper

We show that Csanky's fast parallel algorithm for computing the characteristic polynomial of a matrix can be formalized in the logical theory LAP, and can be proved correct in LAP from the principle of linear independence. LAP is a natural theory for reasoning about linear algebra introduced by Cook and Soltys. Further, we show that several principles of matrix algebra, such as linear independence or the Cayley-Hamilton Theorem, can be shown equivalent in the logical theory QLA. Applying the separation between complexity classes AC^0[2] contained in DET(GF(2)), we show that these principles are in fact not provable in QLA. In a nutshell, we show that linear independence is ``all there is'' to elementary linear algebra (from a proof complexity point of view), and furthermore, linear independence cannot be proved trivially (again, from a proof complexity point of view).

Affiliated with

Also associated with

No associations

Rating

Feasible Proofs of Matrix Properties with Csanky's Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Feasible Proofs of Matrix Properties with Csanky's Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Feasible Proofs of Matrix Properties with Csanky's Algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455532