Relaxing LMI domination matricially

Given linear matrix inequalities (LMIs) L₁ and L₂ in the same number of variables it is natural to ask: (Q₁) 1) does one dominate the other, that is, does L₁(X) ≥ 0 imply L₂(X) ≥ 0? 2) are they mutually dominant, that is, do they have the same solution set? Such problems can be NP-hard. We describe a natural relaxation of an LMI, based on substituting matrices for the variables x_j. With this relaxation, the domination questions (Q₁) and (Q₂) have elegant answers, indeed reduce to semidefinite programs (SDP) which we show how to construct. For our “matrix variable” relaxation a positive answer to (Q₁) is equivalent to the existence of matrices V_j such that L₂(x) = V₁*L₁(x)V₁ + ⋯ + V_μ*L₁(x)V_μ. (A₁) As for (Q₂) we show that L₁ and L₂ are mutually dominant if and only if, up to certain redundancies described in the paper, L₁ and L₂ are unitarily equivalent. An observation at the core of the paper is that the relaxed LMI domination problem is equivalent to a classical problem. Namely, the problem of determining if a linear map τ from a subspace of matrices to a matrix algebra is “completely positive”.