Finding the "Q-span" of vectors in Q(q) Apologies if this question is quite basic.
Consider the $\mathbb{Q}(q)$-vector space $V = \mathbb{Q}(q)^n$ with standard ordered basis $\{e_1,\ldots,e_n\}$.
Suppose someone hands you some vectors $v_1,\ldots,v_k \in V$ in the form of an $n \times k$ matrix $M$ whose columns are the coefficients of $v_i$ in the $e_i$ basis.
Question: Is there an algorithmic way to find a basis the $\mathbb{Q}$-vector space $\mathrm{Span}_{\mathbb{Q}(q)}(\{v_1,\ldots,v_k\}) \cap \mathrm{Span}_{\mathbb{Q}}(\{e_1,\ldots,e_n\})$? Is this implemented in some common math software, such as Sage?

Example: Suppose $M$ is the matrix
$$ M= \begin{pmatrix} 1 & 0 & 0 & 0 & 1 \\ -q & 1 & 1 & 0 & 1 \\ 0 & 1 & -q & 0 & 1 \\ 0 & -q & 1 & 0 & 1 \\ 0 & -q & -q & 1 & 1 \\ 0 & 0 & 0 & -q & 1 \end{pmatrix}$$
Then I believe the vector space I am interested in is the $\mathbb{Q}$-span of the columns of
$$ N=\begin{pmatrix} 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}$$
For example, the first column of $N$ can be expressed as $M \cdot v$ where $v =( \frac{-q(q+1)}{q^3+q^2+q+1}, \frac{1}{q^3+q^2+q+1}, \frac{-q^2}{q^3+q^2+q+1}, \frac{q+1}{q^3+q^2+q+1}, \frac{q(q+1)}{q^3+q^2+q+1})^T$.

I have not been able to find a way to systematically do this on a computer, but there is a hack I've been using: namely, choose a couple random values $q_1,q_2,\ldots,q_m \in \mathbb{Q}$ for $q$, and the take the intersection of $\mathrm{Span}_{\mathbb{Q}(q)}(\{v_1,\ldots,v_k\})$ when we specialize $q$ to these different values. In practice this works okay; still, I would like to know if there's a smarter way to go about it.
 A: As I pointed out in the comments, what you ask is a particular case of more general algorithms concerning Gröbner bases of submodules of free modules over polynomial rings.  But let me address the particular case you asked about.  We can divide the question you ask into two problems (where $k$ is a field and $q$ an indeterminate), which are then solved separately:

*

*Given elements in $k(q)^n$ generating a $k(q)$-vector subspace $M \subseteq k(q)^n$, find generators of the $k[q]$-submodule $N := M \cap k[q]^n$ of $k[q]^n$.


*Given elements in $k[q]^n$ generating a $k[q]$-submodule $N \subseteq k[q]^n$, find generators of the $k$-vector subspace $N \cap k^n$ of $k^n$.
Concerning problem 1.  By multiplying by a common denominator, we can assume that the given generators of $M$ are in $k[q]^n$.  See their matrix as a $k[q]$-linear map $T\colon k[q]^m \to k[q]^n$ (with $m$ being the number of generators given, the generators being $T(e_1),\ldots,T(e_m)$; and we have $M = \operatorname{im}(T\otimes_{k[q]} k(q))$).  Now using the Smith normal form algorithm, we can algorithmically find $U\colon k[q]^m \to k[q]^m$ and $U'\colon k[q]^n \to k[q]^n$ invertible such that $T = U'DU$ with $D\colon k[q]^m \to k[q]^n$ being diagonal: here, $U$ is just a change of generators (having no effect on $M$), and $U'$ is a change of coordinates that preserves $k[q]^n$, so we are reduced to the case where the given matrix $T$ of generators is diagonal, say $T(e_i) = d_i e_i$ with $d_i \neq 0$ in $k[q]$ for $1\leq i\leq r$ and $T(e_i) = 0$ for $i>r$.  But in this case the $k(q)$-vector subspace $M$ is simply spanned by the $e_i$ for $1\leq i\leq r$, and $M\cap k[q]^n$ is too.
‣ To summarize, to solve problem 1, write down your generator matrix, multiply by a common denominator to get its coefficients in $k[q]$, apply the Smith normal form algorithm over $k[q]$ and just replace nonzero coefficients in the diagonal matrix by $1$'s.
Concerning problem 2.  See the given generators of $N$ as a $k[q]$-linear map $T\colon k[q]^m \to k[q]^n$ (with $m$ being the number of generators given; and we have $N = \operatorname{im}(T)$).  This time using Hermite normal form, we can find $U\colon k[q]^m \to k[q]^m$ invertible such that $T = HU$ with $H\colon k[q]^m \to k[q]^n$ being in Hermite normal form (see below), so again we are reduced to the case where the given matrix $T$ of generators is in Hermite normal form.  What this means precisely is that these generators $T(e_i)$ satisfy:

