Matrices whose nullspace is nicely shaped

Question

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

Answer 1

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.

Answer 2

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?

substantially edited, with changed conclusion after fixing per Kevin's comments

Yes.

Consider the following null space matrix (denote it by $N$):

 1    -1     3
 1     5    35
 1     0     0
 1     5     0
 1     0    15

Write $w = (a,b,c)^T$ and $w' = (a',b',c')^T$. The example question asks if there is a solution to the equations $Nw = x$ and $Nw' = x^2$, where componentwise multiplication is indicated. Pick your favorite ordered tuple for the degree 2 monomials (in general for such a thing I like the grlex order referenced in Uniquely generate all permutations of three digits that sum to a particular value? but): here, I'll use $z=(a^2,b^2,c^2,ab,ac,bc)^T$.

Let $P$ be the matrix

       1           1           9          -2           6          -6
       1          25        1225          10          70         350
       1           0           0           0           0           0
       1          25           0          10           0           0
       1           0         225           0          30           0

Now the example is equivalent to $Pz = (Nw)^2$.

W/l/o/g, let $a = 1$ or $a = 0$.

If $a = 0$, then $a'=0$, $b'=5b^2$, and $c'=15c^2$ (from the bottom three rows of $P$, respectively). Substituting these into the equations corresponding to the top two rows of $P$ lead to the two equations $b^2+9c^2-6bc=-5b^2+45c^2$ and $25b^2+1225c^2+350bc=25b^2+525c^2$, which have the solutions $b, c = 0$ and $-2c = b$.

The first solution is disallowed since the components of $x$ are required to be distinct, but $w = (0,-2,1)^T$ and $w' = (0,20,15)^T$ (or appropriate multiples thereof) work, and MATLAB confirms this.

If $a = 1$, it follows that $a' = 1$, $b' = 2b + 5b^2$, and $c' = 2c + 15c^2$ (from the bottom three rows of $P$, respectively). Substituting these into the equations corresponding to the top two rows of $P$ leads to the two equations are $1-2b-5b^2+6c+45c^2 = 1+b^2+9c^2-2b+6c-6bc$ and $1+10b+25b^2+70c+1125c^2=1+25b^2+1225c^2+10b+70c+350bc$. These simplify to $-6b^2+36c^2+6bc=0$ and $2c+7b=0$. Substituting $c=-7b/2$ into the first of these yields $-6b^2+441b^2-21b^2 = 0$, which fails unless $b, c = 0$, which is again disallowed since the components of $x$ are required to be distinct.

Answer 3

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.