Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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
add comment

3 Answers

up vote 1 down vote accepted

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.

share|improve this answer
It looks like the key equation is a tautology. I'll work on clarifying this. –  Steve Huntsman Jan 14 '10 at 6:39
add comment

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


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.

share|improve this answer
"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
add comment

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.

share|improve this answer
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.