*

*$T(e_i)$ is nonzero for $1\leq i\leq r$ and zero for $i>r$,


*for $i\leq r$, we have $T(e_i) = \sum_{j=n_i}^n a_{i,j} e_j$ where $1\leq n_1 < \cdots < n_r \leq n$ is an increasing sequence, the lead coefficient $a_{i,n_i}$ is unitary, and $\deg(a_{j,n_i}) < \deg(a_{i,n_i})$ (†) when $1\leq j<i$.
But if a combination $z = \sum_{i=1}^m T(c_i e_i) = \sum_{i=1}^m c_i\, T(e_i)$, with $c_i \in k[q]$, of such vectors, belongs to $k^n$, then necessarily all $c_i$ belong to $k$: indeed, otherwise, if $s$ is the smallest $i$ such that $\deg(c_i)>0$, then coordinate $n_s$ of $z$ is $\sum_{i=1}^s c_i a_{i,n_s} = \big(\sum_{i=1}^{s-1} c_i a_{i,n_s}\big) + c_s a_{i,n_s}$, the term $\sum_{i=1}^{s-1} c_i a_{i,n_s}$ has degree $<\deg(a_{s,n_s})$ by (†) and because all $c_i$ have degree $0$ here, and the last term $c_s a_{i,n_s}$ has degree $\deg(c_s) + \deg(a_{s,n_s}) > 0$, a contradiction.  Now once $c_i$ all belong to $k$, it is clear that $\sum_{i=1}^m c_i\, T(e_i)$ belongs to $k^n$ exactly when the $T(e_i)$ with $c_i\neq 0$ themselves belong to $k^n$.
‣ To summarize, to solve problem 2, write down your generator matrix, apply the Hermite normal form algorithm, and only keep generators which are in $k^n$.
(A reference for the Hermite and Smith normal form used here is: Adkins & Weintraub, Algebra: An Approach via Module Theory (1992, Springer GTM 136), §5.2–5.3.  Note that there is a typo in definition 2.8, their $n_r\leq m$ should be $n_r\leq n$.  I wrote things using linear maps in order to avoid confusion between rows and columns of a matrix, but here we want column echelon form, so take the transpose of their table 2.1.)
Maybe we can avoid subdividing the problem in 1 and 2 as I did, or at least avoid doing a Smith normal form and then a Hermite normal form (there's probably a lot of redundancy involved here), I didn't think about this.  Also, I'm pretty sure all of this is already implemented in Sage, though it might be a not completely trivial problem to bring the various bits together.
A: Too long for a comment. How about something like this? It's probably quite inefficient, but maybe it's a start.
First assume that the columns are linearly independent over $\mathbb{Q}(q)$, you can always throw out some extra vectors.
Next, add an extra dummy column $x =(x_1,...,x_n)^T$ to $M$ to get $(M|x)$.
Now take all the $n+1 \times d$ minors and set the determinants equal to zero. This gives a big homogeneous system of linear equations in the $x_i$'s with
coefficients in $\mathbb{Q}(q)$.
Now turn this into a (even larger) rational system of equations in the $x_i$'s by thinking in $\mathbb{Q}((q)) \supset \mathbb{Q}(q)$ taking each power of $q$ separately.
Edit: Actually $\mathbb{Q}((q))$ is overkill, you can just clear denominators and work in $\mathbb{Q}[q]$.
