A study is made of the numerical condition of the coordinate map associating to each polynomial its coefficients with respect to a given basis of polynomials. This problem depends on the choice of norms for the sets of polynomials of a given maximal degree, and the corresponding sets of coefficients. In the present work we discuss three different choices of norms for the sets of polynomials, and equip the set of coefficients with a suitable Hölder vector norm.

In the first part we choose for the sets of polynomials the supremum norm with respect to some compact set in the complex plane. Relations to Zolotarov--type and Markov--type extremal problems for polynomials in the complex plane are used to derive approximately tight estimates for various coordinate maps, including the bases of Faber polynomials and Newton polynomials. In particular, we discuss the numerical condition of the basis of monomials on intervals and ellipses, generalizing previous work of Gautschi.

The second part deals with sequences of orthogonal polynomials, where the sets of polynomials are equipped with an $L_2$--norm induced by some other scalar product. Here, equivalently, one has to study the condition number of (modified) moment matrices such as positive definite Toeplitz or Hankel matrices. We propose a lower bound for the condition number in terms of the supports of the underlying measures. Furthermore, asymptotics are given for a particular class of modified moment matrices.

The aim of the third part is to derive approximately tight lower bounds for the condition number of special structured matrices, such like Vandermonde-like, Krylov and Hankel matrices. Here the link to coordinate maps is obtained by taking for the sets of polynomials the supremum norm with respect to some discrete set. In particular, we give lower bounds for the $p$-condition number of a real Vandermonde matrix of order $n$ growing exponentially in $n$. These bounds are shown to be attained up to a factor $n^2$. In addition, we determine explicitly the optimal node configuration which minimizes the $1$-condition number.

Krylov matrices consist of colums $B^j\cdot b$, $j=0,1,..,n$, where $B$ is a normal matrix of size $m>n$ with eigenvalues being located in some real or complex set $G$. It is shown that, for estimating the Euclidean condition number, it is sufficient to discuss the case of diagonal $B$, and in this case a Krylov matrix becomes a rowscaled Vandermonde matrix. We provide an explicit expression for the $n$th root limit of the optimal bound for the condition number of such Krylov matrices. In the case of real $G$, lower bounds in terms of $n,G$ are given which again are shown to be approximately tight, improving results obtained recently by Tyrtyshnikov.

As an application, we discuss the condition number of positive definite Hankel matrices, including for example moment matrices such as the famous Hilbert matrix.