Matrices cuya nullspace se forma muy bien

Question

Estoy buscando condiciones naturales en $a_{ij}$ a garantizar que el espacio nulo de la $n\times m$ matriz $A=(a_{ij})$ tiene una buena base.

El espacio nulo de { {1,-2,1,0,0}, {0,1,-2,1,0}, {0,0,1,-2,1} } es el conjunto de vectores $\langle x_1,x_2,x_3,x_4,x_5\rangle^T$ $x_1,\dots,x_5$ en progresión aritmética o constante, es decir, hay un grado cero o uno de los polinomios $p(t)$$x_i = p(i)$. El espacio nulo de { {3,3,-23,21,-4}, {6,3,-38,36,-7} } se compone de puntos para los cuales hay un en-la mayoría-cuadrática $p(t)$$x_1=p(1),x_2=p(2),x_3=p(3),x_4=p(4),x_5=p(6)$, con el que el pasado 6 de no ser un error tipográfico.

En particular, necesito una base para el espacio nulo de la forma$\{\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\}$, $x_i$ distintos (no necesariamente enteros).

Como otro ejemplo, considere la matriz { {3,-3,1,0,-1}, {20,-16,5,-9,0} }. Me he enterado de que el espacio nulo de la matriz tiene base $\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$, pero sólo porque me hizo la matriz de esa manera. Incluso con una matriz específica, tal como esta, no sé cómo calcular esa base, o para garantizar que existe o no existe.

Aquí están las evidentes condiciones necesarias: las filas deben ser independientes; cada fila debe sumar 0; ninguna fila puede tener exactamente dos a cero de los componentes.

Como un problema específico (no tengo interés en esto como un problema en particular, de la mente, pero puede ayudar a la discusión) considere la matriz { {35,-3,-42,10,0}, {15,3,-8,0,-10} }. ¿Tiene esa base?

Para el fondo, la estoy buscando en construcciones de conjuntos de $X$ de enteros que no contienen soluciones a un sistema de ecuaciones lineales. Esa base como en el anterior significa que una solución ha x_i en la imagen de un polinomio, y ya sé cómo construir conjuntos que no tienen esos (progresiones aritméticas son un caso especial).

Answer 1

Si usted invertir la matriz de Vandermonde obtendrá los vectores que son ortogonales a los vectores en el deseado nullspace. Usted puede utilizar estos vectores para la construcción de una matriz con la deseada nullspace. Sin embargo no creo que el promedio de la matriz tendrá un nullspace. Usted tendrá m parámetros de la $x_i$ $n$ más de las coordenadas de las combinaciones de estos vectores que da n+m parámetros para $mn$ variables. De esta disparidad en los parámetros que se ve en la mayoría de los casos no habrá una solución en el otro lado de la inversa de la Vandermonde es conocido por lo que es fácil construir ejemplos de este tipo.

Answer 2

Como un problema específico (que no tengo el interés en este particular el problema, claro está, pero puede ayudar a la discusión) considere la matriz { {35,-3,-42,10,0}, {15,3,-8,0,-10} }. ¿Tiene esa base?

sustancialmente editado, con la modificación de conclusión después de la fijación por Kevin comentarios

Sí.

Considere el siguiente espacio nulo de la matriz (denota por $N$):

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

Escribir $w = (a,b,c)^T$$w' = (a',b',c')^T$. El ejemplo de pregunta es si hay una solución a las ecuaciones $Nw = x$$Nw' = x^2$, donde las componentes de la multiplicación se indica. Elija su favorito ordenó tupla para el grado 2 monomials (en general, para una cosa que me gusta el grlex el fin de que se hace referencia en Exclusiva de generar todas las permutaciones de tres dígitos que se suma a un valor determinado? pero): aquí, voy a usar las $z=(a^2,b^2,c^2,ab,ac,bc)^T$.

Deje $P$ ser la matriz

       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

Ahora el ejemplo es equivalente a $Pz = (Nw)^2$.

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

