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



Dependence of trace norm on matrix size for smooth vs. random matrices.
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.]


