6
$\begingroup$

Let $A = [A_{ij}]$ be an $n\times n$ square matrix with complex entries, and let $\sigma_k$, $k=1,\ldots, n$ be its singular values. Suppose that the squared Frobenius norm satisfies $ \mathrm{Tr}(A^\dagger A) = \sum_{i,j=1}^{n}|A_{ij}|^2 = \sum_{k=1}^n\sigma^2_k=1 \>, $ where $A^\dagger$ is the conjugate transpose of $A$.

Is the vector given by the absolute values squared of the entries, $(|A_{ij}|^2)_{ij}$, majorized by the vector $(\sigma_k^2)_k$? (As usual when discussing majorization, with proper padding of 0's, so that both vectors have $n^2$ elements.)

Consider vectors $(a_i)$ and $(b_i)$ of length $m$ such that $\sum_{i=1}^m a_i = \sum_{i=1}^m b_i$. Then, we say that $a$ majorizes $b$ if $\sum_{i=1}^k a_{(i)} \geq \sum_{i=1}^k b_{(i)}$ for each $1 \leq k \leq m$, where $a_{(i)}$ denotes the $i$th largest element of $(a_i)$ and likewise for $b_{(i)}$ with respect to $(b_i)$.

For a more detailed definition of majorization, please see http://en.wikipedia.org/wiki/Majorization .

I looked numerically for a counterexample, and found none. If it is true, I would suppose it is well-known, and in case I would appreciate a reference as precise as possible.

Thank you!

  • 0
    OK, I think I got the proof :) I will post it as soon as possible.2011-04-15

2 Answers 2

4

We will actually prove something stronger and then see that the desired result follows.

Let $A$ be defined as in the problem and take $\newcommand{\Atr}{A^{\dagger}}B = \Atr A$. Let $a_{ij}$ denote the $(i,j)$th element of $A$. Note that the diagonal elements of $B$, which we denote by $b_{ii}$ are real nonnegative numbers. We assume without loss of generality that $b_{ii} \geq b_{i+1,i+1} \geq 0$ for all $1 \leq i < n$.

Claim 1: The diagonal of $B$ majorizes $(|a_{ij}|^2)_{ij}$.

Let $s_k = \sum_{i=1}^k b_{ii}$ denote the sum of the $k$ largest $b_{ii}$. For each $i$, $b_{ii} = \sum_{j=1}^n |a_{ji}|^2$ is the sum of the squared moduli of the elements in the $i$th column of $A$. Consider the $k$ largest $|a_{ij}|^2$. Then, these $k$ elements lie within no more than $k$ unique columns of $A$ and, so, the sum of these $k$ elements is clearly less than or equal to the sum of the corresponding $b_{ii}$'s. But, this latter sum is definitely smaller than $s_k$. This holds for each $1 \leq k \leq n$ and so the claim is established since also $\sum_{i=1}^n b_{ii} = \sum_{i=1}^n \sum_{j=1}^n |a_{ij}|^2$.

Theorem (von Neumann): Let $S$ and $T$ be arbitrary complex-valued $n \times n$ matrices. Let $(\sigma_i)$ and $(\tau_i)$ be the singular values of $S$ and $T$, respectively, in nonincreasing order. Then, $|\mathrm{Tr}(ST)| \leq \sum_{i=1}^n \sigma_i \tau_i$.

A nice, elementary proof of this can be found in

L. Mirsky, A trace inequality of John von Neumann, Monatsh. Math. 79 (4): 303–306, 1975, MR0371930.

We don't actually need such a strong statement to prove the next claim, but I give the result above because it's very nice and doesn't seem to be as well-known as it should be.

Claim 2: Let $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0$ be the eigenvalues of $B$. Then $(\lambda_i)$ majorizes $(b_{ii})$.

