35
$\begingroup$

This is mostly a reference request, as this must be well-known!

Let $A$ and $B$ be two real symmetric matrices, one of which is positive definite. Then it is easy to see that the product $AB$ (or $BA$, which has the same eigenvalues) is similar to a symmetric matrix, so has real eigenvalues. Take the vectors of eigenvalues of $A$ and of $B$, sorted in decreasing order, and let their componentwise product be $ab$. What is known about the relationship (e.g., inequalities) between $ab$ and the vector of eigenvalues of the product $AB$ (also taken in decreasing order)?

Some experimentation gives the conjecture that there is a majorization order between them, for instance. This must be well-known!

$\endgroup$
2
  • 2
    $\begingroup$ Not exactly what you're asking for, but I assume you're familiar with von Neumann's trace inequality, Richter's corresponding lower bound and L. Mirsky's elementary proofs of these. $\endgroup$
    – cardinal
    Sep 2, 2012 at 19:01
  • 1
    $\begingroup$ Somewhat related: math.stackexchange.com/a/47830/7003 $\endgroup$
    – cardinal
    Sep 2, 2012 at 19:03

2 Answers 2

37
$\begingroup$

Here are the results that you are probably looking for.

The first one is for positive definite matrices only (the theorem cited below fixes a typo in the original, in that the correct version uses $\prec_w$ instead of $\prec$).

Theorem (Prob.III.6.14; Matrix Analysis, Bhatia 1997). Let $A$ and $B$ be Hermitian positive definite. Let $\lambda^\downarrow(X)$ denote the vector of eigenvalues of $X$ in decreasing order; define $\lambda^\uparrow(X)$ likewise. Then, \begin{equation*} \lambda^\downarrow(A) \cdot \lambda^\uparrow(B) \prec_w \lambda(AB) \prec_w \lambda^\downarrow(A) \cdot \lambda^\downarrow(B), \end{equation*}

where $x \cdot y := (x_1y_1,\ldots ,x_ny_n)$ for $x,y \in \mathbb{R}^n$ and $\prec_w$ is the weak majorization preorder.

However, when dealing with matrix products, it is more natural to consider singular values rather than eigenvalues.

Therefore, the relation that you might be looking for is the log-majorization \begin{equation*} \log \sigma^\downarrow(A) + \log\sigma^\uparrow(B) \prec \log\sigma(AB) \prec \log\sigma^\downarrow(A) + \log\sigma^\downarrow(B), \end{equation*} where $A$ and $B$ are arbitrary matrices, and $\sigma(\cdot)$ denotes the singular value map.

Reference

  1. R. Bhatia. Matrix Analysis. Springer, GTM 169. 1997.
$\endgroup$
5
  • $\begingroup$ What is $\lambda(AB)$? You only defined $\lambda^\uparrow$ and $\lambda^\downarrow$. $\endgroup$ Jan 2, 2015 at 10:53
  • $\begingroup$ @DavidE.Roberson $\lambda(AB)$ is the vector whose elements are the eigenvalues of $AB$. I edited the question and added the definitions of $\cdot$ and $\prec$ so that the inequality should be more clearer now. $\endgroup$
    – Tadashi
    Jan 9, 2015 at 2:37
  • $\begingroup$ @shamisen but eigenvalues in what order? $\endgroup$ Jan 9, 2015 at 7:22
  • 2
    $\begingroup$ @MichałMasny It does not matter what order because the majorization preorder does not depend on order. By the way, does anyone know a direct proof of the first result? In Bhatia's book it proves the second result which is stronger, but I would like to know if there is a somewhat easier direct proof of the first result. $\endgroup$ Jan 9, 2015 at 10:22
  • 1
    $\begingroup$ Can somebody please point out when does the equality hold true, in both the lower bound and upper bound part separately, in the "weak majorization preorder's" of theorem 1 above? $\endgroup$
    – seavoyage
    Mar 31, 2017 at 23:24
0
$\begingroup$

Let $A,B$ be $n \times n$ Hermitian matrices whose eigen values are non-negatives. Let $ \lambda_1(X) \geq \lambda_2(X) \geq \cdots \geq \lambda_n(X)$ denote ordered eigenvalues of $n \times n$ Hermitian matrix $X$.

