Necessary and sufficient conditions are formulated for checking robust stability of an uncertain polynomial matrix. Various stability regions and uncertainty models are handled in a unified way. The conditions, stemming from a general optimization methodology similar to the one used in $\mu$-analysis, are expressed as a rank-one LMI, a non-convex problem frequently arising in robust control. Convex relaxations of the problem yield tractable sufficient LMI conditions for robust stability of uncertain polynomial matrices.