Walks on directed graphs and matrix polynomials

We give a matrix generalization of the family of exponential polynomials in one variable phi(k)(x). Our generalization consists of a matrix of polynom ials Phi(k)(X) = (Phi(i, j)((k))(X))(i, j = 1)(n) depending on a matrix of variables X = (x(i, j))(i, j = 1)(n). We prove some identities of the matri x exponential polynomials which generalize classical identities of the ordi nary exponential polynomials. We also introduce matrix generalizations of t he decreasing factorial (x)(k) = x(x - 1)(x - 2) ... (x - k + 1), the incre asing factorial (x)((k)) = x(x + 1)(x + 2) ... (x + k - 1), and the Laguerr e polynomials. These polynomials have interesting combinatorial interpretat ions in terms of different kinds of walks on directed graphs. (C) 2000 Acad emic Press.