The combinatorial power of the companion matrix. (English) Zbl 0838.15015

The explicit polynomials for all elements in an arbitrary power of the companion matrix depending on \(n\) variables are obtained using combinatorial methods. Several applications are discussed as well as the relationship with Waring’s formula on symmetric functions, the general solution to homogeneous linear recurrence relations, the multiplicative inverse of formal power series, the generating function of compositions (of numbers), a unified approach to Chebyshev polynomials, Dickson polynomials of various kinds arising from the theory of finite fields and combinatorial expansions of Toeplitz matrices.
Reviewer: G.Bonanno (Davis)


15B57 Hermitian, skew-Hermitian, and related matrices
Full Text: DOI


[1] Beerends, R. J., Chebyshev polynomials in several variables and the radical part of the Laplace-Beltrami operator, Trans. Amer. Math. Soc., 328, 779-814 (1991) · Zbl 0739.22008
[2] Bonetti, F.; Rota, G.-C.; Senato, D.; Venezia, A. M., On the foundation of combinatorial theory, X, A categorical setting for symmetric functions, Stud. Appl. Math., 86, 1-29 (1992) · Zbl 0748.05093
[3] Brualdi, R. A.; Ryser, H. J., Combinatorial Matrix Theory, (Rota, G.-C., Encyclopedia Math. Appl., 39 (1991), Cambridge U.P.) · Zbl 0405.05014
[5] Chen, W. Y.C., Context-free grammars, differential operators and formal power series, Theoret. Comput. Sci., 117, 113-129 (1993) · Zbl 0788.68082
[6] Chen, W. Y.C.; Lih, K. W.; Yeh, Y. N., Cyclic tableaux and symmetric functions, Stud. Appl. Math., 94, 327-333 (1995) · Zbl 0824.05061
[7] Coddington, E. A.; Levinson, N., Theory of Ordinary Differential Equations (1955), McGraw-Hill: McGraw-Hill New York · Zbl 0042.32602
[8] Comtet, L., Advanced Combinatorics (1974), Reidel: Reidel Dordrecht
[9] Doubilet, P., On the foundations of combinatorial theory VII: Symmetric functions through the theory of distribution and occupancy, Stud. Appl. Math., 51, 377-396 (1972) · Zbl 0274.05008
[10] Friedman, B., Principles and Techniques of Applied Mathematics (1956), Wiley: Wiley New York · Zbl 0072.12806
[11] Fromme, J. A.; Goldberg, M. A., Equations arising in two-dimensional aerodynamics, (Goldberg, M. A., Solution Methods for integral Equations (1979), Plenum: Plenum New York) · Zbl 0434.65102
[12] Gao, S.; Lenstra, H. W., Optimal normal bases, Des. Codes Cryptogr., 2, 315-323 (1992) · Zbl 0770.11055
[14] Gautschi, W., On mean convergence of extended Lagrange interpolation, J. Comput. Appl. Math., 43, 19-35 (1992) · Zbl 0761.41003
[15] Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), Wiley: Wiley New York · Zbl 0519.05001
[17] Lancaster, P.; Tismenesky, M., The Theory of Matrices (1985), Academic
[18] Lidl, R.; Mullen, G. L.; Turnwald, G., Dickson Polynomials, (Pitman Monographs Surveys Pure Appl. Math., 65 (1993), Longman Scientific and Technical: Longman Scientific and Technical Essex, England) · Zbl 0823.11070
[19] Lidl, R.; Niederreiter, H., Introduction to Finite Fields and Their Applications (1986), Cambridge U.P. · Zbl 0629.12016
[20] Louck, J. D., Exact normal modes of oscillation of a linear chain of identical particles, Amer. J. Phys., 30, 8, 585-5900 (1962) · Zbl 0129.43805
[21] Louck, J. D., Trace formulas for a rigid asymmetric rotator-type Hamiltonian, J. Molecular Spectroscopy, 10, 263-277 (1963)
[22] Macdonald, I. G., Symmetric Functions and Hall Polynomials (1979), Oxford U.P.,: Oxford U.P., Oxford · Zbl 0487.20007
[23] Mason, J. C., Chebyshev polynomials of the second, third and fourth kinds in approximation, indefinite integration, and integral transforms, J. Comput. Appl. Math., 49, 169-178 (1993) · Zbl 0793.33010
[24] Mason, J. C.; Elliott, G. H., Near-minimax complex approximation by four kinds of Chebyshev polynomial expansion, J. Comput. Appl. Math., 46, 291-300 (1993) · Zbl 0782.30031
[25] Mason, J. C.; Elliott, G. H., Constrained near-minimax approximation by weighted expansion and interpolation using Chebyshev polynomials of the second, third and fourth kinds, (Zwick, D.; Zalik, R., Algorithms for Constrained Approximation and Optimization, Proc. Workshop Univ. Vermont (1993)) · Zbl 0828.65057
[26] Mullin, R. C.; Onyszchuk, I.; Vanstone, S. A.; Wilson, R. M., Optimal normal bases in \(GF (p^n )\), Discrete Applied Math., 22, 149-161 (1988-1989) · Zbl 0661.12007
[27] Rota, G.-C., Baxter algebras and combinatorial identities, parts II, Bull. Amer. Math. Soc., 75, 330-334 (1969) · Zbl 0319.05008
[28] Rybowicz, M., Search of primitive polynomials over finite fields, J. Pure and Appl. Algebra, 65, 139-151 (1990) · Zbl 0713.11085
[29] Schmitt, W. R., Antipodes and incidence coalgebras, J. Combin. Theory Ser. A, 46, 264-290 (1987) · Zbl 0699.05003
[30] Stanley, R. P., (Enumerative Combinatorics, Vol. I (1986), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole Monterey, Calif.) · Zbl 0608.05001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.