Matrices whose nullspace is nicely shaped I'm looking for natural conditions on $a_{ij}$ to guarantee that the null space of the $n\times m$ matrix $A=(a_{ij})$ has a nice basis.
The null space of { {1,-2,1,0,0}, {0,1,-2,1,0}, {0,0,1,-2,1} } is the set vectors $\langle x_1,x_2,x_3,x_4,x_5\rangle^T$ with $x_1,\dots,x_5$ in arithmetic progression or constant, i.e., there is a degree zero or one polynomial $p(t)$ with $x_i = p(i)$. The null space of { {3,3,-23,21,-4}, {6,3,-38,36,-7} } consists of points for which there is an at-most-quadratic $p(t)$ with $x_1=p(1),x_2=p(2),x_3=p(3),x_4=p(4),x_5=p(6)$, with that last 6 not being a typo.
In particular, I need a basis for the null space of the form $\{\langle 1,1,\dots,1\rangle^T,\langle x_1,\dots,x_m\rangle^T, \dots, \langle x_1^{m-n-1},\dots,x_m^{m-n-1}\rangle^T\}$, with the $x_i$ distinct (not necessarily integers).
As another specific example, consider the matrix { {3,-3,1,0,-1}, {20,-16,5,-9,0} }. I happen to know that the null space of this matrix has basis $\langle 1,1,1,1,1\rangle^T, \langle 1,4,7,-1,-2 \rangle^T, \langle 1^2,4^2,7^2 ,(-1)^2,(-2)^2\rangle^T$, but only because I made the matrix that way. Even with a specific matrix such as this, I don't know how to compute such a basis, or to guarantee that one exists or doesn't exist.
Here are the obvious necessary conditions: the rows must be independent; each row must add up to 0; no row can have exactly two nonzero components.
As a specific problem (I've no interest in this as a particular problem, mind you, but it may help the discussion) consider the matrix { {35,-3,-42,10,0}, {15,3,-8,0,-10} }. Does it have such a basis?
For background, I'm looking at constructions of sets $X$ of integers that contain no solutions to a system of linear equations. Such a basis as above means that a solution has x_i in the image of a polynomial, and I already know how to construct sets that don't have those (arithmetic progressions are a special case).
 A: After quite a bit of tinkering, I decided that the example and a more fully realized generalization merited separate answers, not least because my initial answer entered community wiki due to the number of edits I made.
Let $N$ be a null space matrix for $A$, i.e., the columns of $N$ are annihilated by $A$. We want vectors $w,w',\dots,w^{(m-n-2)}$ s.t. $(Nw)^{\ell+1} = Nw^{(\ell)}$. Define $z^{(\ell)}$ by $z^{(\ell)}_{i(\alpha)} := w^\alpha$, where $i(\alpha)$ is the grlex index of 
$\alpha \in$ $ X_{m-n,\ell+1} \equiv$ {$\beta \in \mathbb{Z}^{m-n}: \sum_k \beta_k = \ell + 1$}.
Now let $P^{(\ell)}$ be the $m \times |X_{m-n,\ell+1}|$ matrix with entries given by
$P^{(\ell)}_{j,i(\alpha)} :=$ coefficient of $w^\alpha$ in $(\sum_k N_{jk}w_k)^{\ell+1}$. 

To obtain this coefficient explicitly,
  note that 
$(\sum_k N_{jk}w_k)^{\ell+1} =
> \sum_{\alpha \in X}
> \binom{\ell+1}{\alpha}N_{j,\cdot}^\alpha
> w^\alpha$
whence $P^{(\ell)}_{j,i(\alpha)}$
  equals
$\binom{\ell+1}{\alpha}
> N_{j,\cdot}^\alpha$.
For example, with $N_{j,\cdot} =
> (2,3,5,7)$, $\ell = 2$, and $\alpha =
> (0,1,1,1)$, so that $i(\alpha) = 6$,
  we have that $P^{(\ell)}_{j,i(\alpha)}
> =$
$\binom{3}{1,1,1}
> N_{j,\cdot}^{(0,1,1,1)} = 3! \cdot 3
> \cdot 5 \cdot 7 = 630$. 
Extending this example, 
$P^{(2)}_{j,\cdot} =
> (343,343,735,525,125,441,630,225,189,135,27,294,420,150,252,180,54,84,60,36,8)$.

Then the existence (ignoring distinctness of entries) of $w^{(\ell)}$ s.t. $(Nw)^{\ell+1} = Nw^{(\ell)}$ is equivalent to the existence of a solution to 
$(Nw)^{\ell+1} = P^{(\ell)}z^{(\ell)}$. 
Note that for all $\ell$ this is really an equation in the components of $w$, viz.
$\left(\sum_k N_{jk} w_k \right)^{\ell+1} = \sum_{\alpha \in X} \binom{\ell+1}{\alpha} N_{j,\cdot}^\alpha w^\alpha$
and it should (at least) be amenable to solution in a computer algebra routine.
A: If you invert the Vandermonde matrix you will get vectors which are orthogonal to the vectors in the desired nullspace. You can use these vectors to construct a matrix with the desired nullspace. However I don't think the average matrix will have such a nullspace. You will have m paramters for the $x_i$ and $n$ more for the coordinates of the combinations of these vectors that gives n+m parameters for $mn$ variables. From this disparity in parameters it looks like in most cases there will not be a solution on the other hand the inverse of the Vandermonde is known so it is easy to construct examples of this type.
