How is the knot equivalence problem represented?
By this I mean I am looking for an analogy that compares with graph equivalence. For graph equivalence, we have two graphs $G_1$ and $G_2$ with adjacency matrices $A$ and $B$ respectively and we seek if there is a permutation matrix $P$ with transpose $P'$ such that $A=PBP'$.
Is there an analogous matrix theoretic framework for knot equivalence? For any decision problem input have to be polynomially sized.
By knot, I assume you mean a knot in $S^3$. Typically a knot is encoded as a diagram, which you might think of as a tetravalent planar graph, with some kind of description of undercrossings and overcrossings, say by some kind of labelling of the half edges incident to every vertex. Abstractly, the notion of equivalence is ambient isotopy; combinatorially, in terms of the diagram, there are the three types of Reidemeister moves.
There are other data types used (like self-avoiding cycles in the integer lattice, or triangulations of $S^3$ together with a cycle in its 1-skeleton), but they will all differ essentially from (finite) graphs in the following way: for any given knot type, there will be infinitely many descriptions of it in that data type. So equivalence will not be as "simple" as conjugation by a permutation matrix. Instead, a priori, one must search through an infinite collection of descriptions related by local moves. Improving on this, Lackenby has shown a polynomial bound on the number of Reidemeister moves to recognize an unknot. More generally, given the current state of things, it's entirely possible knot equivalence is in $\mathsf{P}$.
Not sure if this what you wanted but there is one purely combinatorial way (among thousands of others) to encode (tame) knots and define their equivalence:
This is actually equivalent to how the problem of equivalence for knots was formulated in one of the earliest surveys of the subject of topology: Max Dehn and Poul Heegaard. "Analysis situs". Springer, 1910. The modern language of topological spaces didn't exist back then so they just formulated an equivalent combinatorial problem for lattice knots.
Let $\mathbb F^3$ be the free group on three generators $(x,y,z)$, we will see a knot as an element of its commutator subgroup, such that no proper subword is in the commutator. In other words, if we draw a lattice path prescribed by the reduced word (that is, go up one step if the current letter is $z$, go down if it's $z^{-1}$ etc.) then the first condition amounts to the closedness of the path and the second to the absence of self-intersections.
Now define an operation: pick a letter, say $x$ in the word representing a knot and rewrite it with $zxz^{-1}$ or $z^{-1}xz$ or $y^{-1}yz$ or $yxy^{-1}$ and reduce, if necessary. If this operation does not develop self intersection, let's call it elementary switch.
Two knots are isotopic in the topological sence if and only if there is a sequence of elementary switches which connect them.
It is easy to see that one can double any knot by elementary switches, and then one can apply a theorem of Hinojosa-Verjosvky-Verjovsky-Marcotte (which also seems to be a rather folklore result) which says that doubling + elementary switches is equivalent to isotopy.
Also a picture of a lattice knot from a paper of Alan Turing, where he defines equivalence in the same way:
