Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have real positive semidefinite matrices (symmetric) $A$ and $B$, both are $n \times n$.

I am looking for upper bounds and lower bounds on the $m$-th largest eigenvalue of $AB$, in terms of the eigenvalues of $A$ and $B$.

I know, for example, that the $det(AB)=det(A)det(B)$ and that the determinant of a square matrix equals the product of its eigenvalues, but that wouldn't give me what I am looking for, because I want to focus only on the top $m$ largest eigenvalues of $AB$.

share|improve this question
2  
Bounding the largest magnitude eigenvalue is easy: $\rho(AB) \le \|AB\| \le \|A\| \ \|B\| = \rho(A)\rho(B)$. –  p.s. Jul 24 '12 at 19:43
    
Are you sure you want to bound the eigenvalues of AB, rather than its singular values? The eigenvalues could even be complex. Most of the time, when people talk about "m largest ... of the matrix", the ellipsis is filled with "singular values". –  user31373 Jul 25 '12 at 14:43
    
@Leonid, the matrix structure is such that $AB = C'CD'D$. There is a theorem that says that the non-zero eigenvalues of this matrix is the same as that of $(CD')(DC')$. That's a symmetric matrix, and therefore must have positive eigenvalues. –  kloop Jul 25 '12 at 15:05
    
@kloop Agreed. Still, this means you are looking to estimate the singular values of $CD'$ in terms of the singular values of $C$ and $D$. Where $C$ and $D$ can be taken to be positive semidefinite as well (square roots of $A$ and $B$). –  user31373 Jul 25 '12 at 15:59
add comment

1 Answer 1

up vote 2 down vote accepted

Let the eigenvalues of $A$ be $a_1\ge a_2\ge \dots \ge a_n$, and the eigenvalues of $B$ be $b_1\ge b_2\ge \dots \ge b_n$. According to the discussion in comments, we are looking for bounds on the singular values of $AB$, denoted $s_1\ge s_2\ge \dots \ge s_n$. The min-max principle is the natural tool to use. Actually, the Wikipedia article does not state the form I'd like to use here: the $k$th largest singular value of $M$ is $\inf\{\|M-T\|:\mathrm{rank}\, T\le k-1\}$. This formula appears in another article with attribution to Allakhverdiev (and no reference). I think the result of Allakhverdiev was the extension to compact operators in Hilbert spaces, but don't know for sure. In general, Wikipedia articles on singular values are a toxic mess.

Claim 1: $s_k\le \min\{ a_i b_{j} : i+j=k+1\}$.

Proof: Let $T$ be an operator of rank $\le i-1$ such that $a_i=\|A-T\|$. Similarly, let $S$ be an operator of rank $\le j-1$ such that $b_{j}=\|B-S\|$. Since $\|(A-T)(B-S)\|\le a_i b_{j}$, it remains to estimate the rank of $(A-T)(B-S)-AB$. Writing $(A-T)(B-S)-AB=-T(B-S)-AS$, we see that the rank is at most $j-1+i-1=k-1$, as desired.

Claim 2: $s_k\ge \max\{ a_i b_{j} : i+j=k+n\}$.

If $A$ and $B$ are invertible, Claim 2 follows by applying Claim 1 to $(AB)^{-1}$. Indeed, the $k$th largest singular value of $AB$ is the reciprocal of the $(n+1-k)$th largest singular value of $(AB)^{-1}$. The $(n+1-k)$th largest singular value of $(AB)^{-1}$ does not exceed $\min \{a_{n+1-i}^{-1}b_{n+1-j}^{-1} : i+j=n+2-k\}$. Decoding these sums of indices, we get Claim 2. The general case follows by considering $A+\epsilon I$ and $B+\epsilon I$, and letting $\epsilon\to 0$.

share|improve this answer
add comment

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.