Matriz de vandermonde

AjustarCompartirImprimirCitar

Concepto matemático

En álgebra lineal, un Matriz de Vandermonde, nombrado por Alexandre-Théophile Vandermonde, es una matriz con los términos de una progresión geométrica en cada fila: una ${displaystyle (m+1)times (n+1)}$ matriz

{displaystyle V=V(x_{0},x_{1},cdotsx_{m})={begin{bmatrix}1&x_{0}&x_{0}^{2}&dots &x_{0}^{n}\1&x_{1}&x_{1}^{2}&dots &x_{1}^{n}\1&x_{2}&x_{2}^{2}&dots &x_{2}^{n}\vdots &vdots &vdots &ddots &vdots \1&x_{m}&x_{m}^{2}&dots &x_{m}^{n}end{bmatrix}}}

con entradas ${displaystyle V_{i,j}=x_{i}^{j}}$ , el j^T potencia del número $x_{i}$ , para todos los índices basados en cero $i$ y $j$ . La mayoría de los autores definen la matriz de Vandermonde como la transposición de la matriz anterior.

El determinante de una matriz de Vandermonde cuadrado (cuando $n=m$ ) se llama un Determinante de Vandermonde o polinomio de Vandermonde. Su valor es:

<math alttext="{displaystyle det(V)=prod _{0leq iDet()V)=∏ ∏ 0≤ ≤ i.j≤ ≤ n()xj− − xi).{displaystyle det(V)=prod _{0leq i madejleq n}(x_{j}-x_{i}).}<img alt="{displaystyle det(V)=prod _{0leq i

Esto no es cero si y sólo si todo $x_{i}$ son distintos (no dos son iguales), haciendo invertible la matriz Vandermonde.

Aplicaciones

El problema de la interpolación polinomio es encontrar un polinomio ${displaystyle p(x)=a_{0}+a_{1}x+a_{2}x^{2}+dots +a_{n}x^{n}}$ que satisfice ${displaystyle p(x_{0})=y_{0},ldotsp(x_{m})=y_{m}}$ para determinados puntos de datos ${displaystyle (x_{0},y_{0}),ldots(x_{m},y_{m})}$ . Este problema puede ser reformulado en términos de álgebra lineal por medio de la matriz Vandermonde, como sigue. $V$ calcula los valores de $p(x)$ en los puntos ${displaystyle x=x_{0}, x_{1},dots x_{m}}$ mediante una multiplicación de matriz ${displaystyle Va=y}$ , donde ${displaystyle a=(a_{0},ldotsa_{n})}$ es el vector de los coeficientes y ${displaystyle y=(y_{0},ldotsy_{m})=(p(x_{0}),ldotsp(x_{m}))}$ es el vector de valores (ambos escritos como vectores de columna):

{displaystyle {begin{bmatrix}1&x_{0}&x_{0}^{2}&dots &x_{0}^{n}\1&x_{1}&x_{1}^{2}&dots &x_{1}^{n}\1&x_{2}&x_{2}^{2}&dots &x_{2}^{n}\vdots &vdots &vdots &ddots &vdots \1&x_{m}&x_{m}^{2}&dots &x_{m}^{n}end{bmatrix}}cdot {begin{bmatrix}a_{0}\a_{1}\vdots \a_{n}end{bmatrix}}={begin{bmatrix}p(x_{0})\p(x_{1})\vdots \p(x_{m})end{bmatrix}}.}

n = m

{displaystyle x_{0},dots x_{n}}

VVSí.

p(x)

a

{displaystyle Va=y}

${displaystyle a=V^{-1}y}$ .

Es decir, la aplicación de coeficientes a valores de polinomios es una aplicación lineal biyectiva con la matriz V, y el problema de interpolación tiene una solución única. Este resultado se llama teorema de unisolvencia y es un caso especial del teorema chino del resto para polinomios.

En las estadísticas, la ecuación ${displaystyle Va=y}$ significa que la matriz de Vandermonde es la matriz de diseño de la regresión polinomio.

En el análisis numérico, resolver la ecuación ${displaystyle Va=y}$ ingenuamente por la eliminación gaisiana resultados en un algoritmo con la complejidad del tiempo O(n³). Explorando la estructura de la matriz de Vandermonde, se puede utilizar el método de diferencias divididas de Newton (o la fórmula de interpolación de Lagrange) para resolver la ecuación en O(n²) tiempo, que también da la factorización UL de $V^{{-1}}$ . El algoritmo resultante produce soluciones extremadamente precisas, incluso si $V$ está mal acondicionado. (Véase la interpolación polinómica.)

El determinante de Vandermonde se utiliza en la teoría de la representación del grupo simétrico.

Cuando los valores $x_{i}$ pertenece a un campo finito, el determinante de Vandermonde también se llama el determinante Moore, y tiene propiedades que son importantes en la teoría de códigos BCH y códigos de corrección de errores Reed-Solomon.

La transformación discreta Fourier se define por una matriz Vandermonde específica, la matriz DFT, donde la $x_{i}$ son elegidos para ser n^T raíces de la unidad. El Fast Fourier transforma el producto de esta matriz con un vector en O(n log²nHora.

En la teoría física del efecto Hall cuántico, el determinante de Vandermonde muestra que la función de onda de Laughlin con factor de llenado 1 es igual a un determinante de Slater. Esto ya no es cierto para factores de llenado diferentes de 1 en el efecto Hall cuántico fraccionario.

En la geometría de la polihedra, la matriz de Vandermonde da el volumen normalizado de arbitrariedad $k$ -caras de politopes cíclicos. Específicamente, si ${displaystyle F=C_{d}(t_{i_{1}},dotst_{i_{k+1}})}$ es un $k$ -cara del politopo cíclico ${displaystyle C_{d}(T)subset mathbb {R} ^{d}}$ correspondiente a $<math alttext="{displaystyle T={t_{1}<cdots T={}t1.⋯ ⋯ .tN}⊂ ⊂ R{displaystyle T={t_{1} # Subset mathbb {R}<img alt="{displaystyle T={t_{1}<cdots$ , entonces

<math alttext="{displaystyle mathrm {nvol} (F)={frac {1}{k!}}prod _{1leq mnvol()F)=1k!∏ ∏ 1≤ ≤ m.n≤ ≤ k+1()tin− − tim).{displaystyle mathrm {nvol} (F)={frac {1} {k}}prod _{1leq m madenleq ¿Qué?<img alt="{displaystyle mathrm {nvol} (F)={frac {1}{k!}}prod _{1leq m

Determinante

El determinante de una matriz de Vandermonde cuadrada se llama polinomio de Vandermonde o determinante de Vandermonde. Su valor es el polinomio.

<math alttext="{displaystyle det(V)=prod _{0leq iDet()V)=∏ ∏ 0≤ ≤ i.j≤ ≤ n()xj− − xi){displaystyle det(V)=prod _{0leq i donejleq n}(x_{j}-x_{i})}<img alt="{displaystyle det(V)=prod _{0leq i

que no es cero si y sólo si todo $x_{i}$ son distintos.

El determinante de Vandermonde fue a veces llamado el discriminación, pero en la terminología actual el discriminante de un polinomio ${displaystyle p(x)=(x-x_{0})cdots (x-x_{n})}$ es cuadrado del determinante Vandermonde de las raíces $x_{i}$ . El determinante de Vandermonde es una forma alternada en el $x_{i}$ , lo que significa que cambiar dos $x_{i}$ cambia el signo, y ${displaystyle det(V)}$ así depende del orden para el $x_{i}$ . Por el contrario, el discriminante ${displaystyle det(V)^{2}}$ no depende de ningún orden, por lo que la teoría de Galois implica que el discriminante es una función polinomio de los coeficientes de $p(x)$ .

La fórmula determinante se demuestra a continuación de tres maneras. El primero utiliza propiedades polinómicas, especialmente la propiedad única de factorización de los polinomios multivariados. Aunque conceptualmente simple, involucra conceptos no elementales de álgebra abstracta. La segunda prueba se basa en los conceptos de álgebra lineal de cambio de base en un espacio vectorial y el determinante de una aplicación lineal. En el proceso, calcula la descomposición LU de la matriz de Vandermonde. La tercera prueba es más elemental pero más complicada y utiliza sólo operaciones elementales de filas y columnas.

Primera prueba: propiedades polinómicas

Por la fórmula Leibniz, ${displaystyle det(V)}$ es un polinomio en el $x_{i}$ , con coeficientes enteros. Todas las entradas $i$ la columna (con base cero) tiene un grado total $i$ . Así, de nuevo por la fórmula Leibniz, todos los términos del determinante tienen un grado total

{displaystyle 0+1+2+cdots +n={frac {n(n+1)}{2}};}

(ese es el determinante es un polinomio homogéneo de este grado).

Si, para $ineq j$ , un sustituto $x_{i}$ para $x_{j}$ , uno consigue una matriz con dos filas iguales, que tiene por lo tanto un determinante cero. Así, por el factor teorema, ${displaystyle x_{j}-x_{i}}$ es un divisor de ${displaystyle det(V)}$ . Por la propiedad de factorización única de polinomios multivariados, el producto de todos ${displaystyle x_{j}-x_{i}}$ divideciones ${displaystyle det(V)}$ , eso es

<math alttext="{displaystyle det(V)=Qprod _{1leq iDet()V)=Q∏ ∏ 1≤ ≤ i.j≤ ≤ n()xj− − xi),{displaystyle det(V)=Qprod _{1leq i madejleq n}(x_{j}-x_{i}),}<img alt="{displaystyle det(V)=Qprod _{1leq i

Donde $Q$ es un polinomio. Como producto de todos ${displaystyle x_{j}-x_{i}}$ y ${displaystyle det(V)}$ tienen el mismo grado ${displaystyle n(n+1)/2}$ , el polinomio $Q$ es, de hecho, una constante. Esta constante es una, porque el producto de las entradas diagonales de $V$ es ${displaystyle x_{1}x_{2}^{2}cdots x_{n}^{n}}$ , que es también el monomial que se obtiene tomando el primer término de todos los factores en $<math alttext="{displaystyle textstyle prod _{0leq i∏ ∏ 0≤ ≤ i.j≤ ≤ n()xj− − xi).{displaystyle textstyle prod _{0leq i didjleq n}(x_{j}-x_{i}).}<img alt="{displaystyle textstyle prod _{0leq i$ Esto prueba que

<math alttext="{displaystyle det(V)=prod _{0leq iDet()V)=∏ ∏ 0≤ ≤ i.j≤ ≤ n()xj− − xi).{displaystyle det(V)=prod _{0leq i madejleq n}(x_{j}-x_{i}).}<img alt="{displaystyle det(V)=prod _{0leq i

Segunda prueba: mapas lineales

Vamos $F$ ser un campo que contenga todos ${displaystyle x_{i},}$ y $P_{n}$ el $F$ espacio vectorial de los polinomios de grado inferior o igual a $n$ con coeficientes en $F$ . Vamos

{displaystyle varphi:P_{n}to F^{n+1}}

ser el mapa lineal definido por

{displaystyle p(x)mapsto (p(x_{0}),p(x_{1}),ldotsp(x_{n}))}

La matriz de Vandermonde es la matriz $varphi$ con respecto a las bases canónicas de $P_{n}$ y ${displaystyle F^{n+1}.}$

Cambiar la base de $P_{n}$ equivale a multiplicar la matriz de Vandermonde por una matriz de cambio de base $M$ (de la derecha). Esto no cambia el determinante, si el determinante $M$ es 1.

Los polinomios $1$ , $x-x_{0}$ , ${displaystyle (x-x_{0})(x-x_{1})}$ ,..., ${displaystyle (x-x_{0})(x-x_{1})cdots (x-x_{n-1})}$ son monía de los respectivos grados 0, 1,..., $n$ . Su matriz sobre la base monomial es una matriz triangular superior $U$ (si los monomiales se ordenan en grados crecientes), con todas las entradas diagonales iguales a una. Esta matriz es por lo tanto una matriz de cambio de base de determinante. La matriz $varphi$ sobre esta nueva base

{displaystyle {begin{bmatrix}1&0&0&ldots &0\1&x_{1}-x_{0}&0&ldots &0\1&x_{2}-x_{0}&(x_{2}-x_{0})(x_{2}-x_{1})&ldots &0\vdots &vdots &vdots &ddots &vdots \1&x_{n}-x_{0}&(x_{n}-x_{0})(x_{n}-x_{1})&ldots &(x_{n}-x_{0})(x_{n}-x_{1})cdots (x_{n}-x_{n-1})end{bmatrix}}}

Así, el determinante de Vandermonde es igual al determinante de esta matriz, que es el producto de sus entradas diagonales.

Esto demuestra la igualdad deseada. Además, se obtiene la descomposición LU de $V$ como ${displaystyle V=LU^{-1}}$ .

Tercera prueba: operaciones de filas y columnas

Esta tercera prueba se basa en el hecho de que si se suma a una columna de una matriz el producto por un escalar de otra columna entonces el determinante permanece sin cambios.

Así, restando a cada columna – excepto la primera – la columna anterior multiplicada por $x_{0}$ , el determinante no se cambia. (Estas restas deben hacerse a partir de las últimas columnas, para restar una columna que aún no ha sido cambiada). Esto da la matriz

{displaystyle {begin{bmatrix}1&0&0&0&cdots &0\1&x_{1}-x_{0}&x_{1}(x_{1}-x_{0})&x_{1}^{2}(x_{1}-x_{0})&cdots &x_{1}^{n-1}(x_{1}-x_{0})\1&x_{2}-x_{0}&x_{2}(x_{2}-x_{0})&x_{2}^{2}(x_{2}-x_{0})&cdots &x_{2}^{n-1}(x_{2}-x_{0})\vdots &vdots &vdots &vdots &ddots &vdots \1&x_{n}-x_{0}&x_{n}(x_{n}-x_{0})&x_{n}^{2}(x_{n}-x_{0})&cdots &x_{n}^{n-1}(x_{n}-x_{0})\end{bmatrix}}}

Aplicando la fórmula de expansión de Laplace a lo largo de la primera fila, obtenemos ${displaystyle det(V)=det(B)}$ , con

{displaystyle B={begin{bmatrix}x_{1}-x_{0}&x_{1}(x_{1}-x_{0})&x_{1}^{2}(x_{1}-x_{0})&cdots &x_{1}^{n-1}(x_{1}-x_{0})\x_{2}-x_{0}&x_{2}(x_{2}-x_{0})&x_{2}^{2}(x_{2}-x_{0})&cdots &x_{2}^{n-1}(x_{2}-x_{0})\vdots &vdots &vdots &ddots &vdots \x_{n}-x_{0}&x_{n}(x_{n}-x_{0})&x_{n}^{2}(x_{n}-x_{0})&cdots &x_{n}^{n-1}(x_{n}-x_{0})\end{bmatrix}}}

Como todas las entradas $i$ -la fila de $B$ tener un factor ${displaystyle x_{i+1}-x_{0}}$ , uno puede sacar estos factores y obtener

<math alttext="{displaystyle det(V)=(x_{1}-x_{0})(x_{2}-x_{0})cdots (x_{n}-x_{0}){begin{vmatrix}1&x_{1}&x_{1}^{2}&cdots &x_{1}^{n-1}\1&x_{2}&x_{2}^{2}&cdots &x_{2}^{n-1}\vdots &vdots &vdots &ddots &vdots \1&x_{n}&x_{n}^{2}&cdots &x_{n}^{n-1}\end{vmatrix}}=prod _{1Det()V)=()x1− − x0)()x2− − x0)⋯ ⋯ ()xn− − x0)Silencio1x1x12⋯ ⋯ x1n− − 11x2x22⋯ ⋯ x2n− − 1⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ 1xnxn2⋯ ⋯ xnn− − 1Silencio=∏ ∏ 1.i≤ ≤ n()xi− − x0)Det()V.){displaystyle det(V)=(x_{1}-x_{0})(x_{2}-x_{0})cdots (x_{n}-x_{0}){beginvmatrix}1 limitx_{1} ################################################################################################################################################################################################################################################################ 'x_{2} {n-1}\vdots &vdots &vdots >vdots \1 conx_{n} limitx_{n}{2} limitcdots ¿Qué? ¿Por qué?<img alt="{displaystyle det(V)=(x_{1}-x_{0})(x_{2}-x_{0})cdots (x_{n}-x_{0}){begin{vmatrix}1&x_{1}&x_{1}^{2}&cdots &x_{1}^{n-1}\1&x_{2}&x_{2}^{2}&cdots &x_{2}^{n-1}\vdots &vdots &vdots &ddots &vdots \1&x_{n}&x_{n}^{2}&cdots &x_{n}^{n-1}\end{vmatrix}}=prod _{1

Donde $V'$ es una matriz de Vandermonde $x_{1},ldotsx_{n}$ . Iterando este proceso en esta pequeña matriz de Vandermonde, uno eventualmente consigue la expresión deseada ${displaystyle det(V)}$ como el producto de todos ${displaystyle x_{j}-x_{i}}$ tales que $<math alttext="{displaystyle ii.j{displaystyle i donej} <img alt="i$ .

Rango de la matriz de Vandermonde

An $m \times n$ rectangular matriz de Vandermonde tal que $m \leq n$ tiene rango $m$ si y sólo si todo $x i$ son distintos.
An $m \times n$ rectangular matriz de Vandermonde tal que $m \geq n$ tiene rango $n$ si y sólo si hay $n$ de la $x i$ Eso es distinto.
Una matriz de Vandermonde cuadrado es invertible si y sólo si $x i$ son distintos. Se conoce una fórmula explícita para el inverso (ver abajo).

Matriz de Vandermonde inversa

Como se explicó anteriormente en Aplicaciones, el problema de la interpolación polinomio para ${displaystyle p(x)=a_{0}+a_{1}x+a_{2}x^{2}+dots +a_{n}x^{n}}$ satisfacción ${displaystyle p(x_{0})=y_{0},ldotsp(x_{n})=y_{n}}$ es equivalente a la ecuación matriz ${displaystyle Va=y}$ , que tiene la solución única ${displaystyle a=V^{-1}y}$ . Hay otras fórmulas conocidas que resuelven el problema de la interpolación, que debe ser equivalente a lo único ${displaystyle a=V^{-1}y}$ , por lo que deben dar fórmulas explícitas para la matriz inversa $V^{{-1}}$ . En particular, la interpolación Lagrange muestra que las columnas de la matriz inversa

{displaystyle V^{-1}={begin{bmatrix}1&x_{0}&dots &x_{0}^{n}\vdots &vdots &&vdots \[.5em]1&x_{n}&dots &x_{n}^{n}end{bmatrix}}^{-1}=L={begin{bmatrix}L_{00}&!!!!cdots !!!!&L_{0n}\vdots &&vdots \L_{n0}&!!!!cdots !!!!&L_{nn}end{bmatrix}}}

son los coeficientes de los polinomios de Lagrange

${displaystyle L_{j}(x)=L_{0j}+L_{1j}x+cdots +L_{nj}x^{n}=prod _{0leq ileq n atop ineq j}{frac {x-x_{i}}{x_{j}-x_{i}}}={frac {f(x)}{(x-x_{j}),f'(x_{j})}},,}$

Donde ${displaystyle f(x)=(x-x_{0})cdots (x-x_{n})}$ . Esto se demuestra fácilmente: los polinomios claramente satisfacen ${displaystyle L_{j}(x_{i})=0}$ para $ineq j$ mientras ${displaystyle L_{j}(x_{j})=1}$ , por lo que podemos calcular el producto ${displaystyle VL=[L_{j}(x_{i})]_{i,j=0}^{n}=I}$ , la matriz de identidad.

Matrices confluentes de Vandermonde

Como se describe antes, una matriz de Vandermonde describe el problema de interpolación de álgebra lineal de encontrar los coeficientes de un polinomio $p(x)$ grado $n-1$ basado en los valores ${displaystyle p(x_{1}),,...,,p(x_{n})}$ , donde ${displaystyle x_{1},,...,,x_{n}}$ son diferencia puntos. Si $x_{i}$ no son distintos, entonces este problema no tiene una solución única (y la matriz Vandermonde correspondiente es singular). Sin embargo, si especificamos los valores de los derivados en los puntos repetidos, entonces el problema puede tener una solución única. Por ejemplo, el problema

{displaystyle {begin{cases}p(0)=y_{1}\p'(0)=y_{2}\p(1)=y_{3}end{cases}}}

Donde ${displaystyle p(x)=ax^{2}+bx+c}$ , tiene una solución única para todos $y_{1},y_{2},y_{3}$ con ${displaystyle y_{1}neq y_{3}}$ . En general, supongamos que $x_{1},x_{2},...,x_{n}$ son (no necesariamente distintos) números, y suponen para la simplicidad que los valores iguales están adyacentes:

{displaystyle x_{1}=cdots =x_{m_{1}}, x_{m_{1}+1}=cdots =x_{m_{2}}, ldots x_{m_{k-1}+1}=cdots =x_{m_{k}}}

Donde $<math alttext="{displaystyle m_{1}<m_{2}<cdots m1.m2.⋯ ⋯ .mk=n,{displaystyle - No.<img alt="{displaystyle m_{1}<m_{2}<cdots$ y ${displaystyle x_{m_{1}},ldotsx_{m_{k}}}$ son distintos. Entonces el problema de interpolación correspondiente es

{displaystyle {begin{cases}p(x_{m_{1}})=y_{1},&p'(x_{m_{1}})=y_{2},&ldots&p^{(m_{1}-1)}(x_{m_{1}})=y_{m_{1}},\p(x_{m_{2}})=y_{m_{1}+1},&p'(x_{m_{2}})=y_{m_{1}+2},&ldots&p^{(m_{2}-m_{1}-1)}(x_{m_{2}})=y_{m_{2}},\qquad vdots &&&qquad vdots \p(x_{m_{k}})=y_{m_{k-1}+1},&p'(x_{m_{k}})=y_{m_{k-1}+2},&ldots&p^{(m_{k}-m_{k-1}-1)}(x_{m_{k}})=y_{m_{k}}.end{cases}}}

La matriz correspondiente para este problema se llama confluentes Matriz de Vandermonde, dado como sigue. Si $1leq i,jleq n$ , entonces $<math alttext="{displaystyle m_{ell }ml l .i≤ ≤ ml l +1{displaystyle - ¿Qué? #<img alt="{displaystyle m_{ell }$ para un único ${displaystyle 0leq ell leq k-1}$ (denotación) ${displaystyle m_{0}=0}$ ). Dejamos

<math alttext="{displaystyle V_{i,j}={begin{cases}0&{text{if }}jVi,j={}0sij.i− − ml l ,()j− − 1)!()j− − ()i− − ml l ))!xij− − ()i− − ml l )sij≥ ≥ i− − ml l .{displaystyle V_{i,j}={begin{cases}0 [6pt]{dfrac {(j-1)}{(j-(i-m_{ell })}})}x_{i}{j-(i-m_{ell })} {i}{j-i-(i-m_{ell }} {if }jgeq i-m_{casi}end}<img alt="{displaystyle V_{i,j}={begin{cases}0&{text{if }}j

Esta generalización de la matriz de Vandermonde la hace no singular, de modo que existe una solución única para el sistema de ecuaciones y posee la mayoría de las demás propiedades de la matriz de Vandermonde. Sus filas son derivadas (de algún orden) de las filas originales de Vandermonde.

Otra manera de derivar esta fórmula es tomando un límite de la matriz de Vandermonde como la $x_{i}$ Se acercan. Por ejemplo, para obtener el caso de $x_{1}=x_{2}$ , tomar restar la primera fila de segundo en la matriz original de Vandermonde, y dejar ${displaystyle x_{2}to x_{1}}$ : esto produce la fila correspondiente en la matriz confluente de Vandermonde. Esto deriva el problema generalizado de la interpolación con valores y derivados dados como límite del caso original con puntos distintos: dar ${displaystyle p(x_{i}),p'(x_{i})}$ es similar a dar ${displaystyle p(x_{i}),p(x_{i}+varepsilon)}$ para pequeños $varepsilon$ . Los geométricos han estudiado el problema de rastrear puntos confluentes a lo largo de sus líneas tangentes, conocidas como compacitificación del espacio de configuración.