# Are random circulant matrices almost orthonormal?

Let $(X_1, X_2, \dots, X_n)$ be i.i.d. ${\cal N}(0,1)$. We construct a random circulant matrix $M$:

$$M = \frac{1}{\sqrt n}\begin{pmatrix}X_1 &X_2 &X_3 \dots &X_n\\ X_n &X_1 & X_2 \dots &X_{n-1}\\ \vdots &\vdots &\vdots &\vdots\\X_2 &X_3 &X_4 \dots &X_1\end{pmatrix}.$$

My questions are the following:

1. Is $M$ "almost orthonormal" in a precise probabilistic sense?

2. Related to above, is it possible to upper-bound the largest possible dot product between any two rows of $M$ by a suitably small $\epsilon_n$?

Note that this says that $MM^T$ is close to the identity matrix $I_{n \times n}$, as we are bounding the off-diagonal entries of $MM^T$ by $\epsilon_n$, while the diagonal entries are close to $1$.

• What do you mean by "upper-bound the largest possible dot product"? All of the $X_i$ could be equal to $10^{10^{10}}.$ You can upper bound it with high probability, but that's the best you can do. – Igor Rivin Oct 14 '17 at 0:05
• If $D$ is the absolute value of the largest dot product, one could seek a bound of the sort $\mathbb P(D > \epsilon_n) < \epsilon_n$ for a suitable choice of $\epsilon_n \to 0$. – VSJ Oct 14 '17 at 2:25
• Yes, that follows from Marcel's answer, using, e.g., Markoff's inequality. – Igor Rivin Oct 14 '17 at 3:24

The diagonal elements of $P=\frac{1}{N}MM^T$, like $$P_{11}=\frac{1}{N}\sum_{i=1}^NX_i^2,$$ satisfy $\langle P_{11}\rangle=1$ and $\langle P_{11}^2\rangle=1+2/N$ (variance decreases like $N^{-1}$).

On the other hand, off-diagonal elements like $$P_{12}=\frac{1}{N}\sum_{i=1}^{N}X_iX_{i+1}$$ satisfy $\langle P_{12}\rangle=0$ and $\langle P_{12}^2\rangle=1/N$ (variance also decreases like $N^{-1}$).

In this sense I would say $P$ is close to the identity.

Marcel's solution provides a good approach for understanding the marginal statistics. Here are a few supplementary comments that might give a little insight into the joint distribution.

Let $D$ be the discrete Fourier transform matrix, i.e. the $j,k$-th entry is: $$D_{j,k}=e^{-2\pi i jk/N}/\sqrt{N}$$ Consider the discrete Fourier transform of the first row of $M$, i.e. $$(G_1,...,G_N)=(1/\sqrt{N})(X_1,...,X_N)D$$ Let $G$ be a diagonal matrix with diagonal entries $G_1,...,G_N$. Then $D$ diagonalizes $M$ (see, e.g., this description), that is: $$M = D G D^{-1}$$

If we took the $X_i$ to be complex-valued Gaussian variables, then we would be essentially done at this point: since $D$ is unitary, and the Gaussian is spherically symmetric, then the $G_i$ would be i.i.d. (complex) Gaussian random variables with mean 0 and variance $1/n$. (That is, if we sampled the $G_i$ as i.i.d complex $\mathcal{N}(0,1/n)$, then $DGD^{-1}$ has the same distribution as samples from the original circulant matrix.) It follows that $$MM^*=(DGD^{-1})(DG^*D^{-1})=DGG^{-1}D^*$$ It then follows that the eigenvalues of $MM^{*}$ (or, if you prefer, the squared singular values of $M$) are distributed like $n$ i.i.d draws from a rescaled $\chi^2$ distribution with 2 degrees of freedom (which happens to simplify to an exponential distribution), where we rescale by dividing by $n$. From an eigenvalue perspective, this is a complete characterization of the "orthonormality" of $M$.

However, your $X_i$ are probably real-valued. This causes a small book-keeping headache, but doesn't really change much. In brief: since the $X_i$ are real-valued, the $G_i$ will be symmetric. We can convert our $n\times n$ complex-valued matrices into corresponding $2n \times 2n$ real-valued matrices (say, $D'$ and $G'$). Then observe that there are only $n$ of the $2n$ diagonal elements in $G$ are free, and only $n$ of the $2n$ inputs to $D'$ are non-zero (namely, the ones corresponding to the real values of the inputs in $D$). Noting that the resulting decimated matrices are still unitary, we then reduce to the previous case, except with $\chi^2/n$ distributions with only 1 degree of freedom.

• I'm confused about one part: Marcel's answer indicates that $MM^*$ is close to identity. Thus it should have eigenvalues close to 1? But your argument says eigenvalues are iid from a chi square distribution so they aren't all close to 1. How to reconcile these? – VSJ Nov 2 '17 at 4:04
• Ah, @VSJ , that is my mistake: I forgot to pass through the prefactor of $1/\sqrt(n)$ in the original definition of $M$. I will fix that now, at which point I think Marcel's answer is consistent with mine. – Bill Bradley Nov 3 '17 at 13:31
• Hi Bill, I'm not sure that is a mistake. Because even then, the eigenvalues will converge to 0 and not 1. Perhaps it is the case that the matrix is tending "pointwise" to identity, but it is not tending fast enough, and therefore the eigenvalues don't converge? – VSJ Nov 3 '17 at 17:52