On the convexity of element-wise norm 1 of the inverse 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?
 A: 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.
A: The function that you have is convex for unitarily invariant norms, but for the (basis dependent) elementwise absolute value, it can clearly break as a trivial counterexample below shows.
\begin{equation*}
 X = \begin{pmatrix}
 2 & 0 & 0\\\\
 0 & 1 & 0\\\\
 0 & 0 & 1
\end{pmatrix},\qquad Y = \begin{pmatrix}
 10  &    9 &    5\\\\
     9 &   10 &    5\\\\
     5 &    5 &    4
\end{pmatrix}
\end{equation*}
Now, simply define $Z = 0.5(X+Y)$, and consider $g(H)=\|H^{-1}\|_1$ as your function. 
Then, we see that $g(Z) = 3.1692$, while $0.5(g(X)+g(Y)) = 3$, clearly violating convexity.
