Matrix completions, norms and Hadamard products

Abstract:

Let ${M_{m,n}}$ (respectively, ${H_n}$) denote the space of $m \times n$ complex matrices (respectively, $n \times n$ Hermitian matrices). Let $S \subset {H_n}$ be a closed convex set. We obtain necessary and sufficient conditions for ${X_0} \in S$ to attain the maximum in the following concave maximization problem: \[ \max \{ {\lambda _{\min }}(A + X):X \in S\} \] where $A \in {H_n}$ is a fixed matrix. Let $\circ$ denote the Hadamard (entrywise) product, i.e., given matrices $A = [{a_{ij}}],\;B = [{b_{ij}}] \in {M_{m,n}}$ we define $A \circ B = [{a_{ij}}{b_{ij}}] \in {M_{m,n}}$. Using the necessary and sufficient conditions mentioned above we give elementary and unified proofs of the following results. (a) For any $A \in {M_{n,n}}$ \[ \omega (A) \equiv \max \{ |{x^{\ast }}Ax|:x \in {C^n},\;{x^{\ast }}x = 1\} \leqslant 1\] if and only if there is a matrix $Z \in {H_n}$ such that \[ \left ( {\begin {array}{*{20}{c}} {I + Z} & A \\ {{A^{\ast }}} & {I - Z} \\ \end {array} } \right ) \geqslant 0.\] (b) For any $A \in {M_{m,n}}$ \[ \max \{ ||A \circ B|{|_\infty }:||B|{|_\infty } \leqslant 1\} \leqslant 1\] if and only if there are matrices $P \in {H_m},\;Q \in {H_n}$ such that \[ \left ( {\begin {array}{*{20}{c}} P & A \\ {{A^{\ast }}} & Q \\ \end {array} } \right ) \geqslant 0,\qquad P \circ I \leqslant I,\qquad Q \circ I \leqslant I.\] (c) For any $A \in {M_{n,n}}$ \[ \max \{ \omega (A \circ B):\omega (B) \leqslant 1\} \leqslant 1\] if and only if there is a matrix $P \in {H_n}$ such that \[ \left ( {\begin {array}{*{20}{c}} P & A \\ {{A^{\ast }}} & P \\ \end {array} } \right ) \geqslant 0,\qquad P \circ I \leqslant I.\] We also consider other norms that can be represented in this way and show that if a norm can be represented in this way then so can its dual.