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?
Some observation:
Unfortunately matrix inversion is $S_+$ - convex 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: Here is a counterexample for $n \geq 3$. It is enough to show that $f$ is not convex along a rank-1 direction.
Let $x \in \mathbb{R}^n$ with $\lVert x \rVert = 1$ and consider the function $$g(t) = \lVert (I + t xx^T)^{-1} \rVert_1 \,, t \geq 0 \,.$$
By the matrix inversion lemma,
$$
(I + t xx^T)^{-1} = I - \frac{t}{1 + t} xx^T \,.
$$
Note that the diagonals of the above matrix are non-negative.
Then
$$
g(t) 
= n + \alpha \frac{t}{1 + t} \,,
$$
where
$$
\alpha 
= -1 + \sum_{i \neq j} \lvert x_i \rvert \lvert x_j \rvert
= -2 + \sum_{ij} \lvert x_i \rvert \lvert x_j \rvert
= \lvert x \rvert_1^2 - 2
\,.
$$
We can choose $x$ so that $\lvert x \rvert_1^2 = n$ and $n > 2$ by assumption.
Such a choice yields $g$ that is not convex.
A: I'm going to share the work I did on this problem---even though I didn't get a positive result. Perhaps you can work with it.
We can write your problem as follows:
$$f(A) = \inf \{ \|B\|_1 \,|\, B=A^{-1} \}$$
Now consider the following modified function:
$$\tilde{f}(A) = \inf \{ \|B\|_1 \,|\, B\succeq A^{-1} \} = \inf\{ \|B\|_1 \,|\, B - A^{-1} \in \mathcal{S}^n_+ \}$$
This function is convex. Here's the proof. First, define the following extended-valued function:
$$g(A,B) = \begin{cases} \|B\|_1 & A \succ 0, ~ B \succeq A^{-1} \\ +\infty & \text{otherwise} \end{cases}$$
If $g(A,B)$ is convex, then so must be $\tilde{f}$, since partial minimizations of convex functions are convex, and $\tilde{f}(A) = \inf_B g(A,B).$ Clearly, $g$ is convex at points in its domain---but we do not know if the domain is convex, yet:
$$\mathop{\textrm{dom}}(g) = \{ (A,B)\in\mathcal{S}^n\times\mathcal{S}^n \,|\, A \succ 0, ~ B \succeq A^{-1} \}
= \left\{ (A,B)\in\mathcal{S}^n\times\mathcal{S}^n \,\middle|\, A \succ 0, ~ \begin{bmatrix} B & I \\ I & A \end{bmatrix} \succeq 0 \right\}.$$
This is a convex set, being the intersection of some linear matrix inequalities on $(A,B)$. Therefore, $g$ is convex, and so is $\tilde{f}$.
Now: is $f\equiv \tilde{f}$? It is true for other convex functions on $B$, such as the trace and the determinant: and indeed, both $\mathop{\textrm{Tr}}(A^{-1})$ and $\mathop{\textrm{det}}(A^{-1})$ are convex. But is it true for $\|A^{-1}\|_1$? Before I tried to prove this, I wrote some MATLAB code using CVX, a toolbox I wrote for convex optimization. Here's the code:
function test_norm1inv( A )
n = size(A,1);
cvx_begin quiet
    variable B(n,n) symmetric
    minimize(sum(sum(abs(B))));
    [B,eye(n);eye(n),A] == semidefinite(2*n)
cvx_end
fprintf( 'CVX result: %g\n', cvx_optval )
fprintf( 'Analytic result: %g\n', sum(sum(abs(inv(A)))) );

Here's some example output:
>> A = randn(10,10); test_norm1inv( A*A' )
CVX result: 44998.8
Analytic result: 45000.3
>> A = randn(10,10); test_norm1inv( A*A' )
CVX result: 686.876
Analytic result: 686.889
>> A = randn(10,10); test_norm1inv( A*A' )
CVX result: 87.0088
Analytic result: 99.938
>> A = randn(10,10); test_norm1inv( A*A' )
CVX result: 82.3252
Analytic result: 96.8455

BZZT. I'm glad I didn't spend any time trying to prove the positive---it is clear that $\tilde{f}\not\equiv f$. I've manually confirmed that the matrix $B$ produced by CVX does indeed satisfy $B\succeq A^{-1}$, and that $\|B\|_1<\|A^{-1}\|_1$. Indeed, the values of $B$ produced by this approach look quite different from $A^{-1}$.
Now I have to say that this shakes any confidence I might have had that your original function, $f$, is convex. That said, I also wrote some simple code to perform convexity tests on pairs of randomly generated PSD matrices, and it failed to find a counterexample. If I think of anything more, I will edit my answer.
