Are random circulant matrices almost orthonormal?

Question

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

Answer 1

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.

Answer 2

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.