Let the system of numbers (elements of a field) $ \{x_1,x_2,\dots,x_n \} $ be given, not necessarily distinct. Matrix of the form $$ \mathbf V_{m\times n}(x_1, x_2,\ldots,x_n) = \left( \begin{array}{llll} 1& 1& \ldots& 1\\ x_1& x_2& \ldots& x_n\\ x_1^2& x_2^2& \ldots& x_n^2\\ \vdots& \vdots& & \vdots \\ x_1^{m-1}& x_2^{m-1}& \ldots& x_n^{m-1} \end{array} \right)_{m\times n} $$ or its transpose is called $ m \times n $-Vandermonde's matrix.

A particular case of Vandermonde's matrix is the matrix of disrete Fourier transform $$ F=\left[ \varepsilon_j^{k} \right]_{j,k=0}^{n-1}= $$ $$ = \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon_1 & \varepsilon_1^2 & \dots & \varepsilon_1^{n-1} \\ 1 & \varepsilon_2 & \varepsilon_2^2 & \dots & \varepsilon_2^{n-1} \\ 1 & \varepsilon_3 & \varepsilon_3^2 & \dots & \varepsilon_3^{n-1} \\ \vdots & & & & \vdots \\ 1 & \varepsilon_{n-1} & \varepsilon_{n-1}^{2} & \dots & \varepsilon_{n-1}^{n-1} \end{array} \right)_{n\times n} \quad \mbox{where} \ \varepsilon_j:= \cos \frac{2 \pi j}{n} + {\mathbf i} \, \sin \frac{2 \pi j}{n} $$ is the root of $1$ of the order $n$. The relation $ \varepsilon_j=\varepsilon_1^j $ provides an alternative form of the matrix $$ F= \left[ \varepsilon^{jk} \right]_{j,k=0}^{n-1}= $$ $$ =\left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon & \varepsilon^2 & \dots & \varepsilon^{n-1} \\ 1 & \varepsilon^2 & \varepsilon^4 & \dots & \varepsilon^{2(n-1)} \\ 1 & \varepsilon^3 & \varepsilon^6 & \dots & \varepsilon^{3(n-1)} \\ \vdots & & & & \vdots \\ 1 & \varepsilon^{n-1} & \varepsilon^{2(n-1)} & \dots & \varepsilon^{(n-1)^2} \end{array} \right)_{n\times n} \quad \mbox{where} \ \varepsilon = \cos \frac{2 \pi}{n} + {\mathbf i} \, \sin \frac{2 \pi}{n} \ . $$

The determinant of (a square!) $ n\times n $-Vandermonde's matrix is called Vandermonde's determinant. If $ n=1 $ then it is just $ 1 $. For $ n>1 $ we denote it as $ V(x_1,\dots,x_n) $: $$ V(x_1,\dots,x_n)= \left| \begin{array}{llll} 1& 1& \ldots& 1\\ x_1& x_2& \ldots& x_n\\ x_1^2& x_2^2& \ldots& x_n^2\\ \vdots& \vdots& & \vdots \\ x_1^{n-1}& x_2^{n-1}& \ldots& x_n^{n-1} \end{array} \right|= \left| \begin{array}{llll} 1& x_1& \ldots& x_1^{n-1}\\ 1& x_2& \ldots& x_2^{n-1}\\ \vdots& \vdots& & \vdots \\ 1 & x_n& \ldots & x_n^{n-1} \end{array} \right| \, . $$ This is evidently a polynomial in $ x_1,\dots,x_n $: $$ V(x_1,x_2)=x_2-x_1,\ V(x_1,x_2,x_3)= x_1^2x_3-x_1x_3^2+x_1x_2^2-x_1^2x_2+x_2x_3^2-x_2^2x_3, \dots , $$ and it is a homogeneous one of the degree $ n(n-1)/2 $ with integer coefficients. It is reducible over $ \mathbb Z $.

Theorem. The following identity is valid:

$$ V(x_1,\dots,x_n) \equiv \prod_{1\le j < k \le n} (x_k-x_j)\ . $$

Vandermonde's determinant of the order $ n\ge 2 $ does not vanish if and only if all the numbers $ x_1,x_2,\dots,x_n $ are distinct.

Example.

$$ V(x_1,x_2,x_3)\equiv (x_2-x_1)(x_3-x_1)(x_3-x_2) \ ; $$ $$ V(x_1,x_2,x_3,x_4) \equiv $$ $$ \equiv (x_2-x_1)(x_3-x_1)(x_3-x_2)(x_4-x_1)(x_4-x_2)(x_4-x_3) \ . $$ ♦

The determinant of the discrete Fourier transform matrix is computed by the formula

