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

-
I think the first row of your matrix is $\langle -3,3,-1,0,1\rangle$ . When I tried this approach, I unfortunately could not get any new Behrend-type constructions. The sparser constructions are harder to compare to known results, as there are no good known general constructions. Maybe you will succeed. – Boris Bukh Nov 27 '09 at 16:28

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.

-
It looks like the key equation is a tautology. I'll work on clarifying this. – Steve Huntsman Jan 14 '10 at 6:39

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.

-
"equivalent to $Pz = (Nx)^2$" should be "equivalent to $Pz= Nw'$". It isn't WLOG that $a=1$ (perhaps $a=0$). Working from $a=1$, I get the same $a',b',c'$ that you do, but when I substitute into the first two equations, I get a different second equation: $25 b^2+10 b+525 c^2+70 c+1 = 25 b^2+350 b c+10 b+1225 c^2+70 c+1$, whence $b=-2c$ or $c=0$. If $c=0$ then the first equ gives $b=0$, but with $b=-2c$, it works. So $Nw$ with $w=(1,b,-2b)$ works, and we just need to choose b so that the components of $Nw$ are distinct. – Kevin O'Bryant Jan 12 '10 at 9:35
Setting $a'=1,b'=2b+5b^2,c'=2c+15c^2$, we get $(Nw)^2=Nw'=(-5 b^2-2 b+45 c^2+6 c+1,25 b^2+10 b+525 c^2+70 c+1,1,25 b^2+10b+1,225 c^2+30 c+1)^T.$ With $a=1$, we get $Pz=P(1,b^2,c^2,b,c,bc)^T=(b^2-6 b c-2 b+9 c^2+6 c+1,25 b^2+350 b c+10 b+1225 c^2+70 c+1,1,25b^2+10 b+1,225 c^2+30 c+1)^T.$ The last 3 equations are tautologies, and the first two reduce to $-6 b^2+6 b c+36 c^2=0, 350 b c + 700 c^2=0.$ These have a trivial solution $b=c=0$, which doesn't allow us to satisfy the remaining condition, that the components of $x$ be distinct. They have another solution: $b=-2c$, which works. – Kevin O'Bryant Jan 12 '10 at 22:04

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.

-
Which Vandermonde matrix do you mean? The given example is a 2x5 matrix, the null space has dimension 3, so ... – Kevin O'Bryant Dec 7 '09 at 13:25
The 5x5 matrix for $x_1$ through $x-5$, its inverse will will have two rows that are perpendicular to the vector of five 1's and the first two powers of $x_1$ through $x-5$ they or any nondegenerate combination of these two rows will form a 2x5 matrix that has the desired nullspace and this construction can be used to form the desired matrix of any dimensions $m$ and $n$ with a nullspace of the desired type, $n$ greater than $m$ using the $nxn$ Vandermonde matrix. – Kristal Cantwell Dec 7 '09 at 18:04