# "High complexity" of eigenbasis of Wigner matrices?

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

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

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

• 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) Commented Jul 10 at 15:22
• 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. Commented Jul 10 at 15:38