Question first asked on math.stackexchange here: <https://math.stackexchange.com/questions/317209/on-the-convexity-of-element-wise-norm-1-of-the-inverse>


**On the convexity of element-wise norm 1 of the inverse**


Let us define $\|A\|\_1$ the element wise norm 1 of a matrix $A \in \mathbb{R}^{n \times m}$ as $$\|A\|\_1=\sum\_{i,j} |A\_{i,j}| $$


Obviously, this function is convex over $\mathbb{R}^{n \times m}$. Is it true that the function $f:S^n\_{++} \longrightarrow \mathbb{R}$, defined as $f(A) = \|A^{-1}\|\_1$, is convex? Here we denote with $S^n \supset S^n\_+ \supset S^n\_{++}$ respectively the set of Symmetric, Positive Semidefinite (PSD) and Positive Definite (PD) $n \times n$ matrices.


**Some observations:**


Unfortunately matrix inversion is convex with respect to $S\_+$, while $\|.\|\_1$ is non decreasing with respect to the cone $R^{n \times m}\_+$ and not with respect to $S\_+$ (it is easy to find counterexamples). Hence theorems on combination of convex functions are not applicable.


I have tried to formulate function $f$ as $max\{ \ trace(M\_i A^{-1}) \ \}\_{i\in\mathcal{I}}$ where the $M\_i\in S^n$ live in a family of matrices with elements equal to 1 or -1 so as to cover all the possible combinations of signed sums of elements of $A^{-1}$ but unfortunately not all such $M\_i$ are PSD and therefore not all $trace(M\_i A^{-1})$ are convex in $A$. Therefore I was not able to define $f$ as the pointwise max of convex functions.


I have also tried to consider
$$
\|A^{-1}\|\_1= \sum\_{i,j}=\frac{|\det A\_{\hat{\imath}\hat{\jmath}}|}{detA}
$$
where $\det A\_{\hat{\imath}\hat{\jmath}}$ is the minor associated to the $n-1 \times n-1$ sub-matrix obtained by eliminating row $i$ and column $j$ from $A$. But I have no intuition on how to go further...


Any thought?



On the convexity of element-wise norm 1 of the inverse
The answer is *Yes* when $n=2$,but **No** when $n\ge3$. Here is the analysis.


The differential $L\_A$ of $A\mapsto A^{-1}$ is $L\_A=-A^{-1}BA^{-1}$. Likewise, the Hessian is
$$H\_A[B]=2A^{-1}BA^{-1}BA^{-1}=\frac2{(\det A)^3}\hat A B\hat AB\hat A,$$
where $\hat A$ is the adjugate matrix (mind that $A$ being symmetric, $(\det A)A^{-1}=\hat A$). Finally, the Hessian of the norm of $A^{-1}$ is
$$\phi\_A[B]=\frac2{(\det A)^3}\sum\_{i,j}{\rm sgn}(\hat a\_{ij})(\hat A B\hat AB\hat A)\_{ij}.$$
For the function to be convex over $S\_n^{++}$, it is therefore necessary and sufficient (the singular part of the Hessian, located at matrices such that some entry of $A^{-1}$ vanishes, is positive) to have, for every $S\in S\_n^{++}$ and $B\in Sym\_n$
$$\sum\_{i,j}{\rm sgn}(s\_{ij})(SBSBS)\_{ij}\ge0.$$


When $B$ runs over $Sym\_n$, $S^{1/2}BS^{1/2}$ covers $Sym\_n$, and its square covers $S\_n^+$. Thus $SBSBS$ runs over $S\_n^+$. We infer that the convexity is equivalent to the property that for every $S\in S\_n^{++}$ and $K\in S\_n^+$, there holds
$$\sum\_{i,j}\epsilon\_{ij}k\_{ij}\ge0,$$
where $\epsilon(S):=(({\rm sgn}(s\_{ij}))\_{i,j}$.
This amounts to saying that the matrix $\epsilon(S)$ is positive semi-definite.


This inequality turns out to be true if $n=2$, because
$$\epsilon(S)=\begin{pmatrix} 1 & \pm1 \\\\ \pm1 & 1 \end{pmatrix}.$$
But this is false if $n\ge3$. Take for instance a matrix $A$ such that $S$, thus $(\det A)A^{-1}$, be a small disturbance of $I\_3$, with negative off-diagonal entries. Then
$$\epsilon(S)=\begin{pmatrix} 1 & -1 & -1 \\\\ -1 & 1 & -1 \\\\ -1 & -1 & 1 \end{pmatrix}$$
is indefinite.