Si $a = 0$, luego $a'=0$, $b'=5b^2$, y $c'=15c^2$ (a partir de la parte inferior tres filas de $P$, respectivamente). Sustituyendo en las ecuaciones correspondientes a las dos filas superiores de $P$ de plomo para las dos ecuaciones $b^2+9c^2-6bc=-5b^2+45c^2$$25b^2+1225c^2+350bc=25b^2+525c^2$, los que tienen las soluciones $b, c = 0$$-2c = b$.

La primera solución no está permitida desde los componentes de $x$ son necesarios para ser distinto, sino $w = (0,-2,1)^T$ y $w' = (0,20,15)^T$ (o la que corresponda múltiplos) de trabajo, y MATLAB confirma esto.

Si $a = 1$, se deduce que $a' = 1$, $b' = 2b + 5b^2$, y $c' = 2c + 15c^2$ (a partir de la parte inferior tres filas de $P$, respectivamente). Sustituyendo en las ecuaciones correspondientes a las dos filas superiores de $P$ conduce a las dos ecuaciones se $1-2b-5b^2+6c+45c^2 = 1+b^2+9c^2-2b+6c-6bc$$1+10b+25b^2+70c+1125c^2=1+25b^2+1225c^2+10b+70c+350bc$. Estos simplificar a$-6b^2+36c^2+6bc=0$$2c+7b=0$. Sustituyendo $c=-7b/2$ en el primero de estos rendimientos $-6b^2+441b^2-21b^2 = 0$, lo que falla si $b, c = 0$, en tanto que es rechazado debido a que los componentes de $x$ están obligados a ser distinto.

Answer 3

Después de un poco de retoques, decidí que el ejemplo y más plenamente la generalización merecido por separado las respuestas, no menos debido a que mi respuesta inicial entró wiki de la comunidad, debido a que el número de ediciones que he hecho.

Deje $N$ ser un espacio nulo de la matriz de $A$, es decir, las columnas de a $N$ son aniquilados por $A$. Queremos vectores $w,w',\dots,w^{(m-n-2)}$ s.t. $(Nw)^{\ell+1} = Nw^{(\ell)}$. Definir $z^{(\ell)}$ $z^{(\ell)}_{i(\alpha)} := w^\alpha$ donde $i(\alpha)$ es el grlex índice de

$\alpha \in$ $ X_{m-n,\ell+1} \equiv$ {$\beta \in \mathbb{Z}^{m-n}: \sum_k \beta_k = \ell + 1$}.

Ahora vamos a $P^{(\ell)}$ $m \times |X_{m-n,\ell+1}|$ matriz con entradas dadas por

$P^{(\ell)}_{j,i(\alpha)} :=$ coeficiente de $w^\alpha$$(\sum_k N_{jk}w_k)^{\ell+1}$.

Para obtener este coeficiente explícitamente, tenga en cuenta que

$(\sum_k N_{jk}w_k)^{\ell+1} = > \sum_{\alpha \in X} > \binom{\ell+1}{\alpha}N_{j,\cdot}^\alpha > w^\alpha$

de dónde $P^{(\ell)}_{j,i(\alpha)}$ es igual

$\binom{\ell+1}{\alpha} > N_{j,\cdot}^\alpha$.

Por ejemplo, con $N_{j,\cdot} = > (2,3,5,7)$, $\ell = 2$, and $\alpha = > (0,1,1,1)$, so that $i(\alpha) = 6$, tenemos que $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$.

La ampliación de este ejemplo,

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

A continuación, la existencia (haciendo caso omiso de la distinción de las entradas) de $w^{(\ell)}$ s.t. $(Nw)^{\ell+1} = Nw^{(\ell)}$ es equivalente a la existencia de una solución para

$(Nw)^{\ell+1} = P^{(\ell)}z^{(\ell)}$.

Tenga en cuenta que para todas las $\ell$ esto es realmente una ecuación en la que los componentes de $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$

y en caso de que (al menos) ser susceptibles de solución en un sistema de álgebra de rutina.