MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


Consider two d x d complex matrices, R and S, whose entries lie in the unit disk:

$\quad |R_{i,j}|<1 \quad$ and $\quad |S_{i,j}|<1 $.

Say that R is constructed by randomly choosing complex numbers from the unit disk, but S is constructed as

$\quad S_{i,j} = f(i/d,j/d)$

where $f(x,y)$ is a smooth function for $x,y \in [0,1]$, with $|f(x,y)|<1$. In other words, the entries of S are smooth functions of the indices (in the limit of large d), but those of R are not.


How do the trace norms

$\quad ||R||=Tr[\sqrt{R^\dagger R}] \quad$ and $\quad ||S||=Tr[\sqrt{S^\dagger S}]$

of these matrices behave as $d \to \infty$ ?

Numerical Evidence

A few lines of Mathematica strongly suggest that

$\quad ||R|| \propto d^{3/2}$


$\quad ||S|| \propto d$

for large d. (The proportionality constants depend on the probability distribution used to pick numbers from the unit disk for R and the function $f(x,y)$ used to pick entries for S, respectively.)

What explains this behavior?


After Willie's excellent answer below, I thought I'd mention that it's really fast to see the scaling behavior once you discretize the function. Let $F$ be some matrix of discrete values for the function, and let $J_n$ be the $n \times n$ matrix with all elements equal to unity.

$||F \otimes J_n|| = \mathrm{Tr} \sqrt {(F^\dagger \otimes J_n)( F \otimes J_n)} = \mathrm{Tr} \sqrt {(F^\dagger F) \otimes (J_n J_n)} = ||F|| \cdot ||J_n|| = n ||F||$

Basically, the idea is that once the dimension of $F$ is large enough to capture the important detail in the function, increasing the dimension is really just increasing the dimension of $J$.

share|cite|improve this question
Not sure if the "quantum-algebra" tag is appropriate, but I'm not competent to judge... – Yemon Choi Jul 20 '10 at 21:45
Note that $||S||=0$ for all $d$ if the support of $f$ is contained in $[0, 1/2]\times [0, 1/2]$ or $[1/2, 1]\times [1/2, 1]$. – Daniel Litt Jul 20 '10 at 21:53
Maybe not. This is the mathematical part of a quantum information calculation, but I don't really know what the "quantum-algebra" tag is. If someone else agrees that it's not appropriate, I'll happily remove the tag. – Jess Riedel Jul 20 '10 at 21:54
I guess the first statement should follow from well-known principles. We know where the density of states for i.i.d. matrices converges to, and then the claim follows by integrating $|x|$ against it. The second statement seems more tricky. – Helge Jul 20 '10 at 22:00
But Daniel, isn't true that if $f(x,y) = 1$ on $[0, 1/2]\times [0, 1/2]$ and vanishes otherwise, then $\mathrm{Tr} [\sqrt{S^\dagger S}] = \mathrm{Tr} [S] = d/2$ ? In any case, I agree that the linear behavior of $||S||$ might not survive for carefully chosen $f(x,y)$ (and, of course, for $f=0$), but I think it should be preserved for "most" $f$. – Jess Riedel Jul 20 '10 at 22:08
up vote 5 down vote accepted

To flesh out Helge's answer a bit before I go to bed:

Assume that $f(x,y)$ is a smooth function on the unit square. Define the functions $f_n(x,y) = f(\frac{\lfloor nx \rfloor}{n}, \frac{\lfloor ny\rfloor}{n})$. This is a piecewise step function. Observe that the operator $S$ of dimension $d$ is the same if you define it relative to $f$ or $f_d$. It is elementary to show that $f_n\to f$ uniformly (as functions).

Define an action of $f_n$ on $L^2[0,1]$ by $$ g(x) \mapsto \int_0^1 f_n(x,y)g(y) dy $$ and note that for a $n$-vector $v = (v_1,\ldots, v_n)$ we can associate $$ g_v(x) = \sum v_i \chi_{[\frac{i-1}{n},\frac{i}{n})} $$ we observe that $$ f_n(g_v(x)) = \frac{1}{n} g_{Sv}(x)$$ the $1/n$ factor coming from the fact that the length of the segment $[(i-1) / n, i/n)$ is $1/n$.

Now consider $V^n$ as the subspace of $L^2[0,1]$ spanned by $\chi_{[\frac{i-1}{n},\frac{i}{n})}$. By definition $f_n$ annihilates its orthogonal complement, and $f_n$ restricted to $V^n$ is equivalent to a rescaled version of $S$, so in particular you have that the trace norms of $f_n$ (acting on $L^2$) is the same as $1/n$ times the trace norm of $S$ (acting on $\mathbb{R}^n$).

To finish you just need to note that via some functional analysis voodoo the corresponding operators $f_n\to f$, and so the trace norms of $f_n$ converges. Therefore you have that $1/n$ times the trace norm of $S$ converges to a constant (which may be zero). Note that the regularity for $f$ is only needed in this last step, and you probably just need uniform continuity to assure that the operators converge in a strong enough sense.

[Addendum: all the functional analysis voodoo you need (which is not very much for this problem) can be found in Reed & Simon, volume 1, chapter 6.]

share|cite|improve this answer
Thanks for the great answer. The helpfulness of MOers continues to blow me away. – Jess Riedel Jul 21 '10 at 19:02

I will limit myself to the statement about $S$, see my comment above for $R$. I think the main insight into understanding this is to do the computation for the $d \times d$ matrix $$ A = \begin{pmatrix} 1 & \dots & 1 \\\ \vdots & \ddots & \vdots \\\ 1 & \dots & 1 \end{pmatrix}, $$ so all entries are $1$. Since $A^\dagger = A$ and $A \geq 0$, we have that $tr(\sqrt{A^\dagger A}) = d$, which is the scaling you see.

So why do I think it is sufficient. If you generate a matrix as described above, you can rewrite it as blocks of the form of A up to a small error. This essentially uses that $f$ is Lipschitz. Of course this is still far away from a mathematical proof, but I hope one could turn it into one.

share|cite|improve this answer
Thanks so much. This was definitely the key idea. – Jess Riedel Jul 21 '10 at 19:03

Your Answer


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.