Symmetric functions and the Vandermonde matrix (Q1883472): Difference between revisions

The authors discuss symmetric functions and related combinatorial numbers and their recurrences and relate this to the factorization of structured matrices, such as Vandermonde matrices. First definitions and properties are recalled for symmetric functions, defined as \[ \sigma_r(x_1,\ldots,x_n) = \sum_{1\leq i_1<\cdots<i_r\leq n} x_{i_1}\cdots x_{i_r}~~\text{and}~~ \tau_r(x_1,\ldots,x_n) = \sum_{\lambda_1+\cdots+\lambda_n=r} x_1^{\lambda_1}\cdots x_n^{\lambda_n}; \] the related Stirling numbers and \(q\)-Stirling numbers of the first and second kind are essentially obtained from these when \(x_i=i\), respectively \(x_i=q^{i-1}\) in \(\sigma_r\) and \(\tau_r\). Then it is shown how the symmetric functions appear in the expressions for the elements in the LDU factorization of a Vandermonde matrix and its inverse. Similarly, Stirling and \(q\)-Stirling numbers appear in factorizations of the corresponding Pascal and Stirling matrices. The properties of the symmetric functions are finally used to give a constructive proof for the fact that the \(L\) and the \(U\)-factors for the inverse of a Vandermonde matrix of size \(n+1\) can be written as the product of \(n\) bidiagonal matrices. This gives an \(O(n^2)\) algorithm for the solution of a Vandermonde system.