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

  • $\begingroup$ Not sure if the "quantum-algebra" tag is appropriate, but I'm not competent to judge... $\endgroup$
    – Yemon Choi
    Jul 20, 2010 at 21:45
  • $\begingroup$ 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]$. $\endgroup$ Jul 20, 2010 at 21:53
  • $\begingroup$ 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. $\endgroup$ Jul 20, 2010 at 21:54
  • $\begingroup$ 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. $\endgroup$
    – Helge
    Jul 20, 2010 at 22:00
  • $\begingroup$ 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$. $\endgroup$ Jul 20, 2010 at 22:08

2 Answers 2


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.]

  • $\begingroup$ Thanks for the great answer. The helpfulness of MOers continues to blow me away. $\endgroup$ Jul 21, 2010 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.


Your Answer

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

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