# Characterizing invertible nonnegative matrices with bounded sums

Almost a year ago, I asked in this question about obtaining a tight bound on the sum of the entries of the inverse of a strictly positive definite matrix. Denis Serre gave a nice counterexample showing that there does not exist such a bound.

I am actually more interested in the following (presumably much harder) question:

Characterize the class of $n \times n$, elementwise nonnegative, semidefinite matrices with entries in $[0,1]$, whose pseudoinverse satisfies $e^TA^{\dagger}e \le n$?

Here $A^\dagger$ denotes the Moore-Penrose pseudoinverse and $e$ denotes the vector of all ones.

In particular, I am seeking equivalent conditions so that given an $A$, one can decide whether it belongs to the said class or not. For example, $A=I_n$ belongs to this class, as do the matrices described in this question (with $\alpha=1/n$).

The following partial answer applies to matrices $A \ \in \ M^{n \times n}$ of the question, if $A$ is also symmetric (semidefinite in the narrow sense), but the principles will be useful to understand the general case, I suppose.

The first version contained a stupid mistake, which I corrected after I found my first solution to be inconsistent with the solution to the second problem linked to in the question.

As our matrix $A$ in question is symmetric, it can be written as

$$A \ = \ \lambda_1 v_1v_1^T + \lambda_2 v_2v_2^T + \ldots + \lambda_k v_kv_k^T \, ,$$

where the $\lambda_i$ are its non-vanishing singular values and eigenvalues in this special case $(k \ \leq \ n)$, which we have arranged in decreasing order, so $\lambda_1$ is a Perron root of $A$, and the $v_i$ are corresponding orthonormal eigenvectors. We allow a multiple Perron root, hence there is no irreducibility assumption. We can take $v_1$ to have non-negative entries though, which we shall do.

The Moore-Penrose inverse is then given as

$$A^\dagger \ = \ \frac{1}{\lambda_1} v_1v_1^T + \frac{1}{\lambda_2} v_2v_2^T + \ldots + \frac{1}{\lambda_k} v_kv_k^T \, .$$

The key observation following an elementary and simple computation is

$$e^T(xx^T)e \ = \ (c_x)^2 \, ,$$

where $x$ is an arbitrary column vector and $c_x$ is its component sum, so the result is non-negative, if $x$ contains real numbers as entries.

As the entries of $v_1$ are non-negative and $v_1$ has unit length, its component sum is at least $1$ and at most $\sqrt{n}$, which occurs if and only if all components are equal. But as the $v_i$ form an orthonormal system, all other $v_i$ must have vanishing component sums in this case, as they are orthogonal to $e$ in particular. Therefore we have

$$e^T A^\dagger e \ = \ \frac{n}{\lambda_1}$$

in this case, while we have

$$e^T A^\dagger e \ = \ \sum_{i=1}^k \frac{(c_{v_i})^2}{\lambda_i}$$

and therefore

$$\frac{1}{\lambda_1} \ \leq \ e^T A^\dagger e \ \leq n \sum_{i=1}^k \frac{1}{\lambda_i}$$

in general.

In particular, we have $$e^T A^\dagger e \ = \ n$$ if $A$ is doubly stochastic.