# zbMATH — the first resource for mathematics

Symmetric functions and the Vandermonde matrix. (English) Zbl 1063.15023
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.

##### MSC:
 15B57 Hermitian, skew-Hermitian, and related matrices 15A09 Theory of matrix inversion and generalized inverses 65F05 Direct numerical methods for linear systems and matrix inversion 11B75 Other combinatorial number theory 05A10 Factorials, binomial coefficients, combinatorial functions 05E05 Symmetric functions and generalizations
Full Text:
##### References:
  Andrews, G.E., The theory of partitions, (1998), Cambridge University Press Cambridge · Zbl 0906.05004  Björck, A.; Pereyra, V., Solution of Vandermonde systems of equations, Math. comp., 24, 893-903, (1970) · Zbl 0221.65054  Cheon, G.S.; Kim, J.S., Stirling matrix via Pascal matrix, Linear algebra appl., 329, 49-59, (2001) · Zbl 0988.05009  Eisinberg, A.; Franzé, G.; Pugliese, P., Vandermonde matrices on integer nodes, Numer. math., 80, 75-85, (1998) · Zbl 0913.65022  Eisinberg, A.; Pugliese, P.; Salerno, N., Vandermonde matrix on integer nodesthe rectangular case, Numer. math., 87, 663-674, (2001) · Zbl 0974.65029  Gohberg, I.; Koltracht, I., Triangular factors of Cauchy and Vandermonde matrices, Integral equations oper. theory, 26, 46-59, (1996) · Zbl 0858.15006  Gohberg, I.; Olshevsky, V., The fast generalized parker – traub algorithm for inversion of Vandermonde and related matrices, J. complexity, 13, 208-234, (1997) · Zbl 0883.65018  Goodman, T.N.T., Total positivity and shape of curves, (), 157-186 · Zbl 0894.68159  Goodman, T.N.T.; Oruç, H.; Phillips, G.M., Convexity and generalized Bernstein polynomials, Proc. edin. math. soci., 42, 179-190, (1999) · Zbl 0930.41010  Gould, H.W., The q-Stirling numbers of the first kind and the second kind, Duke math. J., 28, 281-289, (1961) · Zbl 0201.33601  D.E. Knuth, The Art of Computer Programming, Vol. 1, Addison-Wesley, Reading, MA, 1973. · Zbl 0302.68010  Konvalin, J., Generalized-binomial coefficients and the subset-subspace problem, Adv. appl. math., 21, 228-240, (1998)  MacDonald, I.G., Symmetric functions and Hall polynomials, (1979), Clarendon Press Oxford · Zbl 0487.20007  Martı́nez, J.J.; Peña, J.M., Factorization of cauchy – vandermonde matrices, Linear algebra appl., 284, 229-237, (1998) · Zbl 0935.65017  Martı́nez, J.J.; Peña, J.M., Fast algorithms of björck – pereyra type for solving cauchy – vandermonde linear systems, Appl. num. math., 26, 343-352, (1998) · Zbl 0898.65011  H. Oruç, The generalized Bernstein polynomials and total positivity, Ph.D. Thesis, University of St. Andrews, 1998; http://web.deu.edu.tr/halil.oruc/.  Oruç, H.; Phillips, G.M., Explicit factorization of the Vandermonde matrix, Linear algebra appl., 315, 113-123, (2000) · Zbl 0959.15011  Oruç, H.; Phillips, G.M., q-Bernstein polynomials and Bézier curves, J. comput. appl. math., 151, 1-12, (2003) · Zbl 1014.65015  Oruç, H.; Tuncer, N., On the convergence and iterates of q-Bernstein polynomials, J. approx. theory, 117, 301-313, (2002) · Zbl 1015.33012  Phillips, G.M., Two millenia of mathematics from archimedes to Gauss, (2000), Springer New York  Phillips, G.M., Interpolation and approximation by polynomials, (2003), Springer New York · Zbl 1023.41002  Schumaker, L.L., Spline functions: basic theory, (1981), Wiley · Zbl 0449.41004  R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, MA, 1999. · Zbl 0928.05001  Zhizheng, Z., The linear algebra of the generalized Pascal matrix, Linear algebra appl., 250, 51-60, (1997) · Zbl 0873.15014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.