This is the post I needed to refine (or perhaps exacerbate) some cloudy layman thinking, thank you (or perhaps apologies in advance). > Matrices are problemati

This is the post I needed to refine (or perhaps exacerbate) some cloudy layman thinking, thank you (or perhaps apologies in advance). > Matrices are problematic for some reasons. Primarily, by treating a graph as a matrix, we impose an ordering over all vertices which is often arbitrary. This jumped out, as well as a question about whether the terseness people value in notations is a feature of anything else we study at all, and whether terseness creates its own artifacts and blind spots. This idea of graphs and matrices being dynamical systems and state machines appears to be what you get when you remove time/ordinality from them, where they become things with a field of states. It implies there are cases where this ordinality artifact in adjacency matrices provides information, and cases where the ordinality of a matrix representation is noise or a constraint. Intuitively, since the dimension of the adjacency matrix that expresses a graph must be equal or greater than the highest degree node in the graph. (via the pigeon hole principle I recently learned from another HN comment) it seems like for a given graph, you cannot determine the dimensions of the adjacency matrix that expresses the graph without evaluating all graph nodes for their maximum degree. Which frames this conclusion from the post: > First is theoretical: we must show that binary matrix mutiplication is Turing-equivalent. Second, we must show a proof-of-concept via binary recompilation. Third, we must develop a robust toolchain for compiling and introspecting a wide variety of graph programs. Does this imply that determining the Turing-equivalency between graphs and matrices is NP-complete or -hard?