×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andrews, G.E., The theory of partitions, (1998), Cambridge University Press Cambridge · Zbl 0906.05004
[2] Björck, A.; Pereyra, V., Solution of Vandermonde systems of equations, Math. comp., 24, 893-903, (1970) · Zbl 0221.65054
[3] Cheon, G.S.; Kim, J.S., Stirling matrix via Pascal matrix, Linear algebra appl., 329, 49-59, (2001) · Zbl 0988.05009
[4] Eisinberg, A.; Franzé, G.; Pugliese, P., Vandermonde matrices on integer nodes, Numer. math., 80, 75-85, (1998) · Zbl 0913.65022
[5] Eisinberg, A.; Pugliese, P.; Salerno, N., Vandermonde matrix on integer nodesthe rectangular case, Numer. math., 87, 663-674, (2001) · Zbl 0974.65029
[6] Gohberg, I.; Koltracht, I., Triangular factors of Cauchy and Vandermonde matrices, Integral equations oper. theory, 26, 46-59, (1996) · Zbl 0858.15006
[7] 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
[8] Goodman, T.N.T., Total positivity and shape of curves, (), 157-186 · Zbl 0894.68159
[9] 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
[10] 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
[11] D.E. Knuth, The Art of Computer Programming, Vol. 1, Addison-Wesley, Reading, MA, 1973. · Zbl 0302.68010
[12] Konvalin, J., Generalized-binomial coefficients and the subset-subspace problem, Adv. appl. math., 21, 228-240, (1998)
[13] MacDonald, I.G., Symmetric functions and Hall polynomials, (1979), Clarendon Press Oxford · Zbl 0487.20007
[14] Martı́nez, J.J.; Peña, J.M., Factorization of cauchy – vandermonde matrices, Linear algebra appl., 284, 229-237, (1998) · Zbl 0935.65017
[15] 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
[16] H. Oruç, The generalized Bernstein polynomials and total positivity, Ph.D. Thesis, University of St. Andrews, 1998; http://web.deu.edu.tr/halil.oruc/.
[17] Oruç, H.; Phillips, G.M., Explicit factorization of the Vandermonde matrix, Linear algebra appl., 315, 113-123, (2000) · Zbl 0959.15011
[18] Oruç, H.; Phillips, G.M., q-Bernstein polynomials and Bézier curves, J. comput. appl. math., 151, 1-12, (2003) · Zbl 1014.65015
[19] Oruç, H.; Tuncer, N., On the convergence and iterates of q-Bernstein polynomials, J. approx. theory, 117, 301-313, (2002) · Zbl 1015.33012
[20] Phillips, G.M., Two millenia of mathematics from archimedes to Gauss, (2000), Springer New York
[21] Phillips, G.M., Interpolation and approximation by polynomials, (2003), Springer New York · Zbl 1023.41002
[22] Schumaker, L.L., Spline functions: basic theory, (1981), Wiley · Zbl 0449.41004
[23] R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, MA, 1999. · Zbl 0928.05001
[24] 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.