"Matrix complexity" - is it possible? While browsing old CStheory.se posts, I ran across a fascinating blog post on the matrix mortality problem.  Unless I've misinterpreted the problem, it states that given a finite collection of 3 x 3 matrices with integer entries for each matrix value, one must decide if there exists a finite product of those matrices that equals a matrix comprised of all zeros.

Amazingly, this problem is undecidable, due to a reduction from the Post correspondence problem.  My question is:  Given the undecidability of the problem, and its link to a problem that is linked to Turing machines, can you show that there exists a way to characterize (for example) all r.e. languages, the class P, and the class NP using matrices?

I've done a little work on this myself, but lack the training to be sure if my belief is correct.  This problem would, I think, require a little bit of work on the reader's part to solve.

I don't know how to use LaTeX to write matrices on SE, but here's my first attempt to characterize NP:


  Given a finite set $S$ of 3 x 3 matrices with integer entries and an integer $k$ as an NP "query," let an additional matrix $M$ be taken as a "structure."  The "query" accepts the "structure" if there exists a product of $|M|^k + k$ matrices from $S$ that equals a matrix that consists of only zeros.


This attempt is not complete and does include any proof, as you see, but I wanted to give my first thoughts on the problem to see if a more sophisticated attempt could be made to formalize a notion of matrix complexity.  This is interesting because, like Fagin's characterization of NP using descriptive complexity, it could be used to characterize NP in a machine-independent fashion.
This isn't a characterization of NP: it's just an NP-complete problem (well, I assume it's NP-complete, anyway). OK, if so, you could characterize NP as the class of problems reducible to your matrix problem but how are you going to define reductions? Using reductions from some existing model of computation (e.g., Turing machines) would be self-defeating. What advantages would such a characterization have over, say, considering NP to be the class of problems reducible to, say, independent set?

Also, the "structure" matrix $M$ plays no role in the problem except via its determinant so there's no reason for it to be a matrix, rather than just a natural number.