The gap between the complex structured singular value of a complex matrix M and its convex upper bound is considered. New necessary and sufficient conditions for the existence of the gap are derived. It is shown that determining whether there exists such a gap is as difficult as evaluating a structured singular value of a reduced rank matrix (whose rank is equal to the multiplicity of the largest singular value of M). Furthermore, if an upper bound on this reduced rank problem can be obtained, it is shown that this provides an upper bound on the original problem that is lower than the convex relaxation upper bound. An example that illustrates our procedure is given. We also give the solution of several structured-approximation problems of independent interest.