# Majorization relation between the absolute values squared of the entries of a matrix and the singular values squared

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!

-
I presume the $\sigma_k$ are arranged in descending order? –  joriki Apr 15 '11 at 7:45
@joriki: the notion of majorization is such that involves ordering the entries of the vectors in descending order; for more details please see the first lines of the Wikipedia entry @cardinal: thanks, but yours is not a countexample. For one thing, the matrix you propose does not satisfies the hypothesis $\textrm{Tr}(A^\dagger A)=1$. If properly rescaled by multiplying it by $1/\sqrt{2}$, it satisfies the conjecture, as it has only one singular value equal to 1. –  Marco Apr 15 '11 at 12:39
Sorry to delete my comment. My example was related to a symmetric idempotent matrix. I misunderstood the question, as I suspected and was deleting the comment to cut down on noise. In the end, it appears I've added to it. –  cardinal Apr 15 '11 at 12:44
@cardinal: no problem :) Thanks for your consideration of the question! –  Marco Apr 15 '11 at 12:47
I've proposed an edit to your question to hopefully make the constraint a little more visible. As it was formatted, I actually missed it the first time around. After my edit is peer-reviewed, be sure to check it to see that no errors have been introduced. –  cardinal Apr 15 '11 at 12:51

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


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.

-
Thanks! I have to check the steps you provide, but I believe they are correct. I did not know the theorem of von Neumann (BTW, the statement probably misses an absolute values on the the left-hand side), and is good that you pointed it out! I do not have my matrix analysis books with me, but I think I saw Claim 2 somewhere in those books today. For Claim 1, I admit I do not see it now, but it is probably because I am tired. Thanks for putting such effort in solving the problem! –  Marco Apr 16 '11 at 1:49
@Marco: I left the absolute-value sign off on purpose to make things clearer. It doesn't weaken the statement in our particular case, though it does in general, of course. –  cardinal Apr 16 '11 at 2:59
@Marco: $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$. Does that help clear up Claim 1 for you? –  cardinal Apr 16 '11 at 3:03
@cardinal 1) thanks for the clarification of Claim 1; let me say that your explanation in the comment is much better than the formulation of the proof of the claim in the answer :) 2) as announced in the comments to the question, I had also found a proof; you can see it in the edited text of the question [and now as answer] 3) I found that Claim 2 corresponds to what is also known as "Schur's theorem" (see Exercise II.1.12 of Bathia, "Matrix Analysis") 4) for your statement of von Neumann's theorem the absolute value can not be avoided as it regards matrices with complex entries. Thanks again. –  Marco Apr 16 '11 at 3:37
@Marco: Thanks for the references; I'll look them up. The proofs I've given were from scratch in that I did not have these results at hand. As regards von Neumann's theorem, in this particular case the absolute value is unnecessary since the diagonal elements of all the matrices considered are real even if the off-diagonals may have non-zero imaginary parts. –  cardinal Apr 16 '11 at 3:38

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.

-