Let $W$ be an $N \times N$ complex Wigner matrix, i.e. i.i.d. entries restricted to Hermitian matrices. Let $W=UDU^{\ast}$, i.e. $U$ encodes the eigenbasis of $W$. Are there any statements known about the "complexity" of $U$? The exact notion of complexity used here is vague for now, but I mean statements like:

  • It requires around $\approx N^2 \log\frac{1}{\varepsilon}$ random bits to approximate the distribution of $U$ in some sense
  • With high probability $U$ cannot be generated by a $polylog(N)$ size sequence of "simple" matrices (e.g. $2 \times 2$ rotations)

Such statements can be proved for GUE, where by unitary invariance of the ensemble the matrix $U$ is Haar random. By universality, I would expect similar statements should hold for Wigner matrices (possibly with some moment assumptions).

  • 1
    $\begingroup$ if the elements of $W$ have a normal distribution, then $U$ is in the GUE, so you are back to the familiar case. $\endgroup$ Commented Jul 9 at 18:00

1 Answer 1


$\newcommand{\E}{\mathbb{E}}$For the first question, we cannot hope in the full generality for the $\Omega(N^2 \log (1/\varepsilon))$ lower bound --- say, if we look at a symmetric matrix $W$ with independent $\{\pm 1\}$ entries, we can encode the matrix $U$ exactly just by specifying matrix $W$ explicitly, which we can do using $N^2$ bits.

The lower bound $\Omega(N^2)$ for constant $\varepsilon=0.01$ is conceptually simple, let me discuss only the case where $W$ is a $\{ \pm 1\}^{n \times n}$ (symmetric) matrix, and then briefly discuss how to generalize it, to -- say, any symmetric distribution of entries $W_{ij} \sim - W_{ij}$ with variance one $\E W_{ij}^2 = 1$ and bounded fourth moment $\E W_{ij}^4 \leq B$.

We will use the following

Lemma Let $f: \{ \pm 1\}^n \to \{0, 1\}^m$ be an encoding function, and $g:\{0, 1\}^m \to \{\pm 1\}^n$ be decoding, s.t. with probability at least $1/3$ over random $x \in \{ \pm 1\}^n$ we have $d_H(g(f(x)), x) \leq 1/4$, where $d_H$ is the normalised Hamming distance $d_H(x, y) := |\{k : x_k \not= y_k\}|/n$. Then $m \geq n/2$.

This is very standard, see for example Lemma 2 in Entropy arguments used by Jean Bourgain.

Clearly this implies the following

Corollary Let $f : \{ \pm 1\}^{n\times n} \to \{0, 1\}^m$ be an arbitrary encoding, and $d: \{0, 1\}^m \to \{ \pm 1\}^{n\times n}$ be a decoding, and $W$ be a symmetric Wigner matrix with independent $\{ \pm 1\}$ entries (above diagonal). If $\|d(f(W)) - W \|_F \leq 2^{-4} n^2$ with probability at least $1/3$, then $m\geq n^2/4$.

This is just because on $\{\pm 1\}^{n \times n}$ the Hamming distance between corresponding vectors is (up to a constant factor) the same as Froebenius norm of the difference between the matrices.

I will show that if we could encode the matrix $U$ up to a small Frobenius norm error $2^{-12} n$ with $n^2/16$ bits, then we could encode matrix $W$ up to a small Frobenius norm error with $n^2/4$ bits --- which by the previous corollary is impossible.

We will encode $W$ as a pair $(\tilde{U}, \tilde{D})$. Since with high probability all eigenvalues of $W$ are in the range $\pm O(\sqrt{n})$, by simple discretization we can encode the vector of eigenvalues up to an element-wise error $n^{-10}$ using $O(n \log n)$ bits --- ensuring that $\|\tilde{D} - D\|_F \leq 1$.

If we could find orthogonal $\tilde{U}$ s.t. with probability $1/3$ we had $\|\tilde{U} - U\|_F \leq 2^{-12} n$, and encode $\tilde{U}$ using $n^2/16$ bits, we would chose $\tilde{W}$ to be the Frobenius-norm projection of $\tilde{U} \tilde{D} \tilde{U}^T$ on symmetric $\{\pm 1\}^{n\times n}$ matrices.

