Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$).

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.