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

## 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?

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

-
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

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

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

-
Thanks so much. This was definitely the key idea. – Jess Riedel Jul 21 '10 at 19:03