# Computing relations on the columns of a matrix

Given an $m\times n$ (with $n>m)$ matrix $M$ over a polynomial ring $R=k[x_1,...,x_n]$, suppose that every column of $M$ is an $R$-linear combination of $m$ specified columns. I would like to explicitly find these linear combinations. Are there any programs that would allow me to do this?

Of course, I can do this manually (and I have so far), but I am dealing with matrices with over a 100 polynomials and it's taking up a lot of time.

-
What do you mean by "rank" here? Do you mean the rank over the fraction field of $R$? – Qiaochu Yuan Apr 24 '11 at 17:43
The column space of the matrix is a submodule of $R^m$. Submodules of free modules are free. So the rank of this submodule is well defined, unless I am missing something. – Milo Kunis Apr 24 '11 at 17:54
@Milo: your second statement is false. See mathoverflow.net/questions/16953/… . So what condition do you actually want? That the column space is all of $R^m$? – Qiaochu Yuan Apr 24 '11 at 18:01
@Qiaochu: It states in Hungerford's book that submodules of free modules are free. I don't have it handy, but I will check what assumptions on the ring he makes. books.google.com/… – Milo Kunis Apr 24 '11 at 18:08
In any case, without worrying about the definition of the rank, I know every column is an $R$-linear combination of $m$ specified columns. I would like to find the coefficients that govern these linear combinations hopefully using some software. – Milo Kunis Apr 24 '11 at 18:10