$B$ has an eigendecomposition such that $B = Q \Lambda Q^*$ where $Q$ is unitary and $\Lambda$ is a diagonal matrix corresponding to $(\lambda_i)$. Now, note that $\newcommand{\Tr}{\mathrm{Tr}} s_k = \Tr(J_k^T B J_k) $ where $\newcommand{\zmat}{\mathbf{0}} J_k = \left(\begin{matrix} I_k \\ \zmat \end{matrix}\right) $ with $I_k$ being a $k \times k$ identity matrix and $\zmat$ being an $(n-k) \times k$ all-zeros matrix.

Then $ \Tr(J_k^T B J_k) = \Tr(J_k^T Q \Lambda Q^* J_k) = \Tr(Q^* J_k J_k^T Q \Lambda) \>. $

Observe that $Q^* J_k J_k^T Q$ is a Hermitian matrix with $k$ singular values that are one and $n-k$ that are 0, and so by von Neumann's theorem, we get that $ s_k = |s_k| = |\Tr(J_k^T B J_k)| \leq \sum_{i=1}^k 1 \cdot \lambda_i = \sum_{i=1}^k \lambda_i \> . $

Since this holds for each $k \leq n$, the claim is established.

Epilogue: Combining Claims 1 and 2 gives the desired result as stated in the question. But, Claim 2 by itself is actually quite a bit stronger. Also, as alluded to above, more elementary means can be used to show Claim 2 and they are almost as easy as wielding von Neumann's somewhat bigger hammer.

  • 0
    @Marco: Fair points. I've moved my proof of Claim 1 in the comments up to the main body and clarified the statment of von Neumann's theorem. (I was originally going to give a proof only for *real* $A$ and then flippantly leave it to the reader to extend to complex-valued $A$. But, I got a bit sloppy in the process of opting in the end for proving the latter case. Thanks for your remarks.) Cheers.2011-04-16
2

NOTE: Let us see if I can post this answer now :)


First, let me note that the condition that the Frobenius norm is one is irrelevant, since multiplying the matrix by some positive constant changes both the entries and the singular values by the same multiplicative constant. Anyway, for the same reason, we can restrict to the case mentioned in the question.

The solution is more easily seen in the language of quantum information. The entries $A_{ij}$ of the matrix can be seen as the coefficients of a bipartite state vector $|\psi\rangle=\sum_{ij}A_{ij}|i\rangle|j\rangle$, where $\{|i\rangle\}$ and $\{|j\rangle\}$ are (local) orthonormal bases. Suppose that the largest $k$ entries $|A_{ij}|^2$ correspond to pairs of indexes $(i,j)\in I_k$, where $I_k$ is some $k$-element subset of the set $\{ (i,j)|i,j=1,\ldots,n \}$. Then

$ \sum_{(i,j)\in I_k}|A_{ij}|^2 = \sum_{(i,j)\in I_k}\textrm{Tr}(|i\rangle\langle i|\otimes |j\rangle\langle j| |\psi\rangle\langle\psi|) $

This quantity is less than

$ \sum_{i:\exists j s.t. (i,j)\in I_k}\textrm{Tr}(|i\rangle\langle i|\otimes I |\psi\rangle\langle\psi|)=\textrm{Tr}_1(\sum_{i:\exists j s.t. (i,j)\in I_k}|i\rangle\langle i|\textrm{Tr}_2(|\psi\rangle\langle\psi|)) $

where $I$ denotes the identity matrix/operator and we have split the trace into the trace onto the first system and onto the second system. The matrix $\textrm{Tr}_2(|\psi\rangle\langle\psi|)$ is positive semidefinite, with eigenvalues corresponding to the squares of the singular values of $A$ (it is the reduced state of $|\psi\rangle$ in the language of quantum information), and we have

$ \textrm{Tr}_1(\sum_{i:\exists j s.t. (i,j)\in I_k}|i\rangle\langle i|\textrm{Tr}_2(|\psi\rangle\langle\psi|))\leq \max_{P_k} \textrm{Tr}_1(P_k\textrm{Tr}_2(|\psi\rangle\langle\psi|))=\sum_{i=1}^k\sigma_k^2, $

where the maximum is over projections of rank $k$. Since this is valid for any $k$, the conjecture is proven.