$$ \det F = \left\{ \begin{array}{ll} n^{n/2} {\mathbf i}^{n(n-1)/2+1} & \mbox{ if }\ n_{} \mbox{ is even }, \\ n^{n/2} {\mathbf i}^{n(n-1)/2} & \mbox{ if }\ n_{} \mbox{ is odd }. \end{array} \right. $$

Vandermonde's matrix naturally appears in the polynomial (algebraic) interpolation problem.

Problem. Construct a univariate polynomial $ y_{}=f(x) $ that takes the values according to the following table $$ \begin{array}{c|ccccc} x & x_1 & x_2 & \dots & x_n \\ \hline y & y_1 & y_2 &\dots & y_n \end{array} $$ Here the numbers $ \{ x_{j}, y_{j} \}_{j=1}^n $ are from $ \mathbb Q_{} $ or $ \mathbb R_{} $ or $ \mathbb C_{} $, or, generally, the elements of an arbitrary field which will be denoted further by $ \mathbb A_{} $. The numbers $ \{ x_{j} \}_{j=1}^n $ are called interpolation nodes while the polynomial in question is referred to as interpolation polynomial.

Theorem. If $ x_{1},\dots,x_{n} $ are distinct, then there exists a unique polynomial $ f(x) \in \mathbb A_{}[x] $ of the degree $ \le n_{}-1 $ such that $ f(x_{1})=y_{1},\dots,f(x_{n})=y_{n} $.

Proof. Coefficients of the polynomial $ f(x)=A_{0}+A_1x+\dots+A_{n-1}x^{n-1} $ can be determined from the following system of linear equations $$ \left\{\begin{array}{ccl} A_0+A_1x_1+\dots+A_{n-1}x_1^{n-1}&=&y_1 \\ A_0+A_1x_2+\dots+A_{n-1}x_2^{n-1}&=&y_2 \\ \dots & & \dots \\ A_0+A_1x_n+\dots+A_{n-1}x_n^{n-1}&=&y_n, \end{array} \right. $$ with the matrix being just Vandermonde's. By theorem from the previous section, its determinant is not zero. Due to Cramer's theorem, the system possesses a unique solution. ♦

Фактическое нахождение коэффициентов интерполяционного полинома посредством решения системы линейных уравнений по формулам Крамера достаточно громоздко. «Сходу» удается получить только выражения для $ A_0 $ и $ A_{n-1} $.

Example. For $ n=4 $, one has

$$ A_0=\frac{\left| \begin{array}{clll} y_1 & x_1 & x_1^2 & x_1^3 \\ y_2 & x_2 & x_2^2 & x_2^3 \\ y_3 & x_3 & x_3^2 & x_3^3 \\ y_4 & x_4 & x_4^2 & x_4^3 \end{array} \right|}{V(x_1,x_2,x_3,x_4)}= $$ expand this determinant by the entries of the first column $$ =\frac{y_1x_2x_3x_4V(x_2,x_3,x_4)-y_2x_1x_3x_4 V(x_1,x_3,x_4)+y_3x_1x_2x_4V(x_1,x_2,x_4)-y_4x_1x_2x_3V(x_1,x_2,x_3)}{V(x_1,x_2,x_3,x_4)}= $$ $$ =\frac{y_1x_2x_3x_4}{(x_1-x_2)(x_1-x_3)(x_1-x_4)}+\frac{y_2x_1x_3x_4}{(x_2-x_1)(x_2-x_3)(x_2-x_4)}+\frac{y_3x_1x_2x_4}{(x_3-x_1)(x_3-x_2)(x_3-x_4)}+ $$ $$ +\frac{y_4x_1x_2x_3}{(x_4-x_1)(x_4-x_2)(x_4-x_3)} \, . $$ $$ A_4=\frac{\left| \begin{array}{clll} 1 & x_1 & x_1^2 & y_1 \\ 1 & x_2 & x_2^2 & y_2 \\ 1 & x_3 & x_3^2 & y_3 \\ 1 & x_4 & x_4^2 & y_4 \end{array} \right|}{V(x_1,x_2,x_3,x_4)}= $$ expand this determinant by the entries of the first column: $$ =\frac{y_1}{(x_1-x_2)(x_1-x_3)(x_1-x_4)}+\frac{y_2}{(x_2-x_1)(x_2-x_3)(x_2-x_4)}+ $$ $$ + \frac{y_3}{(x_3-x_1)(x_3-x_2)(x_3-x_4)} +\frac{y_4}{(x_4-x_1)(x_4-x_2)(x_4-x_3)} \, . $$

♦

However, with the aid of some extra manipulations, one can reduce interpolation polynomial computation to that of Vandermonde's determinant. For this aim, utilize the result of Exercise 7 ☞ HERE. If $ f(x)=A_{0}+A_1x+\dots+A_{n-1}x^{n-1} $ with the column of coefficients satisfying the matrix eqyuation $$ \mathbf V \left[\begin{array}{l} A_0 \\ A_1 \\ \vdots \\ A_{n-1} \end{array} \right] = \left[\begin{array}{l} y_1 \\ y_2 \\ \vdots \\ y_{n} \end{array} \right] \, , $$ then $$ f(x) \equiv \left| \begin{array}{llrrrc} 1 & x_1 & x_1^2 & \dots & x_1^{n-1} & -y_1 \\ 1 & x_2 & x_2^2 & \dots & x_2^{n-1} & -y_2 \\ \vdots & \vdots & & & & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{n-1} & -y_n \\ 1 & x & x^2 & \dots & x^{n-1} & 0 \end{array} \right| \Big/ \left| \begin{array}{lrrrr} 1 & x_1 & x_1^2 & \dots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \dots & x_2^{n-1} \\ \vdots & \vdots & & & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{n-1} \end{array} \right| \equiv $$ Now expand the determinant from the numerator by the entries of its last column $$ \equiv (-1)^{n-1} y_1\frac{V(x_2,\dots,x_n,{\color{RubineRed} x})}{V(x_1,x_2,\dots,x_n)}+(-1)^{n-2}y_2\frac{V(x_1,x_3,\dots,x_n,{\color{RubineRed} x})}{V(x_1,x_2,\dots,x_n)} $$ $$ +\dots+ y_n\frac{V(x_1,x_2,\dots,x_{n-1},{\color{RubineRed} x})}{V(x_1,x_2,\dots,x_n)} \equiv $$ and reorder the rows in the determinants of the numerators of the fractions $$ \equiv y_1\frac{V({\color{RubineRed} x},x_2,\dots,x_n)}{V(x_1,x_2,\dots,x_n)}+y_2\frac{V(x_1,{\color{RubineRed} x},\dots,x_n)}{V(x_1,x_2,\dots,x_n)}+\dots+ y_n\frac{V(x_1,x_2,\dots,x_{n-1},{\color{RubineRed} x})}{V(x_1,x_2,\dots,x_n)} \, . $$ Now exploit the theorem from the previous section and cancel the common factors of numerators and denominators. Denote $$ W(x) = (x-x_1)\times \dots \times (x-x_n) \, , $$ $$ W_j(x) = \frac{W(x)}{x-x_j} = $$ $$ =(x-x_1)\times \dots \times (x-x_{j-1}) (x-x_{j+1})\times \dots \times (x-x_n) \quad \mbox{for} \quad j\in \{1,\dots,n\} . $$ This results in representation of the interpolation polynomial as $$ f(x) \equiv \sum_{j=1}^n \frac{y_jW_j(x)}{W_j(x_j)}= $$ $$ \begin{array}{ll} = & \displaystyle y_1\frac{(x-x_2)\times \dots \times (x-x_n)}{(x_1-x_2)\times \dots \times (x_1-x_n)}+ \\ + & \displaystyle y_2\frac{(x-x_1)(x-x_3)\times \dots \times (x-x_n)}{(x_2-x_1)(x_2-x_3)\times \dots \times (x_2-x_n)}+ \\ + & \dots+ \\ + & \displaystyle y_n\frac{(x-x_1)\times \dots \times (x-x_{n-1})}{(x_n-x_1)\times \dots \times (x_n-x_{n-1})} . \end{array} $$ This representation is known as the Lagrange's form of interpolation polynomial. The easily deduced equality $$ W_j(x_j)=W^{\prime}(x_j) $$ allows to rewrite this form in the equivalent equality $$ f(x) \equiv \sum_{j=1}^n \frac{y_jW_j(x)}{W^{\prime}(x_j)} \, . $$ Polynomials $$ \widetilde W_j(x) = W_j(x)/W_j(x_j) \equiv W_j(x)/W^{\prime}(x_j) \quad \mbox{for} \quad j \in \{1,\dots,n\} \, , $$ from this equality are oftenly called the basic interpolation polynomials. They possess the following property $$ \widetilde W_j(x_k) = \delta_{jk} \ , $$ where $ \delta_{jk} $ denotes Kronecker's delta. In other words, $ \widetilde W_j(x) $ is the interpolation polynomial for the table $$ \begin{array}{c|ccccc} x & x_1 & x_2 & \dots & x_{j-1} & x_j & x_{j+1} & \dots & x_n \\ \hline y & 0 & 0 & \dots & 0 & 1 & 0 & \dots & 0 \end{array} $$

Representation of the interpolation polynomial in Lagrange's form does not yield the explicit expressions for the polynomial coefficients. For the latter, it is necessary to expand the basis polynomials in powers of $ x $. On performing this $$ {\widetilde W}_j(x)\equiv w_{j0}+w_{j1}x+\dots+ w_{j,n-1}x^{n-1} \, , $$ the inverse matrix to Vandermonde's one can be constructed.

Theorem. If all the numbers $ x_1,x_2,\dots,x_n $ are distinct, then

$$ \left( \begin{array}{llll} 1& 1& \ldots& 1\\ x_1& x_2& \ldots& x_n\\ x_1^2& x_2^2& \ldots& x_n^2\\ \vdots& \vdots& & \vdots \\ x_1^{n-1}& x_2^{n-1}& \ldots& x_n^{n-1} \end{array} \right)^{-1}= \left( \begin{array}{llll} w_{10}& w_{11}& \ldots& w_{1,n-1}\\ w_{20}& w_{21}& \ldots& w_{2,n-1}\\ \dots & & & \dots \\ w_{n0}& w_{n1}& \ldots& w_{n,n-1}\\ \end{array} \right) \, . $$

Proof can be done in a variety of ways. The easiest one is a formal checking of the validity of the statement by multiplication of the matrix $ \left[ w_{jk} \right]_{j=1,\dots,n,k=0,\dots,n-1} $ by the Vandemonde's matrix from the left-hand side. This results in $$ \left(\begin{array}{llll} \widetilde W_1(x_1) & \widetilde W_1(x_2) & \dots & \widetilde W_1(x_n) \\ \widetilde W_2(x_1) & \widetilde W_2(x_2) & \dots & \widetilde W_2(x_n) \\ \dots & & & \dots \\ \widetilde W_n(x_1) & \widetilde W_n(x_2) & \dots & \widetilde W_n(x_n) \end{array} \right) $$ and this is an identity matrix due to the properties of the basis interpolation polynomials. ♦

Example. Compute

$$ \left(\begin{array}{ccc} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 4 & 9 \end{array} \right)^{-1} \, . $$

Solution. One has $$ W(x)=(x-1)(x-2)(x-3) \ , $$ $$ \widetilde W_1(x)=\frac{(x-2)(x-3)}{(1-2)(1-3)} = 3 -\frac{2}{5}x+\frac{1}{2}x^2,\ $$ $$ \widetilde W_2(x)=\frac{(x-1)(x-3)}{(2-1)(2-3)} = -3 +4\,x-x^2,\ $$ $$ \widetilde W_3(x)=\frac{(x-1)(x-2)}{(3-1)(3-2)} = 1 -\frac{3}{2}x+\frac{1}{2}x^2 \, . $$

Answer. $$ \left(\begin{array}{ccc} 3 & -5/2 & 1/2 \\ -3 & 4 & -1 \\ 1 & -3/2 & 1/2 \end{array} \right) \, . $$

Prove that sum of all the rows of $ \mathbf V^{-1} $ equals $ [1,0,0,\dots,0] $.

The next problem is the parallelization of computation of the basis interpolation polynomials. For this aim, calculate the values $$ \xi_1=\frac{1}{W^{\prime}(x_1)},\dots, \xi_n=\frac{1}{W^{\prime}(x_n)} \, . $$ and compose the column $$ \Xi_0=\left[\xi_1,\dots, \xi_n\right]^{\top} \, . $$ Multiply it by the column $$ \Lambda=\left[x_1,\dots, x_n\right]^{\top} \ . $$ Here vector multiplication is Hadamard's one, i.e. componentwise: $$ \Xi_1= \Xi_0 \otimes \Lambda= \left[\xi_1 x_1 ,\dots, \xi_n x_n \right]^{\top} \ . $$ On continuing the multiplication process further, generate the sequence $$ \Xi_0, \Xi_1=\Xi_0 \otimes \Lambda, \Xi_2=\Xi_1 \otimes \Lambda, \dots, \Xi_{n-1}=\Xi_{n-2} \otimes \Lambda, \dots, \Xi_{2n-2} = \Xi_{2n-3} \otimes \Lambda \ . $$ In accordance with the Euler-Lagrange equalities, the sum of entries of each column $ \Xi_0,\dots,\Xi_{n-2} $ is just $ 0_{} $, while that of $ \Xi_{n-1} $ equals $ 1 $.

Theorem[2]. Calculate the sums of entries of the columns $ \Xi_n, \Xi_{n+1},\dots, \Xi_{2n-2} $, i.e. the values

$$ \sigma_k = \sum_{j=1}^n \frac{x_j^{n+k-1}}{W^{\prime}(x_j)} , \quad k\in \{1,\dots,n-1\} \ . $$ Columns of the matrix $$ \mathbf V^{-1}:=\left[\mathbf V_{[1]}^{-1},\mathbf V_{[2]}^{-1},\dots, \mathbf V_{[n]}^{-1} \right] $$ are connected with the columns $ \Xi_0, \Xi_{1},\dots, \Xi_{n-1} $ via the following recursive relations: $$ \left\{ \begin{array}{lcl} \mathbf V_{[n]}^{-1}&=&\Xi_0, \\ \mathbf V_{[n-1]}^{-1}&=&\Xi_1-\sigma_1 \mathbf V_{[n]}^{-1}, \\ \mathbf V_{[n-2]}^{-1}&=&\Xi_2-\sigma_1 \mathbf V_{[n-1]}^{-1} - \sigma_2 \mathbf V_{[n]}^{-1}, \\ \dots & & \dots \\ \mathbf V_{[1]}^{-1}&=&\Xi_{n-1}-\sigma_1 \mathbf V_{[2]}^{-1} - \sigma_2 V_{[3]}^{-1}- \dots - \sigma_{n-1} \mathbf V_{[n]}^{-1}. \end{array} \right. $$

Proof. From the Euler-Lagrange equalities it follows that $$ \mathbf V\cdot \mathbf V_{[n]}^{-1}=\mathbf V\cdot \Xi_0=\left[\sum_{j=1}^n\frac{ 1}{W^{\prime}(x_j)},\ \sum_{j=1}^n\frac{ x_j}{W^{\prime}(x_j)},\dots, \sum_{j=1}^n\frac{ x_j^{n-1}}{W^{\prime}(x_j)} \right]^{\top}= $$ $$ = [0,0,\dots,0,1]^{\top} \, . $$ From the just obtained equality, we deduce that $$ \mathbf V\cdot \mathbf V_{[n-1]}^{-1}=V\cdot \Xi_1-\sigma_1 \mathbf V \cdot \mathbf V_{[n]}^{-1} = [0,0,\dots,1,\sigma_1]^{\top} - \sigma_1 [0,0,\dots,0,1]^{\top} = $$ $$ = [0,0,\dots,1,0]^{\top} \, . $$ Application of the two obtained equalities proves the third equality from the theorem: $$ \mathbf V\cdot \mathbf V_{[n-2]}^{-1}=V\cdot \Xi_2-\sigma_1 \mathbf V \cdot \mathbf V_{[n-1]}^{-1} - \sigma_2 \mathbf V \cdot \mathbf V_{[n]}^{-1} = $$ $$ =[0,0,\dots,1,\sigma_1,\sigma_2]^{\top} - \sigma_1 [0,0,\dots,1,0]^{\top} - \sigma_2 [0,0,\dots,0,1]^{\top} = [0,0,\dots,1,0,0]^{\top} \, . $$ And so on. ♦

Example. For the above treated example

$$ \mathbf V=\left(\begin{array}{ccc} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 4 & 9 \end{array} \right) $$ one has $$ x_1=1,\ x_2=2,\ x_3=3,\ W^{\prime}(1)=2,\ W^{\prime}(2)=-1,\ W^{\prime}(3)=2 \, . $$ From a system of columns $ \Xi_0, \Xi_{1},\Xi_{2},\Xi_{3}, \Xi_{4} $ compose the matrix $$ \left[ \begin{array}{rrrrr} 1/2 & 1/2 & 1/2 & 1/2 & 1/2 \\ -1 & -2 & -4 & -8 & -16 \\ 1/2 & 3/2 & 9/2 & 27/2 & 81/2 \end{array} \right] \ . $$ Sum the two last columns componentwise $$ \sigma_1=6, \ \sigma_2=25 $$ and apply the theorem: $$ \begin{array}{lll} V_{[3]}^{-1}&=& \left[ \begin{array}{r} 1/2 \\ -1 \\ 1/2 \end{array} \right], \ \\ V_{[2]}^{-1}&=& \left[ \begin{array}{r} 1/2 \\ -2 \\ 3/2 \end{array} \right]- 6 \left[ \begin{array}{r} 1/2 \\ -1 \\ 1/2 \end{array} \right]= \left[ \begin{array}{r} -5/2 \\ 4 \\ -3/2 \end{array} \right], \\ V_{[1]}^{-1}&=& \left[ \begin{array}{rrrrr} 1/2 \\ -4 \\ 9/2 \end{array} \right] - 6\, \left[ \begin{array}{r} -5/2 \\ 4 \\ -3/2 \end{array} \right]-25\, \left[ \begin{array}{r} 1/2 \\ -1 \\ 1/2 \end{array} \right]= \left[ \begin{array}{r} 3\\ -3 \\ 1 \end{array} \right] \ . \end{array} $$ ♦

Theorem. The inverse of the matrix of the discrete Fourier transform is given by the formula:

$$ F^{-1}=\frac{1}{n}\left[ \varepsilon_{-j}^{k} \right]_{j,k=0}^{n-1} $$ $$ =\left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon_{-1} & \varepsilon_{-1}^2 & \dots & \varepsilon_{-1}^{n-1} \\ 1 & \varepsilon_{-2} & \varepsilon_{-2}^2 & \dots & \varepsilon_{-2}^{n-1} \\ 1 & \varepsilon_{-3} & \varepsilon_{-3}^2 & \dots & \varepsilon_{-3}^{n-1} \\ \vdots & & & & \vdots \\ 1 & \varepsilon_{-(n-1)} & \varepsilon_{-(n-1)}^{2} & \dots & \varepsilon_{-(n-1)}^{n-1} \end{array} \right) \quad \mbox{where} \ \varepsilon_{-j}:= \cos \frac{2 \pi j}{n} - {\mathbf i} \, \sin \frac{2 \pi j}{n} $$ With the aid of the relation $ \varepsilon_{-j}=\varepsilon_{-1}^j=\overline{\varepsilon_1}^j $, this matrix is oftenly represented as $$ F^{-1}= \frac{1}{n}\left[ \overline{\varepsilon}^{jk} \right]_{j,k=0}^{n-1} $$ $$ =\frac{1}{n} \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \overline{\varepsilon} & \overline{\varepsilon}^2 & \dots & \overline{\varepsilon}^{n-1} \\ 1 & \overline{\varepsilon}^2 & \overline{\varepsilon}^4 & \dots & \overline{\varepsilon}^{2(n-1)} \\ 1 & \overline{\varepsilon}^3 & \overline{\varepsilon}^6 & \dots & \overline{\varepsilon}^{3(n-1)} \\ \vdots & & & & \vdots \\ 1 & \overline{\varepsilon}^{n-1} & \overline{\varepsilon}^{2(n-1)} & \dots & \overline{\varepsilon}^{(n-1)^2} \end{array} \right) \quad \mbox{where} \ \overline{\varepsilon} = \cos \frac{2 \pi}{n} - {\mathbf i} \, \sin \frac{2 \pi}{n} \ . $$

The kernel of the matrix $$ \mathbf V_{m\times n}(x_1, x_2,\ldots,x_n) = \left( \begin{array}{llll} 1& 1& \ldots& 1\\ x_1& x_2& \ldots& x_n\\ x_1^2& x_2^2& \ldots& x_n^2\\ \vdots& \vdots& & \vdots \\ x_1^{m-1}& x_2^{m-1}& \ldots& x_n^{m-1} \end{array} \right)_{m\times n} $$ where $ m<n $ and all the $ x_1,x_2,\dots,x_n $ are distinct, has the basis vectors $$ \big[x_1^j/W^{\prime}(x_1), \dots, x_n^j/W^{\prime}(x_n)\big]^{\top} \ \mbox{ where } j\in \{0,1,\dots,n-m-1\} \, . $$ This follows from the Euler-Lagrange equalities.

The kernel of the matrix $$ \left( \begin{array}{llll} 1 & x_1 & x_1^2 & \dots & x_1^{m-1} \\ 1 & x_2 & x_2^2 & \dots & x_2^{m-1} \\ \vdots & & & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{m-1} \end{array} \right)_{n\times m} $$ has the basis vector $ \left[ w_0,\dots, w_n \right]^{\top} $ if $ n=m-1 $, and the basis vectors $$ \left[ w_0,\dots, w_n,0, 0, \dots, 0 \right]^{\top}, \ \left[0,w_0,\dots, w_n,0, \dots, 0 \right]^{\top}, \dots , \left[0,\dots,0, w_0,\dots, w_n \right]^{\top} \, . $$ if $ n < m-1 $. Here $ \{w_j\} $ stand for the coefficients of the canonical form of the polynomial $$ \prod_{k=1}^n (x-x_k) \equiv w_0+w_1x+\dots+w_nx^n \, , $$ т.е. $$ w_0=(-1)^n \prod_{k=1}^n x_k, \dots, w_{n-1}=-\sum_{k=1}^n x_k, w_n=1 \, . $$

A natural generalization of the Vandermonde matrix is¹⁾ $$ \widehat{\mathbf V}=\left( \begin{array}{cccc} x_1^{n_1} & x_1^{n_2} & \dots & x_1^{n_m} \\ x_2^{n_1} & x_2^{n_2} & \dots & x_2^{n_m} \\ \vdots & & & \vdots \\ x_m^{n_1} & x_m^{n_2} & \dots & x_m^{n_m} \end{array} \right) \quad \mbox{where} \ \{n_1, n_2, \dots, n_m \} \subset \mathbb N \cup \{ 0 \} . $$ We denote its determiant as $ \widehat V $.

Similar to ☞ SECTION, denote $$ W(x):=\prod_{j=1}^m (x-x_j) \, . $$ Compute the expressions $$ \sigma_k(x_1,\dots,x_m) = \sum_{j=1}^{m} \frac{x_j^{m+k-1}}{W^{\prime}(x_j)} \quad \mbox{ for } \ k \in \{-(m-1),-(m-2),\dots,-1,0, 1,2, \dots \} \, . $$

Theorem 1. The following equalities are valid:

$$ \sigma_0 \equiv 1; \ \sigma_k \equiv 0 \quad \mbox{for} \ k \in \{-1,-2,\dots,-(m-1)\} \, . $$ For $ k>0 $, the expression $ \sigma_k $ is a symmetric polynomial with respect to $ x_1,\dots,x_m $, equal to the sum of all the possible monomials of the degree $ k $: $$ \sigma_k=\sum_{j_1+\dots+j_m=k}x_1^{j_1}\times \dots \times x_m^{j_m} \, . $$

Equalities $$ \sum_{j=1}^m \frac{x_j^k}{W'(x_j)}=\left\{ \begin{array}{cc} 0 & \mbox{if} \ k< m-1; \\ 1 & \mbox{if} \ k= m-1. \end{array} \right. $$ are known as the Euler-Lagrange equalities.

Example. For $ m=4 $, one gets

$$ \sigma_3=x_1^3+x_2^3+x_3^3+x_4^3+x_3^2x_2+x_3^2x_1+x_4x_3^2+x_3x_4^2+x_2^2x_3+x_1^2x_3 $$ $$ +x_2^2x_1+x_1^2x_2+x_1x_4^2+x_2^2x_4+x_2x_4^2+x_1^2x_4+x_3x_1x_2+x_1x_4x_3+x_2x_4x_3+x_1x_2x_4 $$

Theorem 2. The following relations are valid

$$ \sigma_k=\frac{1}{\displaystyle \prod_{1\le \ell<j \le m} (x_j-x_{\ell})}\left| \begin{array}{cccc} 1 & 1 & \dots & 1 \\ x_1 & x_2 & \dots & x_m\\ \vdots & & & \vdots \\ x_1^{m-1} & x_2^{m-1} & \dots & x_m^{m-1}\\ x_1^{k+m-1} & x_2^{k+m-1} & \dots & x_m^{k+m-1} \end{array} \right| \quad \mbox{ for } \ k\in \mathbb N \, . $$

Theorem 3. The following formula due to Crocchi

$$ \sigma_{k-1} s_1+\sigma_{k-2} s_2+\dots+\sigma_{1} s_{k-1} + s_k = k \sigma_k \, . $$ connects $ \sigma_k $ with the Newton's sums $ s_k=x_1^k+x_2^k+\dots+x_m^k $ of the polynomial $ W(x) $.

Theorem 4. One has

$$ \widehat V=\left| \begin{array}{cccc} \sigma_{n_1} & \sigma_{n_1-1} & \dots & \sigma_{n_1-m} \\ \sigma_{n_2} & \sigma_{n_2-1} & \dots & \sigma_{n_2-m} \\ \vdots & & & \vdots \\ \sigma_{n_m} & \sigma_{n_m-1} & \dots & \sigma_{n_m-m} \end{array} \right| \prod_{1\le \ell <j \le m} (x_j-x_{\ell}) $$

In view of the Euler-Lagrange equalities, one might expect that the matrix in the right-hand side of the last formula possesses several zero entries.

Example.

$$ \left| \begin{array}{cccc} x_1^{1} & x_1^{2} & x_1^4 & x_1^{6} \\ x_2^{1} & x_2^{2} & x_2^4 & x_2^{6} \\ x_3^{1} & x_3^{2} & x_3^4 & x_3^{6} \\ x_4^{1} & x_4^{2} & x_4^4 & x_4^{6} \end{array} \right|= \left| \begin{array}{cccc} 0 & 0 & \sigma_1 & \sigma_3 \\ 0 & 1 & \sigma_2 & \sigma_4 \\ 1 & \sigma_1 & \sigma_3 & \sigma_5 \\ \sigma_1 & \sigma_2 & \sigma_4 & \sigma_6 \end{array} \right| \prod_{1\le \ell < j \le 4} (x_j-x_{\ell}) \, . $$

To prove this formula, let us multiply the matrices $$ \left( \begin{array}{cccc} 1/W^{\prime} (x_1) & 1/W^{\prime} (x_2) & 1/W^{\prime} (x_3) & 1/W^{\prime} (x_4) \\ x_1/W^{\prime} (x_1) & x_2/W^{\prime} (x_2) & x_3/W^{\prime} (x_3) & x_4/W^{\prime} (x_4) \\ x_1^2/W^{\prime} (x_1) & x_2^2/W^{\prime} (x_2) & x_3^2/W^{\prime} (x_3) & x_4^2/W^{\prime} (x_4) \\ x_1^3/W^{\prime} (x_1) & x_2^3/W^{\prime} (x_2) & x_3^3/W^{\prime} (x_3) & x_4^3/W^{\prime} (x_4) \end{array} \right) \left( \begin{array}{cccc} x_1^{1} & x_1^{2} & x_1^4 & x_1^{6} \\ x_2^{1} & x_2^{2} & x_2^4 & x_2^{6} \\ x_3^{1} & x_3^{2} & x_3^4 & x_3^{6} \\ x_4^{1} & x_4^{2} & x_4^4 & x_4^{6} \end{array} \right) $$ and the Euler-Lagrange equalities lead to $$ = \left( \begin{array}{cccc} \sigma_{-2} & \sigma_{-1} & \sigma_1 & \sigma_3 \\ \sigma_{-1} & \sigma_0 & \sigma_2 & \sigma_4 \\ \sigma_0 & \sigma_1 & \sigma_3 & \sigma_5 \\ \sigma_1 & \sigma_2 & \sigma_4 & \sigma_6 \end{array} \right)= \left( \begin{array}{cccc} 0 & 0 & \sigma_1 & \sigma_3 \\ 0 & 1 & \sigma_2 & \sigma_4 \\ 1 & \sigma_1 & \sigma_3 & \sigma_5 \\ \sigma_1 & \sigma_2 & \sigma_4 & \sigma_6 \end{array} \right) \, . $$ Turn to determinants in this equality: $$ \left| \begin{array}{cccc} 1/W^{\prime} (x_1) & 1/W^{\prime} (x_2) & 1/W^{\prime} (x_3) & 1/W^{\prime} (x_4) \\ x_1/W^{\prime} (x_1) & x_2/W^{\prime} (x_2) & x_3/W^{\prime} (x_3) & x_4/W^{\prime} (x_4) \\ x_1^2/W^{\prime} (x_1) & x_2^2/W^{\prime} (x_2) & x_3^2/W^{\prime} (x_3) & x_4^2/W^{\prime} (x_4) \\ x_1^3/W^{\prime} (x_1) & x_2^3/W^{\prime} (x_2) & x_3^3/W^{\prime} (x_3) & x_4^3/W^{\prime} (x_4) \end{array} \right|= $$ $$ =\frac{1}{\prod_{j=1}^4 W^{\prime} (x_j)} \left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ x_1 & x_2 & x_3 & x_4 \\ x_1^2 & x_2^2 & x_3^2 & x_4^2 \\ x_1^3 & x_2^3 & x_3^3 & x_4^3 \end{array} \right|= $$ $$ =\frac{\displaystyle \prod_{1\le \ell <j \le m} (x_j-x_{\ell})}{\displaystyle \prod_{1\le \ell <j \le m} (x_j-x_{\ell})^2}=\frac{1}{\displaystyle \prod_{1\le \ell <j \le m} (x_j-x_{\ell})} \, . $$ ♦

For some particular cases, the non-singularity of the generalized Vandermonde's matrix can be guaranteed.

Theorem 5 [5]. If $ 0 \le n_1< n_2 < \dots < n_m $ and $ 0 < x_1< \dots < x_m $, then

$$ \widehat V > 0 \, .$$

☞ HERE

[1].Knuth D. The Art of Computer Programming. V.1,Addison-Wesley, 2023.

[2]. Marov A.V., Uteshev A.Yu. Matrix formalism of the Reed-Solomon codes. Vestnik of Saint Petersburg University. Series 10, 2016, issue 4, pp. 4–17. (in Russian)

[3]. Encyklopädie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen. Bd. I. Arithmetik und Algebra. Editor: Meyer W.F. 1898-1904. Leipzig, Teubner

[4]. Proskuryakov I.V. Problems in Linear Algebra. Mir, Moscow, 1978

[5]. Pólya G. , Szegö G.Problems and Theorems in Analysis. V.2. Springer. 1998