Dependence of trace norm on matrix size for smooth vs. random matrices.

Question

Problem

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.

Question

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

but

$\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?

Addendum

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

Answer 1

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

Answer 2

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.