Let $R=\mathbb Z[t^{\pm}]$ and $M$ a finitely generated $R$-module. With $A$ a presentation matrix, i.e we have the following exact sequence (usually I'm working with the case where $A$ is an square matrix with $\text{det} A\not=0$): $$ 0\rightarrow R^m\overset{A}{\rightarrow} R^n\rightarrow M\rightarrow 0 $$ Is known that two presentation matrices $A$ and $B$ of $M$ differ by a sequence of matrix moves of the following forms and their inverses [Theorem 6.1 An Introduction to Knot Theory]:

$1)$ Permutation of rows or colums.

$2)$ Replecing $A$ for $\left[\begin{array}{l}A&0\\0&u\end{array}\right]$ with $u\in R^\star=\{\pm1,\pm t,\pm t^2,...\}$.

$3)$ Addition of extra column of zeros to the matrix A.

$4)$ Addition of scalar multiple of a row (or column) to another row (or column).

My objective is to find an algorithm that given a square presentation matrix, gives another square presentation matrix with dimension as low "as possible". Since $R$ isn't PID ( In the case that R was PID this could be solved finding the smith form of the matrix A) probably there isn't an algorithm that give the square presentation matrix with lowest dimension but I'm wondering if there is an algorithm that gives you a resonably good matrix in this sense i.e. the output of the algorithm is a square matrix with reasonbly low dimension.

In the cases I'm working this matrices are of the form $A=V-tV^t$, where $V$ is the seifert matrix of a knot and the good thing is that usually have a lot of $1$ so the first steps are easy. But I have no clue what to do next.

I'm also wondering which algebra computational system would be better to implement this algorithm, right now I'm trying to do it with sage but I'm stucked.

Thank you very much in advance!

  • $\begingroup$ When you write `is known that ...', you are really using the fact that projective modules over $R$ are free. So, I would suspect that any algorithm would be as hard as proving the freeness of projective modules algorithmically. $\endgroup$ – Mohan Jul 1 '19 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.