Then, $\lambda_j(AB) \leq \lambda_i(A)\lambda_{j-i+1}(B),$ for any $i \leq j$.

Proof. Let $a_i,b_i$ and $c_i$ be the unitary eigenvectors of $A,B$ and $A+B$, respectively. Namely, $A a_i = \lambda_i(A)a_i$ and so on.

Let $V_a,V_b$ and $V_c$ are vector spaces spanned by the vectors $\{a_i,...,a_n\}$ and $\{b_{j-i+1},...,b_n\}$ and $\{c_1,...,c_j\}$, respectively. Then, $V_a \cap V_b \cap V_c \neq 0$. In fact, for arbitrary vector spaces $X,Y$, we can say $\dim (X \cap Y) = \dim(X)+\dim(X) -\dim(X+Y )$ and using this twice, it follows that

$\dim(V_a \cap V_b \cap V_c ) =\dim(V_a \cap( V_b \cap V_c) )$

$=\dim(V_a) + \dim( V_b \cap V_c) - \dim(V_a + ( V_b \cap V_c)) $

$=\dim(V_a) + \dim( V_b ) + \dim( V_c) - \dim( V_b +V_c) - \dim(V_a + ( V_b \cap V_c)) $

$\geq\dim(V_a) + \dim( V_b ) + \dim( V_c) - n -n $

$= (n-i+1) + (n-j+i-1)+1 + j - n -n$

$= 1,$

and thus there is a nonzero unit vector $x \in V_a \cap V_b \cap V_c.$

Because $x \in V_c$, we can write $x= \sum_{\nu =1}^j x^\nu c_\nu$ and then,

$<x,(AB)x>= < \sum_{\nu =1}^j x^\nu c_\nu , (AB) \sum_{\nu =1}^j x^\nu c_\nu >$

$ = < \sum_{\nu =1}^j x^\nu c_\nu , \sum_{\nu =1}^j x^\nu \lambda_\nu(AB)c_\nu >$

$ = \sum_{\nu =1}^j | x^\nu |^2 \lambda_\nu(AB)$

$ \geq \sum_{\nu =1}^j | x^\nu |^2 \lambda_j(AB)$

$ = \lambda_j(AB) \cdots \cdots \cdots (1).$

Similarly, because $x \in V_a$, we can write $x= \sum_{\nu =i}^n x^\nu a_\nu$ and then,

$<x,Ax>= < \sum_{\nu =i}^n x^\nu a_\nu , A\sum_{\nu =i}^n x^\nu a_\nu >$

$ = < \sum_{\nu =i}^n x^\nu a_\nu , A\sum_{\nu =i}^n x^\nu a_\nu >$

$ = \sum_{\nu =i}^n | x^\nu |^2 \lambda_\nu(A )$

$ \leq \sum_{\nu =i}^j | x^\nu |^2 \lambda_i(A )$

$ = \lambda_i(A ) \cdots \cdots \cdots (2).$

Similarly, $<x,Bx> \leq \lambda_{j-i+1}(B ) \cdots \cdots \cdots (3).$

Combining the inequalities (1),(2),(3) and Cauchy Schwartz inequality, we get

$\lambda_j(AB) \leq <x,(AB)x> \leq |<A^*x , Bx>| \leq |A^*x| \dot | Bx| \leq \lambda_i(A ) \lambda_{j-i+1}(B ). $

This completes the proof.

$\endgroup$
2
  • $\begingroup$ This can not possibly be true. Take two 2x2 diagonal matrices with eigenvalues (1,K) for large K. $\endgroup$
    – zotachidil
    Aug 2, 2022 at 14:04
  • $\begingroup$ I read the proof and I noticed that there is a typo in the statement. So, I replaced $\lambda_i(AB) \leq \lambda_i(A)\lambda_{j-i+1}(B)$ with $\lambda_j(AB) \leq \lambda_i(A)\lambda_{j-i+1}(B).$ If it is still incorrect, please let me know. $\endgroup$ Aug 5, 2022 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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