We will argue that $\|\tilde{W} - W\|_F \leq 2^{-4} n^2$. Indeed, if $\|\tilde{U} - U\|_F \leq 2^{-12} n$ since $\|D\|_F \leq O(n)$, we get $$ \|\tilde{U} D \tilde{U}^T - U D U^T\|_F \leq \|U D (\tilde{U}^T - U^T)\|_F + \|(\tilde{U} - U) D \tilde{U}^T\|_F \leq 2 \|(\tilde{U} - U) D\|_F \leq 2^{-6} n^2, $$

Similarly if $\|D - \tilde{D}\|_F \leq 1$ then $$ \|\tilde{U} D \tilde{U}^T - \tilde{U} \tilde{D} \tilde{U}^T\|_F = \|D - \tilde{D}\|_F \leq 1, $$ hence by triangle inequality we have $$ \|W - \tilde{U} \tilde{D} \tilde{U}^T\|_F \leq 2^{-5} n^2. $$ Let us now take $\tilde{W}$ to be the projection of $\tilde{U} \tilde{D} \tilde{U}^T$ on symmetric $\{\pm 1\}^{n\times n}$ matrices, i.e. $\tilde{W} := \mathrm{argmin}_{X\in \mathcal{S}} \|X - \tilde{U} \tilde{D}\tilde{U}^T\|_F$ where $\mathcal{S} \subset \{\pm 1\}^{n \times n}$ is the family of all symmetric matrices.

Then by the definition of projection, and since $W$ itself in $\mathcal{S}$ matrix we have $\|\tilde{W} - \tilde{U}\tilde{D}\tilde{U}^T\|_F \leq \|W - \tilde{U}\tilde{D}\tilde{U}^T\|_F$, and by triangle inequality $$ \|W - \tilde{W}\|_F \leq \|W - \tilde{U} \tilde{D}\tilde{U}^T\|_F + \|\tilde{W} - \tilde{U} \tilde{D}\tilde{U}^T\|_F \leq 2^{-4} n^2. $$

Since the total encoding of $(\tilde{U}, \tilde{D})$ needs to use $n^2/4$ bits by Corollary, and we can encode $\tilde{D}$ using $O(n \log n)$ bits, the total encoding of $\tilde{U}$ needs at least $n^2/8$ bits.

To handle the case of more general symmetric distribution of entries $W_{ij}$, note that the distribution of $W_{ij}$ is the same as $|W_{ij}| \varepsilon_{ij}$ where $\varepsilon_{ij}$ are independent $\{\pm 1\}$. By the Payley-Zygmunt inequality, with good probability a constant fraction of entries is bounded away from zero $|W_{ij}| \geq \delta$, for some constant $\delta$, and if we recover $W$ with small Frobenius norm error, we will be able to recover the signs $\varepsilon_{ij}$ on a constant fraction of those entries which are bounded away from zero -- and to do this, we need encoding of size $\Omega(n^2)$.

It looks like that the second impossibility is the consequence of the first: if I could write $U=S_1 S_2 \ldots S_m$ for some sequence of $m$ simple unitary matrices $S_i$, we could approximate each $S_i$ by a $\tilde{S}_i$ up to small $\varepsilon \leq 2^{-10} / m$ Frobenius error, s.t. each of the matrices $\tilde{S}_i$ is described using only $O(\log(nm))$ bits. Then $\|U - \prod_i \tilde{S}_i\|_F \leq m \varepsilon \leq 2^{-10}$, and the total number of bits used to encode $U$ is $m \log(nm)$ --- implying $m \gtrsim n^2/\log n$ by the previous discussion.

  • $\begingroup$ One thing - why is it clear that $\Vert \tilde{W} - \tilde{U} \tilde{D} \tilde{U}^{\ast} \Vert < 2^{-5} n^2$? (in other words, why is the projection of our approximation onto +/-1 matrices a good approximation) $\endgroup$ Commented Jul 10 at 15:22
  • $\begingroup$ Hi, it's been a while! I've expanded a bit more on this in the answer - it follows since $\tilde{W}$ is a projection, and $W$ is itself a $\{\pm 1\}^{n\times n}$ symmetric matrix. $\endgroup$ Commented Jul 10 at 15:38

Your Answer

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

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