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).



Matrices whose nullspace is nicely shaped
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.


