# How small can we make a modulus and still perform linear algebra on these pairs?

We can work with numbers of the form $(a^n + a^m)$, where $a$, $n$, and $m$ are all naturals, and $-v \le m \le v$ and $-v \le n \le v$. There is one more possibility: $a^n$ could be replaced by $0$, and $a^m$ could be replaced by zero.

Now we can get a Vandermonde-like matrix with these numbers. For example, there could be a problem:

$$\left[ \begin{array}{ccc|c} (2^1 + 2^3) & (2^{-5}+2^7) & (2^2 + 0) & c_1 \\ (3^1 + 3^3) & (3^{-5}+3^7) & (3^2 + 0) & c_2 \\ (4^1 + 4^3) & (4^{-5}+4^7) & (4^2 + 0) & c_3 \\ \end{array} \right]$$

...Here we're trying to find the reduced row echelon form to determine the numbers associated with $c_1$, $c_2$, and $c_3$. In the above example there are $3$ rows. We will assume that we are working with matrices of $r$ rows.

If we want to solve many problems for matrices of $r$ rows by linear algebra mod a prime $p$, how large must $p$ be, in order to get full column rank? Here we are assuming that the entries in the matrix are numbers of the form described at the top of the question. Also, we want to ensure that we have full column rank.

ATTEMPT AT CLARIFICATION

In other words, we have a matrix filled with the numbers in the form at the top of the question. We can assume that the original matrix has full column rank. Now if we start working modulo smaller and smaller $p$, my understanding is that the columns could end up being the same. So how large must we make $p$ in order to guarantee that the matrix still has full column rank?

-
The integers modulo a prime are a field, so most results should carry over with no (or little) change. What exactly are you after? – vonbrand Mar 3 '14 at 11:55
@vonbrand: If the results should carry over with no change (up to equivalence modulo $p$), that's all I want. I'm just looking for a proof that I can do this modulo $p$ for a small $p$. It seems to me now, that $p$ isn't really important, since the results in any field will be equivalent modulo $p$. – Matt Groff Mar 3 '14 at 13:03