The problem addressed in this paper is the construction of homogeneous polynomial Lyapunov functions (HPLFs) for linear systems with time-varying structured uncertainties. A sufficient condition for the existence of an HPLF of given degree is formulated in terms of a linear matrix inequalities (LMI) feasibility problem. This condition turns out to be also necessary in some cases depending on the dimension of the system and the degree of the Lyapunov function. The maximum l(infinity) norm of the parametric uncertainty for which there exists a homogeneous polynomial Lyapunov function is computed by solving a generalized eigenvalue problem. The construction of such Lyapunov functions is efficiently performed by means of popular convex optimization tools for the solution of problems in LMI form. Comparisons with other classes of Lyapunov functions through numerical examples taken from the literature show that HPLFs are a powerful tool for robustness analysis. (C) 2003 Published by Elsevier Science Ltd.